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 (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:

class A {
    int a;
  public:
    A(int aa) : a(aa) {
    }
    virtual void f() {
        cout << "A ";
    }
    virtual void g() = 0;
};

class B : public A {
  public:
    int bx;
    B();
    B(int);
    void f() {
        A::f();
        cout << "B ";
    }
    void g() {
        f();
        cout << "C ";
    }
};

int main() {
    ...
}

Questão 1.1

 F  B* p = new B; B->bx = 1;

A segunda instrução está errada, pois o primeiro operando do operador de selecção de membro -> deveria ser um ponteiro.  Neste caso nem sequer é um valor: é um tipo, o que é um erro.

Nenhuma das instruções está sintacticamente errada.  Mas a verdade é que na primeira se define um ponteiro que não se inicializa, e portanto contém um endereço arbitrário.  Assim, a segunda instrução está errada, pois refere-se ao conteúdo de uma posição de memória que só por sorte (ou melhor, por azar) é que corresponde a um objecto da classe B ou de uma classe compatível.  Resumindo: usar um ponteiro não inicializado é um erro.

Neste caso não há qualquer problema.  A variável a é da classe B, a referência b é inicializada com a (ou seja, b torna-se sinónimo de a), e finalmente atribui-se um valor à variável membro bx da instância a através da referência b.

 Questão 1.2

 F  B::B(int aa) { a = aa; }

A variável A::a é privada da classe A, pelo que B não pode aceder-lhe directamente.

As variáveis membro de uma classe base são tipicamente inicializadas pelo construtor da classe base, que por sua vez deve ser invocado na lista de inicializadores do construtor da classe derivada.

Numa lista de inicializadores podem constar apenas construtores de classes base e inicializadores de variáveis membro da própria classe.  Ora a variável A::a não é membro de B, pelo que não pode constar na lista de inicializadores.  Note-se que o problema existiria mesmo que A::a fosse pública.

Neste caso não é feita uma invocação explícita do construtor de A na lista de inicializadores do construtor de B.  Assim, o compilador tenta invocar implicitamente o construtor por omissão de A.  Como este não existe, é um erro.  Mesmo que o construtor por omissão existisse, o corpo do construtor (entre {}) seria sempre absurdo (embora sem qualquer erro sintáctico): a instrução A(aa); tem como resultado a criação de uma nova instância temporária da classe A que é imediatamente descartada.  É uma instrução tão inútil quanto a instrução 1;.

 Questão 1.3

A* a = new B;
a->g();

 V  A B C
 F  A C
 F  Não dá para executar o programa porque dá erro de compilação na classe B.

Como o procedimento A::g() é virtual (aliás, puramente virtual), a invocação a->g() tem como resultado a invocação do procedimento B::g(), pois o objecto apontado pelo ponteiro a é da classe B.  Em B::g() começa por se invocar o procedimento B::f() (e não A::f()), que por sua vez começa por invocar o procedimento A::f().

Questão 2

class Processo {
  public:
    // Construtores da classe:
    Processo();
    Processo(..., int prioridade);

    // Devolve a prioridade do processo (0 é prioridade máxima, 100 mínima):
    int prioridade() const;

    ...
};

Questão 2.1

O método void FilaPrioritária::tira() retira sempre o processo da frente da fila, i.e., o processo mais prioritário ou, caso exista mais do que um com a mesma prioridade, o que tiver sido colocado na fila em primeiro lugar.

O procedimento de inserção void FilaPrioritária::põe(const Processo& processo) deve colocar o novo processo de modo a que os processos na fila continuem organizados por prioridade e de tal modo que, para processos com a mesma prioridade, o primeiro a entrar na fila seja sempre o primeiro a sair.

Não precisa de definir nesta alínea quaisquer das funções ou procedimentos membro da classe, mas deve declarar todas as funções e procedimentos membro que devam constar na interface da classe, incluindo as correspondentes às operações usuais com filas.

[2 valores]

Há duas soluções para este problema.  Uma, mais simples, usa herança privada. A outra, mais complicada, usa uma lista como variável membro da fila.  Embora a primeira seja preferível, apresentam-se abaixo as duas versões:

class FilaPrioritária : private Lista<Processo> {
public:
    void põe(const Processo& processo);
    void tira();
    using Lista<Processo>::frente;
    using Lista<Processo>::comprimento;
    using Lista<Processo>::vazia;
};

ou

class FilaPrioritária {
public:
    void põe(const Processo& processo);
    void tira();
    Processo& frente();
    Processo frente() const;
    int comprimento() const;
    bool vazia() const;

private:
    Lista<Processo> processos;
};

Questão 2.2

[2 valores]

Mais uma vez apresentam-se as duas versões.  Apresenta-se a solução completa.  Note-se a simplicidade da solução com herança privada:

inline void FilaPrioritária::põe(const Processo& processo) {
    Iterador i = primeiro();
    while(i != fim() &&
          i.item().prioridade() <= processo.prioridade())
        ++i;
    insere(i, processo);
}

inline void FilaPrioritária::tira() {
    tiraPrimeiro();
}

ou

inline void FilaPrioritária::põe(const Processo& processo) {
    Lista<Processo>::Iterador i = processos.primeiro();
    while(i != processos.fim() &&
          i.item().prioridade()<= processo.prioridade())
        ++i;
    processos.insere(i, processo);
}

inline void FilaPrioritária::tira() {
    processos.tiraPrimeiro();
}

inline Processo& FilaPrioritária::frente() {
    return processos.frente();
}

inline Processo FilaPrioritária::frente() const {
    return processos.frente();
}

inline int FilaPrioritária::comprimento() const {
    return processos.comprimento();
}

inline bool FilaPrioritária::vazia() const {
    return processos.vazia();
}

Questão 3

Questão 3.1

int Memória::reserva(int tamanho);
void Memória::liberta(int endereço);

Ao libertar a memória deve ser verificado se o conteúdo da posição indicada pelo utilizador tem um número diferente de zero e, nesse caso, deve ser posto de novo a zero indicando que o bloco previamente reservado se encontra agora livre.  Se a posição indicada contiver zero, então deve ser emitida uma mensagem de erro assinalando tentativa de libertar um bloco não reservado.  Deve-se verificar se o endereço passado como argumento é válido (i.e., maior ou igual a 0 e menor que 1024).

Não precisa de definir quaisquer das funções ou procedimentos membro da classe nesta alínea.

[2 valores]

class Memoria {
public:
    static const int tamanho = 1024;

    Memoria();
    int reserva(int espaco);
    void liberta(int endereco);

private:
    int mem[tamanho];
};

Questão 3.2

[2 valores]

Apresenta-se a solução completa.

inline Memoria::Memoria() {
    for(int i = 0; i != tamanho; ++i)
        mem[i] = 0;
}

inline int Memoria::reserva(int espaco) {
    if(espaco <= 0 || espaco > tamanho) {
        cerr << "Memória: não posso reservar esse espaço!"
             << endl;
        return -1;
    }

    int endereco = 0;
    // Usa-se um ciclo do while porque se garante que a guarda é
    // sempre verdadeira no início do ciclo.  Note-se que o ciclo
    // termina normalmente apenas quando não há espaço livre suficiente!
    do {
        // Procura espaço livre.  Percorre desde o endereço corrente até ao
        // fim do bloco a reservar ou até encontrar posição ocupada
        // (note-se que a guarda do ciclo garante que a memória não se
        // esgota durante o ciclo):
        int i = endereco;
        for(; i != endereco + espaco && mem[i] == 0; ++i)
            continue;

        // Se não encontrou qualquer posição ocupada, então há espaço
        // começando em endereco:
        if(i == endereco + espaco) {
            mem[endereco] = espaco;
            return endereco;
        }

        // Caso contrário a pesquisa pode recomeçar em i + mem[i], pois não há
        // espaço antes do bloco começado em i e pode-se saltar logo para o
        // seu fim:
        endereco = i + mem[i];
    } while(endereco + espaco <= tamanho);
    return -1;
}

inline void Memoria::liberta(int endereco) {
    if(endereco < 0 || endereco >= tamanho)
        cerr << "Memória: libertando endereço inválido."
             << endl;
    else if(mem[endereco] == 0)
        cerr << "Memória: libertando memória livre." << endl;
    else
        mem[endereco] = 0;
}

Questão 4

struct Nó {
    typedef int Item;

    // Não existe ponteiro para o nó anterior!
    Nó* seguinte;      // ponteiro para o nó seguinte.
    Item item;         // guarda o item propriamente dito.

    // Construtor:
    Nó(Nó* s, const Item& i) : seguinte(s), item(i) {
    }
};

[2 valores]

Neste caso é necessário ter o cuidado de verificar se a lista ligada está vazia, pois nesse caso o ponteiro primeiro tem de ser actualizado.  Em qualquer dos casos é fundamental alterar o ponteiro último.

void põeFim(Nó*& primeiro, Nó*& último, const Item& i) {
    if(ultimo == 0)
        // A lista está vazia:
        primeiro = ultimo = new Nó(0, i);
    else {
        // A lista tem pelo menos um elemento:
        ultimo->seguinte = new Nó(0, i);
        ultimo = ultimo->seguinte;
    }
}

Questão 5

class Tarefa {
  public:

    // Construtor (não há construtor por omissão):
    Tarefa(std::string descrição, std::string notas);

    // Destrutor virtual:
    virtual ~Tarefa() {}

    // Acesso à descrição e às notas:
    std::string descrição() const;
    std::string notas() const;

    // Devolve duração da tarefa (em dias):
    virtual int duração() const = 0;

    // Devolve custo da mão de obra da tarefa (em escudos):
    virtual int custoMãoObra() const = 0;

    // Devolve custo do material da tarefa (em escudos):
    virtual int custoMaterial() const = 0;

  private:
    std::string descrição_;
    std::string notas_;
};

Defina também a função int TarefaAdministrativa::custoMaterial().  Não é necessário nesta alínea implementar qualquer das outras funções ou procedimentos membro da classe TarefaAdministrativa.

[3 valores]

Apresenta-se a solução completa.

class TarefaAdministrativa : public Tarefa {
  public:

    // Construtor (não há construtor por omissão):
    TarefaAdministrativa(std::string descrição,
                         std::string notas,
                         int custo_mão_obra_dia,
                         int duração);

    // Acesso ao custo da mão de obra por dia:
    int custoMãoObraDia() const;

    // Devolve duração da tarefa (em dias):
    int duração() const;

    // Devolve custo da mão de obra da tarefa (em escudos):
    int custoMãoObra() const;

    // Devolve custo do material da tarefa (em escudos):
    int custoMaterial() const;

  private:
    int custo_mão_obra_dia_;
    int duração_;
};

TarefaAdministrativa::TarefaAdministrativa(std::string descrição,
                                           std::string notas,
                                           int custo_mão_obra_dia,
                                           int duração)
    : Tarefa(descrição, notas),
      custo_mão_obra_dia_(custo_mão_obra_dia),
      duração_(duração) {
}

int TarefaAdministrativa::custoMãoObraDia() const {
    return custo_mão_obra_dia_;
}

int TarefaAdministrativa::duração() const {
    return duração_;
}

int TarefaAdministrativa::custoMãoObra() const {
    return duração() * custo_mão_obra_dia_;
}

int TarefaAdministrativa::custoMaterial() const {
    return 0;
}

Questão 6

[2 valores]

A utilização de guardas tem duas vantagens muito relacionadas:

1. Durante a inserção ou remoção de nós não é necessário verificar quaisquer casos particulares.  Por exemplo, a inserção no fim da lista ligada é feita da mesma forma que a inserção em qualquer outro local da lista ligada e não exige alterações aos ponteiros representativos da lista (tipicamente os ponteiros para o primeiro e último elementos, ou, no caso de se utilizarem guardas, os ponteiros para as guardas inicial e final).
2. Simplifica a acção de percorrer uma lista, pois a guarda do ciclo verifica se ainda não se atingiu a guarda final (em ciclos para a frente).  O ponteiro usado para percorrer a lista, quando o ciclo termina, fica referenciando a guarda final, o que permite posteriormente, por exemplo, inserir um novo nó antes da guarda final sem que o procedimento de inserção tenha de distinguir qualquer caso particular.  Isto é particularmente útil aquando de inserções ordenadas numa lista ligada.