Baixe o app para aproveitar ainda mais
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.
Compartilhar