2010exame2a

42 %
58 %
Information about 2010exame2a
Education
aed

Published on March 8, 2014

Author: e-for-all

Source: slideshare.net

AED - Algoritmos e Estruturas de Dados 2009/2010 - 2o Semestre 2o Exame, 8 Julho 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 Quest˜o a Resposta 1 2 3 4 5 6 7 8 9 1. Suponha um conjunto de N n´meros inteiros (N muito grande), organizados numa tabela sou bre a qual ´ implementado o seguinte algoritmo: dado um n´mero k, esse n´mero ´ pesquisado e u u e na tabela; o algoritmo retorna TRUE ou FALSE respectivamente, consoante encontrou ou n˜o o a n´mero k na tabela. Em m´dia, quantas compara¸˜es s˜o efectuadas durante a execu¸˜o da u e co a ca fun¸˜o, admitindo que ela ´ o mais eficiente poss´ ca e ıvel? A. B. C. D. O(k) se a pesquisa se iniciar pelo ultimo ´ ´ ındice da tabela O(log N ) se a tabela estiver ordenada O(log N ) se n˜o houver n´meros repetidos na tabela a u O(N ) em qualquer caso, quer a tabela esteja ordenada ou n˜o a 2. 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 71 12 63 5 92 80 45 0 28 99 36 58 0 0 0 0 0 0 71 5 5 5 5 5 12 71 12 12 12 12 63 12 71 28 28 28 5 63 28 71 36 36 92 28 63 36 71 45 80 92 36 63 45 71 45 80 92 45 63 58 28 45 80 92 58 63 36 36 45 80 92 80 99 58 58 58 80 92 58 99 99 99 99 99 A. Inser¸˜o ca B. Bubble C. Shellsort (h=5, 3, 1) D. Quicksort 11 3. Considere a `rvore bin´ria indicada na figura ` sua direita. a a a Considere que a mesma ´ varrida mediante uma dada e estrat´gia e que em cada n´ se imprime o n´mero are o u mazenado no n´. Suponha que ´ utilizado um varrio e mento Pr´-fixado. Indique que sequˆncia ´ apresene e e tada na sa´ ıda? A. B. C. D. 17 5 3 7 6 11 − 5 − 17 − 3 − 7 − 13 − 19 − 6 − 8 − 15 − 18 − 20 3 − 5 − 6 − 7 − 8 − 11 − 13 − 15 − 17 − 18 − 19 − 20 3 − 6 − 8 − 7 − 5 − 15 − 13 − 18 − 20 − 19 − 17 − 11 11 − 5 − 3 − 7 − 6 − 8 − 17 − 13 − 15 − 19 − 18 − 20 1 13 8 19 15 18 20

