ID 906781 Banca FCC Órgão TRT - 9ª REGIÃO (PR) Ano 2013 Provas FCC - 2013 - TRT - 9ª REGIÃO (PR) - Técnico Judiciário - Tecnologia da Informação Disciplina Algoritmos e Estrutura de Dados Assuntos Algoritmos Algoritmos de Busca Algoritmos de Ordenação Considere as afirmativas sobre i) Métodos de pesquisa sequencial e de pesquisa binária ii) Métodos de ordenação Sabendo que N se refere ao número de elementos do conjunto, a alternativa em que i) e ii) estão ambas ERRADAS, é Alternativas i) O funcionamento do método pesquisa binária baseia-se no princípio de reduzir à metade, sucessivamente, o “universo de busca”. Desse princípio resulta sua eficiência. ii) O método da bolha (bubble sort) e o método de seleção (selection sort) são ambos O(N2). i) O método de pesquisa binária não pode ser aplicado quando os dados estão ordenados em ordem decrescente, mesmo se o código do método for readequado. ii) O método de Seleção (Selection sort) é o método mais rápido para qualquer tamanho de N se os elementos já estão ordenados, pois este é o seu melhor caso, que é O(Log2 N). i) No pior caso do método pesquisa sequencial são realizadas N comparações. ii) No método Quicksort, inicialmente o vetor é dividido em uma sublista da direita e uma da esquerda, de modo que todo elemento da sublista da esquerda seja menor que os da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva. i) A quantidade de comparações que o método de pesquisa binária realiza é aproximadamente igual ao número de vezes que N pode ser dividido por 2 até resultar 1, isto é, log2N. Assim, a ordem de complexidade do método é logarítmica. ii) Quando N é muito grande é desejável que o método de ordenação realize o menor número de trocas. i) No melhor caso da pesquisa sequencial é realizada 1 comparação para se localizar um elemento. ii) O método Quicksort é, essencialmente, uma aplicação do princípio “dividir para conquistar”. Responder Comentários b) i) O método de pesquisa binária não pode ser aplicado quando os dados estão ordenados em ordem decrescente, mesmo se o código do método for readequado. Está errada pois a pesquisa binária pode sim ser realizada em um array cuja ordem é decrescente, para isso basta alterar o algoritmo, adaptando-o a esse tipo de ordenação.ii) O método de Seleção (Selection sort) é o método mais rápido para qualquer tamanho de N se os elementos já estão ordenados, pois este é o seu melhor caso, que é O(Log2 N). Está errada pois esses fatos tratam-se na verdade sobre o insertion sort, esse algoritmo possui uma grande flexibilidade com relação ao grau de ordenação prévia do vetor, se adaptando bem aos casos onde o vetor está razoavelmente pré-ordenado, sendo em seu melhor caso O(Log² N). Que complexidade é essa? O(Log² N)? Nos materiais do provas de TI as complexidades para o melhor caso para o Selection e o Insertion são respectivamente O(n²) e O(n). b-A pesquisa ou busca binária é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria Força Guerreiro!!!!!!