Questão 163702

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2010
• Provas: CESGRANRIO - 2010 - Petrobrás - Analista de Sistemas Júnior - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Pilhas

Uma sequência desordenada de números armazenada em um vetor é inserida em uma árvore AVL. Após a inserção nesta árvore, é feito um percurso em ordem simétrica (em ordem) e o valor de cada nó visitado é inserido em uma pilha. Depois de todos os nós serem visitados, todos os números são retirados da pilha e apresentados na tela.
A lista de números apresentada na tela está

• A. ordenada ascendentemente de acordo com os números.
  
• B. ordenada descendentemente de acordo com os números.
  
• C. na mesma ordem do vetor original.
  
• D. na ordem inversa do vetor original.
  
• E. ordenada ascendentemente de acordo com sua altura na árvore.

Gabarito: B

Comentários

• Letra B CORRETA
  
  Insiram em uma arvore AVL aqui e vejam que ao remover em in-order teremos um vetor ordenado ascendentemente. Este vetor alimenta uma pilha. Agora sim, teremos a reversão do ordenamento pois a pilha é FILO.
  

• Uma outra idéia para resolver essa questao é:
  
  Imagina uma arvore bem simples com 3 elementos { 1, 2 , 3 },
  
  2 é a raiz da arvore
  1 é a subarvore esquerda
  3 é a subarvore direita
  
  Lembrando que os elementos da subarvore Esquerda sao sempre menores que a raiz
  os elementos da subarvore Direita sao sempre maiores que a raiz
  
  Ao percorrer a arvore em-ordem, faremos o percurso E-R-D (Esquerda-Raiz-Direita), ou seja, 1 depois 2 depois 3.
  Nessa mesma ordem eles serao inseridos na pilha (FILO)
  
  | 3 | --> ultimo elemento inserido
  | 2 |
  | 1 |
   ----
  
  Ao desempilhar teremos: 3, 2, 1.
  
  abs,
  bons estudos.
   

• A inserção dos elementos desordenados em uma árvore AVL, ordena-os. Realizando o percurso em ordem simétrica ( em ordem) está percorrendo a árvore AVL em ordem crescente dos número e como eles são inseridos em uma pilha (LIFO) e retirado de lá para serem exibidos na tela, logo, está sendo retirado do maior número para o menor - ordenado descendente.
• O início da questão (vetor desordenado...) é só blá blá blá. Uma vez que os números estejam em uma árvore AVL, sabemos que a árvore terá as seguintes propriedades:
  1- Cada nó terá 0, 1 ou 2 filhos (árvore binária);
  2- Os filhos da esquerda de um nó pai serão sempre menores que o nó pai e os da direita serão sempre maiores que o nó pai (árvore de busca binária);
  3- A árvore será balanceada e as diferenças de níveis entre as subárvores à esquerda e direita de um nó será de -1, 0 ou 1 (AVL).
  Ex:http://upload.wikimedia.org/wikipedia/commons/thumb/0/06/AVLtreef.svg/250px-AVLtreef.svg.png
  Quando percorrermos essa AVL na ordem simétrica (esquerda, visita nó, direita), teremos o seguinte:
  9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76. 
  Ou seja, ficou na ordem crescente dos números. Porém, a questão diz que à medida que os nós foram sendo visitados, esses números foram sendo inseridos em uma pilha. Então, a pilha ficou assim:
  76
  72
  67
  54
  50
  23
  19
  17
  14
  12
  9
  E depois esses números foram sendo impressos na tela. Como é uma pilha, então foi sendo retirado do topo (LIFO). Assim, ficou na tela:
  76, 72, 67, 54, 50, 23, 19, 17, 14, 12, 9.
  Ou seja, em ordem decrescente dos números.
• Essa questão não tem mistério. Não é necessário fazer conta nem nenhum tipo de desenho ou rascunho. Basta pensar da seguinte maneira:
  
  A saída de um percurso do tipo em-ordem numa árvore AVL (ou binária) é uma lista ordenada crescentemente. Após inseri-los em uma pilha a ordem fica invertida, no sentido decrescente.
  
  Simples assim.
• Muito bom o comentário do Alessandro, mas aqui vai somente uma pequena correção: 
  
  
  
  

  troque a palavra FIFO (First-In, First-Out = Primeiro a Entrar é o Primeiro a Sair = Fila) por LIFO (Last-In, First-Out = Último a Entrar Primeiro a Sair = Pilha).