ListaExercicios2- Estrutura de Dados

Prévia do material em texto

Ministério da Educação
Universidade Tecnológica Federal do Paraná
Campus Cornélio Procópio
Departamento Acadêmico de Computação
ESTRUTURA DE DADOS - C31 – Engenharia de Computação
Prof. Danilo Sipoli Sanches
Lista de Exercícios – 2
1. Escreva algoritmos recursivos para determinar o número de nós ímpares numa árvore binária e
a soma do conteúdo de todos os nós numa árvore binária.
2. Considerando uma estrutura de árvore binária que armazena valores inteiros, escreva uma
função que retorne a soma dos números inteiros armazenados em nós que são folhas da árvore
(isto é, nós que não têm filhos). O protótipo da função deve ser:
3. Suponha que as notas de uma prova de uma turma de alunos estejam armazenadas numa
“árvore binária de busca”, ordenada pelos números de matrícula dos alunos. A estrutura desta
árvore é dada a seguir:
Escreva uma função para retornar a nota de um aluno, dado seu número de matrícula.
4. Considere uma árvore binária de busca que armazena os dados dos alunos de uma turma,
usando a média do aluno como critério de ordenação. As médias dos alunos associados aos nós
da sub-árvore à esquerda são menores que a média do aluno associado à raiz, e as médias
dos alunos associados aos nós da sub-árvore à direita são maiores ou iguais à média do nó da
raiz. O tipo que representa um nó da arvore é dado por:
Escreva uma função que receba como parâmetros uma árvore definida pela estrutura acima e os
limites de um intervalo fechado de notas, e retorne quantos alunos têm médias dentro deste
intervalo. O protótipo dessa função é dado por:
5. Implemente uma função em C para testar se uma árvore binária é uma árvore binária de busca.
Se a árvore binária testada não for uma árvore binária de busca, construa uma nova árvore
binária, sendo que esta árvore deverá ser binária de busca. Para isso, a construção dessa árvore
binária de busca deverá ser realizada a partir do percurso ordem simétrica da árvore binária
existente;
6. Considerando as seguintes declarações de uma árvore binária
a) Implemente uma função que, dada uma árvore, retorne a quantidade de nós que possuem
apenas um filho dessa árvore. O protótipo do função deverá ser: int um_filho(Arv* arv); 
b) implemente uma função que, dada uma árvore, retorne a quantidade de nós que não são
folhas, isto é, nós que possuem pelo menos um filho. Essa função deve obedecer o
protótipo: int intermediários(Arv* arv);
7. Dado a árvore do tipo AVL a seguir, pede-se:
a. Desenvolva a função para calcular o fator de balanceamento FB de todos os nós; 
b. Faça um código em C para a inserção em uma árvore AVL inserindo os nós 4, 14 e 16.
Para cada novo nó inserido, deverá ser calculado o FB da árvore (item a) afim de
verificar se a árvore continua balanceada. Caso a árvore esteja desbalanceada, construa
o algoritmo de rotação necessário para garantir o balanceamento.
 
8. Simule graficamente (usando algum editor gráfico do computador) o processo de inserção dos
nós (a, z, b, y, c, x, d, w, e, v, f) de forma a construir uma arvore AVL. Se for necessário o
rebalanceamento de nós, mostre qual o procedimento a fazer. 
9. Mostre a árvore-B de ordem 4 resultante (usando algum editor gráfico do computador) da
entrada das letras (C G J X N S U O A E B H I) na ordem apresentada. 
	ESTRUTURA DE DADOS - C31 – Engenharia de Computação
	Prof. Danilo Sipoli Sanches
	Lista de Exercícios – 2