UNIVERSIDADE DO ALGARVE
Faculdade de Ciências e Tecnologia
Departamento de Engenharia Electrónica e Informática
Estruturas de dados (2004/2005)
Licenciaturas em Engenharia de Sistemas e Informática, Ensino de Informática e Informática
Exame época recurso
21 de Julho 2005
Duração: 2h00m
Ao longo do enunciado considere o array de inteiros: int ai[ ] = { 4, 6, 2, 5, 1, 3, 7 };
1.
a) (0.5v) Explique o que é impresso pelo seguinte segmento de código:
int i;
for (i=0; i<7; i+=2) printf ("%d ", *(ai+i));
b) (0.5v) Quais as alterações e efectuar ao código acima para que sejam impressos os
elementos de índice impar do array ai, isto é: 6 5 3
2.
a) (1.25v) Implemente uma função que reserve memória dinamicamente para um array de n
inteiros, e retorne um ponteiro para esse array ou NULL em caso de insuficiência de
memória. Indique pré-condições e excepções se necessário.
b) (1v) Escreva um segmento de código que reserve memória dinamicamente para um array
de 7 inteiros e copie para esse array os elementos do array ai pela mesma ordem.
3. Neste exercício considere que lista refere-se a uma lista simplesmente ligada de inteiros.
a) (0.75v) Declare um ponteiro e uma estrutura que permitam referenciar um nó da lista.
b) (1.5v) Escreva um segmento de código que crie uma nova lista, copiando os elementos do
array ai para essa lista pela mesma ordem.
c) (1v) Escreva um segmento de código que remova da lista criada na alínea anterior (e da
memória) o 2º nó, isto é o nó cujo elemento é o número 6.
d) Supondo que se pretende implementar um stack baseado numa lista:
i. (1v) Em que ponto da lista se devem fazer as operações de inserção e remoção de
elementos de modo que o tempo de execução destas seja constante e o menor possível?
Justifique.
ii. (1v) Implemente a função int STACKtop (link s), que retorna (mas não elimina) o
elemento no topo do stack s.
e) (1v) Supondo que existe um ponteiro para o ultimo nó da lista, identificado por plast,
escreva uma função que adicione em tempo constante, um nó já existente ao fim da lista.
4. Pretende-se implementar o ADT com suporte para múltiplas instâncias Date, para manipulação de
datas de acordo com o calendário Gregoriano. Cada instância guarda uma data em 3 inteiros: o dia,
o mês e o ano. Considerando que no ficheiro date.h será declarado o interface do ADT e o ficheiro
date.c terá a implementação, escreva todo o código necessário (incluindo protótipos de funções),
nos ficheiros correctos, de acordo com:
Exame época recurso ED 2004 / 2005 - 1/2
a) (0.75v) Estrutura do ADT e ponteiro para esta (identificado por Date). A estrutura contém
3 inteiros para guardar o dia, mês e ano.
b) (1.25v) Supondo que está disponível a função void sysdate (int *day, int *month, int
*year) que retorna nos seus argumentos a data actual do sistema, declare e defina a função
Date DATEnow (void) que cria uma nova instancia deste ADT e que retorna um ponteiro
para esta ou NULL no caso de insuficiência de memória.
c) (1v) Declare e defina a função void DATEprint (Date d) que escreve na consola a
instância d no formato: dia / mes / ano. Indique pré e pós condições se necessário.
d) (0,75v) Escreva um segmento de código que usando este ADT mostre no monitor a data
actual do sistema
e) (0.75v) Proponha uma estrutura alternativa para o ADT que permita poupar memória no
armazenamento do dia, mês e ano.
5. Seja a definição de um nó numa árvore binária:
typedef struct node *link;
struct node { int item; link left, right; };
a) (1.5v) Supondo que está disponível a função:
/* Descrição: se root == NULL é criado o nó raiz da árvore com o item t,
senão um novo nó com o item t é adicionado à árvore binária de pesquisa
com raiz root, onde o item do filho esquerdo é menor que o item do pai
e o item do filho direito é maior ou igual que o item do pai.
POS: Adiciona novo nó à árvore de pesquisa e retorna a raiz da árvore */
link btree (link root, int t);
escreva um segmento de código que percorra o array ai desde o índice 0 para o final, e
adicione cada elemento do array a uma árvore binária de pesquisa (inicialmente vazia).
b) (0.75v) Represente esquematicamente a árvore binária de pesquisa criada na alínea anterior.
c) (1v) Implemente uma função que retorne a altura de uma árvore binária. Considere que uma
árvore com apenas um nó, a raiz, tem altura 0.
6. Considere o código do algoritmo de ordenação Quicksort para inteiros:
void qs(int* a, int n){
int i;
int partition (int *a, int n) {
/* ... */
if (n<2) return;
i=partition(a, n);
qs(a, i);
qs(a+i+1, n-i-1);
}
}
a) (0.75v) Modifique o algoritmo de modo que se os elementos numa partição forem menores
que 10 sejam ordenados pela função: void selection (int *a, int n).
b) (1.25v) Seja a função void swap (int *a, int *b) que troca o valor dos seus dois
argumentos, defina a função: void selection (int *a, int n), que implementa o algoritmo de
ordenação por selecção.
c) (0.75) O algoritmo de ordenação por selecção é adequado para ordenar colecções guardadas
em ficheiros (por exemplo no disco rígido). Porquê?
Exame época recurso ED 2004 / 2005 - 2/2