Questão 795142

• Banca: FCC
• Órgão: TST
• Ano: 2012
• Provas: FCC - 2012 - TST - Técnico Judiciário - Programação
• Disciplina: Algoritmos e Estrutura de Dados

Considere a estrutura de dados Árvore Binária de Busca (ABB). Se inserirmos numa ABB os nós:

60, 10, 20, 80, 15, 75, 12 e 77,


nessa ordem, a altura da árvore e o nível do nó 15, respectivamente, serão
Dado: A raiz fica no nível 1 da árvore

• A. 5 e 5
• B. 5 e 4
• C. 6 e 4
• D. 6 e 3
• E. 7 e 4

Gabarito: B

Comentários

• Árvore:
  
                                          60
                               10                   80
                                   20          75 
                               15                 77
                           12
• Não entendi porque esta arvore eh assim:
  
  Achei que poderia ser assim :
  
                  60
         15                   77
   12      20           75      80
  10

• 1) Pegue lápis e papel e vamos construir a árvore com a sequencia de nós 60, 10, 20, 80, 15, 75, 12 e 77

  60: 60 vira raiz.
  10: 10<60 então vai para a esquerda de 60
  20: 20<60 então vai para a esquerda de 60 e encontra o 10. 20>10 então vai para a direita do 10
  80: 80>60 então vai para a direita de 60
  15: 15<60 vai para esquerda e encontra o 10. 15>10, vai para a direita e encontra o 20. 15<20 e vai para a esquerda de 20.
  75: 75>60 vai para a direita e encontra o 80. 75<80, vai para a esquerda de 80.
  12: faça vc mesmo e ele ficará à esquerda de 15.
  75: faça vc memso e ele ficará à direita de 75.
  
  Pq se faz assim?
  Uma árvore binária com raiz R é uma ABB se:       (1) A chave (informação) de cada nó da sub-árvore esquerda de R é menor do que a chave (informação) do nó R;       (2) A chave de cada nó da sub-árvore direita de R é maior do que a chave do nó R;       (3) As sub-árvores esquerda e direita também são ABBs.
  2) A imagem ficará mais ou menos assim:
  .......................................60
  
  ..........................10.....................80
  
  ................................20...........75
  
  ..........................15......................77......
  
  ......................12
  
  
  3) Quem está em qual nível?
  A raiz 60 está no nível 1.
  10 e 80 no nível 2.
  20 e 75 no nível 3.
  15 e 77 no nível 4.
  12 no nível 5.
  Até aqui ficaríamos com as letras "b" e "c", pois o 15 está no nível 4.
  
  4) Qual altura da árvore?
  A Altura de uma árvore é número de níveis da árvore. Esta tem 5 níveis.
  
  Ficamos com a letra "b"
  
  ;)
  
  
  
  
  
  
  

• Silvia, fiquei com essa dúvida também. Mas parece que a questão não quer que você ordene a sequência e depois construa a árvore. A árvore deve ser construída baseada na sequência dada.

• A altura não seria igual ao nível da folha + 1? Marquei a C por achar que a folha (12), com nível igual a 5, considerando esse caso específico com a raiz = 1, teria a altura = 6 (altura da árvore).

• Eu demorei a perceber mas não existe o balanceamento dessa árvore, isso pelas possíveis respostas, então deve ser seguir apenas a sequência sendo que o nó 12 fica no nível mais alto (5), que corresponde a altura da árvore, e o nó 15 sendo pai deste no nível 4. Reposta da questão letra B.

• Força Guerreiro!!!!!!