Questão 606175

• Banca: CESGRANRIO
• Órgão: FINEP
• Ano: 2011
• Provas: CESGRANRIO - 2011 - FINEP - Analista - Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados

Considere as definições a seguir.
• O nível do nó raiz de uma árvore é 1.
• O nível de qualquer nó subsequente é igual ao nível do seu nó pai mais 1.
• A profundidade de uma árvore é igual ao maior nível encontrado dentre todos os seus nós.
Partindo-se das premissas acima, a menor e a maior quantidade de nós, respectivamente, que poderiam existir em uma árvore binária de profundidade 4 são

• A. 3 e 15
• B. 4 e 15
• C. 3 e 16
• D. 4 e 16
• E. 5 e 16

Gabarito: B

Comentários

• Maior quantidade de nó (15):
                                                 N1                                                     -Profuncidade 1
                        N2                                          N3                               -Profuncidade 2
              N4                N5                   N6                   N7                  -Profuncidade 3
        N8     N9     N10    N11     N12    N13     N14    N15           -Profuncidade 4
  
  Menor quantidade de nó (4):
                                                N1                                                      -Profuncidade 1
                                                N2                                                      -Profuncidade 2
                                                N3                                                      -Profuncidade 3
                                                N4                                                      -Profuncidade 4
  
• h = profundidade = altura = 4
  quantidade máximo de número de nós = 2^h -1 = 2^4 -1 = 15
  quantidade mínima = h = 4
• Nível      Mínimo de Nós Por Nível        Máximo de Nós Por Nível
    1             1                                   1 (raiz)       
    2             1                                   2 
    3             1                                   2 * 2 = 4
    4             1                                   4 * 2 = 8
              ---------                     ------------------------
                  4                                 15
  
  

• Para árvores do tipo ziguezague (cada nó não folha só possui um filho) temos que n (número de nós) =h (profundidade). No caso seriam 4 nós.  
  

  O total de nós n em uma árvore binária cheia (que seria o máximo) de altura d é a soma do número de nós a cada nível: 

  n = 2^0 + 2^1 + 2^2 + ..... + 2^d = Σ 2^j, onde j=0...d -> n = 2^(d+1) -1; 

  como a profundidade h é igual a d+1 então n = 2^4 -1 = 16 - 1 = 15

  E se a pergunta fosse "Qual é o número de folhas de uma árvore cheia com n nós?" 

  n = 2^(d+1) -1 -> d = log (n+1) –1; d = log (16) - 1 = 4 - 1 = 3 -> 2^3 = 8, existe 8 nós folhas em uma árvore cheia de 15 nós.