Faculdade de Engenharia da Universidade do Porto
Licenciatura em Engenharia Electrotécnica e de Computadores
Algoritmos e Estruturas de Dados, 1998/99

Prova de Avaliação:

1ª Chamada 1998/99 Duração: 2 horas Com Consulta 18/6/1999

1. [5 valores]
O que é que aparece escrito no ecrã quanto é executado o seguinte programa em C++?

#include <iostream.h>
class Hora {
  public: Hora(int h = 12, int m = 0, int s = 0) {
      horas = h; mins = m; segs = s; }
    void Mostra() const {
      cout << horas << ":" << mins << ":" << segs << endl; }
    Hora & Incrementa(int h, int m, int s) {
      m += s / 60; segs += s % 60;
      h += m / 60; mins += m % 60;
      horas += h % 24;
      return *this; }
   private: int horas; int mins; int segs;
};
int main() {
   Hora h1, h2(14,0,0), & h3 = h2;
   h1.Mostra(); h2.Incrementa(0,90,30).Mostra(); h3.Mostra();
   return 0;
}

2. [6 valores]
Escreva uma função CountDistinct, a acrescentar à classe Chain (representação de lista baseada em ligações) estudada nesta disciplina, que conta e retorna o número de elementos distintos da lista, supondo que esta está ordenada (por qualquer ordem). Calcule a complexidade temporal da sua implementação.

3. [6 valores]
Escreva uma função CountLeaves, a acrescentar à classe BinaryTree estudada nesta disciplina, que calcula e retorna o número de folhas (nós sem filhos) existentes na árvore binária.

4. [3 valores]
Pretende-se escrever um programa em C++ para simular a execução de uma série de tarefas; cada tarefa é caracterizada por um tempo de execução (duração) e um conjunto de tarefas dependentes (dependentes), isto é, um conjunto (possivelmente vazio) de tarefas que têm início após a tarefa terminar.

Por exemplo, para os seguintes dados de entrada (não necessariamente introduzidos neste formato)

Tarefa

duração

dependentes

1

2

{2, 4}

2

1

{3}

3

5

{}

4

3

{}

sendo 1 a tarefa inicial, tínhamos a seguinte sequência de execução:


E a saída do programa deverá ser:

 t=0 início da tarefa 1
t=2 fim da tarefa 1
t=2 início da tarefa 2
t=2 início da tarefa 4
t=3 fim da tarefa 2
t=3 início da tarefa 3
t=5 fim da tarefa 4
t=8 fim da tarefa 3
Diga que estruturas de dados e algoritmos estudados nesta disciplina (ou construídos a partir deles), seriam adequados para resolver este problema e apresente uma breve justificação das escolhas efectuadas.

Note que:
1) no instante inicial podem ter início todas as tarefas que não dependem de nenhuma outra tarefa;
2) nenhuma tarefa depende de mais do que uma tarefa;
3) o lançamento de novas tarefas em execução só ocorre quando há uma tarefa que termina;
4) pode recorrer a conceitos de alto nível como, por exemplo, "o conjunto de tarefas em execução no instante t" ou "as tarefas dependentes da tarefa T".

[Página da disciplina] [J. Pascoal Home page] [J. Lopes Home page]
João Pascoal de Faria ([email protected]) / João Correia Lopes (jlopes AT fe.up.pt)
Last modified: Mon Jul 12 14:18:46 1999