Algoritmos e estrutura de dadosAlgoritmos de busca

• (FCC 2013)

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, é



A) 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(N ² ).

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.

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(Log ² N).

C) 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.

D) 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 é, log ₂ N. 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.

E) 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”.


Próximo:
EXERCÍCIOS - Exercício 24

Vamos para o Anterior: Exercício 22

Tente Este: Exercício 40

Primeiro: Exercício 1

VOLTAR ao índice: Algoritmos e estrutura de dados