Exercicios Estruturas de Dados - Arvores

Prévia do material em texto

UNIVERSIDADE ESTADUAL DE FEIRA DE SANTANA
DEPARTAMENTO DE CIÊNCIAS EXATAS - ÁREA DE INFORMÁTICA
PERÍODO LETIVO: 2012.2
DISCIPLINA: EXA 806 Estruturas de Dados
Lista de Exercícios 
1- Considere a seguinte árvore:
	
	
	
	A
	
	
	
	
	
	
	
	
	
	
	
	B
	
	
	
	C
	
	
	
	
	
	
	
	
	D
	
	E
	
	F
	G
	H
	
	
	
	
	
	
	
	
	
	I
	
	J
	K
	L
	
	
	
	
	
	
	
	
	M
	
	N
	
	
	
	
	
	
	
	
	
	
	a- Quais nós são folhas. Qual é o nó raiz.
	b- Qual nó é pai de “C”. Quais são os filhos de “C”.
	c- Quais são os antecessores de “E”. Quais os sucessores de “E”.
	d- Qual a profundidade de “C”. Qual a altura de “C”.
	e- Quantos caminhos diferentes de comprimento 3 existem. Quais são eles.
	f- Liste os nós em Preorder, Inorder, Postorder.
2- Seja a seguinte árvore: 
 A
 B C
 D E F
 
 G H I
	a
	 Quantas sub árvores ela contém?
	g
	 Liste os vértices de quem C é ancestral
	b
	 Quais são os nós folhas? 
	h
	 Liste os vértices de quem D é descendente 
	c
	 Qual o grau de cada nó? 
	i
	 Dê o nível e altura do vértice F. 
	d
	 Qual o grau da árvore? 
	j
	 Dê o nível e a altura do vértice A. 
	e
	 Liste os ancestrais dos nós B, G e I. 
	k
	Qual a altura da árvore ?
	f
	 Identifique todas as relações de parentesco entre os nós
	l
	Liste os nós em Preorder, Inorder, Postorder.
3- Seja uma árvore binária cheia onde todas as folhas estão no nível n. 
	a- Qual o número de nós dessa árvore (em função de n).
	b- Qual o número de folhas do nível n ?
4- Quantos nós tem uma árvore estritamente binária e cheia com x folhas ?.
5- Desenhe todas as árvores binárias possíveis cujo percurso em-ordem seja o seguinte: 1,2, 3, 4.
6-O percurso em pré-ordem de uma árvore binária resultou na impressão da seguinte seqüência: A, B, C, F, H, D, L, M, P, N, E, G, I e o percurso da mesma árvore em em-ordem resultou em: F, C, H, B, D, L, P, M, N, A, I, G, E. Construa uma árvore que satisfaça esses percursos. Ela é única? 
7- a) Desenhe todas as possíveis árvores com 3 nós. 
 b) Desenhe todas as possíveis árvores com 4 nós.
8- Escreva um método para calcular a altura de uma árvore binária. O método recebe uma cópia da raiz da árvore e devolve a altura. 
9- Escreva um método para calcular o número de nós de uma árvore. O método recebe uma cópia da raiz da árvore e devolve o número de nós. 
10- Inserir a seguinte seqüência de elementos em uma árvore AVL: 	1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Mostre como fica a árvore após a inserção de cada elemento e após a rotação (quando precisar). 
11- Sejam os elementos de 1, 2, 3, 4,5, 6, 7. Quais as possíveis disposições de dados de entrada de maneira que a árvore binária de busca (sem balanceamento) satisfaça as condições de árvore AVL após a construção ?
12- Altere a função retirar elemento de uma árvore binária de busca, de maneira que sejam eliminados todos os elementos cujo campo info está entre lim1 e lim2 (inclusive). 
13- Sejam as seguintes árvores de busca binária:
i-
 4 
 		 		 2				 6
			 1		 3	 5 7
ii- 
 6 
 		 		 4				 7
			 3		 5	 
 1 2			
Quais as possíveis disposições dos dados de entrada para produzir cada uma das árvores acima? 
14. Como poderíamos implementar os algoritmos em-ordem, pré-ordem e pos-ordem sem utilizar recursão ? Faça estes três algoritmos.
15. Escreva um programa para copiar uma árvore binária.
16. Um caminhamento por nível em uma árvore, primeiro lista a raiz, em seguida todos os nós que estão no nível 1 então todos os nós do nível 2, etc. Escreva um procedimento para listar os nós de uma árvore binária por nível.
17. Escreva uma função que retorne o pai de um dado nó. 
18. Para um árvore binária qualquer, escreva dois métodos: Uma que insira um filho à direita de um dado nó e outra que insira um filho à esquerda de um dado nó.
19. Insira os números 30, 40, 55, 22, 15, 38, 42, 52, 35 e 32 (nesta ordem) em uma árvore AVL. Liste os nós em Pré-ordem, em-ordem e pos-ordem.
Faça o mesmo para as seqüências:
90, 18, 55, 40, 15, 20.
55, 66, 88, 33, 40, 22, 46, 31.
24 – Para uma árvore B de t = 2, insira os seguintes números na sequência:
15,20,45,55,35,65,30,10,40,18,26,63,12,67,95,12,75,90,03,58,38.