Questão 1588684

• Banca: COSEAC
• Órgão: UFF
• Ano: 2015
• Provas: COSEAC - 2015 - UFF - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados

Pesquisar um valor que corresponda a um valor-chave em uma árvore de pesquisa binária empacotada (equilibrada) com 128 elementos requer no máximo:

• A. oito comparações.
• B. quatro comparações.
• C. cinco comparações.
• D. seis comparações.
• E. sete comparações.

Gabarito: E

Comentários

• 2^7 = 128
  

• Pessoal, não concordei com esse gabarito.

  Nesse caso, não existe elemento do meio, pois o número de elementos é par. Logo a busca poderia se iniciar no elemento 65º. A busca poderia então continuar assim:

  65 - 33 - 17 - 9 - 5 - 3 - 2 - 1

  O que totaliza 8 comparações.

  Tem algo de errado no meu raciocínio?

• Rodrigo, não acho que seu argumento esteja certo, pois imagine uma árvore com 2 elementos.

  2^1 = 2

  Então, seguindo sua lógica teríamos no máximo 1 comparação, o que na prática sabemos que não é verdade, pois faremos no máximo 2 comparações (caso em que o elemento buscado não seja a raiz).

• Força Guerreiro!!!!!!