AED - 2012-2013 - 2o SemestreAlgoritmos e Estruturas de Dados

2o Exame, 27 Junho 2013, 8:00h Duracao: 3 horas

Prova escrita, individual e sem consulta

NOME: NUMERO:

PARTE I - Questoes de Escolha Multipla

Preencha as respostas na tabela (usando apenas letras maiusculas). Se nenhuma opcao servir, escreva NENHUMA.

Se pretender alterar a sua resposta, risque e escreva ao lado a sua nova opcao. Todas as questoes de escolha multipla

valem 0.75 valores. As questoes de escolha multipla nao respondidas sao cotadas com 0 valores, mas por cada resposta

errada sao descontados 0.75/4 valores.

Questao 1 2 3 4 5 6 7 8

Resposta

1. Considere a seguinte recorrencia

CN = CN/3 +Nlog

2(3) log2(N

1/2) + CN/3

Por aplicacao do Master Theorem, qual dos seguintes conjuntos representa a complexidade temporalassociada com a recorrencia dada?

A. O(N log2(3) log2(N)) B. O(N log

2(3) log22(N))

C. O(N log3(2) log2(N)) D. O(N log

3(2) log22(N))

2. Considere que a tabela abaixo representa um acervo, em numeros mais baixos correspondem a maisalta prioridade

{3; 5; 7; 11; 9; 15; 23; 41; 14; 32; 36; 24; 60; 61; 70}

Suponha que se efectuam as seguintes operacoes: (i) baixa-se a prioridade do elemento de valor 7para 31; (ii) sobe-se a prioridade do elemento 61 para 14; (iii) insere-se um novo elemento com ovalor 8; (iv) remove-se o elemento de mais alta prioridade. No contexto exclusivo das operacoes defix-up and fix-down, quantas trocas ao todo se realizam?

A. 7 B. 8 C. 9 D. 10

3. Considere a arvore binaria, ordenada e nao balanceada AVL representada na figura a direita.

Considere que se introduz na arvore umou os dois numeros seguintes: 60 e 70.Qual das seguintes afirmacoes e verda-deira?

98

67

49

23

13

73

140

113

107 134

174

158 202

1

A. A arvore nao fica balanceada AVL com a introducao dos dois numeros.B. A arvore fica balanceada AVL com a introducao dos dois numeros.C. A arvore fica balanceada AVL com a introducao do numero 60 .D. A arvore fica balanceada AVL com a introducao do numero 70 .

4. Considere o seguinte conjunto de cidades com aeroporto:

Lisboa Paris Calcuta Pretoria Faro Oslo Toronto Fortaleza Melbourne Seul Katmandu

A Autoridade Internacional Aeroportuaria (AIA) forneceu-lhe a seguinte lista de ligacoes aereasentre as cidades acima listadas e pediu-lhe que devolvesse a informacao sobre as cidades que seencontram ligadas por via aerea. Enquanto aluno de AED, reconhecendo este problema como umproblema de conectividade, decide aplicar o algoritmo de uniao rapida com compressao de caminhopara resolver o problema.

{(Lisboa, Calcuta), (Paris, Pretoria), (Faro, Fortaleza), (Oslo, Toronto), (Melbourne, Seul),(Lisboa, Paris), (Oslo, Fortaleza), (Lisboa, Faro), (Oslo, Melbourne), (Pretoria, Katmandu)}

Das tabelas abaixo qual e que devia ser enviada a AIA como solucao do problema usando oalgoritmo referido (a ordem das cidades nas tabelas abaixo correspondem a tabela acima, ou sejaa 1a posicao das tabelas abaixo corresponde a cidade de Lisboa, a 2a posicao a cidade de Paris, eassim sucessivamente):

A. Lisboa Lisboa Lisboa Lisboa Lisboa Lisboa Oslo Oslo Lisboa Melbourne Lisboa

B. Lisboa Lisboa Lisboa Lisboa Oslo Oslo Oslo Oslo Lisboa Melbourne Lisboa

C. Lisboa Lisboa Lisboa Lisboa Oslo Oslo Oslo Oslo Oslo Melbourne Lisboa

