AD2_Estrutura de Dados_2008-1_Gabarito

Prévia do material em texto

Estrutura de Dados - 1o. per´ıodo de 2008
Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia
1. (1,5) Desenhe uma a´rvore bina´ria de busca CHEIA COM ALTURA 4, colocando dentro
de cada no´ o valor de sua chave. As chaves sa˜o 1, 2, · · · , k (k e´ o nu´mero de no´s da
a´rvore, que e´ um valor que voceˆ deve deduzir). A seguir, escreva a sequ¨eˆncia de chaves
que corresponde ao percurso em PO´S-ORDEM desta a´rvore.
Resposta: Percurso em po´s-ordem: 1, 3, 2, 5, 7, 6, 4, 9, 11, 10, 13, 15, 14, 12, 8.
8
1 3
2 6
4
5 7 9 11
10 14
12
13 15
2. (1,5) Suponha que voceˆ deseja remover a RAIZ de uma a´rvore bina´ria de busca. Apo´s
removeˆ-la, como voceˆ deve reestruturar a a´rvore de modo que ela continue sendo uma
a´rvore bina´ria de busca? Deˆ um exemplo que mostre seu racioc´ınio. (Sugesta˜o: use a
a´rvore que voceˆ desenhou na questa˜o anterior, removendo sua raiz e reestruturando-a.)
Resposta: Basta selecionar o no´ mais a` direita da suba´rvore esquerda (que e´ o no´ de
maior valor desta suba´rvore), ou o no´ mais a` esquerda da suba´rvore direita (o de menor
valor) e substituir a raiz por este no´. Utilizando o exemplo da a´rvore cheia da questa˜o
anterior, poder´ıamos substituir a raiz pela chave 7 (ou pela chave 9).
7
1 3
2 6
4
5 9 11
10 14
12
13 15
Caso a a´rvore bina´ria de busca na˜o seja cheia, e tanto o no´ de maior valor da suba´rvore
esquerda quanto o no´ de menor valor da suba´rvore direita na˜o sejam folhas, enta˜o basta
8
1 3
2 6
4
5 11
10 14
12
13 15
remoção da raiz
6
1 3
2 5
4
11
10 14
12
13 15
selecionar um destes no´s para substituir a raiz, e “promover” a suba´rvore deste no´ para
sua antiga posic¸a˜o, como no exemplo da figura a seguir.
3. (1,5) Seja T uma a´rvore bina´ria de custo mı´nimo relativa a`s frequ¨eˆncias f1, f2, f3, f
′
0
, f ′
1
, f ′
2
, f ′
3
.
Escreva valores para estas frequ¨eˆncias de modo que T seja uma a´rvore zigue-zague.
Resposta: Para as frequ¨eˆncias f1 = 1, f2 = 2, f3 = 4, f
′
0
= f ′
1
= f ′
2
= f ′
3
= 0 temos a
seguinte a´rvore bina´ria de custo mı´nimo.
s
3
s
2
s
1
R
3
R
2
R
1
R
0
4. (1,5) A partir de uma a´rvore inicialmente vazia, desenhe a a´rvore AVL resultante da
inserc¸a˜o dos no´s com chaves 10, 4, 15, 8, 7, 6 (nesta ordem).
Resposta:
6
4
8 15
10
7
5. (1,5) Desenhe uma a´rvore B de ordem d = 2 com treˆs n´ıveis e o menor nu´mero poss´ıvel
de chaves. (Os valores das chaves ficam a` sua escolha.)
Resposta:
10 15 25 30 40 45 55 60 70 75 85 90
20 35 65 80
50
6. (1,0) Construa um heap com as seguintes prioridades: 18, 25, 41, 34, 14, 10, 52, 50, 48.
Resposta:
In´ıcio:
14
25
18
5210
41
4850
34
Construc¸a˜o do heap:
1) Descer 34:
14
25
18
5210
41
4834
50
2) Descer 41:
14
25
18
4110
52
4834
50
3) Descer 25:
14
50
18
4110
52
2534
48
4) Descer 18:
Heap obtido: 14
50
52
1810
41
2534
48
7. (1,5) Desenhe uma a´rvore de Huffman relativa a`s frequ¨eˆncias 1, 2, 4, 8, 16, 32, 64. A a´rvore
que voceˆ desenhou e´ a u´nica poss´ıvel?
Resposta: Sejam os s´ımbolos s1, s2, s3, · · · , s7 relativos a`s frequ¨eˆncias 1, 2, 4, · · · , 64, res-
pectivamente. A a´rvore desenhada na˜o e´ a u´nica poss´ıvel, ja´ que todas as a´rvores isomor-
fas a ela (que podem se tornar coincidentes atrave´s de uma permutac¸a˜o na ordem das
suba´rvores de seus no´s) tambe´m sa˜o a´rvores de Huffman para estas frequ¨eˆncias.
127
63
31
15
7
3
s
1
s
2
s
3
s
4
s
5
s
6
s
7