Nome do aluno: _______________________________________________

Número do aluno:  ______________________

Assinatura do docente: ________________________________________

Nome do aluno: _______________________________________________

Número do aluno:  ______________________

Turma: ____________

Notas:

• Leia atentamente todo o enunciado (incluindo estas notas) antes de começar a prova.
• Este exame tem cinco (5) questões.
• Duração: 3:30h (três horas e trinta minutos).
• A prova deve ser efectuada sem consulta.
• Sobre a sua secretária só pode estar o enunciado e uma caneta (coloque pastas, roupa, etc. sobre a cadeira ao seu lado).
• Deve responder a todas as questões no próprio enunciado, nos espaços reservados.
• Use as páginas em branco no final do enunciado para rascunho.
• Não destaque as folhas do enunciado (nem mesmo as de rascunho).
• Preencha o seu nome e número no recibo (não o destaque). Este ser-lhe-á entregue, assinado por um docente, depois da prova.
• Só um recibo assinado servirá de prova de que entregou a resolução deste enunciado.
• As cotações encontram-se abaixo de cada alínea (total de 20 valores).
• As notas serão afixadas até às 18:00h de sexta-feira dia 3 de Março de 2000.
• A revisão de provas terá lugar das 9:30 às 11:00h de sexta-feira dia 10 de Março de 2000 no gabinete 11.
• Boa sorte.

Questão 1

Deve preencher todos os espaços indicados por um sublinhado (___) com V ou F. Qualquer espaço não preenchido será considerado como uma resposta errada.

Em geral as alíneas podem ter zero ou mais respostas correctas.  Cada resposta correctamente assinalada vale 0,5 valores.

Nas alíneas em que apenas uma resposta está correcta (se existirem estão assinaladas no texto), responder com mais ou menos do que um V anula a cotação.  A resposta correcta corresponde à cotação completa.  Qualquer outra resposta corresponde a zero valores.

Em todos os casos em que não é explicitamente referida a localização de uma instrução, considere que esta é dada na função main() do programa seguinte:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class A {
  public:
    int z;
    A(const char c = ' ', const int n = 1);
    A(const string& s, const int n = 0);
    int f1();
    int f2(const char);

  private:
    string x;
    char f3();
};

...

int main()
{
    const int i = 1;
    A meu_a('a', 3);
    vector<char> v(1);
    v[0] = 'X';
    ...
}

1.1  Admita que qualquer uma destas instruções é dada na função main() imediatamente após a definição do vector v.  Quais das seguintes instruções estão correctas?

__  A a;
__  A a("a");
__  A a(v[1]);

 [cotação: 1,5]

1.2  Admita que qualquer uma destas instruções é dada na função main() do programa acima. Quais das seguintes instruções estão correctas?

__ char c = meu_a.x[2];
__ i = meu_a.f2('t');
__ int k = f1();
__ meu_a.z = meu_a.f2('x');

 [cotação: 2]

1.3  Assuma que as seguintes instruções são dadas dentro de uma função ou procedimento membro da classe A e que não são declaradas quaisquer variáveis ou constantes dentro dessa função ou procedimento (que não tem quaisquer parâmetros).  Quais das seguintes instruções estão correctas?

__  "ige" = x;
__  char c = f3();

 [cotação: 1]

1.4  Suponha o seguinte:

A::A(const char c, const int n) : z(n) {
    x += c;
}
A::A(const string& s, const int n) : x(s) {
    z = n == 0 ? s.size() : n;
}
int A::f1() {
    int n = x.size();
    return n - z;
}
int main() {
    A a("exame",3), b;
    cout << a.f1() << "   " << b.f1() << endl;
}

__   2   0
__   5   1
__   5   0
__   2   1
 [cotação: 0,5]
Questão 2

Considere uma estação dos correios onde existem 3 postos de atendimento com correspondentes filas de espera (numeradas de 0 a 2): o primeiro posto trata da venda de selos e recepção de cartas, o segundo trata dos serviços telefónicos e o terceiro trata das encomendas.  Nesses postos de atendimento são atendidos utentes, cada um dos quais é identificado por um nome e tem um determinado assunto a tratar, correspondente a um dos postos (mas não forçosamente o correspondente à fila de espera em que se encontra, pois é frequente os utentes deste posto enganarem-se...).

2.1  Defina a classe Utente de modo a guardar:

1. O nome do utente.
2. O número do posto correspondente ao assunto que o utente pretende tratar.

Indique claramente quais dos métodos da classe não alteram a instância implícita.

Não é necessário nesta questão definir qualquer um dos métodos (funções ou procedimentos membro) da classe.

[cotação: 1]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.2  Defina os construtores da classe Utente.

[cotação: 0,5]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.3  Defina as funções de inspecção do nome e posto de atendimento desejado para a classe Utente.

[cotação: 0,5]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.4  Defina a classe FilaDeEspera que deve guardar a informação sobre um conjunto de utentes que irão ser atendidos.  Assume-se que, dadas as limitações de espaço da estação de correios, cada fila não pode ter mais do que 20 utentes.  Deve declarar os métodos necessários para:

