AED - Algoritmos e Estruturas de Dados - 2004/05, 2o Semestre
1o Teste, 5 de Maio de 2005, 20h
Duração: 2h 30mn
Prova escrita, individual e sem consulta
NOME:
NÚMERO:
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 0.25 valores. Questões de escolha
múltipla não respondidas são cotadas com 0 valores, mas por cada resposta errada são descontados 0.25/4 valores.
Questão
Resposta
1
2
3
4
5
6
1. Suponha que lhe é pedido que resolva um problema que envolve um conjunto de dados armazenados de forma
ordenada numa tabela de dimensão N . Para esse efeito desenvolve um algoritmo que realiza dois tipos de operações:
i) dado um elemento procura-o na tabela e modifica-o caso exista; ii) dado um ı́ndice modifica o elemento contido
nesse ı́ndice. Suponha que o seu algoritmo realiza 3 lg N operações do tipo i) seguido de 2N operações do tipo ii).
Suponha que cada modificação é efectuada em tempo constante. Qual é ordem de grandeza da complexidade do
algoritmo, admitindo que ele é o mais eficiente possı́vel?
A.
O(lg N )
B.
O(lg2 N )
C.
O(N lg N )
D.
O(N )
2. Considere um conjuntos de objectos, identificados por um número inteiro, aos quais se aplica o algoritmo de conectividade de união rápida (“quick union”). Considerando a tabela que resulta do processamento dos pares de
objectos indicados em baixo, indique quantas comparações no máximo serão necessárias para efectuar a procura de
qualquer elemento de um próximo par (ou seja quantos testes do tipo id[p]==p serão realizados).
5 − 3,
2 − 7,
A.
3 − 9,
6 − 5,
1
B.
0 − 7,
3 − 6,
3
9 − 4,
C.
0−4
4
D.
2
3. Suponha que num dado passo do algoritmo de ordenação de shellsort se ordenaram os dados constantes numa tabela
com um dado valor de h. Se o estado da tabela for o indicado abaixo, qual é o menor valor de h que pode ter sido
utilizado?
1 1 2 3 2 4 6 8 5 7
A.
h=1
B.
h=2
C.
h=3
D.
h=4
4. Considere a seguinte tabela (1a linha) sobre a qual são listados os passos executados por um algoritmo de ordenação
(restantes linhas). Qual foi o algoritmo usado?
0
0
0
0
0
0
0
6
6
2
2
2
2
2
3
3
3
3
3
3
3
2
2
6
6
4
4
4
7
7
7
7
7
5
5
9
9
9
9
9
9
5
5
5
5
5
5
7
7
4
4
4
4
6
6
6
8
8
8
8
8
8
8
5
5
5
5
5
5
9
A.
B.
C.
D.
1
Inserção
Selecção
Shellsort (h=3, 2, 1)
Bubble sort
5. Seja uma tabela de dispersão, de dimensão M = 11, na qual é armazenada a seguinte sequência de números:
563, 719, 233, 447, 134. Assuma que a função de dispersão utilizada calcula o resto da divisão inteira por M e que
as colisões são resolvidas por encadeamento numa lista. Para os números indicados quantas colisões (c) foram
detectadas e qual é o comprimento (número de elementos) da maior lista (L)?
A.
c = 5, L = 5
B.
c = 2, L = 2
C.
c = 2, L = 3
D.
c = 3, L = 2
6. Considere o grafo representado na figura à direita e indique qual das afirmações seguintes é verdadeira
A
B
C
D
O nó do grafo com maior grau tem grau 5
e o grafo é bipartido.
O grafo é ligado e completo.
O grafo é ligado
e o nó do grafo com maior grau tem grau 5.
O grafo é completo e bipartido.
PARTE II - Questões de Desenvolvimento
Responda às questões de desenvolvimento em folhas de exame devidamente identificadas com nome e número.
[1.0val] 7. Considere a recorrência seguinte: CN = 4CN/4 + 1.
Em função de N , determine qual a ordem de grandeza de CN (ou seja determine f (N ) tal que CN ∈ O(f (N )).
Indique todos os passos da sua derivação. (Sugestão: faça N = 4n e resolva a recorrência resultante)
[2.0val] 8. Considere uma lista de elementos tal que a informação contida em cada elemento da lista é composta por um
número inteiro e um apontador para o próximo elemento da lista. Assuma que os elementos da lista são do tipo
Element, indicado de seguida:
typedef struct ListElement {
int value;
struct ListElement *next;
} Element;
[1.5val] a) Pretende implementar-se em C uma função que, receba dois apontadores para o topo de duas listas deste tipo
e retorne um apontador para uma nova lista resultante da junção e ordenação crescente daquelas. O critério
de ordenação a utilizar é o valor do inteiro contido em cada elemento da lista. Assume-se que as duas listas
de entrada estão também ordenadas de forma crescente. A função deve ser não destrutiva em relação às listas
que recebe (isto é não pode alterar essas listas de forma alguma, pelo que terá de construir a nova lista)!
Use a seguinte assinatura para a função pretendida:
Element* Merge and Sort Lists(Element *head1, *head2);
em que head1 e head2 são os ponteiros para o topo das duas listas de entrada.
[0.5val] b) Supondo que cada uma das listas apontadas por head1 e head2 tem comprimento N , qual é a complexidade
do código desenvolvido em a)? Justifique.
[1.5val] 9. Suponha que se pretende resolver o problema de saber quantos elementos estão repetidos numa tabela de N
elementos de tipo inteiro.
[1.0val] a) Considere o seguinte algoritmo para resolver o problema: para cada elemento percorre-se toda a tabela procurando se existe, ou não, algum duplicado desse elemento. Em função de N indique, justificando, uma expressão
para a complexidade deste algoritmo em termos do número de operações efectuado.
[0.5val] b) É possı́vel melhorar a eficiência do algoritmo anterior pré-processando de forma conveniente os elementos da
tabela. Com os conhecimentos adquiridos na disciplina, descreva um algoritmo que implemente uma estratégia
mais eficiente que a da alı́nea anterior e indique, justificando, uma expressão para a complexidade do novo
algoritmo.
2