Questão 7300

• Banca: ESAF
• Órgão: CGU
• Ano: 2004
• Provas: ESAF - 2004 - CGU - Analista de Finanças e Controle - Tecnologia da Informação - Prova 3
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

Analise as seguintes afirmações relativas a estruturas de dados:

I. Uma árvore binária qualquer de altura 3 tem no máximo 8 folhas.

II. Ao se transformar uma árvore genérica, formada apenas pela raiz e seus quatro filhos, em uma árvore binária, a árvore resultante terá apenas uma folha.

III. A única condição para uma árvore binária de pesquisa ser considerada balanceada é que, para cada nó, a altura da sub-árvore da esquerda seja igual à altura da sub-árvore da direita.

IV. Uma árvore binária de pesquisa balanceada deve ter o número de folhas igual ao número de nós.

Estão corretos os itens:

• A. I e II
• B. II e III
• C. III e IV
• D. I e III
• E. II e IV

Gabarito: A

Comentários

• I. Uma árvore binária qualquer de altura 3 tem no máximo 8 folhas.
  Esta afirmativa está correta?
  Creio eu que uma árvore de altura teria no máximo 1 folha no 1º nível, 2 no 2º nível e 4 no 3º nível. Somando teríamos um número máximo de 7 folhas, e não de 8 como descrito.
• I - (True). From Wikipedia: (The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.) Therefore the max size of a nth binary tree is: SUM from i=1 to i=n of 2^n + 1.
  n = 1 --> 2 + 1 = 3
  n = 2 --> 4 + 2 + 1 = 7
  n = 3 --> 8 + 4 + 2 + 1 = 11.
  
  But see, the item says about the NUMBER OF LEAFS. In this case the deepest level has 8 nodes and all of them are leafs.
  
  II - (False) A binary tree with 5 nodes can have either (3, 2 or 1 leafs) depending how the tree is drawn. 1 leaf node is only one of the possible trees, it's wrong state, as a mandatory rule, that it'll only have 1 leaf node.
• Ola reinaldo, a sua afirmacao esta correta, so corrigindo que as folhas sao no maximo em 4 (quatro), pois folhas sao somento os nos terminais.
• I. altura 3, formula 2**n -> 2**3 = 8. A questão não perguntou o número de nós, que seria (2**3+1)-1=15 nós, mas sim o número de folhas. II. Questão correta, segundo o algoritmo de transformação de genérica para binária: i) Ligar os nós irmãos; ii) Desligar o pai do filhos, exceto do primeiro.Simulando: R(f1)(f2)(f3)(f4) -> R(f1(f2(f3(f4)))), onde somente f4 é folha.Ref.: http://www.inf.pucrs.br/~marcon/AlgoritmosEProgramacaoII/Slides/21_Arvores.ppt, slide 14.III. Errada, pois fb(n)=|altura(dir)-altura(esq)|<=1;II. Se o número de nós contempla o número de folhas (contém) e a árvore tem mais nós que folhas o número náo pode ser igual. Se houver fórmula para isto favor comentar.
• Discordo da afirmativa I ser verdadeira, pois uma árvore de altura 3, os nós folhas não seriam os que estão no nível 3 ? Se eles possuíssem nós folhas a mesma árvore não passaria a ter altura 4 ? Esquisita esta questão.
• Está tudo de acordo com o que nosso amigo "Alexandre Paiva" falou.
  
  E "Victor", não são 4 nós folhas, altura 3 significa que a árvore possui 4 níveis pois a contagem é feita de 0 a 3. A fórmula correta é:
  Número máximo de nós para uma árvore com altura h: 2h+1-1
  Número máximo de nós folha e uma árvore de altura h: (2h+1-1)-(2h-1) = 2h
  
  Notem que para encontar esse valor basta subitrair do máximo de nós, o número máximo de nós se a árvore tivesse um nível a menos:
  
      Altura 2             Altura 1            Nós Folha
          d                       d
     b         f       -     b         f    =   
  a     c e    g                                 a     c e     g
• I - CORRETA
  Segundo Tanenbaum:
  • "A altura de uma árvore binária é o nível máximo de suas folhas (ocasionalmente conhecida como profundidade da árvore)",
  • "A profundidade de uma  árvore binária significa o nível  máximo  de  qualquer  folha  na  árvore"
  • "A raíz da árvore tem nível 0"
   
  De acordo com as definições de Tanenbaum o nó 8 da árvore acima seria o nível 3, como este é o nível máximo esta seria então a altura da árvore. E como podemos observar a árvore acima tem 8 folhas (nós sem filhos).
  
  II CORRETA -
  

  Conversão de Árvore Genérica em Árvore Binária consiste nos seguintes passos:
  1º passo: A raiz da árvore genérica será também a raiz da árvore binária;
  2º passo: Manter a ligação de cada nodo com seu filho mais à esquerda, se o nodo possuir apenas um nodo este é o filho a esquerda (esta ligação mostrará o filho a esquerda na árvore binária);
  3º passo: Formar uma nova ligação de cada nodo com seu irmão à direita (esta ligação mostrará o filho a direita na árvore binária);
  4º passo: As ligações restantes são desconsideradas.
  
  Àrvore Genérica     -> Binária
        o                            o
  o  o  o  o                        o
                                        o
                                         o
                                          o -> Única folha                    

  III - ERRADA - A altura não precisar ser igual, pode ter diferença de um nível
  De acordo com Tanembaum:
  • Uma árvore  binária  balanceada (chamada  ocasionalmente  árvore  AVL  é  uma  árvore  binária  na  qual  as alturas  das  duas  subárvores  de  todo  nó  nunca  diferem  em  mais  de  1).
  IV - ERRADA - A árvore acima está balanceada e tem um total de 15 nós (nós internos + nós externos ou folhas), os nós externos são 8, ou seja, é menor do que o total de nós.
  LETRA A