Questão 2670244

• Banca: CESGRANRIO
• Órgão: Banco da Amazônia
• Ano: 2018
• Provas: CESGRANRIO - 2018 - Banco da Amazônia - Técnico Científico - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Uma árvore binária completa de busca, isto é, uma árvore em que todos os níveis têm o máximo número de elementos, tem um total de N nós.

O número máximo de comparações necessárias para encontrar um elemento nessa árvore é

• A. N
• B. N²
• C. log₂ (N+1)
• D. (N+1)*log₂ (N+1)
• E.
  

Gabarito: C

Comentários

• Complexidade de Árvores de busca é da ordem de (Log N).

  Algoritmos de complexidade O(log n) são chamados de complexidade logarítmica e resolvem um problema quebrando-o em problemas menores.

  LETRA C

• Força Guerreiro!!!!!!

• Uma árvore binária completa possui, em cada nível, o dobro de nós do nível anterior. Isto é, ela segue uma progressão geométrica começando do primeiro nó raiz: 1, 2, 4, 8, ...

  É fácil observar que a quantidade total de nós (N) de uma árvore desse tipo com n níveis é a soma da P.G. finita:

  N = 2ⁿ - 1

  Dessa forma, para encontrar um nó qualquer, seguindo a lógica de uma árvore de busca, basta saber em qual nível ele está. Assim, obteremos a quantidade de comparações pedida na questão isolando n da fórmula anterior .

  N = 2ⁿ - 1

  N+1 = 2ⁿ

  log₂(N+1) = n

  Resposta: C)