advertisement

2010exame1a

60 %
40 %
advertisement
Information about 2010exame1a
Education
aed

Published on March 8, 2014

Author: e-for-all

Source: slideshare.net

advertisement

AED - Algoritmos e Estruturas de Dados 2009/2010 - 2o Semestre 1o Exame, 23 Junho 2010, 13:00h Dura¸˜o: 3 horas ca Prova escrita, individual e sem consulta ´ NUMERO: NOME: PARTE I - Quest˜es de Escolha M´ltipla o u Preencha as respostas na tabela (usando apenas letras mai´sculas). Se nenhuma op¸˜o servir, escreva NENHUMA. u ca Se pretender alterar a sua resposta, risque e escreva ao lado a sua nova op¸˜o. Todas as quest˜es de escolha m´ltipla ca o u valem 0.5 valores. As quest˜es de escolha m´ltipla n˜o respondidas s˜o cotadas com 0 valores, mas por cada o u a a resposta errada s˜o descontados 0.5/4 valores. a Utilize a mesma tabela para indicar se respondeu ou n˜o a cada uma das perguntas de desenvolvimento. Para tal fa¸a a c uma marca para cada problema que resolveu e entregou. Quest˜o a Resposta 1 2 3 4 5 6 7 8 9 1. Considere o algoritmo quick-find aplicado ao problema da Conectividade. Admita que o algoritmo ´ implementado da seguinte forma: para o par de entrada a-b, todos os elementos da parti¸˜o de e ca b s˜o alterados para a parti¸˜o de a. Considere que aplica este algoritmo a um problema com a ca 10 objectos, identificados por n´meros inteiros entre 0 e 9, com a seguinte sequˆncia de entrada: u e 1-2, 3-4, 7-6, 2-6, 1-6, 4-9, 5-8 Considerando a situa¸˜o neste momento, se na entrada aparecer agora o par 2 − 5, indique qual ca o n´mero de elementos que mudam de parti¸˜o: u ca A. 1 B. 2 C. 4 D. 6 2. Indique qual das afirma¸˜es seguintes ´ verdadeira: co e A. C. lg4 ) √ N ∈ O(lg3 N 2 N lg N ∈ O(lg N ) N √2 N 2 ∈ O(N 2 lg N ) lg √ lg 3 N ∈ O( 3 lg N ) B. D. 3. Considere a seguinte tabela (1a linha) sobre a qual s˜o listados alguns passos executados por um a algoritmo de ordena¸˜o (restantes linhas). Qual ´ o algoritmo usado? ca e 3 10 7 11 6 1 4 9 5 2 12 8 1 1 1 1 1 1 3 2 2 2 2 2 10 3 3 3 3 3 7 10 4 4 4 4 11 7 10 5 5 5 6 11 7 10 6 6 2 6 11 7 10 7 4 4 6 11 7 10 9 5 5 6 11 8 5 9 8 8 8 11 8 8 9 9 9 9 12 12 12 12 12 12 A. Inser¸˜o ca B. Shellsort (h=4, 2, 1) C. Bubble D. Quicksort 4. Considere o seguinte acervo (“heap”), no qual a prioridade ´ mais elevada quanto maior for o valor. e 35 25 33 18 23 28 30 3 10 8 20 5 15 11 No total quantas trocas entre elementos da tabela s˜o efectuadas nas rotinas de FixUp() e a FixDown() durante a execu¸˜o da seguinte sequˆncia de opera¸˜es (Nota: ap´s cada opera¸˜o ´ ca e co o ca e sempre necess´rio repˆr a condi¸˜o de acervo; conte apenas as trocas feitas no contexto das rotinas a o ca indicadas): (i) Inserir no acervo o valor 34; (ii) Baixar a prioridade do valor 25 para 3; (iii) Retirar o elemento mais priorit´rio. a A. 5 B. 6 C. 8 1 D. 9

5. Suponha que os seguintes n´meros s˜o introduzidas numa tabela de dispers˜o (”hash table”): u a a 14735, 28342, 53735, 35, 1300, 2342, 31753, 41735, 28342, 20035, 18645, 19735. Assuma que a fun¸˜o de dispers˜o (para indexa¸˜o na tabela) ´ a seguinte: f (x) = x mod 1000 (ou seja, ca a ca e o resto da divis˜o por 1000). Assuma que n´meros repetidos n˜o s˜o armazenados, quando tal ´ a u a a e verificado, e que colis˜es s˜o resolvidas por lista, com inser¸˜o no final. Qual das afirma¸˜es ´ o a ca co e verdadeira? (contabilize compara¸˜es apenas entre n´meros) co u A. C. Ocorrem 7 colis˜es e 9 compara¸˜es. o co Ocorrem 10 colis˜es e 10 compara¸˜es. o co B. D. Ocorrem 6 colis˜es e 9 compara¸˜es. o co Ocorrem 6 colis˜es e 8 compara¸˜es. o co 6. Considere o grafo indicado em baixo ` esquerda e assuma que o mesmo n˜o ´ direccionado mas ´ a a e e ponderado, como se indica do lado direito do grafo. Assumindo que aplica o algoritmo de Prim tomando o v´rtice D como ponto de partida, indique qual das afirma¸˜es ´ falsa. e co e D I E H J A C F B G A. B. C. D. O A A A A↔D, A↔B, A↔C, B↔C, E↔I C↔H, H↔I, H↔J, B↔F, E↔H C↔F D↔E, G↔J C↔E I↔J F↔H F↔G 2 3 4 5 6 7 8 9 custo da MST que se obt´m ´ 33 e tem 9 arestas. e e aresta que une os v´rtices D e E ´ a quinta a entrar na MST. e e aresta que une os v´rtices C e F ´ a quarta a entrar na MST. e e aresta que une os v´rtices H e I ´ a oitava a entrar na MST. e e PARTE II - Quest˜es de Desenvolvimento o Responda `s quest˜es de desenvolvimento em folhas de exame devidamente identificadas com nome e n´mero. a o u Responda a cada quest˜o numa folha separada. a [4.0] 7. A sua empresa foi contratada para resolver um problema aparentemente complicado que envolve um determinado cliente. Como teve AED no seu curso, vocˆ apercebe-se de que o problema pode e ser descrito como um grafo e que a solu¸˜o passa por determinar se h´ ou n˜o algum ciclo nesse ca a a grafo. Reconhecendo que esta ´ uma excelente oportunidade para mostrar as suas capacidades e e conhecimentos vocˆ oferece-se de imediato para realizar esta tarefa. e [2.5] a) Escreva o c´digo de uma fun¸˜o detect cycle(), cuja assinatura ´ a indicada em baixo ` o ca e a direita e que implementa um algoritmo por si projectado para verificar a existˆncia de e ciclos no grafo. A fun¸˜o deve retornar 0 se n˜o existirem ciclos no grafos ou um valor inteiro ca a maior do que 0 que indica o comprimento do ciclo encontrado, medido pelo n´mero de arestas u do ciclo. Por exemplo o grafo do Problema 6 tem um ciclo de tamanho 4 constitu´ pelas ıdo arestas que ligam os n´s C-E-H-F (al´m de v´rios outros ciclos). o e a Admita que a representa¸˜o do grafo se suporta na estrutura indicada em baixo ` esquerda e ca a que foi j´ allocada e preenchida com os dados do grafo. Assuma que al´m desta representa¸˜o, a e ca G, existe uma tabela de inteiros, marked[], cuja dimens˜o ´ o n´mero de n´s do grafo, G->V, a e u o e que foi inicializado a 0 em todas as posi¸˜es. co typedef struct Dgraph { int V; int E; int **adj; } DGRAPH; DGRAPH *G; int marked[]; int detect cycle(DGRAPH *G, int marked[]); 2

