AD1_Estrutura de Dados_2006-1_Gabarito

Prévia do material em texto

Estrutura de Dados - 1o. per��odo de 2006
Gabarito da Primeira Avalia�
~ao �a Dista^n
ia
1. Es
rever as seguintes fun�
~oes em nota�
~ao O:
n
3
+ 10; n
2
� 2 logn; 8n
n
� 5:4
n
; (n� 1)
n
+ n
n�1
; 51.
Resposta: n
3
+10 = O(n
3
); n
2
� 2 logn = O(n
2
); 8n
n
� 5:4
n
= O(n
n
); (n� 1)
n
+n
n�1
=
O(n
n
); 51 = O(1).
2. Para 
ada item abaixo, responda \
erto" ou \errado", justi�
ando:
a. Se a 
omplexidade de melhor 
aso de um algoritmo for f , ent~ao o n�umero de passos
que o algoritmo efetua, qualquer que seja a entrada, �e �(f).
Resposta: errado, pois o pior 
aso pode 
orresponder a um n�umero de passos dado
por uma fun�
~ao g que n~ao seja �(f).
b. Se a 
omplexidade de pior 
aso de um algoritmo for f , ent~ao o n�umero de passos
que o algoritmo efetua, qualquer que seja a entrada, �e O(f).
Resposta: 
erto, pois qualquer que seja o n�umero de passos, estar�a limitado superi-
ormente por f , que �e a fun�
~ao do pior 
aso.
. A 
omplexidade de pior 
aso de um algoritmo para um 
erto problema �e ne
essari-
amente maior do que qualquer limite inferior para o problema.
Resposta: Se por \maior"entende-se \estritamente maior", isto �e, que a 
omplexi-
dade de pior 
aso �e 
(f) mas n~ao �(f), onde f �e a fun�
~ao de limite inferior, ent~ao
a a�rmativa est�a errada, pois a 
omplexidade de pior 
aso pode \empatar"
om o
limite inferior.
Mas se por \maior" entende-se apenas que a a 
omplexidade de pior 
aso �e 
(f),
ent~ao a a�rmativa est�a 
erta, porque a de�ni�
~ao de limite inferior diz justamente
que a 
omplexidade de pior 
aso de qualquer algoritmo para o problema �e 
(f).
3. Seja f
1
; f
2
; : : : ; f
n
uma seque^n
ia de elementos de�nida do seguinte modo: f
1
= 0; f
2
=
1; f
3
= 1; f
j
= f
j�1
� f
j�2
+ f
j�3
para j > 3. Elabore um algoritmo n~ao re
ursivo para
determinar o elemento f
n
da seque^n
ia. Cal
ule sua 
omplexidade em fun�
~ao de n.
Resposta:
f [1℄ := 0;
f [2℄ := 1;
f [3℄ := 1; para j = 4 : : : n fa�
a f [j℄ := f [j � 1℄� f [j � 2℄ + f [j � 3℄;
A 
omplexidade do algoritmo a
ima �e O(n).
4. Determinar a express~ao da 
omplexidade m�edia de uma bus
a n~ao ordenada de n 
haves,
em que a probabilidade de bus
a da 
have i �e o dobro da probabilidade de bus
a da 
have
i�1, para i = 2; :::n. Supor, ainda, que a probabilidade de a 
have pro
urada se en
ontrar
na lista �e igual a q.
Resposta: Seja p a probabilidade de bus
a da 
have 1. Temos ent~ao que p + 2p + 4p +
� � �+ 2
n�1
p = q. Colo
ando p em evide^n
ia e utilizando a f�ormula para soma dos termos
de uma P.G., temos p = q=(2
n
� 1). Logo, a express~ao da 
omplexidade m�edia neste 
aso
�e dada pela express~ao:
C:M: = (1:1 + 2:2 + 3:4 + 4:8 + 5:16 + � � �+ n:2
n�1
)
q
2
n
� 1
+ n(1� q)
onde a par
ela �nal n(1 � q) refere-se ao 
aso em que a informa�
~ao pro
urada n~ao se
en
ontra na lista.
5. Comparar algoritmos de bus
a, inser�
~ao e remo�
~ao em uma lista n~ao ordenada nas
alo
a�
~oes sequen
ial e en
adeada.
Resposta:
Bus
a - O(n) para alo
a�
~ao sequen
ial, O(n) para en
adeada.
Inser�
~ao - O(1) para alo
a�
~ao sequen
ial (inserir no �nal), O(1) para alo
a�
~ao en
adeada.
Remo�
~ao - O(1) para alo
a�
~ao sequen
ial (tomar o �ultimo elemento e 
olo
�a-lo no "bu-
ra
o"deixado pelo elemento removido), O(1) para alo
a�
~ao en
adeada.
Obs: na pr�ati
a, a inser�
~ao e a remo�
~ao exigem uma bus
a pr�evia. Portanto, na pr�ati
a,
todos os algoritmos a
ima se tornam O(n).
6. Sejam L
1
e L
2
duas listas ordenadas, simplesmente en
adeadas 
om n�o-
abe�
a. Apresen-
tar um algoritmo que 
onstrua uma lista ordenada 
ontendo os elementos 
omuns a L
1
e
L
2
. (Supor que tanto L
1
omo L
2
n~ao 
onte^m elementos repetidos.)
Resposta:
pont1 := ptlista1 " :prox % ponteiro para a lista 1
pont2 := ptlista2 " :prox % ponteiro para a lista 2
ptaux := ptnovo % a lista resultante ini
iar�a em ptnovo
enquanto pont1 6= � e pont2 6= � fa�
a
se pont1 " :info < pont2 " :info
ent~ao pont1 := pont1 " :prox
sen~ao
se pont2 " :info < pont1 " :info
ent~ao pont2 := pont2 " :prox
sen~ao % s~ao elementos iguais !
o
upar(pt);
pt " :info := pont1 " :info
pt " :prox := �
ptaux " :prox := pt
ptaux := pt %ptaux aponta para o �ultimo n�o
pont1 := pont1 " :prox
pont2 := pont2 " :prox
�m-enquanto
7. Des
reva algoritmos de inser�
~ao e remo�
~ao em pilhas e �las, implementadas utilizando
alo
a�
~ao en
adeada.
Resposta:
Inser�
~ao na pilha:
o
upar(pt)
pt " :info := novo� valor
pt " :prox := topo
topo := pt
Remo�
~ao da pilha:
se topo 6= � ent~ao
pt := topo
topo := topo " :prox
valor � re
uperado := pt " :info
deso
upar(pt)
sen~ao underflow
Inser�
~ao na �la:
o
upar(pt) pt " :info := novo� valor
pt " :prox := �
se fim 6= � ent~ao
fim " :prox := pt
sen~ao ini
io := pt
fim := pt
Remo�
~ao da �la:
se ini
io 6= � ent~ao
pt := ini
io
ini
io := ini
io " :prox
se ini
io = � ent~ao fim := �
valor � re
uperado := pt " :info
deso
upar(pt)
sen~ao underflow
8. Seja 1; 2; : : : ; n uma seque^n
ia de elementos que ser~ao inseridos e posteriormente retirados
de uma pilha P uma vez 
ada. A ordem de in
lus~ao dos elementos na pilha �e 1; 2; : : : ; n,
enquanto a de remo�
~ao depende das opera�
~oes realizadas. Por exemplo, 
om n = 3, a
seque^n
ia de opera�
~oes \in
luir em P , in
luir em P , retirar de P , in
luir em P , retirar de
P , retirar de P" produzir�a a permuta�
~ao 2; 3; 1 a partir da entrada 1; 2; 3. Representando
por I; R, respe
tivamente, as opera�
~oes de inser�
~ao e remo�
~ao da pilha, a permuta�
~ao
2; 3; 1 pode ser denotada por IIRIRR. De um modo geral, uma permuta�
~ao �e 
hamada
admiss��vel quando ela puder ser obtida mediante uma su
ess~ao de in
lus~oes e remo�
~oes
em uma pilha a partir da permuta�
~ao 1; 2; : : : ; n. Assim, por exemplo, a permuta�
~ao
2; 3; 1 �e admiss��vel. Pede-se:
(i) Determinar a permuta�
~ao 
orrespondente a IIIRRIRR, n = 4.
Resposta: 3; 2; 4; 1
(ii) De^ um exemplo de permuta�
~ao n~ao admiss��vel.
Resposta: 4; 1; 2; 3 (para n = 4). Motivo: ap�os remover o 4, o 1 se en
ontra no fundo
da pilha e n~ao pode ser o pr�oximo a ser removido.