Questão 2743297

• Banca: FGV
• Órgão: MPE-AL
• Ano: 2018
• Provas: FGV - 2018 - MPE-AL - Analista do Ministério Público - Administrador de Banco de dados
• Disciplina: Algoritmos e Estrutura de Dados

Em uma árvore B de ordem d, onde cada nó que não o raiz possui entre d e 2d chaves, estão armazenadas 30.000 chaves.

Sabendo-se que d=8, assinale a opção que indica o número máximo de nós visitados para a localização de uma chave.

• A. 3
• B. 5
• C. 7
• D. 15
• E. 15.000

Gabarito: B

Comentários

• Fórmula do pior caso na busca de árvore B

  d<=1 + log[d/2] ((n+1)/2)

  d<= 1+ log[4](15000.5) = 7,93 e não 5 como o gabarito da questão

• Força Guerreiro!!!!!!

• Pessoal é só contar quantas interações são necessárias para chegar ao resultado. Lembrando que deve ser incluído a interação que passar do valor.

  1º - > 8 = 8

  2º -> 8 x 8 = 64

  3º -> 8 x 8 x 8 = 512

  4º -> 8 x 8 x 8 = 4.096

  5º -> 8 x 8 x 8 x 8 = 32.768

  Número máximo de nós = 5

  Bons Estudos. Não desiste!