AD2_Estrutura de Dados_2013-1_Gabarito

Prévia do material em texto

Estrutura de Dados - 1o. per´ıodo de 2013
Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia
Todas as questo˜es valem 1,0 ponto.
1. Determinar a a´rvore bina´ria de busca o´tima relativa a`s seguintes frequeˆncias: f1 = 1, f2 =
1, f3 = 1, f
′
0 = 0, f
′
1 = 0, f
′
2 = 0, f
′
3 = 0. Determine as matrizes F , c e k associadas ao
algoritmo, que esta˜o descritas no livro-texto.
Resposta: As matrizes do algoritmo de ca´lculo da a´rvore o´tima sa˜o:
Matriz dos custos c[i, j]:
0 1 3 5
- 0 1 3
- - 0 1
- - - 0
Matriz dos valores F [i, j]:
0 1 2 3
- 0 1 2
- - 0 1
- - - 0
Matriz dos valores minimizantes k:
- 1 1 (2) 2
- - 2 2 (3)
- - - 3
- - - -
Da u´ltima matriz acima obtemos a a´rvore o´tima de raiz s2, filho esquerdo s1 e direito s3.
2. Ainda com relac¸a˜o a`s a´rvores bina´rias de busca o´timas, determine condic¸o˜es suficientes
sobre as frequeˆncias f1, . . . , fn e f
′
0, f
′
1, . . . , f
′
n
, para que a a´rvore o´tima resultante tenha
a seguinte caracter´ıstica: si+1 e´ filho direito de si, para i = 1, . . . , n− 1.
Resposta: fn = 1, fn−1 = 2, fi = fi+1 + fi+2 +1, 1 ≤ i ≤ n− 2, e f
′
0 = f
′
1 = · · · = f
′
n
= 0.
3. Desenhe uma a´rvore AVL de altura 4 que seja minimal, isto e´, tal que a exclusa˜o de
qualquer de seus no´s provoca a diminuic¸a˜o de sua altura.
Resposta:
30
20
10
5
25
45
40
4. Desenhe uma a´rvore AVL de altura 4 que seja maximal, isto e´, tal que a inclusa˜o de
qualquer no´ provoca o aumento de sua altura.
Resposta:
22 285 12
10 25 40
30
20 45
60
4235 6855
5. Desenhe uma a´rvore B de ordem d = 2 com treˆs n´ıveis. (Os valores nos no´s ficam a` sua
escolha.) A seguir, escolha uma nova chave de forma que a sua inserc¸a˜o exija uma cisa˜o
propaga´vel. Desenhe a a´rvore B resultante apo´s a inserc¸a˜o.
Resposta:
7
8
9
10
22
23
25
30
40
52
56
58
65
70
85
90
6
12
20
27
60
80
50
15
17
19
1
2
3
Inserindo a chave 11, temos uma cisa˜o propaga´vel, que resulta na seguinte a´rvore B:
7
8
22
23
25
52
56
58
65
70
85
90
6
9
60
80
12
50
15
17
19
1
2
3
30
40
10
11
20
27
6. Execute o me´todo de ordenac¸a˜o por heap (“heapsort”), aplicando-o a`s seguintes priori-
dades (nesta ordem): 18, 25, 41, 34, 14, 10, 52, 50, 48. Desenhe as configurac¸o˜es sucessivas
da a´rvore durante o processo de ordenac¸a˜o.
Resposta:
In´ıcio:
14
25
18
5210
41
4850
34
Construc¸a˜o do heap: (comando arranjar(n))
Descer 34:
14
25
18
5210
41
4834
50
Descer 41:
14
25
18
4110
52
4834
50
Descer 25:
14
50
18
4110
52
2534
48
Descer 18:
Heap
obtido:
14
50
52
1810
41
2534
48
m := 9
trocar(TB[1],TB[9]) 14
50
25
1810
41
5234
48
m := 8
descer(1,8) 14
48
50
1810
41
5225
34
trocar(TB[1],TB[8])
14
48
25
1810
41
5250
34
m := 7
descer(1,7) 14
34
48
1810
41
5250
25
trocar(TB[1],TB[7])
14
34
18
4810
41
5250
25
m := 6
descer(1,6) 14
34
41
4810
18
5250
25
trocar(TB[1],TB[6])
14
34
10
4841
18
5250
25
m := 5
descer(1,5) 14
25
34
4841
18
5250
10
trocar(TB[1],TB[5])
34
25
14
4841
18
5250
10
m := 4
descer(1,4) 34
14
25
4841
18
5250
10
trocar(TB[1],TB[4])
34
14
10
4841
18
5250
25
m := 3
descer(1,3) 34
14
18
4841
10
5250
25
trocar(TB[1],TB[3])
34
14
10
4841
18
5250
25
m := 2
descer(1,2) 34
10
14
4841
18
5250
25
trocar(TB[1],TB[2])
34
14
10
4841
18
5250
25
m := 1
descer(1,1) 34
14
10
4841
18
5250
25
7. Seja T uma tabela de dispersa˜o com 5 posic¸o˜es implementada por encadeamento exterior.
A func¸a˜o de dispersa˜o e´ h(x) = x mod 5. Desenhe a tabela apo´s a inclusa˜o das chaves
43,89,56,23,14,22,10,20.
Resposta:
0
1
2
3
T
10 20
56
22
l
l
l
43 23 l
4 89 14 l
8. Escreva um algoritmo que, dadas duas cadeias de caracteresX e Y , verifica se a cadeiaX e´
prefixo ou sufixo ou ambas as coisas da cadeia Y . Exemplo: se X = aba e Y = abacataba,
enta˜o X e´ prefixo e sufixo de Y simultaneamente; ao passo que se X = taba, enta˜o neste
caso X e´ apenas sufixo de Y .
Resposta: Sejam m o comprimento de X e n o comprimento de Y .
i := 1
pre := V
suf := V
enquanto i ≤ m fac¸a
se X[i] = Y [i] enta˜o
i := i+ 1
sena˜o
i := m+ 1
pre := F
se pre = V enta˜o imprimir (“X e´ prefixo de Y”)
sena˜o imprimir (“X na˜o e´ prefixo de Y”)
i := 1
j := n−m+ 1
enquanto j ≤ n fac¸a
se X[i] = Y [j] enta˜o
i := i+ 1
j := j + 1
sena˜o
j := n+ 1
suf := F
se suf = V enta˜o imprimir (“X e´ sufixo de Y”)
sena˜o imprimir (“X na˜o e´ sufixo de Y”)
9. Construa uma a´rvore de Huffman para as frequeˆncias satisfazendo: fi = 1 se i e´ par,
fi = 2 se i e´ ı´mpar. O ı´ndice i varia de 1 a 10.
Resposta:
15
s10s9
3
s2 s4
2
s8s6
2
4
s1 s3
4
s7s5
4
8 7
10. Responda: como e´ a a´rvore de Huffman relativa a n frequeˆncias iguais? (Suponha que n
e´ da forma n = 2k, isto e´, n e´ uma poteˆncia de 2.)
Resposta: E´ uma a´rvore cheia de altura k + 1. Inicialmente, temos 2k a´rvores com um
u´nico no´ (altura 1), de mesmo valor. O algoritmo vai unindo estas a´rvores duas a duas,
ate´ que todas fac¸am parte de uma a´rvore cheia com 3 no´s (altura 2). Como n e´ poteˆncia
de 2, o algoritmo vai sempre unindo sempre duas a´rvores cheias em uma u´nica a´rvore
cheia, e somente une duas a´rvores de altura x quando na˜o houver mais nenhuma a´rvore
de altura menor que x. Ao final do algoritmo, duas a´rvores cheias de altura k sa˜o unidas
em uma a´rvore cheia de altura k + 1.