Prova de Avaliação:

Recurso, 1999/2000, Duração: 2 horas, Com Consulta, 10/7/2000

Pergunta 1, [5 valores]

Considere o seguinte programa em C++:

1 #include <iostream.h>
2 #include <math.h>
3
4 template <class T>
5 class serieGeometrica { // série do tipo ai=a0 r^i-1
6   public:
7     void serieGeometrica(double a0, double r = 1)
8       { a0 = elem0; r = razao; }
9     void elem(int i) const
10       { return elem0 * pow(razao, i - 1); }
11     const double elem0, razao;
12 };
13
14 int main()
15 {  cout << "a0 r n? ";
16    cin >> double a0 >> double r >> int n;
17    serieGeometrica s (a0, r);
18    for (int i = 0; i <= n; i+1)
19       cout << 'a' << i << '=' << s->elem(i) << '\n';
20    return 0;
21 }

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, supondo que o utilizador introduz  1  2  4.

Pergunta 2, [6 valores]

Retome a classe Chain, usada para representar listas de forma ligada. Escreva um construtor de cópia para esta classe, isto é, um construtor que tem como argumento um objecto do mesmo tipo Chain (passado por referência só para consulta) e que inicializa o objecto que está a ser construído com uma cópia do objecto passado como argumento.

Pergunta 3, [5 valores]

Retome a classe BinarySearchTree, usada para representar e processar árvores binárias de pesquisa de forma ligada. Escreva uma função-membro ContaIntervalo que retorna o número de nós que têm um valor compreendido entre dois limites (inferior e superior) especificados como argumentos da função. Pode criar funções auxiliares.

Pergunta 4, [4 valores]

Suponha que se pretende escrever um programa em C++ que lê do standard input um texto e determina a frequência de ocorrência de cada palavra nele contida.  O programa deve escrever no standard output as palavras e respectivas frequências, por ordem alfabética (como num dicionário). A frequência de ocorrência de uma palavra é a razão entre o número de vezes que essa palavra surge no texto e o número total de palavras.
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, justificando, qual seria a complexidade temporal e espacial desse programa.