AED - Algoritmos e Estruturas de Dados
Licenciatura em Engenharia Electrónica
Exame de 17 de Junho de 2015 - 1a Época - Resolução
Prova escrita, individual e sem consulta. 20 valores.
NÚMERO:
NOME:
PARTE I - Questões de Escolha Múltipla
Preencha as respostas na tabela (usando apenas letras maiúsculas). Se nenhuma opção servir, escreva NENHUMA.
Se pretender alterar a sua resposta, risque e escreva ao lado a sua nova opção. Todas as questões de escolha múltipla
valem 1 valor. As questões de escolha múltipla não respondidas são cotadas com 0 valores, mas por cada resposta
errada são descontados 1/4=0.25 valores.
Questão
Resposta
1
A
2
C
3
B
4
C
5
D
6
B
7
B
8
C
1. Considere o seguinte extracto de programa em C:
#include <stdio.h>
#define N 10
int k,j,n=0;
for(k = 0 ; k < N; k++)
for(j = k + 1; j < N; j++)
n++;
printf("%d\n",n);
Indique qual a saı́da deste programa:
A.
45
B.
55
C.
60
D.
66
R. Há várias formas de chegar a este resultado. Uma forma simples é verificar que os dois ciclos
correspondem a varrer os elementos da sub-matriz triangular superior (ou inferior) de uma matrix
quadrada de N × N (ou seja, excluindo os elementos da diagonal). É simples perceber que o
resultado deve ser então (N 2 − N )/2. Note que N 2 − N são todos os elementos da matriz excepto
a diagonal, a divisão por 2 corresponde à sub-matriz indicada.
Uma forma alternativa é verificar que para k = 0 o ciclo interior é executado N − 1 vezes, para
k = 1, N − 2, etc. No total, o número de vezes que o ciclo interior é executado é dado por
(N − 1) + (N − 2) + (N − 3) + ... + 2 + 1
Isto não é mais que a soma dos elementos de uma progressão aritmética. Recordando que, no caso
deste tipo de progressão, a soma dos elementos é dada por,
M
X
k=1
ak =
a1 + aM
×M
2
E que neste caso M = N − 1, a1 = N − 1, aM = 1, resulta
M
X
k=1
ak =
(N − 1) + 1
N2 − N
× (N − 1) =
2
2
2. Considere o seguinte extracto de programa em C:
struct s {
int n;
struct s *p;
} *b = NULL,*a;
int j;
for(j=0;j<3;j++){
a = malloc(sizeof(struct s));
a->n = j-3;
a->p=b; b=a;
}
while(b!=NULL) {
printf("%d ",b ->n);
b = b -> p;
}
Indique qual a saı́da deste programa:
A.
123
B.
-3 -2 -1
C.
-1 -2 -3
D.
321
R. Os elementos são inseridos na base da lista na sequência -3, -2, -1, ficando p último elemento
na base. A listagem corresponde obviamente a −1, −2, −3.
3. Considere que uma árvore é suportada em C com a estrutura:
typedef struct tree {
char c;
struct tree*l,*r;
} Tree;
é usada para uma representação de uma árvore binária , a qual após inicializada, pode ser representada desta forma:
Admita que esta árvore é listada a partir da raiz usando a seguinte função:
void list(Tree *t){
if(t){
list(t->r);
list(t->l);
printf("%c",t->c);
}
}
Indique qual a saı́da deste programa:
A. ABCDEFG
B. ACBEGFD
C. GFEDCBA
D. DBACFEG
R. É fácil de ver que se trata de uma listagem da árvore da direita para a esquerda em ordem
pós-fixada (ou post-order). Basta olhar para um elemento para saber qual a resposta correcta...
4. Indique qual das afirmações seguintes é falsa:
√
A. N (N
+ 3)5 ∈ O(N 7 / N + 1)
√
C. N 2 N + 1 ∈ O(N 2 lg(N ))
B.
D.
√
N 2 N + 3 ∈ O(N 5/2 )
log(N 3 ) ∈ O(log N 2 )
R. . É suficiente verificar que em A. a função é de ordem O(N 6 ) e a da direita de O(N 6+1/2 ),
pelo que a afirmação é verdadeira. Em B., a função à esquerda é da ordem de O(N 2+1/2 ) =
O(N 5/2 ), pelo que a afirmação é igualmente verdadeira. Em D., basta notar que O(log(N α )) =
O(α log(N )) = O(log(N )), pelo que ambos os membros √
são da ordem de O(log(N )). Em C, descontando o factor multiplicativo N 2 , basta recordar que N cresce mais depressa que lg(N ), pelo
que a afirmação é falsa.
5. Considere uma árvore ordenada e perfeitamente balanceada de N inteiros. Considere um algoritmo
que percorre todos os nós da árvore e, em cada nó da árvore, efectua N operações.
A complexidade deste algoritmo é (deverá indicar a ordem de complexidade correspondente ao
menor dos majorantes):
A.
C.
O(N 2 log2 N )
O(N log2 N )
B.
D.
O(N )
O(N 2 )
R. É fácil verificar que se são percorridos N nós e em cada nó efectuadas N operações elementares,
a complexidade tem que ser O(N 2 ).
6. Indique qual das tabelas seguintes não pode ser um acervo:
A.
20
15
13
12
11
10
9
B.
20
15
15
13
12
16
11
C.
9
3
8
1
2
8
7
D.
9
8
3
7
6
1
2
R. . Basta representar as tabelas em forma de árvore e verificar a condição de acervo.
7. Considere uma árvore binária ordenada totalmente balanceada com 31 nós. No pior caso, o número
de nós que é preciso percorrer para saber se um determinado item se encontra na árvore é
A.
31
B.
5
C.
10
D.
1
R
R. Sendo a árvore balanceada, a altura é dada por h = (log2 (N ) + 1 = 5. O pior caso corresponde
ao nó procurado estar nas folhas terminais, em que será necessário percorrer um número de nós
igual à altura da árvore.
8. Admita que tem uma lista ordenada de inteiros, representados por uma lista simplesmente ligada.
O número médio de operações necessárias para determinar qual o nó em que se encontra um inteiro
que faz parte da lista é:
A.
N
B.
log2 N
C.
N/2
D.
log2 (N/2)
R. Se a lista tem N elementos, e a procura é feita sequencialmente, o melhor caso será 1 e e o pior
N . Em média será N/2. Nota: se fosse omitida a indicação de que o elemento faz parte da lista,
poderia haver muitas procuras de elementos inexistentes, em que o número de operações seria N .
Nestas condições não seria possı́vel estimar o valor médio.
PARTE II - Questões de Desenvolvimento
Responda às questões de desenvolvimento em folhas de exame devidamente identificadas com nome e número.
[3.0V]
9. Considere uma lista simplesmente ligada de reais suportada num tipo L definido por
typedef struct list {
float x;
struct list *next;
} L;
Escreva uma função com protótipo
float average(L *base);
que receber um apontador para a base da lista e que retorna o valor médio de todos os elementos
da lista. Nota: se a lista estiver vazia, o valor retornado deve ser 0.
R.
float average(L *b){
int n=0; float sum = 0;
if(b == NULL) return 0;
while(b != NULL){
sum += b -> x; n++;
}
return sum / n;
}
[3.0V]
10. Considere uma árvore suportada num tipo T definido por
typedef struct tree {
float x;
struct tree *left,*right;
} T;
[2.0V] a) Escreva uma função com protótipo
int
count(T *r);
que recebe como argumento um apontador para a raı́z da árvore r e que retorna o número
total de elementos na árvore.
R.
int count(Tree *t){
if(t == NULL)
return 0;
else
return count(t->l) + count(t->r) + 1;
}
[1.0V] b) Indique a complexidade do algoritmo, admitindo que a árvore tem N nós.
R. Dado que a cada nó da árvore é percorrido apenas uma vez, a complexidade é obviamente O(N ).
[3.0V]
11. O algoritmo quick sort baseia-se na noção de partição e função de partição. Considere uma função
de partição aplicada a uma tabela de inteiros com o protótipo
int partition(int a[],int l, int r)
em que l e r são os ı́ndices que indicam o primeiro e último elemento do subconjunto da tabela
que se pretende particionar.
Admita que aplicamos o algoritmo de partição a uma tabela de 12 inteiros x[] e que, após a
chamada a esta função na forma
i = partition(x,0,11);
a tabela fica organizada como se segue:
28
7
41
8
1
50
82
78
57
75
60
94
[1.0V] a) Indique o valor de i retornado pela função partition.
R. A partição divide a tabela em duas partes, em que a primeira corresponde a todos os valores
menores que um elemento pivot, e a segunda todos os valores superiores. O valor retornado
pela função é o ı́ndice pivot. É fácil verificar que i=5
[2.0V] b) Escreva uma função de ordenação baseada no algoritmo quick sort com protótipo
void quicksort(int x[],int l, int r)
e que utiliza a função partition() definida anteriormente. Nota: não é necessário escrever o
código da função partition().
R.
void quicksort(int x[],int l, int r){
int i;
if(r <= l) return;
i = partition(x,l,r);
quicksort(x,l,i-1);
quicksort(x,i+1,r);
}
[1.0]
12. Considere o seguinte algoritmos recursivo:
int xpto{int *tab, int N){
if(N<=1)
return 0;
else
return xpto(tab,N/2) + xpto(tab+N/2,N/2);
}
Admita para simplificar que N é uma potência de 2. Determine a equação de recorrência e a
complexidade da função xpto().
R.
CN = CN/2 + CN/2 = 2CN/2
com condição terminal C1 = 1. Fazendo por conveniência, N = 2k ,
C2k
=
2C2k /2 = 2C2k−1
C2k−1
=
2C2k−2
ou seja
C2k
=
4C2k−2
C2k
=
8C2k−3
C2k
=
2j C2k−j
Generalizando
Para j = k,
C2k
=
2k C20 = 2k C1 = 2k
ou seja
CN
pelo que a complexidade é O(N ).
= N
[2.0V]
13. Considere o seguinte grafo:
Determine os caminhos mı́nimos de A a todos os nós da árvore, usando o algoritmo de Dijkstra. Não
se pretende o código, apenas a explicitação da sequência de operações e testes. Nota: a resposta
só será valorizada se forem indicados todos os passos do algoritmo de Dijkstra. R.
Passo 1, Nó A=0, resta {B, C, D, E, F }
B = 2, A → B
C = 5, A → C
F = 2, A → F
Passo 2, Nó B=2 (podia rb ser o F), resta {C, D, E, F }:
B = 2, A → B
C = 3, B → C
D = 5, B → D
F = 2, A → F
Passo 3, Nó F=2, resta {C, D, E}:
B = 2, A → B
C = 3, B → C
D = 3, F → D
E = 3, F → E
F = 2, A → F
Passo 4, Nó C=3 (podia tb ser o D ou E), resta {D, E}:
B = 2, A → B
C = 3, B → C
D = 3, F → D
E = 3, F → E
F = 2, A → F
(nenhum caminho actualizado)
Passo 5, Nó D=3 (podia tb ser o E), resta {E}:
B = 2, A → B
C = 3, B → C
D = 3, F → D
E = 3, F → E
F = 2, A → F
(nenhum caminho actualizado)
Passo 6, Nó E=3, resta {}:
B = 2, A → B
C = 3, B → C
D = 3, F → D
E = 3, F → E
F = 2, A → F
(nenhum caminho actualizado)
logo
A → B, Custo = 2
A → B → C, Custo = 3
A → F → D, Custo = 3
A → F → E, Custo = 3,
A → F , Custo = 2