AED - 2013-2014 - 1o SemestreAlgoritmos e Estruturas de Dados

1o Exame, 4 Janeiro 2014, 11:30h 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

[0.75] 1. Considere uma funcao que recebe N inteiros, efectua 4 operacoes sobre cada um dos N inteiros e sechama a si propria 2 vezes, cada uma delas passando por parametro apenas N-1 dos inteiros. Quala recorrencia que descreve a complexidade de execucao desta funcao?

A. CN = 4CN−1 + 2 B. CN = 2CN−1 + 4N

C. CN = 4CN−1 + 2N D. CN = 2CN−1 + 4

[0.75] 2. Apos a aplicacao de um determinado numero de iteracoes do algoritmo de procura rapida, noproblema da conectividade, obteve-se a seguinte tabela

0 1 2 9 9 5 6 7 0 9

Qual a tabela que se obtem apos se ligar o par 7-8 seguido do par 4-5?

A. 0 1 2 9 5 5 6 8 0 9 B. 0 1 2 5 5 5 6 0 0 5

C. 0 1 2 9 9 9 6 0 0 9 D. 7 1 2 9 9 9 6 7 7 9

[0.75] 3. Considere os algoritmos de ordenacao basicos estudados (selecao, insercao e bubble). Indique qualdas seguintes afirmacoes e falsa. Assuma em cada caso a melhor implementacao de cada algoritmo(adaptativa, optimizada, etc.)

A. O desempenho assimptotico da ordenacao por selecao e independente da ordenacao inicialdos dados.

B. No pior caso, a complexidade assimptotica da ordenacao por insercao e identica a dobubble sort.

C. O numero de trocas com ordenacao por seleccao e quadratico no numero de dados.

D. Para dados quase ordenados, a ordenacao por insercao e quase linear no numero de dados.

1

[0.75] 4. Considere o algoritmo quicksort. Apos a primeira particao de um array de inteiros, obteve-se aseguinte tabela:

4 1 3 5 9 7 8 7 10 13 11 12 11 17 16 16 19 22 20 21

Qual dos seguintes conjuntos so contem elementos que possam ter sido pivot?

A. {5, 16, 20} B. {9, 10, 19} C. {5, 10, 19} D. {9, 16, 20}

[0.75] 5. Suponha que aplicou o algoritmo de Prim a um dado grafo usando o metodo tabular. A tabelafinal e a seguinte. Cada par a/b deve ser interpretado como sendo a o valor da distancia a arvore(MST em construcao) e b o vertice associado com essa distancia.

0 1 2 3 4 5 6 7 8 93 ∞ ∞ ∞ - 7/3 3/3 ∞ 2/3 11/3 11/37 3/7 ∞ 4/7 - 5/7 3/3 1/7 - 6/7 7/76 3/7 2/6 4/7 - 5/7 3/3 - - 6/7 4/61 3/7 - 4/7 - 4/1 3/3 - - 6/7 2/19 3/7 - 2/9 - 4/1 3/3 - - 1/9 -8 3/7 - 1/8 - 4/1 3/3 - - - -2 3/7 - - - 4/1 3/3 - - - -0 - - - - 4/1 2/0 - - - -5 - - - - 4/1 - - - - -4 - - - - - - - - - -

Qual das afirmacoes e falsa?

A. A aresta (8-2) pertence a MST. B. O custo da MST produzida e 18.

C. A aresta (8-9) nao pertence a MST. D. A aresta (6-9) nao pertence a MST.

[0.75] 6. Considere o seguinte acervo, em que a prioridade e inversamente proporcional ao valor de cadaelemento.

5 20 30 40 60 45 55 55 45 62 74 55

Suponha que: i) chama a funcao RemoveMax(.); ii) insere o valor 1; iii) chama a funcao RemoveMax();iv) insere o valor 25. Apos cada uma das operacoes e sempre reposta a condicao de acervo. Indiquequal das hipoteses seguintes corresponde ao acervo final.

A. 1 40 25 45 60 30 55 55 55 62 74 45

B. 20 40 25 45 60 30 55 55 55 62 74 45

C. 5 40 25 45 60 30 55 55 55 62 74 45

D. 20 40 25 45 60 30 55 55 45 62 74 55

[0.75] 7. Considere a seguinte arvore:

1

5

3

2

7

6

8

4

Supondo que se faz o varrimento da arvore de acordo comum determinado metodo e se obtem a seguinte ordem denos:

1 → 7 → 2 → 3 → 6 → 8 → 4 → 5

Indique qual foi o metodo de varrimento utilizado.

A. in-fixado. B. pos-fixado.C. em largura. D. em profundidade.

2

[0.75] 8. Considere que se pretende inserir identificadores (IDs) unicos numa tabela de dispersao, em quecada ID e constituıdo por 3 algarismos: id[1], id[2], id[3], com id[i] ∈ {0, 1, 2, 3}. Exemplos: 010,321, 113, 222 etc..

Seja a seguinte funcao de dispersao:

