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

//pergunta 1, 1a. chamada, 1998/99, NC
   12:0:0
   15:30:30
   15:30:30
// h1 é um objecto da classe Hora, iniciado com os valores por omissão
// (12 horas, 0 minutos e 0 segundos), que não são alterados no resto do
// programa; o objecto h2 é iniciado com 14 horas, 0 minutos e 0
// segundos; a função Incrementa retorna o próprio objecto h2, depois
// de ter sido incrementado de 0 horas, 90 minutos e 30 segundos;
// após o incremento, h2 fica com 15 horas, 30 minutos e 30 segundos.
// h3 é uma referência para h2, portanto h3.Mostra() é o mesmo que
// h2.Mostra()

//pergunta 2, 1a. chamada, 1998/99, MTA
template<class T>
int Chain<T>::CountDistinct() const
{
  if(!first)
     return 0;      // lista vazia
  int distintos=1;  // pelo menos 1 elemento distinto
  ChainNode<T>* current= first;
  T last= current->data;
  while(current->link)
  {
    current= current->link;  // proximo
    if (current->data != last)
    {
       distintos++;
       last= current->data;
    }
  }
  return distintos;
}

//pergunta 3, 1a. chamada, 1998/99, MTA
template<class T>
int BinaryTree<T>::CountLeaves() const
{
   return ContaFolhas(root);
}
template<class T>
int BinaryTree<T>::ContaFolhas(BinaryTreeNode<T> * t)
{
  if (!t) return 0;
  if (!(t->LeftChild || t->RightChild)) return 1;
  return ContaFolhas(t->LeftChild) + ContaFolhas(t->RightChild);
}

//pergunta 4, 1a. chamada, 1998/99, JAS

1. ALGORITMO
Para descrever o algoritmo podemos começar por recorrer às seguintes estruturas de dados, muito genéricas:

L(T): dado de entrada; conjunto de tarefas dependentes da tarefa T (que se podem iniciar logo que T termine)
S: conjunto de tarefas em execução num determinado instante, contendo, para cada tarefa, o instante em que ela terminará

2. ESTRUTURAS DE DADOS
Caracterizando melhor cada uma das estruturas, poderíamos ter:

S: Fila de tarefas em execução (ou seja, que aguardam terminação), ordenadas pelo tempo de terminação, isto é, uma espécie de fila com prioridades.
Cada tarefa seria descrita através de uma estrutura constituída por 2 campos: nº da tarefa e tempo em que a tarefa termina.
Duas operações fundamentais a realizar sobre S seriam: inserir uma tarefa e extrair a tarefa que termina mais cedo. A inserção deve ser feita de forma a manter a fila ordenada com base no tempo de terminação, de modo a que a tarefa que termina mais cedo esteja sempre à cabeça da lista.
L: Array [1..NumTarefas] de tarefas a executar, contendo, para cada tarefa, a sua duração e as tarefas dela dependentes. Dado que o número de tarefas dependentes é variável, estas deveriam ser representadas usando uma lista ligada. Cada elemento do array conterá, além da duração da tarefa, um apontador para o primeiro elemento da lista ligada respectiva.