AD2_Estrutura de Dados_2009-2_Gabarito

Prévia do material em texto

Estrutura de Dados - 2o. per´ıodo de 2009
Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia
Todas as questo˜es valem um ponto cada.
1. Prove ou deˆ contra-exemplo: Uma a´rvore bina´ria pode ser constru´ıda, de forma u´nica, a
partir dos seus percursos em pre´-ordem e po´s-ordem.
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 pre´-ordem e´ AB e o percurso em po´s-ordem
e´ BA. No entanto, elas sa˜o distintas.
2. Determinar a a´rvore bina´ria de custo mı´nimo relativa a`s seguintes frequeˆncias: f1 =
1, f2 = 3, f3 = 2, f4 = 1, f
′
0
= 2, f ′
1
= 2, f ′
2
= 1, f ′
3
= 0, f ′
4
= 3.
Resposta: Para o conjunto de frequ¨eˆncias abaixo,
i 0 1 2 3 4
fi - 1 3 2 1
f ′
i
2 2 1 0 3
as matrizes do algoritmo de ca´lculo da a´rvore o´tima sa˜o:
Matriz dos valores F [i, j]:
2 5 9 11 15
- 2 6 8 12
- - 1 3 7
- - - 0 4
- - - - 3
Matriz dos custos c[i, j]:
0 5 14 19 30
- 0 6 11 22
- - 0 3 10
- - - 0 4
- - - - 0
Matriz dos valores minimizantes k:
- 1 2 2 2
- - 2 2 2(3)
- - - 3 4
- - - - 4
- - - - -
Da matriz k, temos a seguinte a´rvore o´tima, de custo 30:
s
2
s
1
s
4
R
4
R
1
R
0
s
3
R
3
R
2
3. Construa a a´rvore AVL resultante da inclusa˜o (na ordem dada!) dos no´s com os seguintes
valores: 10,4,15,8,7,6. A a´rvore AVL encontra-se inicialmente vazia.
Resposta:
In´ıcio: a´rvore vazia
Inserir 10: 10
Inserir 4:
10
4
Inserir 15:
10
4 15
Inserir 8:
10
4 15
8
Inserir 7:
10
4 15
8
7
 
desregulado! * Efetuar RDE
10
7 15
84
Inserir 6:
 
desregulado! *
Efetuar RD
8
10
7 15
4
6
6
7
4 10
8 15
4. Desenhe uma a´rvore B de ordem 2 e altura treˆs que contenha o maior nu´mero de chaves
poss´ıvel. A seguir, defina uma nova chave para inserir, e desenhe a a´rvore B resultante
da inserc¸a˜o desta chave.
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. Desenhe uma a´rvore B de ordem 2 e altura treˆs que contenha o menor nu´mero de chaves
poss´ıvel. A seguir, escolha uma chave qualquer para ser removida, e desenhe a a´rvore B
resultante da remoc¸a˜o desta chave.
Resposta:
20
21
22
26
27
31
32
25
30
10
15
1
2
11
12
16
17
Ao removermos a chave 2, obtemos a seguinte a´rvore B:
21
22
26
27
31
32
1
10
11
12
16
17
15
20
25
30
6. Determine o heap obtido pela aplicac¸a˜o do algoritmo de construc¸a˜o a`s seguintes priori-
dades: 18, 25, 41, 34, 14, 10, 52, 50, 48.
Resposta: Utilizando a soluc¸a˜o 3 para construc¸a˜o de heaps, obtemos o seguinte heap:
14
50
52
1810
41
2534
48
7. Assista a`s aulas sobre tabelas de espalhamento e fac¸a uma dissertac¸a˜o resumida sobre
como funcionam os me´todos de tratamento de coliso˜es abordados.
Resposta:
O tratamento de coliso˜es por encadeamento exterior consiste em manter m listas en-
cadeadas, uma para cada poss´ıvel enderec¸o-base. Um campo para o encadeamento deve
ser acrescentado a cada no´. Os no´s correspondentes aos enderec¸os-base sa˜o apenas no´s-
cabec¸a para essas listas. Para buscar uma chave x na tabela T , calcula-se h(x) = x mod
m e procura-se x na lista encadeada correspondente ao enderec¸o-base h(x). A inclusa˜o
de uma nova chave x e´ feita no final da lista encadeada correspondente ao enderec¸o-base
h(x).
No modelo de encadeamento interior heterogeˆneo, as coliso˜es sa˜o resolvidas mediante o
emprego de listas encadeadas que compartilham o mesmo espac¸o de memo´ria que a tabela
de dispersa˜o T , que fica dividida em duas zonas: uma de enderec¸os-base, de tamanho p,
e outra reservada aos sinoˆnimos, de tamanho s. Sendo m o tamanho total de T , temos
que p + s = m. Os valores p e s sa˜o fixos. Assim sendo, a func¸a˜o de dispersa˜o deve
obter enderec¸os-base na faixa [0, p − 1] apenas. Neste caso, α = n/m ≤ 1. A estrutura
da tabela e´ a mesma que no caso do encadeamento exterior (dois campos teˆm presenc¸a
obrigato´ria em cada no´).
O modelo de encadeamento interior homogeˆneo consiste em na˜o diferenciar as duas zonas
da tabela. Ou seja, qualquer enderec¸o da tabela pode ser de base ou de colisa˜o. Esta
te´cnica, entretanto, produz o efeito indesejado de provocar coliso˜es secunda´rias, isto e´,
aquelas provenientes da coincideˆncia de enderec¸os para chaves que na˜o sa˜o sinoˆnimas.
8. Deˆ exemplo de duas cadeias X e Y , com 8 e 5 caracteres respectivamente, que leve o
algoritmo de forc¸a bruta para casamento de cadeias a realizar o maior nu´mero poss´ıvel
de comparac¸o˜es entre caracteres. Observac¸a˜o: o algoritmo procura determinar se Y e´
subcadeia de X.
Resposta:
X = aaaaaaaa e Y = aaaab
Nu´mero de comparac¸o˜es = m(n−m+ 1) = 5(8− 5 + 1) = 20.
9. Deˆ exemplo de duas cadeias X e Y , com 8 e 5 caracteres respectivamente, que leve o
algoritmo de forc¸a bruta para casamento de cadeias a realizar o menor nu´mero poss´ıvel
de comparac¸o˜es entre caracteres. Observac¸a˜o: o algoritmo procura determinar se Y e´
subcadeia de X.
Resposta:
X = aaaaaaaa e Y = aaaaa
Nu´mero de comparac¸o˜es = m = 5.
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.) Justifique sua resposta.
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.