Resolução de Prova de Avaliação:
1ª Chamada, 1999/2000, 16/6/2000
1/
Erros:
2/
// formula-based queue iterator implementation, classe members
template<class T>
class Queue {
public:
// ...
int initIterator(T & element);
int next(T & element);
private:
// ...
int current; // current iterator
position
};
template<class T>
int Queue<T>::initIterator(T & element)
{
if (front == rear)
return 0; // empty queue
current= 1;
element= queue[(front + 1) % MaxSize];
return 1;
}
template<class T>
int Queue<T>::next(T & element)
{
if ((front + current) % MaxSize == rear)
return 0; // current is the
last
++current;
element= queue[(front + current) % MaxSize];
return current;
}
3/
// RemoveLeafs, resolução 1
template<class T>
class BinaryTree {
public:
// ...
BinaryTree<T> & RemoveLeafs()
{if (root) root= removeLeafs(root); return *this;}
private:
// ...
BinaryTreeNode<T> * removeLeafs(BinaryTreeNode<T>
* t);
};
// remove folhas da sub-árvore apontada por t; devolve apontador
para a
// sub-àrvore modificada (t ou 0 no caso de ser folha).
template<class T>
BinaryTreeNode<T> * BinaryTree<T>::removeLeafs(BinaryTreeNode<T>
* t)
{
//if (!t) return 0; // empty tree
if (!t->LeftChild && !t->RightChild) { // a leaf
delete t;
return 0;
}
if (t->LeftChild) // left child
t->LeftChild= removeLeafs(t->LeftChild);
if (t->RightChild) // right child
t->RightChild= removeLeafs(t->RightChild);
return t;
}
// RemoveLeafs, resolução 2
template<class T>
class BinaryTree {
public:
// ...
BinaryTree<T> & RemoveLeafs()
{removeLeafs(root); return *this;}
private:
// ...
void removeLeafs(BinaryTreeNode<T> *&
t);
};
// remove folhas da sub-árvore apontada por t (passado por
referência); anula
// apontador para a sub-àrvore modificada no caso de ser
folha.
template<class T>
void BinaryTree<T>::removeLeafs(BinaryTreeNode<T> *&
t)
{
if (!t) return; // empty tree
if (!t->LeftChild && !t->RightChild) { // a leaf
delete t; // free space
t= 0;
// anula apontador
return;
}
if (t->LeftChild) // left child
removeLeafs(t->LeftChild);
if (t->RightChild) // right child
removeLeafs(t->RightChild);
return;
}
4/
Uma vez que os dados de entrada (registos de nascimento) estão
ordenados por ordem não decrescente de datas de nascimento, os
descendentes de uma pessoa vão aparecer depois da própria
pessoa. Assim, não é necessário guardar todos os registos de
nascimento em memória.
Algoritmo possível:
1. Inicializar W (conjunto de trabalho) com o nº de assento de nascimento da pessoa cujos descendentes se pretendem determinar.
2. Enquanto existirem registos de nascimento a ler:
2.1. Ler o próximo registo de nascimento
2.2. Se o nº de assento de nascimento do pai ou da mãe existir em W (o que quer dizer que a pessoa nascida é um descendente),
2.2.1. Escrever no ecrã os dados da pessoa nascida (nº de assento de nascimento, nome, local e data da nascimento)
2.2.2. Inserir em W o nº de assento de nascimento da pessoa nascida.
Estruturas de dados:
O conjunto W pode ser implementado eficientemente por uma tabela de
"hash", porque as únicas operações necessárias (inserir e verificar se
existe) podem ser efectuadas em tempo O(1).
Há o problema de dimensionamento da tabela de hash, para o qual se
podem definir duas soluções:
1. Supôr que o tamanho da lista de entrada aparece antes da lista
propriamente dita (o que altera ligeiramente o enunciado). Nesse caso
dimensiona-se a tabela de acordo com esse tamanho.
2. Dimensionar a tabela de "hash" para um tamanho pré-definido
(exemplo: 1000), e redimensionar para o dobro do tamanho actual cada
vez que a taxa de ocupação da tabela atinge um valor elevado (exemplo:
80%). O nº de redimensionamentos é limitado por O(log n), em que n é o
nº de registos de nascimento, e o tempo de cada redimensionamento é
limitado por O(n), pelo que o tempo total com os redimensionamentos é
limitado por O(n log n).
Complexidade temporal
O tempo para ler os registos de entrada é de ordem O(n), em que n é o
nº de registos de nascimento. O tempo para escrever os dados na saída
também é limitado por O(n). O nº de inserções em W é n no pior
caso. Usando uma tabela de hash, o tempo de cada inserção é O(1), pelo
que o tempo gasto com todas as inserções é O(n) no pior caso. O nº de
procuras em W é 2n no pior caso. Usando uma tabela de hash, o tempo de
cada procura é O(1), pelo que o tempo gasto com todas as inserções é
O(n) no pior caso. Assim, o tempo total é O(n)¸ sem entrar em conta
com os eventuais redimensionamentos da tabela de hash.
Complexidade espacial
Será de O(max(n,m)) em que m é o tamanho inicial da tabela de hash.