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.