AP1_Estrutura de Dados_2006-1_Gabarito

Prévia do material em texto

Curso de Te
nologia em Sistemas de Computa�
~ao
Dis
iplina: Estrutura de Dados e Algoritmos
AP1 - Primeiro Semestre de 2006
Nome -
Assinatura -
Observa�
~oes:
1. Prova sem 
onsulta e sem uso de m�aquina de 
al
ular.
2. Use 
aneta para preen
her o seu nome e assinar nas folhas de quest~oes
e nas folhas de respostas.
3. Vo
e^ pode usar l�apis para responder as quest~oes.
4. Ao �nal da prova devolva as folhas de quest~oes e as de respostas.
5. Todas as respostas devem ser trans
ritas nas folhas de respostas. As
respostas nas folhas de quest~oes n~ao ser~ao 
orrigidas.
1
1. (2,5) Considere a seque^n
ia f
1
; f
2
; : : : ; f
j
dada pela seguinte f�ormula
re
orrente, onde k �e um inteiro positivo:
f
j
= j � 1; para 1 � j � k
f
j
= f
j�1
+ f
j�2
; para j > k
onde f
j
�e o j-�esimo termo da seque^n
ia.
Exemplo: se k = 4, a seque^n
ia �e 0; 1; 2; 3; 5; 8; 13; 21; 34; : : :.
Es
reva um algoritmo re
ursivo que 
al
ule f
j
. Comente sobre a 
om-
plexidade deste algoritmo.
fun�
~ao F(j)
se 1 � j � k
ent~ao retorne j � 1
sen~ao retorne F(j � 1) + F(j � 2)
A 
omplexidade desta fun�
~ao �e exponen
ial em j, pois o n�umero de
hamadas re
ursivas na �arvore de re
urs~ao 
res
e exponen
ialmente. O
n�umero de 
hamadas re
ursivas R(j) para 1 � j � k �e 0, e a partir
da�� R(j) = R(j � 1) + R(j � 2) + 2 para n � 3. A seque^n
ia dos
valores R(j) a partir do k-�esimo termo �e 0; 2; 4; 8; 14; 24; 40; : : :, que
res
e exponen
ialmente.
2. (2,5) Des
reva o algorimo de ordena�
~ao pelo m�etodo da bolha, onde a
entrada �e lista 
om n � 1 elementos. Mostre um exemplo de exe
u�
~ao
para n = 6, desenhando todos os passos intermedi�arios de tro
as de
elementos.
Entrada do algoritmo: vetor V 
om n elementos, desordenados
para i = 1 : : : n fa�
a
BOLHA := i
enquanto BOLHA > 1 fa�
a
se V [BOLHA℄ < V [BOLHA� 1℄
ent~ao AUX := V [BOLHA� 1℄
2
V [BOLHA� 1℄ := V [BOLHA℄
V [BOLHA℄ := AUX
BOLHA := BOLHA� 1
sen~ao BOLHA := 1
Um exemplo: (a bolha est�a mar
ada 
om *)
20* 13 17 11 14 18
20 13* 17 11 14 18
13* 20 17 11 14 18
13 20 17* 11 14 18
13 17* 20 11 14 18
13 17 20 11* 14 18
13 17 11* 20 14 18
13 11* 17 11 14 18
11* 13 17 20 14 18
11 13 17 20 14* 18
11 13 17 14* 20 18
11 13 14* 17 20 18
11 13 14 17 20 18*
11 13 14 17 18* 20
3. (2,5) Des
reva o algoritmo de remo�
~ao de listas simplesmente en
adeadas.
Comente sobre a 
omplexidade deste algoritmo.
No algoritmo abaixo, assuma que o n�o 
abe�
a da lista en
adeada est�a
apontado pelo ponteiro ptlista, e que x �e a 
have a ser removida. Obs:
� �e o ponteiro nulo.
Assuma que a lista �e ordenada.
ant := ptlista; pont := � % ant e pont s~ao ponteiros auxiliares
ptr := ptlista % ptr �e um ponteiro que per
orre a lista
enquanto ptr 6= � fa�
a
se ptr " :
have < x
ent~ao
ant := ptr; ptr := ptr " :prox
sen~ao
3
se ptr " :
have = x ent~ao pont := ptr
ptr := �
se pont = �
ent~ao \elemento n~ao est�a na lista"
sen~ao
ant " :prox := pont " :prox % a
ertar lista
valor � re
uperado := pont " :info
deso
upar(pont)
�m-do-algoritmo
A 
omplexidade de pior 
aso do algoritmo anterior �e O(n), pois no pior
aso pode-se ter que per
orrer toda a lista para en
ontrar o ponto exato
de inser�
~ao (ou 
on
luir que o elemento j�a existe na lista).
4. (2,5 { 0,5 ponto 
ada) De^ as de�ni�
~oes de:
� �arvore bin�aria 
ompleta
�
E aquela que apresenta a seguinte propriedade: se v �e um n�o tal
que alguma sub�arvore de v �e vazia, ent~ao v se lo
aliza ou no �ultimo
ou no pen�ultimo n��vel da �arvore.
� �arvore bin�aria 
heia
�
E aquela que apresenta a seguinte propriedade: se v �e um n�o tal
que alguma sub�arvore de v �e vazia, ent~ao v se lo
aliza no �ultimo
n��vel da �arvore.
� �arvore estritamente bin�aria
�
E aquela que apresenta a seguinte propriedade: todo n�o v possui
ou zero ou dois �lhos.
� n��vel de um n�o
�
E o n�umero de n�os no 
aminho da raiz at�e v.
� altura de um n�o
�
E o n�umero de n�os do maior 
aminho de v at�e um de seus des
en-
dentes.
4