Exame 2011 a

55 %
45 %
Information about Exame 2011 a
Education
aed

Published on March 8, 2014

Author: e-for-all

Source: slideshare.net

AED - Algoritmos e Estruturas de Dados 2010/2011 - 2o Semestre 1o Exame, 11 Junho 2011, 11:30h 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.75 valores. As quest˜es de escolha m´ltipla n˜o respondidas s˜o cotadas com 0 valores, mas por cada resposta o u a a errada s˜o descontados 0.75/4 valores. a Quest˜o a Resposta 1 2 3 4 1. Considere o problema da conectividade, com id = em C que realiza procura. 5 6 7 8 0 1 9 4 9 6 9 7 0 9 , e a seguinte fun¸˜o ca int isConnected (int i, int j) { while (i != id[i]) i = id[i]; while (j != id[j]) j = id[j]; return (i == j); } Qual o par correspondente a (isConnected(5,8), isConnected(2,3))? A. (0, 0) B. (0, 1) C. (1, 0) D. (1, 1) 2. Considere opera¸˜es realizadas sobre conjuntos de itens. O resultado da opera¸˜o ´ escrito sobre co ca e um dos operandos. Utilizando o crit´rio de eficiˆncia temporal, i.e. mais r´pido na execu¸˜o, fa¸a e e a ca c corresponder o par de opera¸˜es (Uni˜o, Intersec¸˜o) com um dos seguintes pares de estruturas de co a ca dados: A. (Lista, Tabela) B. (Tabela, Lista) C. (Tabela, Tabela) D. (Lista, Lista) 3. Considere a seguinte fun¸˜o de reposi¸˜o da ordena¸˜o de um acervo (”heap”) quando a prioridade ca ca ca de um n´ ´ aumentada: oe 1: 2: 3: 4: 5: 6: 7: void FixUp(Item Heap[], int Idx) { if (Idx == 0) return; while (Idx > 0 && lessPri(Heap[(Idx-1)/2], Heap[Idx])) { exch(&Heap[Idx], &Heap[(Idx-1)/2]); Idx = (Idx+1)*2; } } A fun¸˜o lessPri(Item x, Item y) devolve 1 se a prioridade de x for menor do que a de y e ca devolve 0 em caso contr´rio. A fun¸˜o exch(Item *x, Item *y) troca os valores das vari´veis a ca a apontadas por x e y. Em que linha existe um erro? Nota: Entre outras coisas, tome particular aten¸˜o aos propt´tipos definidos para as fun¸˜es e ca o co que s´ uma das linhas poder´ estar errada. o a A. Na linha 2 B. Na linha 3 C. Na linha 4 D. Na linha 5 4. Suponha que numa tabela de dispers˜o (”hash table”) s˜o introduzidos 5 n´meros pela seguinte a a u ordem: {401, 44, 766, 802, 560}. Os 4 primeiros elementos da tabela de dispers˜o obtida s˜o os a a seguintes [560, 401, 766, 802, . . .]. Note-se que nada ´ dito sobre o n´mero de elementos da tabela e u de dispers˜o (pode ter 4 ou mais elementos). As colis˜es s˜o resolvidas por procura linear. Qual a a o a fun¸˜o de dispers˜o usada? ca a