Sugest˜o: Para facilitar a compreens˜o do seu c´digo e garantir que pequenos erros n˜o a a o a limitam a avalia¸˜o do mesmo, ´ conveniente descrever de forma muito sucinta o algoritmo ca e que o c´digo implementa. o Nota: Apenas se pretende determinar se h´ ou n˜o h´ algum ciclo, qualquer que seja o seu a a a comprimento, pelo que assim que se descobrir um ciclo a fun¸˜o deve retornar imediatamente ca o comprimento desse ciclo e terminar a procura. [0.75] b) Determine e justifique qual a complexidade do algoritmo que implementou na fun¸˜o da al´ ca ınea a). Apresente o seu resultado em fun¸˜o dos parˆmetros do grafo (G->V, G->E, etc). ca a [0.75] c) Suponha agora que se pretende determinar n˜o apenas se existe um ciclo no grafo, mas a se existe um ciclo constitu´ por todas as arestas do grafo (sem repetir nenhuma aresta). ıdo Sem escrever qualquer c´digo diga como poderia determinar se tal ciclo existe? Se existe o tal ciclo, como se designa? Se existe tal ciclo, qual ´ o seu comprimento, em termos dos dados e da representa¸˜o do grafo (G->V, G->E, etc)? ca Mude de folha para responder ` pergunta 8 a [2.0] 8. Apresentando todos os c´lculos, resolva a recorrˆncia seguinte e determine a ordem da respectiva a e solu¸˜o utilizando a nota¸˜o assimpt´tica estudada (CN ∈ O(?)): ca ca o CN = CN/3 + lg3 N Nota: a sua resposta deve corresponder ao menor dos majorantes. Mude de folha para responder ` pergunta 9 a [3.0] 9. Considere de novo o grafo do Problema 6. [2.0] a) Determine a ´rvore de caminhos mais curtos (SPT) tomando o v´rtice A como fonte. Aprea e sente os seus c´lculos de forma clara, detalhada e completa para cada itera¸˜o do algoritmo. a ca Por exemplo, mas sem se restringir a estes aspectos, identifique em cada passo do algoritmo o estado da franja de procura e os respectivos pesos, assim como por que ordem entra cada v´rtice na ´rvore. Dever´ ainda indicar qual o valor final do vector st (que codifica a SPT) e e a a do vector wt (que contˆm as distˆncias dos v´rtices ao v´rtice fonte). e a e e [0.5] b) Indique quais os v´rtices que fazem parte do caminho mais curto entre o v´rtice A e o v´rtice e e e J, bem como qual o seu valor de custo. [0.5] c) Diga se a SPT que calculou lhe permite ou n˜o dizer qual o caminho mais curto entre C e F. a Porquˆ? e 3

Add a comment

Related presentations

Related pages

Os maias-resumo-detalhado-por-capitulos - claudia ribeiro

2010exame1a. Education. Tweet. 08. 03. 2014 0 views 2010exame2a. Education. Tweet. 08. 03. 2014 0 views 4 1 series. Tweet. 13. 03. 2014 0 views ...
Read more