Lista de Exercícios sobre Árvore

Prévia do material em texto

ESSA LISTA NÃO VALE PONTO 
Lista de Exercícios sobre árvore 
1. Considere uma Arvore binária de busca do tipo AVL. Pede-se: 
A) Inserir os elementos: 50, 60, 5, 10, 6, 9, 15, 12 e 1. (Explicar cada passo as regras de 
balanceamento) 
B) Na árvore resultante remover os elementos: 6, 15, 10, 5, e 12. 
2. O percurso da árvore abaixo em pré-ordem retorna a seguinte seqüência de nós: 
 
a. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 
b. 4, 8, 5, 2, 9, 6, 10, 11, 7, 3, 1 
c. 1, 2, 4, 5, 8, 3, 6, 8, 7, 10, 11 
d. 4, 2, 8, 5, 1, 6, 9, 3, 10, 7, 11 
e. 1, 2, 4, 5, 8, 3, 8, 5, 7, 11, 10 
Justifique sua resposta: 
3. Dada as seguintes árvores binárias: 
 
 
 
a. Somente a I é uma árvore AVL; 
b. Somente I e II são árvores AVL; 
c. Somente I, II e IV são árvores AVL; 
d. Somente I e III são árvores AVL; 
e. Todas são árvores AVL. 
Justifique sua resposta: calcule o fb de cada nó e justifique sua resposta 
1. Em uma estrutura de árvore binária de busca, foram inseridos os elementos “m”, 
“b”, “c”, “d”, “f”, “e”, nesta seqüência. O tamanho do caminho entre um nó 
qualquer da árvore e a raiz é dado pelo número de arestas neste caminho. Qual 
o tamanho do maior caminho na árvore, após a inserção dos dados acima? 
QUESTÃO (0.5) 
a. 2 b. 3 c. 4 d. 5 e. 6 
 
QUESTÃO (1.0) 
Construa uma árvore com base nas informações abaixo: 
O nodo C tem grau 3. 
O nodo X é neto de C e filho de B. 
O avô de B é A. 
O nodo A tem altura 0 e T tem altura 1. 
Os antepassados de P são A,T e K, que são também antepassados de H. 
T tem grau 2, e um dos seus filhos é o nodo S. 
O nodo G tem 2 sub-árvores que são netos de C. 
D é irmão de G, que é uma folha. 
E e F tem graus 0 e 1 respectivamente e são também netos do nodo C. 
O nodo N tem nível 4. 
 
2) QUESTÃO 
Dada a árvore, preencha a tabela: 
 
Nodo Grau Nível Pai Filhos Ancestrais Descendentes 
A 
B 
C 
D 
E 
F 
G 
H 
I 
J 
K 
L 
M 
N 
O 
 
P 
 
 
A 
E 
B C D 
F G H I J 
K N O 
P M L