QUESTÕES SOBRE ALGORITMOS DE BUSCA I

1. (SUGEP - UFRPE 2018) Suponha que ‘vec’ é um array ordenado de 1000 chaves inteiras. Quantas comparações no máximo são necessárias para verificar se um inteiro qualquer ‘r’ pertence a ‘vec’?

A) 10

B) 50

C) 500

D) 1000

E) 100

2. (CESGRANRIO 2018) Considere uma árvore binária de busca (BST) com n (n>3) níveis (o nó raiz está no nível 1), 2n - 1 nós e todas as chaves diferentes. Suponha, ainda, que algum dos pais de duas folhas seja removido da árvore e, mais tarde, uma chave com o mesmo valor da chave do nó removido seja inserida na árvore.

Quantas são as comparações necessárias para fazer a busca e encontrar o nó cuja chave foi removida e depois reinserida?

A) n – 2

B) n – 1

C) n

D) n +1

E) n + 2

3. (CESPE 2017) Considere que um algoritmo de pesquisa, em um arquivo previamente ordenado, é caracterizado por realizar comparação de chaves e sucessivas divisões no espaço de busca até encontrar o termo pesquisado ou até haver um único registro. Trata-se de um algoritmo de

A) pesquisa por interpolação.

B) pesquisa binária.

C) pesquisa sequencial.

D) árvore de busca binária.

4. (COSEAC 2017) Avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir.

I O método de busca “pesquisa binária” necessita de um ordenamento prévio do vetor.

II O método “pesquisa binária” possui o tempo de busca maior que o método “busca sequencial”.

III O método “busca sequencial” é mais indicado quando se sabe antecipadamente que a maior parte dos registros necessita ser pesquisada.

As afirmativas I, II e III são, respectivamente:

A) V, V e F.

B) V, F e V.

C) F, V e V.