aed3-2011-1-exercicio-2

Prévia do material em texto

Universidade Federal de Lavras
Departamento de Ciência da Computação
GCC109 – Algoritmos e Estruturas de Dados III
Professor: Denilson Alves Pereira
Lista de Exercícios 2
 Data Limite de Entrega: 04/04/11 (Turma 10A) e 07/04/11 (Turma 14A)
 O exercício deve ser entregue pelo Moodle (http://aluno.dcc.ufla.br). Envie arquivos somente nos formatos txt e 
pdf (não enviar .doc, .docx, .odt etc.). Arquivos compactados somente .zip e .tar.gz (não enviar .rar, .z etc.). 
Não use acentos e nem “ç” nos nomes de arquivo.
 Exercício individual. Cópias receberão nota zero.
1. Dê exemplos de: árvore binária completamente balanceada, árvore binária cheia e árvore binária 
balanceada (3 exemplos diferentes).
2. Mostre a árvore binária de pesquisa resultante após:
 (a) inserir as seguintes chaves (número inteiros), nesta ordem: 35, 10, 5, 8, 50, 60, 55, 70, 45, 2
 (b) aplicar o algoritmo DSW para balancear a árvore. Neste caso, mostre também pelo menos 
dois passos intermediários da 1a. fase e dois passos da 2a. fase.
3. Dada a árvore AVL abaixo, mostre a sequencia de árvores resultantes após cada operação 
indicada abaixo:
 (a) Inserir as chaves: 10, 11.
 (b) Inserir a chave 6.
 (c) Inserir a chave 1.
 (d) Inserir as chaves: 2, 3, 7, 9, 12.
4. Implemente em C uma função para efetuar uma rotação simples à esquerda. A função recebe 
como parâmetro um apontador para um apontador para o nó pai. O nó pai tem um filho à direita 
(nó filho). A rotação deve ser feita com o nó filho. Cada nó pode ter outros filhos.
void rotacaoEsquerda (Apontador *p) { . . . }
5. Implemente em C uma função para efetuar uma rotação simples à direita. A função recebe como 
parâmetro um apontador para um apontador para o nó pai. O nó pai tem um filho à esquerda (nó 
filho). A rotação deve ser feita com o nó filho. Cada nó pode ter outros filhos.
void rotacaoDireita (Apontador *p) { . . . }
8
5
134
6. Implemente em C uma função para efetuar uma rotação dupla esquerda-direita. A função recebe 
como parâmetro um apontador para um apontador para o nó avô. O nó avô tem um filho à 
esquerda (nó pai) e o nó pai tem um filho à direita (nó filho). A rotação deve ser feita com o nó 
filho. Cada nó pode ter outros filhos.
void rotacaoEsqDir (Apontador *p) { . . . }
Use as funções implementadas nos exercícios 4 e 5.
Mostre também o código que você usou para testar sua função. Adicione comentários no seu 
código explicando o seu teste.
7. Considerando a implementação do algoritmo DSW disponível no Moodle, explique a estratégia 
usada nas funções DSWBalancingAlgorithm, LeftRotate e RightRotate.
	GCC109 – Algoritmos e Estruturas de Dados III
	Lista de Exercícios 2