Questão 126472

• Banca: ESAF
• Órgão: Prefeitura de Natal - RN
• Ano: 2008
• Provas: ESAF - 2008 - Prefeitura de Natal - RN - Auditor do Tesouro Municipal - Tecnologia da Informação - Prova 2
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

Analise a descrição a seguir:

Na análise de um problema de estrutura de dados, utilizou-se uma árvore binária para representar uma árvore genérica (não-binária) qualquer. Ao se transformar a árvore genérica na árvore binária, observou-se que esta fi cou distribuída da seguinte forma:

No nível 0 ou raiz - um elemento; no nível 1 - um elemento; no nível 2 - dois elementos; no nível 3 - quatro elementos e, fi nalmente, no nível 4 - oito elementos.

Quanto à sua composição, é correto afi rmar que a árvore genérica possui no seu nível 0 ou raiz um elemento, e no seu nível 1

• A. um elemento.
• B. dois elementos.
• C. três elementos.
• D. quatro elementos.
• E. cinco elementos.

Gabarito: D

Comentários

• No seu nível 0, ou raiz, a árvore tem um nó.No seu nível 1, a árvore tem quatro nós.Para identificar quantos nós a árvore genérica terá, a partir de uma binária, basta saber quantos níveis a árvore binária possui abaixo do nó raiz. No nosso caso temos 4.Logo, a resposta é letra E
• Daniel, não entendi muito bem sua explicação pois na questão não está perguntando quantos nós existem na árvore e sim a quantidade de elementos no nível 1 e em meu consenso para este caso seria a letra B, dois elementos.
  
  o
  /
        o      <-- Nível 1
      /   \
   o      o  <--  Dois elementos 
          /  \    /  \
        o    o o   o 
       .
       .
       .

• também achei esquisita a questão...minha opinião seria a B também.

• Esta questão é um típico caso de Conversão de Árvore Genérica em Árvore Binária  em que 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.

  Como exemplo podemos citar o seguinte exemplo:

             O                      O
           /  |  \        =>        |
        O  O  O                 O
                                         \
                                          O
                                             \
                                              O
   

   

   

• Pessoal, como disse o amigo acima, este é um problema de conversão de arvore generica em binaria, acredito que vocês estejam fazendo confusão: Repare que o enunciado pede quantos nos tera o nivel 1 da ARVORE GENERICA e nao da arvore binaria OK?!
  
  Deem uma olhada no slide 15 deste material http://www.slideshare.net/darosajoseluiz/arvores-14349156 mostra como transformar uma arvore generia em binaria de forma super simples.
  
  Abraços!!!

• Tiago, obrigada por compartilhar conosco o link que ensina a transformar uma árvore genérica em uma árvore binária.
  No entanto, tive dificuldades em fazer o caminho inverso, isto é, dada a árvore binária da questão, encontrar uma árvore genérica.
  Ainda não consegui compreender como chegar no resultado de 4 elementos no nível 1. Assim como os demais colegas, eu marquei a alternativa B (dois elementos).

• Pessoal, acho que  entendi, mas em se tratando de composição novamente, se fosse no nível 2 seriam quantos elementos? Seriam 7 ?

  Grato,,