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

Recurso, 1999/2000, 25/7/2000

1/

Erros:

linha 4: não é necessário template <..> já que o tipo T nunca mais é usado

linha 7: tirar void da declaração do construtor inicializador no "cabeçalho" da função;  ordem das atribuições está errada (linha 8)
         serieGeometrica (double a0, double r = 1) : elem0(a0), razao(r) {}

linha 9: a função-membro elem() deve retornar um double
         double elem(int i) const

linha 16: as variáveis devem ser declaradas antes de serem usadas
          double a0, r; int n; cin >> a0 >> r >> n;

linha 17: se o erro da linha 4 não foi detectado, a declaração de s  está errada já que não especifica T

linha 18: incremento de i está errado;  valor inicial de i errado (i>=1)
          for (int i = 1; i <= n; i=i+1)

Saída:

a1=1
a2=2
a3=4
a4=8

Se o valor inicial de i não for ajustado (linha 18) a saída anterior é precedida de uma linha com
a0=0.5

2/

template<class T>
Chain<T>::Chain(const Chain<T> & C)
{
  first=0;
  ChainNode<T> * auxiliar=C.first;
  int i=0;
  while(auxiliar)
  {
    Insert(i,auxiliar->data);
    i++;
    auxiliar=auxiliar->link;
  }
}

3/

template<class T>
int BinarySearchTree<T>::ContaIntervalo(const T & inferior, const T & superior)
{
  return containtervalo(root,inferior,superior);
}

template<class T>
int BinarySearchTree<T>::containtervalo(BinaryNode<T> * t, const T & inferior, const T & superior)
{
  int count=0;
  if(t)
  {
    if(t->data > inferior && t->data < superior) count++;
    if(t->data > inferior) count+=containtervalo(t->left,inferior,superior):
    if(t->data < superior) count+=containtervalo(t->right,inferior,superior);
  }
  return count;
}

ou, em alternativa (menos eficiente porque não tira partido da árvore ser uma árvore binária de pesquisa):

template<class T>
int BinarySearchTree<T>::ContaIntervalo(const T & inferior, const T & superior)
{
  return containtervalo(root,inferior,superior);
}

template<class T>
int BinarySearchTree<T>::containtervalo(BinaryNode<T> * t, const T & inferior, const T & superior)
{
  if(!t) return 0;
  if(t->data > inferior && t->data < superior)
     return 1 + containtervalo(t->left,inferior,superior) + containtervalo(t->right,inferior,superior);
  return containtervalo(t->left,inferior,superior) + containtervalo(t->right,inferior,superior);
}

4/

Usar uma árvore de pesquisa binária em que cada nó contém a palavra e o número de ocorrências respectivo.
Para cada palavra verificar se existe na árvore; se existir, incrementar o seu contador; se não existir inseri-la com contador = 1.
Árvore de pesquisa: pesquisa logarítmica;  ordem alfabética => percorrer árvore em-ordem e imprimir
Sendo n o número de palavras distintas e N o número total de palavras temos complexidade espacial: O(n) e complexidade temporal: O(N lg n)

Alternativas:
1) tabela de dispersão: acessos mais rápidos mas não permite obter as palavras por ordem alfabética; (opção: copiar para vector e ordenar)
2)lista ordenada: pesquisa/inserção de um elemento é linear => O(N ^2) (alternativa inferior)