A. B. C. D. Resto da divis˜o inteira por 10 a Soma dos dois algarismos mais ` direita a Resto da divis˜o inteira por 5 a Um mais a soma dos dois algarismos mais ` direita a 5. Considere uma ´rvore bin´ria ordenada, n˜o necessariamente balanceada. Complete a frase seguinte a a a com a op¸˜o verdadeira. Sendo N o n´mero de n´s, a pesquisa numa ´rvore bin´ria ordenada ca u o a a tem uma complexidade associada... ... que ´ sempre O(N ) e ... que pode ser O(N ) A. C. B. D. ... que ´ sempre O(lg N ) e ... que pode ser O(N 2 ) 6. Considere o tro¸o de c´digo abaixo ` esquerda e a ´rvore bin´ria representada ` direita. c o a a a a C void traverse(tree *h, void (*visit)(link)) { if (h == NULL) return; traverse(h->left, visit); (*visit)(h); traverse(h->right, visit); } D E V F W O I U B N M A fun¸˜o disponibilizada implementa uma estrat´gia de varrimento onde a fun¸˜o visit() imprime ca e ca a letra correspondente a cada um dos n´s. Suponha que utiliza a fun¸˜o disponibilizada aplicada o ca aa ` ´rvore da figura. Qual das afirma¸˜es ´ verdadeira? co e A. B. C. D. O O O O varrimento varrimento varrimento varrimento ´ e ´ e ´ e ´ e Pr´-Fixado com sequˆncia de sa´ C D E V O W U F I B N M. e e ıda In-Fixado com sequˆncia de sa´ V E O D W U C I F N B M. e ıda In-Fixado com sequˆncia de sa´ C D E V O W U F I B N M. e ıda P´s Fixado com sequˆncia de sa´ V O E U W D I N M B F C. o e ıda 7. Usando a nota¸˜o assimpt´tica estudada e dada a express˜o de recorrˆncia CN = CN −1 + N , ca o a e indique qual das express˜es seguintes ´ verdadeira: o e A. C. CN ∈ O(lg3 N ) CN ∈ O(N ) B. D. 2 CN ∈ O √ 2(N /2) lg CN ∈ O( 3 lg N ) 8. Considere a seguinte tabela (primeira linha) sobre a qual s˜o listados alguns passos executados por a um algoritmo de ordena¸˜o (restantes linhas). Qual ´ o algoritmo usado? ca e 3 3 9 7 1 0 9 2 3 7 3 5 1 1 1 1 1 1 3 0 0 0 0 0 9 9 3 3 3 3 7 7 7 2 2 2 3 3 3 3 3 3 0 3 3 3 3 3 9 9 9 9 3 3 2 2 2 5 5 5 3 3 3 3 9 9 7 7 7 7 7 7 3 3 9 9 9 9 5 5 5 7 7 7 A. Inser¸˜o ca B. Shellsort (h=4, 3, 1) C. Shellsort (h=4, 2, 1) D. Quicksort

PARTE II - Quest˜es de Desenvolvimento o Responda a cada uma das quest˜es de desenvolvimento em folhas o identificadas com nome e n´mero. u [6.0] de exame separadas e devidamente 9. Considere que no seu programa para gerar palavras cruzadas necessita determinar uma lista de palavras que satisfazem um conjunto de restri¸˜es. Suponha que existem K restri¸˜es e que possui co co uma tabela de K listas, tal que na lista k, 0 ≤ k < K, est˜o os ´ a ındices de todas as palavras que satisfazem a restri¸˜o k + 1. Essa tabela de listas ser´ produzida sempre que se pretende completar ca a uma palavra no tabuleiro. O seu objectivo ´ produzir uma lista que contenha apenas os ´ e ındices que s˜o comuns a todas as K a listas, produzindo assim todos os ´ ındices candidatos ` posi¸˜o a completar. a ca Suponha que criou o tipo abstracto lista de acordo com a defini¸˜o abaixo e que possui uma ca implementa¸˜o das fun¸˜es necess´rias para criar, manipular e apagar elementos de vari´veis do ca co a a tipo lista. typedef struct lista{ int indice palavra; lista * proxima; } lista; Assuma ainda que existem ao todo N palavras, indexadas numa tabela para 0 ≤ n < N e que cada uma das listas possui Mk elementos, sendo este valor desconhecido ` partida, enquanto que o valor a total de palavras no dicion´rio ´ conhecido. Pode tamb´m assumir que cada uma das listas n˜o a e e a est´ ordenada. a [2.0] a) Escreva o c´digo de uma fun¸˜o temporalmente eficiente em C que receba duas listas de o ca ´ ındices como argumento e retorne a lista contendo a intersec¸˜o das duas. Note que se uma ca lista for vazia a intersec¸˜o das duas listas ser´ naturalmente vazia. A fun¸˜o que se pretende ca a ca que escreva tem a seguinte assinatura: lista * interseccao2(lista *lista1, lista * lista2); [1.0] b) Determine justificadamente a complexidade temporal da fun¸˜o que escreveu em a), como ca fun¸ao de N e/ou do tamanho de cada uma das duas listas, M1 e M2 . Pode assumir que c˜ Mi << N . [2.0] c) Fazendo uso da fun¸˜o que escreveu em a) escreva agora uma fun¸˜o eficiente que produza ca ca a intersec¸˜o de um n´mero arbitr´rio de listas, com a seguinte assinatura: ca u a lista * interseccaok(lista **tabela listas, int k); A vari´vel tabela listas cont´m as listas a intersectar e a vari´vel k indica a dimens˜o da a e a a tabela. Mesmo que n˜o tenha escrito a fun¸˜o interseccao2, assuma que ela est´ dispon´ a ca a ıvel para esta al´ ınea, de acordo com a assinatura especificada. NOTA: Se k for igual a um, o resultado ´ a unica lista da tabela. e ´ [1.0] d) Como fun¸˜o de N , K e/ou Mk , determine a complexidade temporal da fun¸˜o interseccaok. ca ca Pode assumir, por conveniˆncia de an´lise, que o tamanho m´dio das listas ´ M . Caso n˜o e a e e a tenha resolvido a al´ ınea a) e/ou b) assuma que a complexidade da fun¸˜o interseccao2 ´ ca e alguma fun¸˜o f (N, M1 , M2 ) ou f (N, M ), com M identificando o valor m´dio do tamanho ca e de cada lista ou o valor da maior lista, como achar conveniente. Indique qual o caso que considerou. [4.0] 10. Considere que pretende determinar o valor da seguinte fun¸˜o: f (p, q) = pf (p − 1, q) + qf (p, q − 1), ca definida para valores inteiros n˜o negativos de p e q, com f (0, q) = 0 para todo o valor de q ̸= 0, a f (p, 0) = 1 para todo o p ̸= 0, e f (0, 0) = 2.

[2.0] a) Escreva o c´digo de uma fun¸˜o temporalmente eficiente em C com a seguinte assinatura: o ca int f p q(int p, int q); [1.0] b) Considerando as v´rias t´cnicas de desenvolvimento de algoritmos – ”divide-and-conquer”, a e programa¸ao dinmica ascendente e programa¸˜o dinmica descendente –, qual delas utilizou c˜ ca na al´ ınea a)? Justifique a op¸˜o e a resposta. ca [1.0] c) Indique justificadamente quais os requisitos de mem´ria da fun¸˜o que implementou. o ca [4.0] 11. Considere o grafo indicado em baixo e assuma que o mesmo n˜o ´ direccionado mas ´ ponderado, a e e como se indica do lado direito do grafo. B A C D F E G H I E↔F, A↔B, A↔C, B↔E, C↔E A↔D, E↔D C↔D, G↔I, E↔H E↔G F↔I 1 B↔F, F↔G, H↔I, D↔H 2 B↔C, G↔H 3 4 5 6 [2.5] 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 a franja da procura e pesos, assim como dever´ indicar por que ordem entra cada v´rtice na ´rvore e o estado da franja a e a em cada momento. [0.75] 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 G, bem como qual o seu valor de custo. [0.75] c) Diga se a SPT que calculou lhe permite ou n˜o dizer qual o caminho mais curto entre G e H. a Porquˆ? e

Add a comment

Related presentations

Related pages

EXAME.com – Negócios, economia, tecnologia e carreira

Confira as últimas notícias, blogs, vídeos e opiniões de EXAME.com, o site da revista Exame
Read more

Exame Suficiência 2011.1 - YouTube

Exame Suficiência 2011.1 F C R Ferreira; 38 videos; 3,749 views; Last updated on Feb 5, 2015; Play all Share. Loading... Save. Sign in to ...
Read more

Exame 2011 f1especial D3 - YouTube

Exame 2011 f1especial D3 Explicamat. Subscribe Subscribed Unsubscribe 26,909 26K. Loading... ... Standard YouTube License; Loading... Advertisement
Read more

Guia EXAME de Sustentabilidade 2011 by Revista EXAME - issuu

Guia EXAME de Sustentabilidade 2011 da Revista EXAME | Issuu is a digital publishing platform that makes it simple to publish magazines, catalogs ...
Read more

Português: Exame Nacional 2011 - 1.ª fase - Proposta de ...

confundiu-te?? era só dizer que no poema havia sensações visuais e auditivas, porque te confundiu? :s já se sabe que nesta fase Álvaro de ...
Read more

Exame Nacional de 2011 (2.a fase) - exame.leyaeducacao.com

Exame Nacional de 2011 (2.a fase) ... 2_fase_site_prep_exame_geo_11ano_ALVmat9 Author: Administrator Created Date: 8/29/2011 5:04:49 PM ...
Read more

Geometria Descritiva - jpprimo: Exame 2011 - 1 fase ...

Anónimo disse... Boa noite, aqui em Brasília irá acontecer um evento organizado pela SBEM - DF, o V Encontro Brasiliense de Educação ...
Read more

EXAME DE ORDEM UNIFICADO 2011 - estaticog1.globo.com

IV EXAME DE ORDEM UNIFICADO – TIPO 1 – BRANCO Página 1 Ordem dos Advogados do Brasil IV EXAME DE ORDEM UNIFICADO TIPO 1 – BRANCO Atenção!
Read more

Português: Exame Nacional 2011 - 2.ª fase - Proposta de ...

Olá a todos,quanto ao exame estou como todos vós aflita, nao sei mesmo que pensar, até chego a estar com bastante medo da minha nota, na ...
Read more

Microsoft Certification Exam List | Microsoft Learning

Find the Microsoft Certification exams you need to highlight your skills and further your career. Explore our newest exam list.
Read more