AD2_Estrutura de Dados_2007-2_Gabarito

Prévia do material em texto

Estrutura de Dados - 2o. per´ıodo de 2007
Gabarito da Segunda Avaliac¸a˜o a` Distaˆncia
1. (2,0) Seja T uma a´rvore bina´ria, e seja f(v) o nu´mero de no´s pertencentes a` suba´rvore
de T cuja raiz e´ v. Descreva um algoritmo que percorra os no´s de T em ordem na˜o
decrescente de seus valores f(v).
Resposta: Seja n o total de no´s da a´rvore. O procedimento totalNos(pt) calcula f(pt).
Assim, na chamada inicial f(ptraiz) := totalNos(ptraiz), os valores f(v) sa˜o calculados
para todo no´ v pertencente a` T . Em seguida, o procedimento listarNos(ptraiz, cont) e´
utilizado para listar os no´s de T em ordem na˜o decrescente de seus valores f(v).
f(ptraiz) := totalNos(ptraiz)
para cont := 1 ate´ n fac¸a
listarNos(ptraiz, cont)
procedimento totalNos(pt)
filho-esq := pt ↑ .esq; f(filho-esq) := 0
filho-dir := pt ↑ .dir; f(filho-dir) := 0
se filho-esq 6= λ enta˜o
f(filho-esq) := totalNos(filho-esq)
se filho-dir 6= λ enta˜o
f(filho-dir) := totalNos(filho-dir)
retornar (f(filho-esq) + f(filho-dir) + 1)
procedimento listarNos(pt, cont)
se pt ↑ .esq 6= λ enta˜o
listarNos(pt ↑ .esq, cont)
se pt ↑ .dir 6= λ enta˜o
listarNos(pt ↑ .dir, cont)
se (f(pt) = cont) enta˜o
imprimir(pt)
2. (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. (2,0) Determinar a a´rvore bina´ria de custo mı´nimo relativa a`s seguintes frequ¨eˆncias: f1 =
2, f2 = 0, f3 = 3, f
′
0
= 1, f ′
1
= 2, f ′
2
= 1, f ′
3
= 4.
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 a´rvore o´tima com raiz s3, sendo s1 filho esquerdo de
s3 e s2 filho direito de s1.
4. (2.0) Assista a`s aulas sobre a´rvores B. 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 e 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. (2,0) Assista a`s aulas sobre tabelas de espalhamento e explique 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.