4. Considere a ´rvore do problema anterior. Uma an´lise simples mostra que ´ uma ´rvore ordenada a a e a e equilibrada AVL. A ordena¸˜o ´ tal que para qualquer n´, ele tem uma valor superior a todos os ca e o seus descendentes ` esquerda e inferior a todos os seus descendentes ` direita. a a Admita que por ordem se introduzem na ´rvore os n´meros 12 e 9, que a introdu¸˜o satisfaz a a u ca regra de ordena¸˜o e que ap´s a introdu¸˜o de cada n´mero a ´rvore ´ reequilibrada. Diga quais ca o ca u a e os n´s, de acordo com a defini¸˜o de equil´ o ca ıbrio AVL, que ficam momentaneamente desiquilibrados ap´s a introdu¸˜o de cada um dos n´meros indicados (antes da ´rvore ser reequilibrada). o ca u a A. 5, 7 B. 7, 13 C. 5 D. 7 5. Suponha que os seguintes n´meros s˜o introduzidas numa tabela de dispers˜o (”hash table”): u a a 4723, 8342, 3731, 31, 1302, 7332, 1323, 4723, 2812, 3123, 302. Assuma que a fun¸˜o de disca pers˜o (para indexa¸˜o na tabela) ´ a seguinte: f (x) = x mod 100 (ou seja, o resto da divis˜o por a ca e a 100). Assuma que n´meros repetidos n˜o s˜o armazenados, quando tal ´ verificado, e que colis˜es u a a e o s˜o resolvidas por lista, com inser¸˜o no in´ a ca ıcio. Ap´s a inser¸˜o dos n´meros a tabela ´ percorrida o ca u e do ´ ındice 0 ao ind´ 99 e para cada ´ ıce ındice a lista correspondente ´ percorrida, sendo impressos e todos os valores nela constantes. Qual das seguintes sequˆncias ´ apresentada na sa´ e e ıda? A. B. C. D. 302, 1302, 2812, 3123, 1323, 4723, 31, 3731, 7332, 8342 1302, 302, 2812, 4723, 1323, 3123, 3731, 31, 7332, 8342 302, 1302, 2812, 3123, 4723, 1323, 4723, 31, 3731, 7332, 8342 1302, 302, 2812, 4723, 1323, 4723, 3123, 3731, 31, 7332, 8342 6. Considere o grafo G 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. Relativamente ` SPT deste grafo que tem como a fonte o n´ B, indique qual das afirma¸˜es ´ verdadeira. o co e C F I A D H B E G A. B. C. D. J O A A A D↔F, A↔C, F↔I E↔G, B↔D A↔D, B↔E, D↔G, C↔F D↔H H↔I D↔I, G↔J I↔J D↔J H↔J n´ I ´ o 7o n´ a entrar na SPT o e o distˆncia de B a G pelo caminho mais curto ´ de 11. a e distˆncia de B a J pelo caminho mais curto ´ de 13. a e aresta H↔J pertence ` SPT a 2 1 2 3 4 5 6 7 8 9

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 [4.0] 7. As ´rvores bin´rias s˜o estruturas de dados com m´ltiplas aplica¸˜es em computa¸˜o cuja cona a a u co ca stru¸˜o e manipula¸˜o aprendeu em AED. ca ca Numa fase de grande descontentamento na sua empresa, muitos colegas seus queixam-se da excessiva distˆncia a que est˜o da estrutura de topo de decis˜o e outros queixam-se de um esfor¸o muito a a a c desigual de gest˜o dos seus subordinados (por uns terem demasiadas pessoas suas subordinadas e a outros muito poucas). Determinado a confirmar a relevˆncia das queixas constr´i uma a o a ´rvore com a hierarquia de responsabilidades da empresa e descobre que essa ´rvore ´ bin´ria. Uma vez constru´ a ´rvore a e a ıda a ´ necess´rio calcular a que n´ da hierarquia se encontra cada e a ıvel pessoa e quantas pessoas lhe est˜o subordinadas em termos de a responsabilidade. S´ assim poder´ determinar se as queixas o a tˆm raz˜o de ser. e a [2.5] typedef struct BTree { int level; int numsub; Person node; BTree *left; BTree *right; } BTree; a) Para obter esses dados escreva uma fun¸˜o que dada a ra´ de uma ´rvore bin´ria determina ca ız a a para cada n´ o n´ o ıvel em que o n´ se encontra (a ra´ est´ ao n´ o ız a ıvel 0 e todos os “filhos” de um n´ no n´ d est˜o no n´ d+1). Dado os seus excelentes conhecimentos, adquiridos em o ıvel a ıvel AED, a mesma fun¸˜o calcula igualmente o n´mero de subordinados de cada pessoa, ou seja ca u o n´mero de n´s na sub-´rvore de que cada n´ ´ ra´ u o a o e ız. Assuma que os n´s da ´rvore s˜o do tipo BTree definido acima em que o campo Person cono a a tem os dados de cada pessoa (irrelevantes para a sua fun¸˜o), no campo numsub deve guardar ca o n´mero de n´s abaixo do n´ em quest˜o (filhos, netos, bisnetos, etc) e no campo level u o o a o n´ ıvel do n´ (assuma que estes campos est˜o inicialmente a zero em todos os n´s). A sua o a o fun¸˜o retorna um n´mero inteiro que pode usar da forma que for mais conveniente. Assuma ca u a seguinte assinatura para a fun¸˜o: ca int traverse tree(BTree *node, int lev) Para facilitar a compreens˜o do seu c´digo e garantir que pequenos erros n˜o limitam a a o a o avalia¸˜o do mesmo, descreva cuidadosamente o algoritmo que o c´digo implementa. ca Sugest˜o: Calcule em cada n´, recursivamente, o n´mero de sucessores de cada n´ e retorne a o u o esse valor. No percurso descendente na ´rvore determine e guarde o n´ de cada n´ e no pera ıvel o curso ascendente retorne ent˜o o n´mero de sucessores (adicionando o pr´prio n´). Lembre-se a u o o que h´ sucessores na sub-´rvore esquerda e tamb´m na sub-´rvore direita. a a e a [0.5] b) Indique, justificando, no pior caso, qual a complexidade da fun¸˜o que escreveu, em fun¸˜o ca ca do n´mero de n´s da ´rvore N , ou de outro parˆmetro que ache relevante. u o a a [1.0] c) Suponha que no final deste exerc´ verifica, com alguma surpresa, que de facto a sua ´rvore ıcio a tem folhas a profundidades muito variadas e que o n´mero de n´s debaixo de cada n´ (debaixo u o o da sua sub-´rvore) ´ igualmente muito diferente. a e Determinado a eliminar estes problemas vocˆ projecta uma nova hierarquia para a empresa e usando ainda uma ´rvore bin´ria, mas em que os empregados est˜o dispostos na arvore usando a a a ´ a antiguidade como crit´rio: os empregados mais antigos mais perto da ra´ e os empregados e ız mais recentes perto das folhas. Na sua nova hierarquia os empregados est˜o o mais perto da a ra´ poss´ garantindo-se que para cada empregado todos os seus subordinados (todos os n´s ız ıvel o na sub-´rvore de que ele ´ ra´ s˜o mais recentes do que ele. A ´rvore resultante ´ ainda o a e ız) a a e mais compacta poss´ (com a menor altura poss´ ıvel ıvel) para garantir que nenhum empregado 3

