Prova de Avaliação:

1ª Chamada, 1999/2000, Duração: 2 horas, Com Consulta, 16/6/2000

Pergunta 1, [5 valores]

Considere o seguinte programa em C++:

1 #include <iostream.h>
2
3 template <class T>
4 class Intervalo {
5   public:
6       void Intervalo(T inf = 0, T sup = 0)
7         { limiteInf = inf; limiteSup = sup; }
8       void Output() const
9         { cout << "[" << limiteInf << "," << limiteSup << "]\n"; }
10   private:
11       const T limiteInf, limiteSup;
12 };
13
14 main()
15 {
16     Intervalo<float> a(1.0, 2.5), b;
17     Intervalo<int> *c = new Intervalo(1, 5);
18     a.Output();
19     b.limiteSup = 2;
20     b.Output();
21     c.Output();
22     delete [] c;
23     return 0;
24 }

Identifique claramente e corrija os erros contidos neste programa (para cada erro, basta indicar a linha que contém o erro, descrever o erro e rescrever a linha corrigida).  Apresente ainda os resultados da execução do programa corrigido.
 

Pergunta 2, [6 valores]

Considere o tipo de dados abstracto Queue (fila) e a sua implementação baseada em fórmula na classe Queue, estudados nesta disciplina.
Adicione a esta classe os seguintes membros para implementar um iterador:

• um membro-dado privado, current, que indica qual é o elemento corrente do iterador (usado pelas duas funções seguintes);
• um membro-função público initIterator, que devolve, através de um argumento passado por referência, o elemento à cabeça da fila (front); esta função retorna a posição desse elemento na fila (1) e no caso da fila estar vazia a função retorna 0;
• um membro-função público next,  que devolve, através de um argumento passado por referência, o próximo elemento da fila; a função retorna a posição desse elemento na fila (a começar em 1 para o elemento à cabeça da fila); no caso de não existir próximo elemento, a função retorna 0.

Escreva uma função removeLeafs a acrescentar, como membro público, à classe BinaryTree para remover todas as folhas da árvore. A função deve retornar uma referência para a árvore modificada. Se for conveniente, pode escrever funções auxiliares.
Exemplo:

1. árvore antes de remover as folhas 
   
2. árvore depois de remover as folhas
   

Pergunta 4, [4 valores]

Pretende-se escrever um programa em C++ que lê do standard input a identificação de uma pessoa (nº de assento de nascimento) seguida de uma lista (possivelmente extensa) de registos de nascimento e escreve no standard output a identificação de todos os seus descendentes (determináveis a partir dos registos de nascimento).
Cada registo de nascimento tem um número de assento de nascimento (único), o nome da pessoa, a data de nascimento, o local de nascimento, o número de assento de nascimento do pai e o número de assento de nascimento da mãe.
A lista de registos de nascimento lida pelo programa encontra-se ordenada por ordem não decrescente de datas de nascimento.
Diga que estruturas de dados e algoritmos estudados nesta disciplina (ou construídos a partir deles), seriam adequados para resolver este problema de forma eficiente e apresente uma breve justificação das escolhas efectuadas.
Indique também a complexidade temporal e espacial do programa resultante.