aed3-2011-1-exercicio-1

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 1
 Data Limite de Entrega: 20/03/11
 Deve ser entregue pelo Moodle (http://aluno.dcc.ufla.br)
 Exercício individual. Cópias receberão nota zero.
1. Responda às seguintes questões sobre árvores binárias de pesquisa
(a) Desenhe a árvore binária de pesquisa formada pela inserção das seguintes chaves (números inteiros), 
nesta ordem: 22, 12, 27, 7, 14, 5, 4, 3, 6, 10, 32, 37, 24, 23, 25, 34, 39.
(b) Qual a altura do nó de chave 7? Em que nível esta chave se encontra? Qual a altura da árvore?
(c) Existe um caminho entre os nós de chave 27 e 34? Se sim, qual o comprimento deste caminho? E entre 
os nós de chaves 7 e 14?
(d) Qual o pai do nó de chave 24? Quais os filhos do nó de chave 7? Dê exemplos de dois nós irmãos.
(e) Considerando que uma visita ao nó imprime sua chave, qual o resultado impresso pelo caminhamento na 
árvore em pré-ordem? E em in-ordem? E em pós-ordem?
(f) Desenhe a árvore binária de pesquisa formada pela exclusão das seguintes chaves na árvore do item (a): 
5, 22, 32, 4.
2. Com relação à avaliação de expressões usando árvores binárias, responda:
(a) Desenhe a árvore para a expressão infixada: 4 - ((8 * 5) - 2) / (3 + (7 * 8))
(b) Qual a expressão prefixada correspondente? Como você a obteve?
(c) Qual a expressão posfixada correspondente? Como você a obteve?
3. Implemente uma função em C para obter a altura de uma árvore binária.
4. Implemente uma função não recursiva em C para inserir um registro em uma árvore binária de pesquisa.
5. Implemente uma função em C para imprimir as chaves de uma árvore binária com recuos de margem 
proporcionais à profundidade do nó na árvore. Por exemplo, a árvore:
 
 55 Deve ser impressa como (--- = null):
 / \ 55
 33 88 33
 / \ \ 11
 11 44 99 ---
 ---
 44
 ---
 ---
 88
 ---
 99
 ---
 ---
	GCC109 – Algoritmos e Estruturas de Dados III
	Lista de Exercícios 1