AD1_Estrutura de Dados_2005-2_Gabarito

Prévia do material em texto

Estrutura de Dados - 2o. per��odo de 2005
Gabarito da Primeira Avalia�
~ao �a Dista^n
ia
1. Es
rever as seguintes fun�
~oes em nota�
~ao O:
n
3
� 1; n
2
+ 2 logn; 3n
n
+ 5:2
n
; (n� 1)
n
+ n
n�1
; 302.
Resposta: n
3
� 1 = O(n
3
); n
2
+ 2 logn = O(n
2
); 3n
n
+ 5:2
n
= O(n
n
); (n� 1)
n
+ n
n�1
=
O(n
n
); 302 = 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: 
erto, pois o melhor 
aso 
orresponde ao m��nimo de passos que o algoritmo
realiza.
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 �(f).
Resposta: errado. O 
erto seria dizer que o algoritmo efetua O(f) passos qualquer
que seja a entrada, uma vez que o pior 
aso 
orresponde ao n�umero m�aximo de
passos.
. A 
omplexidade de melhor 
aso de um algoritmo para um 
erto problema �e ne
es-
sariamente maior do que qualquer limite inferior para o problema.
Resposta: errado, pois o limite inferior refere-se apenas �a 
omplexidade de pior 
aso.
3. A seque^n
ia de Fibona
i �e uma seque^n
ia de elementos f
1
; f
2
; : : : ; f
n
, de�nida do seguinte
modo: f
1
= 0; f
2
= 1; f
j
= f
j�1
+ f
j�2
. Elaborar um algoritmo, n~ao re
ursivo, para
determinar o elemento f
n
da seque^n
ia, 
uja 
omplexidade seja linear em n.
Resposta:
f [1℄ := 0;
f [2℄ := 1;
para j = 2 : : : n fa�
a f [j℄ := f [j � 1℄ + f [j � 2℄;
4. Determinar a express~ao da 
omplexidade m�edia de uma bus
a n~ao ordenada de n 
haves,
n par, em que as probabilidades de bus
a das 
haves de ordem ��mpar s~ao iguais entre si,
sendo esse valor igual ao dobro da probabilidade de qualquer 
have par. Supor, ainda,
que a probabilidade de a 
have se en
ontrar na lista �e igual a q.
Resposta: Seja p a probabilidade de uma 
have ��mpar. Temos ent~ao que a probabilidade
de uma 
have par �e p=2. Distribuindo a probabilidade q pelas n 
haves, temos que
(n=2)p+ (n=2)(p=2) = q:
Con
lu��mos que p = 4q=3n. Logo, a express~ao da 
omplexidade m�edia neste 
aso �e dada
pela express~ao:
C:M: = (1 + 3 + : : :+ n� 1)
4q
3n
+ (2 + 4 + : : :+ n)
2q
3n
+ 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 ordenada nas alo
a�
~oes
sequen
ial e en
adeada.
Resposta:
Bus
a - O(n) tanto para alo
a�
~ao sequen
ial 
omo para en
adeada.
Inser�
~ao - O(n) para alo
a�
~ao sequen
ial, O(1) para alo
a�
~ao en
adeada.
Remo�
~ao - O(n) para alo
a�
~ao sequen
ial, 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 duas listas, ordenadas, simplesmente en
adeadas 
om n�o-
abe�
a. Apresentar um
algoritmo que inter
ale as duas listas de forma que a lista resultante esteja tamb�em
ordenada.
Resposta:
pont1 := ptlista1 " :prox % ponteiro para a lista 1
pont2 := ptlista2 " :prox % ponteiro para a lista 2
ptaux := ptlista1 % a lista resultante ini
iar�a em ptlista1
enquanto pont1 6= � e pont2 6= � fa�
a
se pont1 " :info < pont2 " :info
ent~ao
ptaux " :prox := pont1
ptaux := pont1
pont1 := pont1 " :prox
sen~ao
ptaux " :prox := pont2
ptaux := pont2
pont2 := pont2 " :prox
�m-enquanto
se pont1 = �
ent~ao ptaux " :prox := pont2
sen~ao ptaux " :prox := pont1
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.