Faculdade de Engenharia da Universidade do Porto
Licenciatura em Engenharia Electrotécnica e de Computadores
Algoritmos e Estruturas de Dados, 1998/99

Prova de Avaliação:

TESTE-EXEMPLO     DURAÇÃO: 2 horas     COM CONSULTA     DATA: 9/6/1999

1. [5 valores] O que é que aparece escrito no ecrã quanto é executado o seguinte programa em C++?

#include <iostream.h>

template <class T, int n>
class Histograma { public: T h[n]; void mostra(); };

template <class T, int n>
void Histograma<T,n>::mostra()
{
   for (int i = 0; i < n; i++) {
       for (int j = h[i]; j > 0; j--) cout << '*';
       cout << '\n';
   }
}

main()
{
   Histograma<int,5> h = {1, 2, 3, 2, 1};
   h.mostra();
   return 0;
}

2. [6 valores] Escreva uma função DeleteDups, a acrescentar à classe LinearList (representação de lista linear baseada em array) estudada nesta disciplina, que elimina elementos repetidos da lista, supondo que a lista já está ordenada por ordem não decrescente. A função não retorna nada.

3. [6 valores]Escreva uma função CountLevel, a acrescentar à classe BinaryTree estudada nesta disciplina, que calcula e retorna o número de nós de nível n existentes numa árvore binária, em que n é um argumento da função.

4. [3 valores] Pretende-se escrever um programa em C++ que lê um texto e imprime uma lista com o número de ocorrências de cada palavra que aparece no texto, ordenada por número de ocorrências decrescente. Palavras com o mesmo número de ocorrências são listadas por ordem de aparição. Para simplificar o problema, considere que o texto apenas contém palavras consituídas por letras minúsculas e espaços a separar palavras, e que não há palavras com mais do que 20 caracteres.
Exemplo de entrada de dados: