Exercícios sobre Árvores em AED1

Prévia do material em texto

Bacharelado em Ciência e Tecnologia Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Árvores
AED1 — Algoritmos e Estruturas de Dados I
Prof. Jurandy G. Almeida Jr.
2o Semestre de 2015
Exerćıcios
1. O que é um árvore? Explique usando um exemplo. Comente sobre implementação de árvores
por meio de listas lineares.
2. Qual tipo abstrato de dados (TAD) é implementado pelos algoritmos de pesquisa? Defina as
operações básicas desse TAD. Quais as desvantagens de implementar esse TAD usando um
vetor ordenado? Em qual situação seria mais útil utilizar apenas um vetor simples? Justifique
a sua resposta.
3. Faça uma comparação entre todos os métodos de pesquisa estudados em aula com relação a
ordem de complexidade, levando em consideração o número de comparações.
4. Considere as técnicas de pesquisa sequencial e pesquisa binária. Descreva as vantagens e
desvantagens de cada uma dessas técnicas, indicando em que situações você usaria cada uma
delas. Dê a ordem de complexidade de melhor e pior caso de cada método, levando em
consideração o número de comparações.
5. Considere a árvore representada através de parênteses aninhados:
( A ( B ) ( C (D ( G ) ( H ) ) ( E ) ( F ( I ) ) ) )
Responda as seguintes questões:
(a) Quantas subárvores contém?
(b) Quais os nós folha?
(c) Qual o grau de cada nó?
(d) Qual o grau da árvore?
(e) Liste os ancestrais dos nós B, G e I.
(f) Identifique as relações de parentesco entre os nós A, G e I.
(g) Liste os nós de quem C é ancestral próprio.
(h) Liste os nós de quem D é descendente próprio.
(i) Dê o ńıvel e a altura do nó F.
(j) Dê o ńıvel e a altura do nó A.
(k) Qual a altura da árvore?
6. Para montar uma árvore genealógica que contém todos os ancestrais consangúıneos de uma
pessoa, qual seria o grau da árvore?
7. Para montar uma árvore genealógica que contém todos os descendentes consangúıneos de uma
pessoa, qual seria o grau da árvore?
8. Dada a árvore:
——————————— 1
—————————– 2
——————— 7
——————— 8
—————————– 3
——————— 9
—————————– 4
——————— 10
————– 14
————– 15
————– 16
————– 17
—— 20
————– 18
————– 19
——————— 11
——————— 12
—————————– 5
——————— 13
—————————– 6
(a) Redesenhe-a na forma tradicional.
(b) Qual o grau da mesma? Explique.
(c) Qual a altura da árvore?
(d) Dê o ńıvel (altura) de cada nó.
(e) Dê o grau de cada nó.
9. O que é uma árvore binária balanceada?
10. Uma árvore binária cuja altura é igual ao número de nós pode possuir nós cheios ? Justifique.
11. Quantos elementos (nós), no mı́nimo e no máximo, pode ter uma árvore binária de altura 5?
12. Uma árvore binária completa e balanceada tem 31 nós até o seu ńıvel n. Sabe-se que ela tem
2n− 1 ńıveis. Quantos nós tem a árvore?
13. Sabendo que uma árvore binária tem altura 5 e está totalmente balanceada e completa,
quantos nós tem o ńıvel 3?
14. Uma árvore binária completa e balanceada com altura 5 tem quantos nós?
15. Sabendo que uma árvore binária está totalmente balanceada e completa e tem 1023 nos até
o seu nivel n, quantos nos tem o nivel n− 1?
16. Sugira uma estrutura de dados para representar uma árvore binária, armazenando um
conteúdo (inteiro) associado a uma chave (inteira).
17. Desenhe uma árvore estritamente binária com 7 nós para a qual os percursos em pré-ordem
e em-ordem produzem a mesma sequência de visitas.
18. Dados os percursos abaixo, reconstruir a árvore original:
pré-ordem: 1, 2, 3, 6, 8, 4, 9, 10, 12, 11, 5, 7, 13
em-ordem: 6, 3, 8, 2, 4, 9, 12, 10, 11, 1, 13, 7, 5
19. Diga, para cada uma das árvores binárias abaixo, se são balanceadas, perfeitamente balance-
adas ou nenhum dos casos ou ambos:
(a) (1 (2 (4) (5)) (3 (6) (7)))
(b) (A (B (D (F)) (E)) (C (G (H))))
20. Quais as propriedades de uma árvore binária de pesquisa?
21. Qual é a altura esperada na situação de pior caso e melhor caso para uma árvore binária de
pesquisa? Justifique a sua resposta.
22. Usando a estrutura de dados para árvore binária vista em aula, implemente as seguintes
operações:
(a) Contar o número de nós de uma árvore.
(b) Calcular a soma de todas as chaves de uma árvore.
(c) Verificar se uma árvore é estritamente binária, isto é, todos os nós não-folhas contém
exatamente 2 filhos.
23. O professor Amongus pensa que descobriu uma extraordinária propriedade de árvore binária
de pesquisa. Suponha que a busca por uma chave k em uma árvore binária de pesquisa
termine em uma folha. Considere três conjuntos: A contém os nós (chaves) à esquerda do
caminho da busca; B, as chaves no caminho da busca; e C, as chaves à direita do caminho da
busca. O professor Amongus afirma que quaisquer três chaves a ∈ A, b ∈ B e c ∈ C devem
satisfazer a < b < c. Apresente um pequeno exemplo que prove que ele está errado.
24. Suponha que tenhamos números entre 1 e 1000 em uma árvore binária de pesquisa e dese-
jamos fazer uma pesquisa (busca) pelo número 363. Qual(is) das seguintes sequências não
poderia(m) ser a sequência de nós examinados? Justifique.
(a) 2, 252, 401, 398, 330, 344, 397, 363.
(b) 924, 220, 911, 244, 898, 258, 362, 363.
(c) 925, 202, 911, 240, 912, 245, 363.
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
(e) 935, 278, 347, 621, 299, 392, 358, 363.
25. Desenhe árvores binárias de pesquisa de alturas 2, 3, 4, 5 e 6 com o seguinte conjunto de
chaves {1, 4, 5, 10, 16, 17, 21}.
26. Desenhe uma árvore binária de pesquisa com a menor altura posśıvel com o seguinte conjunto
de chaves: {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43}.
27. Mostre passo a passo a árvore binária de pesquisa resultante das seguintes operações:
(a) Inserção das chaves 7, 8, 3, 4, 2, 1, 6, 5.
(b) Mostre o percurso em pré-ordem, em-ordem e pós-ordem.
(c) Remoção de 7 e 6.
28. Considere uma árvore binária de pesquisa, inicialmente vazia, a qual armazena caracteres.
Faça a inserção de todas as letras do seu nome completo na mesma sequência da escrita,
desprezando os espaços em branco. Considere, também, todas as letras maiúsculas, sem
acentuação e a ordenação da árvore de acordo com a ordem alfabética, onde a letra A é o
menor valor e a letra Z é o maior.
Exemplo: Dilma Vana Rousseff = DILMAVANAROUSSEFF; inserir a letra D, em seguida
a letra I, depois a letra L e assim por diante até a inserção da última letra que, no exemplo,
é a letra F.
Obs: Letras repetidas devem ser ignoradas.
Alfabeto: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z.
Em seguida, resolva:
(a) Qual é a altura da árvore?
(b) Dê o resultado de um percurso pós-fixado.
(c) Quem é o sucessor do nó de maior altura (caso existam dois ou mais, considere o menor
deles) na árvore?
(d) Quem é o predecessor do quarto nó inserido na árvore?
(e) Indique o resultado da retirada do nó raiz da árvore.
29. Uma árvore binária é zig-zag quando é vazia ou quando não possui nós cheios. Sem usar
recursividade, escreva uma função que recebe o endereço do nó raiz de uma árvore binária e
verifica se ela é zig-zag. Se a árvore dada for zig-zag, a função deverá retornar sua altura;
caso contrário, deverá retornar -1. Não utilize estruturas de dados auxiliares (pilhas, filas,
etc); apenas variáveis locais dos tipos ponteiro ou inteiro.