esteja muito longe do topo da hierarquia. Ao terminar de construir a nova ´rvore vocˆ apercebe-se que h´ uma forma muito compacta de a e a a representar e armazenar. Por exemplo, n˜o precisa em cada n´ dos ponteiros para os filhos a o esquerdo e direito pois sabe sempre onde eles est˜o e que dessa forma todas as opera¸˜es de a co acesso (encontrar qualquer elemento) e altera¸˜o s˜o igualmente muito eficientes. Explique, ca a justificando, que estrutura de dados seria essa? Nesse tipo de estrutura qual ´ o n´ m´ximo a que um dado n´ pode estar se a ´rvore tiver e ıvel a o a um total de N n´s. o a o Nota: N˜o se pretende que escreva nenhum c´digo! Mude de folha para responder ` pergunta 8 a Identifique a nova folha com n´ mero e nome u [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 = 3CN/3 + 1 Nota: a sua resposta deve corresponder ao menor dos majorantes. Mude de folha para responder ` pergunta 9 a Identifique a nova folha com n´ mero e nome u [3.0] 9. Considere de novo o grafo do Problema 6. [2.0] a) Determine a ´rvore de suporte m´ a ınima do grafo (MST) atrav´s do algoritmo de Prim. Inicie e o algoritmo no n´ B. Apresente os seus c´lculos de forma clara, detalhada e completa para o a cada itera¸˜o do algoritmo. Identifique em cada passo do algoritmo o estado da franja ca de procura e os respectivos pesos, assim como por que ordem entra cada v´rtice na ´rvore. e a Dever´ ainda indicar qual o valor final do vector st (que codifica a MST) bem como o custo a total da MST. [0.5] b) No Problema 6 calculou a ´rvore de caminhos mais curtos (SPT) do mesmo grafo tendo como a fonte o n´ B. Justifique que essa ´rvore ´ tamb´m uma ´rvore de suporte. Ser´ que a SPT ´ o a e e a a e tamb´m sempre uma MST? Justifique. e [0.5] c) Diga se a MST que calculou lhe permite ou n˜o dizer qual o caminho mais curto entre B e J. a Porquˆ? e 4

Add a comment

Related presentations

Related pages

2010exame2a - Education

2010exame2a. by education-for-all. on Aug 06, 2015. Report Category: Education
Read more

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

2010exame2a. Education. Tweet. 08. 03. 2014 0 views 4 1 series. Tweet. 13. 03. 2014 0 views Exercicios 1 margarida ponce's conflicted copy 2012 02-21) ...
Read more