Prova de Avaliação:

2ª Chamada, 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 template <class T>
3 class rectangle
4 { private:
5     const T length, height;
6     T position[2] = {0, 0};
7   public:
8     rectangle(T lengthRect = 1, T heightRect = 1)
9     { length = lengthRect; height = heightRect;
10       setPosition();
11     }
12     T Area() const
13     { Area = height * length; }
14     T & setPosition(T x=0, T y=0) const
15     { position = {x, y};
16       return this;
17     }
18 };
19
20 main()
21 { rectangle<int> R1(2), R2[2];
22   rectangle<double> R3;
23   R2.setPosition(1, 3);
24   R1.height++;
25   R3 = R1;
26   cout << "Area(R1)=" << Area(R1) << "\nArea(R3)=" << Area(R3) << endl;
27   return 0;
28 }

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.

Pergunta 2, [6 valores]

Considere a implementação de uma calculadora de stack para operadores aritméticos binários. Neste tipo de calculadora, os operandos são introduzidos antes do respectivo operador.  Por exemplo, a série de dados 2.3 4.5 + 3.0 2.0 - *   significa (2.3 + 4.5) * (3.0 - 2.0) e tem como resultado 6.8. Assuma que a série de dados introduzida pelo utilizador é armazenada numa fila do tipo Queue<CalcElem>, em que Queue é o tipo de dados estudado nas aulas e CalcElem é a classe definida parcialmente da seguinte forma (apenas são indicados os protótipos dos membros públicos relevantes para este exercício):

class CalcElem { // Elemento de expressão aritmética (número ou operador)
 public:
  bool IsOperator();// Retorna true se é operador e false se é número
  double Number();  // Devolve o número (supondo que é número)
  char Operator();  // Devolve símbolo do operador (supondo que é operador)
 // ...
};

Assuma ainda que é dada uma função calc_bin_op  para efectuar o cálculo associado a um operador binário, cujo protótipo é:

double calc_bin_op(char op, double arg1, double arg2);

Escreva uma função CalcStack que, recebendo como argumento uma referência à fila com a série de dados (já preenchida), calcula e retorna o resultado final (do tipo double). Deve recorrer à função calc_bin_op e deve usar um objecto local do tipo Stack<double> para armazenar os valores temporários dos cálculos.

Sugestão: Para cada elemento retirado da fila, a função CalcStack deve proceder da seguinte forma: se é um número, acrescenta-o à stack; se é um operador, extrai os dois últimos valores do topo da stack, calcula o resultado de aplicar o operador a esses valores e coloca esse resultado na stack. No final, a stack deve ter um único valor que é o resultado final pretendido. No exemplo acima, aconteceria o seguinte:
 

próximo elemento da fila	acção a tomar
2.3	coloca na stack
4.5	coloca na stack
+	extrai dois últimos valores da stack e colocana stack a soma (i.e. 6.8=2.3+4.5)
3.0	coloca na stack
2.0	coloca na stack
-	extrai dois últimos valores da stack e colocana stack a diferença (i.e. 1.0=3.0-2.0)
*	extrai dois últimos valores da stack e colocana stack o produto (i.e. 6.8=1.0*6.8)
não há	extrai o valor da stack e terminaretornando esse valor (6.8)

Pergunta 3, [5 valores]

Retome o tipo de dados BinaryTree, usado para representar e processar árvores binárias de forma ligada. Acrescente um membro-função público denominado Mirror que, sem receber qualquer argumento, transforma a árvore noutra que lhe é simétrica em termos de estrutura, conforme o desenho em baixo. Esta função deve retornar uma referência à própria árvore, depois de modificada.

Uma pequena ajuda: o exercício é fácil se construir um segundo membro-função (privado) que, recebendo um apontador para uma sub-árvore, faz a referida transformação a essa sub-árvore de forma recursiva.

Pergunta 4, [4 valores]

Considere uma rede de dados do tipo Ethernet com vários comutadores ligados entre si, conforme exemplifica a figura seguinte.

Em redes com anéis (como o anel 1-2-3-1 no exemplo acima), interessa desfazer ligações em número suficiente para "quebrar" todos os anéis, mantendo a rede conexa. No exemplo acima bastaria desfazer a ligação 2-3 (ou a ligação 1-2 ou a ligação 1-3) para quebrar o único anel existente.

Imagine que se pretende construir um programa para determinar eventuais ligações que deverão ser desfeitas numa dada rede.  Indique, justificando, que estrutura de dados usaria para representar a rede de comutadores e as suas ligações. Esboce um algoritmo capaz de analisar essa estrutura de dados e determinar quais as ligações que deveriam ser desfeitas. Indique, justificando, qual seria a complexidade espacial e temporal desse programa.