Resolução de Prova de Avaliação:

1ª Chamada, 1999/2000, 16/6/2000

1/
Erros:

1. Linha 6: Não se indica tipo de retorno (void) no construtor.
2. Linha 7: Membros-constantes (limiteInf e limiteSup) não podem ser inicializados no corpo do constructor, mas sim no cabeçalho. A linha pode ficar então:
   : limiteInf (inf), limiteSup(sup) {}
3. Linha 17: Deve ser new Intervalo<int> em vez de new Intervalo.
4. Linha 19: Ilegal, porque limiteSup é privado e, além disso, é constante. Uma solução é escrever:
   b = Intervalo(0, 2);
5. Linha 21: Uma vez que c é um apontador, tem de se escrever c->Output em vez de c.Output.
6. Linha 22: Uma vez que c contém o endereço de um objecto isolado em vez de um array, deve-se escrever delete c em vez de delete [] c.

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.