f(ID) = id[1] ∗ 2 + (id[2]//2) + id[3] ∗ 4

em que // representa a divisao inteira.

Considere tambem que a tabela de dispersao permite inserir no maximo 2 IDs por posicao (i.e.,por f(ID)), e que a partir da colisao seguinte a dispersao e feita por procura linear.

Supondo que a ordem de entrada dos elementos e a seguinte:

202 → 102 → 231 → 320 → 221 → 121 → 032 → 331 → 211 → 332 → 201 → 131

Indique qual das seguintes tabelas e compatıvel com a tabela de dispersao que se obtem apos aintroducao dos elementos atras indicados.

A.

8 9 10 11 12211 231 102 331 202201 221 032 131

B.

8 9 10 11 12320 231 102 331 202121 221 032 211 201

C.

8 9 10 11 12211 231 102 032 202201 221 131 331

D.

8 9 10 11 12121 231 102 331 202211 221 032 201 131

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.

[4.5] 9. Assuma uma representacao relativamente standard para grafo suportada em listas de adjacenciase nos seguintes tipos de dados (V e E sao respetivamente o numero de vertices e arestas do grafo):

typedef struct edge { typedef struct graph {int w; int V, E;

struct edge *next; EDGE **adj;

} EDGE; } GRAPH;

[3.0] a) Escreva o codigo de uma funcao que conte o numero de componentes ligados de um dadografo (sub-grafos ligados maximos). A funcao deve receber como argumentos uma estruturagrafo e retornar o numero de componentes ligados (um numero inteiro maior ou igual a um).A assinatura da funcao deve ser:

int CountCompLig(GRAPH *G)

Nota1: se necessitar pode definir e usar variaveis globais mas justifique a sua necessidade eexplique para que servem.Nota2: a funcao indicada pode chamar outras funcoes se for necessario (i.e, o seu codigopode estar organizado em mais do que uma funcao).

[1.0] b) Indique qual a complexidade computacional da solucao proposta.

[0.5] c) Diga que alteracoes teria de introduzir no seu codigo se o grafo passado como argumento afuncao fosse um grafo ponderado.

3

[4.0] 10. Pretende-se desenvolver uma solucao eficiente para o armazenamento e manipulacao de matrizesN × N esparsas, i.e., matrizes em que o numero de elementos nao nulos, Nnz, e muito inferior aonumero maximo de elementos da matriz, Nnz << O(N2).Assuma que os elementos nao-nulos da matriz sao fornecidos um de cada vez (por exemplo lidos deum ficheiro) e que para cada elemento e indicada a linha, coluna e o seu valor (um numero real).

[1.5] a) Assuma inicialmente que os elementos podem surgir por qualquer ordem (i.e. ser lidos por umaordem arbitraria). Sem escrever codigo, descreva uma estrutura de dados e a sequencia deaccoes que permita armazenar de forma eficiente os Nnz elementos nao-nulos de uma matriz.A estrutura proposta deve ser fundamentalmente eficiente em termos de memoria, i.e. naodeve ocupar espaco desnecessario, e deve permitir o acesso a qualquer elemento depois dearmazenado.Nota: Se desejar pode fazer uma representacao grafica da estrutura de dados.

[1.0] b) Analise a complexidade da solucao proposta em termos da memoria ocupada. Indique para asolucao proposta, o custo computacional medio de acesso a um elemento da matriz.

[1.0] c) Se os elementos nao nulos da matriz fossem fornecidos na sequencia dita natural (i.e. porordem de linhas e dentro de cada linha por ordem de colunas) diga como poderia alterara sua estrutura e/ou a sequencia de accoes de preenchimento de forma a melhorar o custocomputacional de acesso a um elemento da matriz (sem piorar a eficiencia de ocupacao dememoria).

[0.5] d) Assuma agora que numa dada aplicacao se torna essencial que o custo de acesso seja o mais efi-ciente possıvel, embora nao se aceite uma ocupacao excessiva de memoria (i.e. nao e aceitavelutilizar uma matriz N × N). Descreva uma estrutura de dados e a sequencia de accoes quepermita armazenar e aceder de forma muito eficiente a cada um dos Nnz elementos de umamatriz.

[4.5] 11. Considere um grafo direccionado e ponderado com 10 vertices, representado por listas de ad-jacencias como indicado abaixo. Por exemplo, o vertice 3 possui uma aresta direccionada para overtice 7 e o seu custo e 2: 3 → (7; 2)

0 → (7; 3) → (2; 6) → (5; 2)1 → (6; 2) → (4; 4) → (2; 5) → (5; 7)2 → (4; 6) → (5; 6) → (6; 10) → (9; 2)3 → (7; 2) → (4; 7) → (9; 11)4 → (7; 5) → (0; 9)5 → (3; 3) → (4; 4) → (1; 7)6 → (7; 1) → (0; 5)7 → (2; 4) → (9; 7) → (8; 6)8 → (2; 1) → (3; 11) → (5; 9)9 → (8; 1) → (1; 2) → (3; 2) → (6; 4)

[3.0] a) Tomando o vertice 6 como vertice fonte, determine a SPT por aplicacao do algoritmo ade-quado.

[0.75] b) Indique qual o caminho optimo entre a fonte e o vertice 5, assim como o seu custo.

[0.75]c) Suponha que e acrescentada a aresta (8 → 4) e que o seu custo nao e conhecido com precisao.

Apenas se sabe que o custo da aresta pertence ao intervalo [a; b], com 0 < a < b < ∞. Qual ovalor de a que garante que esta aresta NAO E usada na SPT? Justifique a sua resposta deforma adequada.

[1.00] 12. Comente a seguinte afirmacao nas duas situacoes abaixo indicadas. Indique em cada caso se everdadeira ou falsa e explique porque. Se entender util, forneca exemplo(s).

“A maior aresta de um grafo so faz parte da sua MST se a sua remocao criar dois sub-grafos naoligados entre si.”

[0.75] a) Caso A: as ponderacoes de todas as arestas sao distintas.

[0.25] b) Caso B: pode haver multiplas arestas com a mesma ponderacao.

4