Questão 1546645

• Banca: FCC
• Órgão: MANAUSPREV
• Ano: 2015
• Provas: FCC - 2015 - MANAUSPREV - Analista Previdenciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados

Considere que a Manausprev armazena os nomes dos beneficiários de aposentadorias em uma Árvore Binária de Busca - ABB. Ao se armazenar, nesta ordem, os nomes Marcos, José, Carolina, Paula, Rui, Pedro e Maria, a ABB resultante

• A. é perfeitamente balanceada.
• B. tem altura 3, que corresponde à altura mínima para armazenar os 7 nomes.
• C. possui como folhas os nomes Rui e Maria.
• D. requer no máximo 3 comparações para localizar qualquer um dos 7 nomes.
• E. requer no máximo 4 comparações para localizar qualquer um dos 7 nomes.

Gabarito: E

Comentários

• A árvore final fica assim:

  
  

  Padrão: Nó (Filho Esquerda, Filho Direita);

  Marcos (José, Paula);

  José (Carolina, Null);

  Paula (Maria, Rui);

  Rui (Pedro, Null);

  Carolina, Maria, Pedro: (Null, Null);

  
  

  
  

  Para garantir o acesso a qualquer nó, é necessário pelo menos 4 comparações. 

  Para ver como a árvore é montada, segue o link: https://www.cs.usfca.edu/~galles/visualization/BST.html

• A: entendo que não é possível afirmar que a árvore é perfeitamente balanceada com a informação dada no enunciado. A questão afirma a ordem da inserção dos nós, mas não aponta onde eles são inseridos. Assim, não é possível afirmar que todos os nós pais possuem dois filhos.

  B: caso os nós, com exceção das folhas, tenham 2 filhos, a altura mínima dessa árvore seria 2.

  C: pela mesma justificativa da alternativa A, não é possível afirmar que Rui e Maria são folhas.

  D: caso os nós, com exceção das folhas, tenham 2 filhos, vamos precisar fazer 4 comparações. Então, não é possível afirmar que tal árvore requer NO MÁXIMO 3 comparações para localizar qualquer um dos 7 nomes.

  E: vide comentários sobre a alternativa D.

  Assumindo (embora o enunciado não tenha tornado isso explícito)

  - que estamos falando de uma ordem alfabética

  - que as palavras com letra "menor" (anteriores no alfabeto) ficam na esquerda

  - que as palavras com letra "maior" ou igual ficam na direita

  Teremos uma árvore com esse aspecto:

                  M

                 /   \

              J       P

            /        /    \

        C        M      R

                         /

                      P

  [e-mail]

• Árvore perfeitamente balanceada: para cada nó, o número de nós de suas sub-árvores esquerda e direita diferem em, no máximo, 1. Não é o caso dessa árvore.
  

• a) E. 

   b) E. Tem altura de 4. 

   c) E, Rui não é folha. 

   d) E. Conforme Maurício afirmou: caso os nós, com exceção das folhas, tenham 2 filhos, vamos precisar fazer 4 comparações. Então, não é possível afirmar que tal árvore requer NO MÁXIMO 3 comparações para localizar qualquer um dos 7 nomes.

   e) C. Vide comentário item 'd'

• Força Guerreiro!!!!!!