D. Lisboa Paris Lisboa Lisboa Lisboa Lisboa Oslo Oslo Lisboa Melbourne Pretoria

5. Seja uma tabela de dispersao de tamanho 100 com ındices livres e em que as colisoes se resolvempor procura linear. Nessa tabela pretende-se armazenar um conjunto de estruturas, utilizandocomo chave para a funcao de dispersao um dos campos da estrutura que contem numeros inteiros.Naturalmente que, sendo a tabela de tamanho 100, para cada numero da chave a funcao de dispersaodetermina um ındice entre 0 e 99, que corresponde ao resto da divisao inteira da chave por 100.

Representando por ’-’ uma posicao vazia, apos algumas insercoes na tabela de dispersao, as pri-meiras oito posicoes estao preenchidas com a seguinte informacao: {14600; 25301; 43099; 56303;66302; 17905; 50004; ’-’}.

Indique qual das sequencias de introducao e compatıvel com aquele preenchimento:

A. 58199, 56303, 45326, 14600, 30009, 25301, 43099, 17905, 66302, 50004.B. 30009, 56303, 58199, 14600, 43099, 45326, 25301, 17905, 66302, 50004.C. 14600, 56303, 58199, 25301, 45326, 30009, 43099, 50004, 17905, 66302.D. 14600, 56303, 58199, 25301, 45326, 43099, 30009, 50004, 66302, 17905.

6. Considere de novo a arvore da Questao 3. Assuma que a arvore e varrida em modo pos-fixado.Indique em que posicao sao processados os vertices 73 e 113.

A. 3 e 9, respectivamente. B. 4 e 8, respectivamente.C. 3 e 8, respectivamente. D. 4 e 9, respectivamente.

7. Considere a seguinte tabela de numeros:

62 83 18 53 07 17 95 86 47 69 25 28

Apos a aplicacao de 3 iteracoes do algoritmo de ordenacao S obtiveram-se as seguintes tabelas:

17 83 18 53 07 25 95 86 47 69 62 28

17 28 18 53 07 25 83 86 47 69 62 95

17 28 18 53 07 25 83 86 47 69 62 95

2

Identifique o algoritmo S.

A. Shell de chave inicial 4. B. Selection. C. Shell de chave inicial 5. D. Quicksort.

8. Abaixo estao representados mapas de estradas entre varias cidades inglesas:

Na figura da esquerda encontram-se representadas apenas as estradas normais, enquanto na figurada direita e igualmente representada uma via rapida circular com tres pontos de acesso T , X e Y .Junto a cada aresta que liga duas cidades ou que liga a cidade R aos pontos de acesso X e Y estaoindicadas as distancias em km. Sabe-se tambem que nas estradas normais e nas vias de acessopode-se circular apenas a uma velocidade maxima de 50Km/h enquanto na via rapida a velocidademaxima e de 100Km/h. Considerando que se pretende encontrar o caminho que demore menostempo de R e T , indique qual das seguintes possibilidades e a correcta:

A. O caminho de menor tempo utiliza a via rapida e passa apenas nos pontos X e T

B. O caminho de menor tempo utiliza a via rapida e passa apenas nos pontos Y e T

C. O caminho de menor tempo nao utiliza a via rapidaD. O caminho de menor tempo utiliza a via rapida e passa nos pontos X , Y e T

PARTE II - Questoes de Desenvolvimento

Responda a cada uma das questoes de desenvolvimento em folhas de exame separadas e devidamente

identificadas com nome e numero.

[5.00] 9. Considere um grafo ponderado nao direccionado de 14 vertices e 28 arestas, cuja matriz de ad-jacencias se apresenta abaixo.

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 12 7 ∞ 2

∞ 0 3 ∞ 16 2 ∞ 13 ∞ ∞ ∞ ∞ ∞ ∞

∞ 3 0 ∞ 10 9 ∞ ∞ ∞ 22 ∞ ∞ ∞ ∞

∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ 4 7 10 ∞

∞ 16 10 ∞ 0 1 14 ∞ ∞ 21 ∞ ∞ ∞ ∞

∞ 2 9 ∞ 1 0 15 16 ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ 14 15 0 12 18 20 ∞ ∞ ∞ ∞

