Handbook de Ti - Algoritmos - Questões Comentadas

www.handbookdeti.com.br Handbook de Questões de TI Comentadas para Concursos: Volume questões de TI\n\nPrefácio\n\nUm algoritmo é um conjunto de operações em sequência para resolver determinado problema.\n\nA noção do algoritmo é extremamente importante para a computação. Não existe um conjunto de regras que nos permita criar novos algoritmos e, portanto, trata-se de umas maiores dificuldades dos inícios em programação.\n\nO estudo de algoritmos é muito cobrado nos concursos na área de tecnologia da informação e, por isso, o Grupo Handbook de TI preparou este volume, que traz uma série de questões comentadas sobre Algoritmos para você se preparar ainda melhor para os certos de seu interesse;\n\nBons estudos.\n\nGrupo Handbook de TI\n\nPágina 1 de 27\nwww.handbookdeti.com.br Handbook de Questões de TI Comentadas para Concursos: Volume questões de TI\n\nDireitos Autorais\n\nEste material é registrado no Escritório de Direitos Autorais (EDA) da Fundação Biblioteca Nacional. Todos os direitos autorais referentes a esta obra são reservados exclusivamente aos seus autores.\n\nOs autores deste material não puderam ser compartilhamentem entre amigos e colegas próximos de estudo. Contudo, a reprodução, parcial ou integral, e o desmembramento deste material de forma indiscriminada através de qualquer meio, inclusive na Internet, extrapolam os limites da colaboração. Essa prática desencoraja o lançamento de novos produtos e enfraquece a comunicação dentro do e-books Handbook de TI;\n\nA série Handbook de Questões de TI Comentadas para Concursos - Além do Gabinete é uma produção independente e conta com você para mantê-la sempre viva...\n\nGrupo Handbook de TI\n\nPágina 2 de 27\nwww.handbookdeti.com.br Handbook de Questões de TI Comentadas para Concursos: Volume questões de TI\n\nCanal de Comunicação\n\nO Grupo Handbook de TI disponibiliza diversos canais de comunicação para os consumidores de TI:\n\nLoja Handbook de TI\nAcesse a nossa loja virtual em http://www.handbooketi.com.br\n\nServiço de Atendimento\nComunique-se diretamente conosco através do e-mail falconosco@handbooketi.com.br\n\nTwitter do Handbook de TI\nAcompanhe de perto promoções e lançamentos de produtos pelo nosso Twitter http://twitter.com/handbooketi Handbook de Questões de TI Comentadas para Concursos: Volume questões de TI\n\nDiz-se que uma função éatada-se so existiu alguma constante, e escrevermos e existir alguma constante em inteiro, tal que implica .... É fácil notar que se encontrar-se... A análise é conhecida como o análise do melhor caso e é pouco utilizada.\n\nDadas funções assim ópticamente não-negativas, dizemos que, está na ordem de, e escrevemos que estender-se e um inteiro, tal que implica ... É fácil notar que se se omitir e se omitir o que foi dada um compreensão básica em relação a complexidade de algoritmos e suas. Handbook de Questões de TI Comentadas para Concursos: Volume questões de TI\nnotações, vamos analisar as alternativas de uma a uma:\n\nA alternativa (A) está claramente errada, já que a notação é utilizada para denotar a análise do melhor caso e não do pior caso.\n\nTambém está equivocada a alternativa (B), visto que quando dizemos que domina assintoticamente, dizemos também que a definição está legitimamente invalida visto que o correto, neste caso, é:\n\nA notação não faz sentido em complexidade de algoritmos, logo, a alternativa (C) pode ser invalidada.\n\nO termo dominante em uma função polinomial pode ser utilizado para determinar a análise de pior caso de um algoritmo. Na função podemos dizer que é, também, um sendo a notação, por exemplo, n², enquanto N não é o termo dominante de polinômio. Portanto, a alternativa (D) está errada.\n\nA alternativa (E) está correta, pois a notação Θ músculo representa o limite superior dos dois as funções. E se as funções, de um limite superior justo entre elas se mantêm equivalente, podemos dizer que Handbook de Questões de TI Comentadas para Concursos Volume questões de TI\n\n2. Assuntos relacionados: Algoritmos, Complexidade de Algoritmos;\nBanco: Cesgranrio\nInstituição: Petrobras\nCargo: Análise de Sistemas Pleno - Processos\nAno: 2006\nQuestão: 56\n\nConsidere os algoritmos a seguir e as suas correspondentes complexidades indicadas. Estão corretas apenas as complexidades indicadas para os algoritmos:\n\nI Busca sequencial de um elemento em um vetor de tamanho N - \nII Busca, via pesquisa binária, de um elemento, em um vetor de tamanho N - \nIII Busca de um rótulo de um nó em uma árvore binária completa, com N nós -\nIV Busca de um rótulo de um nó em uma árvore binária de busca, com N nós - \n\nV Inclusão de um elemento em um vetor ordenado de tamanho N, mantendo-se a ordem: \n\n(a), I, II e III. \n(b), I e IV. \n(c), II e IV. \n(d), I, III, IV e V. \n\nSolução \nA complexidade algorítmica é então expressa em função do tamanho do problema. Em um problema que envolve a ordenação de um vetor, por exemplo, o tamanho do problema seria o tamanho do vetor. Em um problema que envolve a busca por um elemento em uma árvore binária, o tamanho do problema seria a quantidade de elementos contidos na árvore. É comum que se utilize a letra N para expressar o tamanho de um determinado problema.\n\nBoa parte das vezes, na avaliação da complexidade de um algoritmo, interessa ao avaliador descobrir qual será a complexidade do algoritmo quando for submetido a um certo nicho de dados que o faça aparecer em seu pior caso, ou seja, que o faça executar o maior número de operações até que se alcance o resultado final. No estudo da complexidade algorítmica, tal valor é denotado pela notação O. Se um algoritmo, no seu pior caso, precisa executar N operações, diz-se que sua complexidade é O(N).\n\nAssim, vamos analisar cada uma das correspondências algoritmo/complexidade e verificar quais delas estão corretas.\n\n(f) CORRETA Handbook de Questões de TI Comentadas para Concursos Volume questões de TI\n\nUma busca sequencial aqui em um vetor é promovida a partir de uma ordem não relativa ao sentido da outra até que o elemento procurado seja encontrado. Imaginando o caso em que o elemento procurado seja o último elemento a ser avaliado em um vetor de tamanho N, para que se encontre tal elemento o algoritmo precisa executar N operações de comparação. Com isso, o pior caso de tal algoritmo é: \n\n(II) CORRETA \nO processo de busca binária inicia-se com a escolha de um elemento chamado pivot, localizado no centro do vetor. Caso o elemento procurado seja menor que o pivot, seleciona-se um vetor da esquerda e se faz a pesquisa. Caso contrário, seleciona-se o vetor da direita, que é expandido. Assim, a cada iteração, o vetor a busca é dividido pela metade, No número máximo de divisões que poderiam ocorrer estaria estabelecido o número de N na base 2. Portanto, o pior caso da busca binária é: \n\n(III) ERRADA \nEm processo de busca por um elemento em uma árvore binária, a-particionamento do espaço de busca é determinado pelo fato de o elemento procurado ser maior ou menor que o nó que está sendo visto. Caso o elemento seja maior, a busca prosseguirá pela subárvore à direita e vice-versa. Aparentemente, o processo é bem mais eficiente que o processo binário. No entanto, pode acontecer de existir árvores binárias balanceadas, das quais toda subárvore possui uma única raiz que possui um único lado.\n\nNessa situação, como a navegação na árvore binária, pode se necessitar de um número excessivo de nós de texto, pode ocorrer o pior caso de busca por estar presente em diversos nós. Nesse caso, a busca em uma árvore binária, no pior caso, não tem complexidade inferior a\n\n(IV) CORRETA \nNesta afirmativa, a situação é exatamente a ilustrada no item anterior, onde foi mostrado que a complexidade da busca em uma árvore binária no pior caso é. Handbook de Questões de TI Comentadas para Concursos Volume questões de TI\n\n3. Assuntos relacionados: Métodos de Busca, Pesquisa Binária, Árvore B; \nBanco: CESGRANRIO \nInstituição: BNDES \nCargo: Análise de Suporte \nAno: 2008 \nQuestão: 50 \n\nOs dados de uma agenda contendo nome, telefone e endereço de pessoas estão organizados em um arquivo de dados com acesso somente de leitura. Um dispositivo eletrônico D, que possibilita acesso direto, contém, aproximadamente, 90 milhoes de registros organizados por nome. Assumindo que o tamanho do campo elemento é variável e que D pode ter os registros (pré-existentes) de índices que se referiam ao arquivo de dados, é suposto que não possível, qual é a peça que se realiza, em média, menos operações de I/O para consultar todos os registros que pelo nome começando por uma determinada letra?. \n\n(a). Pesquisa binária diretamente sobre arquivo de dados; \n(b). Pesquisa sobre o arquivo de índices indexados pelo nome, implementando um algoritmo de busca em uma árvore B-tree balanceada.\n(c). Pesquisa sequencial sobre o arquivo de índices indexados pelo nome; \n(d). Pesquisa binária sobre o quarto elemento em um arquivo de dados; \n(e). Leitura sequencial direta sobre o arquivo de dados;\n\nSolução\n(A) ERRADA \nPara que fosse possível pesquisa binária diretamente sobre arquivo de dados, como seus registros tem tamanhos variáveis, seria necessário incluir informações que serviriam de \"pointers\" em cada registro. O que não é possível, já que o arquivo de dados permite apenas leitura. Portanto, a alternativa A não é possível. \n\n(B) ERRADA \nDe maneira geral, a abordagem por B-tree é uma boa opção. Entretanto, o importante observar que para recuperar cada registro é necessário uma consulta a B-Tree e posteriormente ao arquivo de dados. Tal implementação utilizaria um número de operações da ordem (n/26)/log(n), onde n é o número total de registros. Analisaremos outras opções adiante. Note que a opção nem explicita como seria o acesso ao arquivo de dados. \n\n(C) CORRETA \nEssa é uma opção bem eficiente para o caso, já que será necessário apenas encontrar a letra do alfabeto correspondente (mesmo que de maneira sequencial) no arquivo de índices e depois percorrer sequencialmente o arquivo de dados. A ordem neste caso é 13/26. Ou seja, mais rápido que o caso descrito na alternativa B. Handbook de Questões de TI Comentadas para Concursos: Volume questões de TI\n\n(D) ERRADA\nO caso e o custo são muito parecidos com aqueles explicados na alternativa B e, como consequência, o seu resultado não supera o desempenho descrito na alternativa C.\n\n(E) ERRADA\nNeste caso, a ordem seria percorrer o arquivo de dados até encontrar o princípio registro cujo nome começa com a letra especificada e depois percorrer todos os elementos que atendem a condição. O custo seria da ordem n/2(n+1)/2.\n\nConcluímos que a alternativa mais eficiente é a alternativa C.\n\nPágina 9 de 27\nwww.handbookedit.com.br