Questão 599707

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2011
• Provas: CESGRANRIO - 2011 - Petrobras - Analista de Sistemas Júnior - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados

Uma árvore AVL é uma árvore binária de busca autobalanceada que respeita algumas propriedades fundamentais. Como todas as árvores, ela tem uma propriedade chamada altura, que é igual ao valor da altura de sua raiz.

Sabendo que a altura de uma folha é igual a um e que a altura de um nó pai é igual ao máximo das alturas de seus filhos mais um, qual estrutura NÃO pode representar uma árvore AVL?

• A. Uma árvore vazia
• B. Uma árvore com dois nós
• C. Uma árvore com três nós e altura igual a dois
• D. Uma árvore com três nós e altura igual a três
• E. Uma árvore com seis nós e altura igual a três

Gabarito: D

Comentários

• A questão informa que a altura de um nó é igual a 1 e que a altura de seu pai é a altura do último nó + 1. Ou seja:
  
      B      - altura 2
  A     C   - altura 1
  
  a) uma árvore vazia tem altura igual a -1 (para a Cesgranrio)
  b) A    - altura 2
         B - altura 1
  é uma árvore AVL. Está balanceada
  c) B     - altura 2
  A     C - altura 1
  Também é uma árvore AVL
  d) A        - altura 3
         B     - altura 2
             C - altura 1
  Não é uma árvore AVL pois ela está desbalanceada
  e)      D       - altura 3
        C    F    - altura 2
     B     E   G - altura 1
  É uma árvore AVL