∞ 13 ∞ ∞ ∞ 16 12 0 19 ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞ 18 19 0 11 ∞ ∞ ∞ ∞

∞ ∞ 22 ∞ 21 ∞ 20 ∞ 11 0 ∞ ∞ ∞ ∞

12 ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ ∞ 0 5 8 13

7 ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ ∞ 5 0 9 14

∞ ∞ ∞ 10 ∞ ∞ ∞ ∞ ∞ ∞ 8 9 0 ∞

2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 13 14 ∞ 0

a)[2.00] Assumindo que a numeracao dos vertices comeca em zero, tome o vertice de ındice 5 como

ponto de partida para determinar a Arvore de Mınima de Suporte (“MST”), usando o algo-ritmo de Prim. Indique justificadamente todos os passos que executar e descreva em detalheos calculos realizados.

b)[2.00] Aplique o mesmo algoritmo tomando agora o vertice 10 como ponto de partida.

c)[0.50] Que fenomeno aconteceu nas duas alıneas anteriores? De uma explicacao para esse fenomeno.

d)[0.50] Comente a seguinte frase: “A MST de um grafo de V vertices pode conter menos que V − 1arestas”. Diga se a frase e verdadeira ou falsa e justifique a sua opcao.

3

[3.00] 10. Considere que se aplicou o algoritmo de Prim a um dado grafo e que esse algoritmo construiu umaMST explıcita. A estrutura de dados onde a arvore esta explicitamente construıda e a seguinte:

typedef struct mst {int vertice;

float custo;

int n filhos;

mst * filhos;

} MST;

em que o campo vertice identifica um dos vertices do grafo, o campo custo indica o valor daaresta usada para inserir esse vertice na MST, o campo n filhos identifica quantos filhos possuiesse vertice e o campo filhos e um vector de dimensao n filhos que aponta para cada uma dassub-arvores cuja raız e um dos filhos.

Suponha que pretende determinar um caminho desde a raız ate as folhas que siga o seguinte criterio:em cada vertice, prosseguir para o filho que possuir o custo mais baixo. Pretende-se produzir umalista contendo os vertices desse caminho. Note que um vertice folha e tal que o seu numero defilhos e zero.

A funcao a desenvolver tem a seguinte assinatura:

lista * caminho greedy(MST * arvore);

em que lista esta definido como

typedef struct lista{int vertice; lista * proximo;}lista;

[2.00] a) Escreva uma funcao em C que concretize aquele objectivo.

[0.25] b1) Assumindo que o grafo possui V vertices e que a MST fornecida possui V − 1 vertices folha,indique qual a complexidade temporal e de memoria da funcao que produz aquele tipo decaminho como funcao de V .

[0.25] b2) Assumindo que o grafo possui V vertices e que a MST fornecida possui V −1 vertices internos,indique qual a complexidade temporal e de memoria da funcao que produz aquele tipo decaminho como funcao de V .

[0.25] b3) Assumindo que o grafo possui V vertices e que a MST fornecida e tal que cada vertice que naoseja folha possui exactamente b filhos, indique qual a complexidade temporal e de memoriada funcao que produz aquele tipo de caminho como funcao de b e V .

[0.25] c) Caracterize o tipo de analise de complexidade que efectuou em cada uma das tres alıneasanteriores.

[4.00] 11. Considere de novo o grafo do Problema 9 ao qual acrescenta uma aresta bi-direccional de peso 3ligando o vertice 6 ao vertice 12.

[3.00] a) Tomando o vertice 6 como ponto de partida, calcule a SPT para o novo grafo por aplicacaodo algoritmo de Dijkstra. Apresente os seus calculos intermedios e justifique-os.

[1.00] b) Trace a SPT que obteve na alınea anterior.

[2.00] 12. Comente as seguintes afirmacoes. Para cada uma, indique se e verdadeira ou falsa e expliqueporque. Se entender util, forneca exemplo(s).

[1.00] a) “A maior aresta de um grafo nao direccionado nunca faz parte de nenhuma SPT desse grafo,qualquer que seja o vertice fonte”.

[1.00] b) “A mais pequena aresta de um grafo nao direccionado pode nao fazer parte de alguma SPTdesse grafo”.

4