Resolução do Exame de Recurso, 20/7/2001

linha 9: public:  carta(P valor, N pinta) {this->valor=valor;naipe=pinta;}


linha 11: carta<P,N> & max(const carta<P,N> & C)


linha 13: return valor > C.valor ? *this : C; 

Saida do programa (aparece escrito no monitor):


        11 de 4
        rei de paus
        Cartas de naipes diferentes !

main() {
  LinkedStack<int> st;
  int x;
  cout << "Escreva os valores (terminar com 0)" << "\n";
  cin >> x;
  while (x!= 0) {
    st.Add(x);
    cin >> x;
  }
  while (!st.IsEmpty()){
    st.Delete(x);
    cout << x << " ";
  }
  return 0;
}

template<class T>
class BinaryTree {
  public:
    BinaryTree() {root=0;}
      ...
    void Acumula() {Acumula(root);}
  private:
    BinaryTreeNode<T> *root;
      ...
    void Acumula(BinaryTreeNode<T> *t);
};      

template<class T> 
void BinaryTree<T>::Acumula(BinaryTreeNode<T> *t) 
{
   if (t) {
   Acumula(t->LeftChild);
   Acumula(t->RightChild);
   if (t->LeftChild)
      t->data += t->LeftChild->data;
   if (t->RightChild)
      t->data += t->RightChild->data;
   }
};

a)
Poderíamos utilizar uma matriz de n x n, sendo n o n.º de cidades. Em cada célula da matriz teríamos a distância da cidade i (linha) à cidade j (coluna). A complexidade espacial desta estrutura seria S(n2).

Poderíamos também utilizar uma tabela de hash cuja chave seria o nome da cidade. Cada célula da tabela de hash corresponderia a uma cidade que teria um apontador para uma lista ligada com as distâncias às restantes cidades. As chaves e as listas ligadas teriam que estar ordenadas da mesma forma. Se a ordem fosse igual à do exemplo, a primeira distância ligada a Londres, cujo índice é 2, seria a distância correspondente à cidade cujo índice é igual a n-2-1=3 (sendo n o n.º de cidades), ou seja Madrid.

b)
Para a representação em matriz (mat) teríamos o seguinte algoritmo:

Para x = 1..n
   Para y = i+1 .. n
      Para z = j+1 .. n
         Se (mat[x][z] >= mat[x][y] + mat[y][z] ou
                mat[x][y] >= mat[x][z] + mat[z][y] ou
                mat[y][z] >= mat[y][x] + mat[x][z] ) então
            escreve Existe inconsistência em x,y,z 
      fim Para
   fim Para
fim Para