AD2_Estrutura de Dados_2012-1_Gabarito

Prévia do material em texto

Estrutura de Dados - 1o. per´ıodo de 2012
Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia
1. (1,0) Falso ou verdadeiro? (Justifique.) O fator de carga de qualquer tabela de dispersa˜o
e´ no ma´ximo igual a 1.
Resposta: Falso. O fator de carga e´ dado pelo nu´mero de chaves dividido pelo nu´mero
de compartimentos da tabela. Logo, se o nu´mero de chaves for maior que o de comparti-
mentos, o fator de carga sera´ maior que 1.
2. (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 sequeˆncia de chaves
que corresponde ao percurso em PRE´-ORDEM desta a´rvore.
Resposta: O percurso em pre´-ordem desta a´rvore e´: 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15.
8
6
4
1 3
2
5 7
14
12
9 11
10
13 15
3. (1,5) Suponha que voceˆ deseja remover um no´ de uma a´rvore bina´ria de busca. Apo´s
remoˆve-lo, 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 um no´ qualquer e reestruturando-
a.)
Resposta: Se o no´ removido for uma folha, na˜o ha´ necessidade de reestruturac¸a˜o, pois a
a´rvore resultante continuara´ sendo bina´ria de busca. Em caso contra´rio (remoc¸a˜o de um
no´ interno), podemos:
(a) substituir o no´ removido pelo no´ mais a` direita (de maior valor) de sua suba´rvore
esquerda (se este no´ for uma folha), ou
(b) substituir o no´ removido pelo no´ mais a` esquerda (de menor valor) de sua suba´rvore
direita (se este no´ for uma folha).
No exemplo da a´rvore da questa˜o anterior, ao removermos o no´ 12, por exemplo, obter´ıamos
uma das duas a´rvores abaixo, dependendo da estrate´gia que adota´ssemos ((a) ou (b)).
8
6
4
1 3
2
5 7
14
13
9 11
10
15
8
6
4
1 3
2
5 7
14
11
9
10
13 15
(a) (b)
Caso a a´rvore bina´ria de busca na˜o seja cheia, e tanto o no´ de maior valor da suba´rvore
esquerda do no´ removido quanto o de menor valor da suba´rvore direita na˜o sejam fol-
has, enta˜o basta selecionar um destes no´s para substituir o no´ removido, e “promover” a
suba´rvore deste no´ para sua antiga posic¸a˜o, como no exemplo da figura a seguir.
11
6
5
4
1 3
2 14
12
10
1513
8
6
4
1 3
2
5
14
12
10
15
remoção do nó 8
11 13
4. (1,5) Seja T uma a´rvore bina´ria de custo mı´nimo relativa a`s frequeˆncias f1, f2, f3, f
′
0
, f ′
1
, f ′
2
, f ′
3
.
Escreva valores para estas frequeˆ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
5. (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
6. (1,5) Desenhe uma a´rvore B de ordem d = 2 com treˆs n´ıveis e o maior nu´mero poss´ıvel
de chaves. (Os valores das chaves ficam a` sua escolha.)
Resposta:
5
10
15
20
1 2 3 4
6 7 8 9
11 12 13 14
16 17 18 19
101 102 103 104
106 107 108 109
111 112 113 114
116 117 118 119
121 122 123 124
21 22 23 24
26 27 28 29
31 32 33 34
36 37 38 39
41 42 43 44
46 47 48 49
30
35
40
45
51 52 53 54
56 57 58 59
61 62 63 64
66 67 68 69
71 72 73 74
55
60
65
70
76 77 78 79
81 82 83 84
86 87 88 89
91 92 93 94
96 97 98 99
80
85
90
95
105
110
115
120
25
50
75
100
7. (1,5) Construa um heap com as seguintes prioridades: 18, 25, 41, 34, 14, 10, 52, 50, 48. A
seguir, redesenhe o heap apo´s a remoc¸a˜o de sua raiz.
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
Apo´s a remoc¸a˜o da raiz:
14
48
50
1810
41
25
34