AD2_Estrutura de Dados_2011-2_Gabarito

Prévia do material em texto

Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia - Segundo Semestre de 2011 - Estrutura de Dados e Algoritmos
1) (2,0) Determinar uma a´rvore bina´ria de busca o´tima supondo as seguintes frequeˆncias de acesso: f1 = 1, f2 = 3, f3 =
2, f4 = 1, f5 = 2, f
′
0
= 2, f ′
1
= 2, f ′
2
= 1, f ′
3
= 0, f ′
4
= 1, f ′
5
= 2. Determinar as matrizes F, c, k associadas ao algoritmo e
desenhar a a´rvore o´tima obtida.
Resposta: As matrizes do algoritmo de ca´lculo da a´rvore o´tima sa˜o:
Matriz dos valores F [i, j]:
2 5 9 11 13 17
- 2 6 8 10 14
- - 1 3 5 9
- - - 0 2 6
- - - - 1 5
- - - - - 2
Matriz dos custos c[i, j]:
0 5 14 19 25 38
- 0 6 11 17 28
- - 0 3 7 16
- - - 0 2 8
- - - - 0 5
- - - - - 0
Matriz dos valores minimizantes k:
- 1 2 2 2 2
- - 2 2 2 3
- - - 3 3 5
- - - - 4 5
- - - - - 5
- - - - - -
Da u´ltima matriz acima, temos a seguinte a´rvore o´tima, de custo 38:
s
2
s
1
R
1
R
0
s
5
R
3
R
2
s
3
R
5
R
4
s
4
2) (1,5) Desenhe todos os formatos poss´ıveis de uma a´rvore AVL com cinco no´s internos.
Resposta: Se removermos todas as folhas de uma a´rvore AVL, temos que a a´rvore resultante tambe´m e´ uma a´rvore AVL.
Assim, temos as seguintes configurac¸o˜es poss´ıveis para os no´s internos:
(a) (b) (c)
(d) (e) (f)
A partir da configurac¸a˜o (a), obtemos 27 a´rvores AVL, ilustradas a seguir:
As a´rvores geradas a partir da configurac¸a˜o (b) sa˜o similares a`s ilustradas para (a), bastando trocar os filhos direito e
esquerdo da raiz de posic¸a˜o.
A partir da configurac¸a˜o (c), obtemos 9 a´rvores AVL, ilustradas a seguir:
A partir da configurac¸a˜o (d), obtemos 9 a´rvores AVL, ilustradas a seguir:
A partir da configurac¸a˜o (e), obtemos 9 a´rvores AVL, ilustradas a seguir:
As a´rvores geradas a partir da configurac¸a˜o (f) sa˜o similares a`s ilustradas para (e), bastando trocar os filhos direito e
esquerdo da raiz de posic¸a˜o.
Totalizando as a´rvores geradas pelas 6 configurac¸o˜es poss´ıveis de no´s internos, temos 90 a´rvores AVL com 5 no´s internos.
3) (1,5) Desenhe a a´rvore AVL obtida pela sequeˆncia de inserc¸o˜es das chaves 20, 19, 18, 16, 15, 17, 2, 6, nesta ordem. Mostre
com desenhos as operac¸o˜es de rotac¸a˜o necessa´rias em cada inclusa˜o.
Resposta:
In´ıcio: a´rvore vazia
Inserir 20: 20
Inserir 19:
20
19
Inserir 18:
20
19
18
 
desregulado! *
Efetuar RD
19
18 20
Inserir 16:
19
18 20
16
Inserir 15:
19
18 20
16
15
 
desregulado! * Efetuar RD
19
16 20
1815
Inserir 17:
 
desregulado! *
Efetuar RDD16
18
19
20
15
17
17
18
16 19
15 20
Inserir 2:
17
18
16 19
15 20
2
Inserir 6: desregulado! *
Efetuar RDD
17
18
16 19
6 2017
18
16 19
15 20
2
6
152
4) (1,5) Desenhar uma a´rvore B de ordem 3 e altura 3 contendo um nu´mero mı´nimo de chaves. A seguir, escolha uma
chave para ser removida, e mostre a a´rvore resultante desta remoc¸a˜o.
Resposta:
- - - 71 72 73
- - - - - 40
- - - 1 2 3 - - - 21 22 23 - - - 31 32 33- - - 11 12 13 - - - 41 42 43 - - - 61 62 63- - - 51 52 53
- - - 10 20 30 - - - 50 60 70
Removendo a chave 1:
20 30 40 50 60 70
2 3 10 11 12 13 - - - 31 32 33 - - - 71 72 73- - - 21 22 23 - - - 41 42 43 - - - 51 52 53 - - - 61 62 63
5) (2,0) Escreva verso˜es na˜o recursivas dos algoritmos de subida e descida de uma chave em uma lista de prioridades
(heap) onde a raiz e´ a chave cuja prioridade tem valor ma´ximo. Compare-os com as verso˜es recursivas.
Resposta: Seja fim uma varia´vel booleana que indica se a chave do no´ i i e´ menor que a de seu pai (procedimento
subir) ou maior que de seus filhos (procedimento descer). Ambos os algoritmos na˜o recursivos apresentados possuem
complexidade O(log n) pois, assim como os recursivos, dependem apenas da altura da a´rvore. No entanto, os algoritmos
na˜o recursivos tendem a ser executados mais rapidamente, por na˜o terem o custo extra das chamadas recursivas.
procedimento subir(i)
j := bi/2c
fim := F
enquanto j ≥ 1 e fim = F fac¸a
se T [i].chave > T [j].chave enta˜o
T [i]⇔ T [j]
i := j
j := bi/2c
sena˜o
fim := V
procedimento descer(i, n)
j := 2i
fim := F
enquanto j ≤ n e fim = F fac¸a
se j < n enta˜o
se T [j + 1].chave > T [j].chave enta˜o
j := j + 1
se T [i].chave < T [j].chave enta˜o
T [i]⇔ T [j]
i := j
j := 2i
sena˜o
fim := V
6) (1,5) Mostre os passos da construc¸a˜o de um heap contendo as seguintes chaves, colocadas nesta ordem em um vetor:
4, 70, 38, 20, 8, 35, 19, 30, 28, 18. A raiz e´ a chave cuja prioridade tem valor ma´ximo. Utilize a Soluc¸a˜o 3 vista em aula para
a construc¸a˜o do heap.
Resposta:
In´ıcio:
4
70 38
20 35 198
30 28 18
Construc¸a˜o do heap:
1) Descer 8:
4
70 38
20 35 1918
30 28 8
2) Descer 20:
4
70 38
30 35 1918
20 28 8
3) Descer 38:
4
70 38
30 35 1918
20 28 8
4) Descer 70:
4
70 38
30 35 1918
20 28 8
4) Descer 4:
Heap obtido:
70
30 38
28 35 1918
20 4 8