Resolução da 2ª chamada, 6/7/2001

#include <iostream.h>
template <class T> class Variavel {
private:
  char nome[20];
  T valor;
public:
  template <class T2> Variavel(const char *nm, const T2 & val)
  { strcpy(nome, nm) /*1*/; Write(val); }
  const char *GetNome () const /*2*/
  { return nome; }
  template <class T2> T2 Read(T2 & val) const
  { val = (T2) valor; return val; /*3*/}
  template <class T2> void Write(const T2 & val) /*4*/
  { valor = (T) val; }
};
main()
{ Variavel<int> x ("x", 10.5);
  Variavel<double> * y = new Variavel<double>("y", 10.5); /*5*/
  double d;
  cout << x.GetNome() << "=" << x.Read(d) << "\n"; /*6*/
  cout << y->GetNome() << "=" << y->Read(d) << "\n"; /*7*/ /*8*/
  return 0;
}

x=10
y=10.5

template<class>
LinearList<T> & LinearList<T>::removeDups()
{
  if (IsEmpty()) 
    return *this;
  for (int i=0; i<length; i++)
    for (int j=i+1, new_len=i+1; j<length; j++) {
      if (element[i]!=element[j])
        element[new_len++]=element[j];
      length=new_length;
    }
  return *this;
}

include<iostream.h>
#include"BinarySearchTree.h"
main()
{
   BinarySearchTree<int> A(0);
   unsgned int x;
   cout << "Introduza os numeros inteiros positivos. Para acabar introduza 0.";
   cin >> x;
   while(x)
   {
      A.insert(x);
      cout >> "valor: ":
      cin >> x;
   }
   // escreve no stdout os valores por ordem decrescente
   while(!A.IsEmpty())
   {
      x= A.findMax();
      cout << "x ; ";
      A.remove(x);
   }
   return 0;
}

O programa efectua o seu trabalho em duas fases.

Na primeira, lê o ficheiro de departamentos e constrói uma tabela de dispersão (hash table) em que a chave é o número do departamento e os dados são o nome. A leitura do ficheiro é feita linha a linha.
Alternativa: se assumirmos que os números dos departamentos são limitados (p.ex. inferiores a 100) podemos substituir a tabela de dispersão por um vector de "strings" em que o índice do vector corresponde ao número do departamento.
Em qualquer dos casos, o acesso ao nome do departamento tem complexidade temporal O(1); a complexidade espacial é O(N), em que N é o número de departamentos.

Na segunda fase, o programa lê o ficheiro de funcionários linha a linha; para cada linha produz IMEDIATAMENTE a linha correspondente do ficheiro de saída. Essa linha contém os três campos do ficheiro de funcionários mais o nome do departamento retirado da tabela construída na primeira parte (se o nome do departamento não constar da tabela, usar "??").
Complexidade espacial: O(1) porque apenas precisamos de espaço para processar uma linha.
Complexidade temporal: O(M) em que M é o número de funcionários.

Globalmente:
Complexidade espacial: O(N)+O(1) = O(N)
Complexidade temporal: O(N+M); para N >> M (que é a situação mais provável), O(M).