AD2_Estrutura de Dados_2010-2_Gabarito

Prévia do material em texto

Estrutura de Dados - 2o. per´ıodo de 2010
Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia
1. Valor (2,0):
Seja T uma a´rvore bina´ria com 8 no´s, e represente por f(vi) o nu´mero de
no´s pertencentes a` suba´rvore de T , com raiz vi. Suponha que v1, v2, . . . , v8
seja uma ordenac¸a˜o dos seus no´s, segundo valores na˜o decrescentes de
f(vi). Desenhe uma a´rvore T que atenda a`s condic¸o˜es acima, assinalando,
em cada no´, o seu ro´tulo vi correspondente.
Resposta: Para a a´rvore T abaixo, temos f(v1) = f(v2) = f(v3) = f(v4) =
1, f(v5) = 2, f(v6) = 3, f(v7) = 5 e f(v8) = 8.
v3
v2v1
v4
v5
v6
v7
v8
2. Valor (2,0):
Prove ou deˆ contra-exemplo: Uma a´rvore bina´ria pode ser constru´ıda, de
forma u´nica, a partir dos seus percursos em po´s-ordem e em n´ıvel.
Resposta: A afirmac¸a˜o e´ falsa. Considere duas a´rvores bina´rias T1 e T2,
onde cada uma delas conte´m apenas dois no´s A e B de forma que:
- em T1, B e´ filho esquerdo de A;
- em T2, B e´ filho direito de A.
Para ambas as a´rvores acima, o percurso em po´s-ordem e´ BA e o percurso
em n´ıvel e´ AB. No entanto, elas sa˜o distintas.
3. Valor (2,0):
Determinar a a´rvore bina´ria de custo mı´nimo relativa a`s seguintes fre-
queˆncias: f1 = 2, f2 = 0, f3 = 3, f
′
0 = 1, f
′
1 = 2, f
′
2 = 1, f
′
3 = 4. Explicitar
todos os ca´lculos envolvidos, bem como as matrizes obtidas nos ca´lculos.
Desenhar a a´rvore o´tima.
Resposta:
As matrizes do algoritmo de ca´lculo da a´rvore o´tima sa˜o:
Matriz dos custos c[i, j]:
0 5 9 22
- 0 3 13
- - 0 8
- - - 0
Matriz dos valores F [i, j]:
1 5 6 13
- 2 3 10
- - 1 8
- - - 4
Matriz dos valores minimizantes k:
- 1 1 3
- - 2 3
- - - 3
- - - -
Da u´ltima matriz acima, obtemos a seguinte a´rvore o´tima:
s2
s1
s3
4. Valor (2,0):
Desenhe uma a´rvore B de ordem 2 e altura 3 contendo o maior nu´mero
poss´ıvel de chaves. A seguir, efetue a inserc¸a˜o de uma nova chave, de forma
a provocar a ocorreˆncia de uma cisa˜o. Desenhe a a´rvore B resultante da
inserc¸a˜o.
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
Ao inserirmos a chave 125, obtemos a seguinte a´rvore B:
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
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
124 125
120
123
100
115
25
50
75
5. Valor (2,0):
Seja a sequeˆncia de chaves
80, 60, 75, 55, 50, 65, 30, 40, 20
Esta sequeˆncia corresponde a uma heap ? Em caso positivo, desenhar
a a´rvore bina´ria correspondente. Em seguida, efetuar a inclusa˜o de uma
nova chave 63, explicitando os passos efetuados pelo algoritmo de inclusa˜o,
atrave´s dos desenhos das a´rvores. Finalmente, efetuar a remoc¸a˜o da chave
80, no heap obtido apo´s a inclusa˜o anterior. De forma similar, explicite
os passos efetuados pelo algoritmo de remoc¸a˜o, atrave´s dos desenhos das
a´rvores.
Resposta: A sequeˆncia de chaves corresponde ao seguinte heap:
3065
75
80
50
60
40 20
55
Inclusa˜o da chave 63:
T[10]=63
n=10 3065
75
80
50
60
40 20
55
63
subir(10):
trocar(T[10],T[5])
3065
75
80
63
60
40 20
55
50
trocar(T[5],T[2])
Heap obtido:
3065
75
80
60
63
40 20
55
50
Remoc¸a˜o da chave 80:
T[1]=T[10]
n=9 3065
75
50
60
63
40 20
55
descer(1,9):
trocar(T[1],T[3])
3065
50
75
60
63
40 20
55
trocar(T[3],T[6])
Heap obtido:
3050
65
75
60
63
40 20
55