1. Inserir um utente no fim da fila.
2. Retirar o utente na frente da fila.
3. Verificar se a fila está vazia.
4. Verificar se a fila está cheia.
5. Devolver o utente que vai ser atendido (o que está na frente da fila).
6. Mostrar todos os utentes na fila.

Não é necessário nesta questão definir qualquer um dos métodos.  Coloque comentários indicando claramente para que serve cada uma das variáveis membro que definir.

[cotação: 2]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.5  Defina o método da classe FilaDeEspera que retira um utente da fila de espera.

[cotação: 1,5]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.6  Defina o método da classe FilaDeEspera que insere um utente na fila de espera.

[cotação: 1,5]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.7  Escreva um programa que simule o funcionamento da estação de correios.  Admita que as filas de espera estão inicialmente vazias.  O programa deve gerar aleatoriamente (ao acaso) um conjunto de utentes que deverão ser distribuídos aleatoriamente pelas 3 filas de espera.  O número de utentes a gerar deve ser dado pelo utilizador do programa no seu início.  Os nomes dos utentes serão escolhidos aleatoriamente a partir da seguinte lista de possíveis nomes:

1. Manel
2. Zé
3. Jaquim
4. Tó
5. Quim

Para gerar números aleatórios deve-se usar a seguinte função: int aleatório(int n).  Esta função, que se assume estar definida algures, gera um número inteiro aleatório (ao acaso) entre 0 e n-1.

Depois de gerar os utentes e de os colocar nas filas de espera, o programa deve simular o atendimento a cada utente de cada fila.  Isto é, até que todas as filas de espera se encontrem vazias, deve ser atendido o utente da primeira fila de espera (se existir), em seguida o utente da segunda fila de espera (se existir) e depois o da terceira fila de espera (se existir).  Após cada sessão de atendimento (considera-se uma sessão de atendimento atender uma pessoa de cada uma das filas de espera), deve ser exibido no ecrã o estado das três filas de espera, i.e., os utentes por atender em cada fila.  A simulação termina quando todas as filas estiverem vazias.

Por exemplo:

Fila 0: Manel:0 Quim:1 Jaquim:0
Fila 1: Zé:1 Quim:1
Fila 2: Tó:0 Jaquim:2 Zé:2

Fila 0: Quim:1 Jaquim:0 Tó:0
Fila 1: Quim:1
Fila 2: Jaquim:2 Zé:2

[cotação: 1]
 
 
 
 
 
 
 
 
 
 
 
 
 

Questão 3

Defina completamente uma classe (Polinómio) que permita manipular polinómios (pode assumir que a ordem máxima é 20).  Deve declarar a classe e definir os seguintes métodos

1. void Polinómio::inserir(const double x, const int n) que permite inserir um termo de ordem n no polinómio.

Tenha em atenção que se for inserido um elemento de ordem igual a outro já existente, este deve ser somado ao existente.
2. void Polinómio::mostra() const que permite visualizar no ecrã uma variável do tipo Polinómio no seguinte formato:

    2×x^0 + -2.1×x^1 + 0.3×x^2 + 4.5×x^3

Deve ainda sobrecarregar o operador += que permite somar um polinómio a outro.  Recorda-se que a soma de dois polinómios consiste num polinómio cujos termos são a soma dos termos de igual ordem dos polinónios somados.

Esta classe deve suportar as seguintes instruções:

Polinómio p;   // define um polinómio que contém o valor 0

p.mostra();
// Escreve no ecrã o seguinte: 0×x^0

p.insere(3.0, 0);
p.insere(4.0, 2);
p.mostra();

// Aparece no ecrã: 3×x^0 + 0×x^1 + 4×x^2

Polinómio q;

q.insere(2.0, 1);
q.insere(-2.0, 2);
q.insere(1.0, 3 );

q.mostra();

// Aparece no ecrã: 0×x^0 + 2×x^1 + -2×x^2 + 1×x^3

p += q;

r.mostra();

// Aparece no ecrã: 3*x^0 + 2*x^1 + 2*x^2 + 1*x^3

Questão 4

Considere a função double norma(const double v[], const int n) que devolve a norma de um vector.  A norma de um vector é a raiz quadrada da soma dos quadrados das suas coordenadas.

4.1  Dada a pré-condição n > 0, indique a condição objectivo (CO), a condição invariante (CI) e a guarda (G) do ciclo necessário à construção desta função.

[cotação: 0,5]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.2  Defina completamente a função indicada.

[cotação: 1]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.3  Prove que o ciclo está correcto verificando que:

1. Se a PC for verdadeira, então a CI também é verdadeira após a inicialização das variáveis e antes da primeira iteração do ciclo, i.e.:
// PC
init
// implica CI.
2. Se a guarda G e a CI  do ciclo forem verdadeiras no início de um passo, então a CI também é verdadeira no fim desse passo, i.e.:
// G e CI
passo
// implica CI
3. Se a guarda G for falsa e a CI for verdadeira, então a CO é verdadeira, i.e.:
// CI e ¬G implicaCO.

Questão 5

De uma forma simplificada, "um algoritmo é um método de resolução de um dado problema, expresso em linguagem natural".
Explicite brevemente as principais características de um algoritmo.

[cotação: 1]