Resolução do exame de 2ª época

ISCTE - ETI

Programação II /Programação Orientada por Objectos

Resolução do exame de 2ª época

1998/1999, 2º semestre

A azul (e indentadas uma vez) as respostas às questões.

Questão 1

Assinale com V (Verdadeiro) as expressões que estão correctas e com F (Falso) as que estão incorrectas.

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:

#include <iostream>
class X {
public:
 X();
 ...
};
class Y {
public:
 virtual void g() const = 0;
};
class A : public Y {
 int a;
 X* px;
public:
 A(int aa) : a(aa), px(0) {
 }
 A(int aa, X* p) : a(aa), px(p) {
 }
 void g() const {
 std::cout << "Execução de A::g(). ";
 }
};
class B : public A {
 int by;
public:
 int bx;
 B(int a, int x, int y = 0) : A(a), by(y), bx(x) {
 }
 B(int a, int x, int y, X* p) : A(a, p), by(y), bx(x) {
 }
 void g() const {
 std::cout << "Execução de B::g(). ";
 A::g();
 }
};
int main() {
 ...
}

Questão 1.1

Quais das seguintes sequências de instruções estão correctas (têm de estar correctas todas as instruções), quer do ponto de vista sintáctico quer do ponto de vista semântico?

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

As instruções estão correctas do ponto de vista sintáctico, mas o conteúdo apontado por p é usado na segunda instrução sem que o ponteiro p tenha sido inicializado.

F B p(1, 2); p->bx = 1;

A variável p é do tipo B (e não ponteiro para B), pelo que o operador de selecção de membro a utilizar só poderia ser o operador ., e nunca o operador ->, que se usa apenas para acesso através de ponteiros ou para instâncias de classes que o definam explicitamente (não é o caso de B).

F B p(1, 2); p.by = 1;

Neste caso o operador de selecção de membro está correcto, mas acontece que by é uma variável membro privada, pelo que estas instruções, que se presume estarem na função main(), não lhe podem aceder.

F B& a; a.bx = 1;

A definição da referência a está errada: uma referência tem de ser sempre inicializada, pois introduz um sinónimo de qualquer coisa.
Note-se que, no caso de um parâmetro duma função, a inicialização de uma referência é feita pelo respectivo argumento imediatamente antes da sua chamada, pelo que a inicialização não está explicita.

[2 valores]

Questão 1.2

Dadas as seguintes definições:

X* x = new X;
A* a = new A(1);
B b(10, 20);
int* i = new int(11);

quais das seguintes instruções são válidas?

V B bb(b);

A linguagem encarrega-se de fornecer automaticamente um construtor por cópia para todas as classes onde tal seja possível. É o caso da classe B. Por isso é possível inicializar uma instância de B à custa de outra instância da mesma classe.

F B bb(*i, *i, *i, &x);

No único construtor de B com quatro parâmetros o último é do tipo X*. Como x é do tipo X*, o seu endereço (optido pelo operador &) é do tipo X** (ponteiro para ponteiro para X), pelo que há uma incompatibilidade de tipos na invocação do construtor e portanto a definição está errada.

F B bb;

A classe B não tem construtor por omissão. A linguagem só fornece um construtor por omissão automaticamente se o programador não fornecer explicitamente nenhum outro construtor (o que não é o caso).

[1,5 valores]

Questão 1.3

Depois das seguintes instruções:

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

o que aparece escrito no écrã (apenas uma resposta está correcta)?

V Execução de B::g(). Execução de A::g().
F Execução de B::g().
F Não aparece nada no ecrã.

O procedimento g() é declarado na classe Y (topo da hierarquia) como virtual. Assim, a invocação de g() através de um ponteiro para a classe A, mas que aponta um objecto da classe B, tem como resultado a invocação da especialização de g() em B (i.e., B::g()). Ou seja, ocorre polimorfismo.

[1,5 valores]

Questão 2

Pretende-se desenvolver uma hierarquia de classes representando itens passíveis de serem guardados numa biblioteca. No topo da hierarquia está uma classe abstracta ItemDeBiblioteca definida da seguinte forma :

class ItemDeBiblioteca {
public:
    ItemDeBiblioteca(const std::string& título) : título_(título) {
    }
    virtual ~ItemDeBiblioteca() {
    }
    // Função membro que devolve true caso o item de biblioteca aborde o assunto passado como
    // argumento e false no caso contrário.
    virtual bool aborda(const std::string& assunto) const = 0;
    std::string título() const {
        return título_;
    }
private:
    std::string título_;
};

Questão 2.1

Defina uma classe Artigo que contém o nome do autor, o título do artigo e o assunto que aborda (tudo std::string). Admite-se que cada artigo aborda apenas um assunto. Devem existir funções que permitem consultar o nome do autor, o título e o assunto do artigo. Devem ainda existir os construtores adequados à classe (inclua um construtor por omissão). Note que um artigo não é um item de biblioteca!

Não é necessário implementar qualquer um dos métodos nesta alínea.

[1 valor]

class Artigo {
public:
    Artigo(const std::string& autor, const std::string& título,
    const std::string& assunto);
    Artigo();
    std::string autor() const;
    std::string título() const;
    std::string assunto() const;
private:
    std::string autor_;
    std::string título_;
    std::string assunto_;
};

Questão 2.2

Defina uma classe concreta Revista, que é um item de biblioteca, e que contenha o nome da empresa editora (uma std::string) e uma lista dos artigos que a compõem (pode usar a classe-modelo Lista dada em anexo para implementar esta lista). Devem existir, para além das funções e procedimentos comuns a todos os itens de biblioteca:

Uma função membro para consultar a editora.
Um procedimento membro para acrescentar um artigo à revista.
O(s) construtor(es) adequado(s) à classe.

Não é necessário implementar qualquer um dos métodos nesta alínea.

[2 valores]

class Revista : public ItemDeBiblioteca {
public:
 Revista(const std::string& título, const std::string& editora);
 std::string editora() const;
 bool aborda(const std::string& assunto) const;
 void acrescenta(const Artigo& artigo);
private:
 std::string editora_;
 Lista<Artigo> artigos;
};

Questão 2.3

Defina o(s) contrutor(es) da classe Revista.

[0,5 valor]

inline Revista::Revista(const std::string& título,
const std::string& editora)
: ItemDeBiblioteca(título), editora_(editora) {
}

Questão 2.4

Preencha a função membro abaixo de modo a que esta devolva true caso o assunto dado como argumento seja abordado em algum dos artigos que constam da revista e false no caso contrário.

bool Revista::aborda(const std::string& assunto) const {
 for(Lista<Artigo>::IteradorConstante i = artigos.primeiro();
 i != artigos.fim(); ++i)
 if(i.item().assunto() == assunto)
 return true;
 return false;
}

[2 valores]

// Apresenta-se aqui a implementação completa incluindo um programa de teste:
#include <string>
#include <iostream>
#include "lista.H"
class ItemDeBiblioteca {
public:
 ItemDeBiblioteca(const std::string título);
 virtual ~ItemDeBiblioteca();
 // Função membro que devolve true caso o item de biblioteca aborde
 // o assunto passado como argumento e false no caso contrário.
 virtual bool aborda(const std::string& assunto) const = 0;
 std::string título() const;
private:
 std::string título_;
};
inline ItemDeBiblioteca::ItemDeBiblioteca(const std::string título)
 : título_(título) {
}
inline ItemDeBiblioteca::~ItemDeBiblioteca() {
}
inline std::string ItemDeBiblioteca::título() const {
 return título_;
}
class Artigo {
public:
 Artigo(const std::string& autor, const std::string& título,
 const std::string& assunto);
 Artigo();
 std::string autor() const;
 std::string título() const;
 std::string assunto() const;
private:
 std::string autor_;
 std::string título_;
 std::string assunto_;
};
Artigo::Artigo(const std::string& autor, const std::string& título,
 const std::string& assunto)
 : autor_(autor), título_(título), assunto_(assunto) {
}
Artigo::Artigo() {
}
inline std::string Artigo::autor() const {
 return autor_;
}
inline std::string Artigo::título() const {
 return título_;
}
inline std::string Artigo::assunto() const {
 return assunto_;
}
class Revista : public ItemDeBiblioteca {
public:
 Revista(const std::string& título, const std::string& editora);
 std::string editora() const;
 bool aborda(const std::string& assunto) const;
 void acrescenta(const Artigo& artigo);
private:
 std::string editora_;
 Lista<Artigo> artigos;
};
inline Revista::Revista(const std::string& título,
 const std::string& editora)
 : ItemDeBiblioteca(título), editora_(editora) {
}
inline std::string Revista::editora() const {
 return editora_;
}
// Não é inline! Colocar no ficheiro de implementação (.C ou .cpp).
bool Revista::aborda(const std::string& assunto) const {
 for(Lista<Artigo>::IteradorConstante i = artigos.primeiro();
 i != artigos.fim(); ++i)
 if(i.item().assunto() == assunto)
 return true;
 return false;
}
inline void Revista::acrescenta(const Artigo& artigo) {
 artigos.poeFim(artigo);
}
int main() {
 Revista r("IEEE Computer", "IEEE Press");
 r.acrescenta(Artigo("M. M. Sequeira", "How to avoid programming",
 "programming"));
 r.acrescenta(Artigo("L. M. Nunes", "How to avoid typing",
 "typing"));
 while(true) {
 std::cout << "Que assunto? ";
 std::string assunto;
 std::getline(std::cin, assunto);
 if(assunto == "")
 break;
 std::cout << "O assunto '" << assunto << "' "
 << (r.aborda(assunto) ? "" : "não ")
 << "é abordado na revista" << std::endl;
 }
}

Questão 3

Preencha o procedimento abaixo, cujos argumentos são uma matriz de inteiros m e um inteiro n que indica o tamanho dessa mesma matriz, de modo a que este procedimento passe todos os elementos da matriz para a posição seguinte à que ocupavam originalmente, passando o último elemento para a primeira posição.

void rodaÀDireita(int m[], int n) {
    int aux = m[n - 1];
    for(int i = n - 1; i != 0; --i)
        m[i] = m[i - 1];
    m[0] = aux;
}

[1 valor]

Questão 4

Preencha o procedimento abaixo de modo a que este ordene uma matriz m contendo n inteiros usando o algoritmo de selecção. Relembra-se que o algoritmo de ordenação por selecção (selection sort) consiste essencialmente em ir seleccionando sucessivamente os elementos mais pequenos até a matriz estar ordenada (em cada passo do algoritmo há uma parte da matriz ordenada, e que contém os elementos mais pequenos da matriz, e outra em que os elementos estão por ordenar).

void ordenaPorSelecção(int m[], int n) {
// Ver Michael Main e Walter Savitch, "Data Structures and Other Objects Using C++",
// Addison-Wesley, Reading Massachusetts, 1997, secção 13.1.
}

[2 valores]

Questão 5.1

Pretende-se criar um conjunto de modelos de classes (ou estruturas), funções e procedimentos que implementem listas duplamente ligadas circulares. Uma lista duplamente ligada circular possui um conjunto de nós duplamente ligados em que o nó seguinte do último nó da lista é o primeiro nó da lista e o nó anterior do primeiro nó da lista é o último nó da lista.

Defina completamente um modelo de estrutura chamada Nó que represente um nó de uma lista duplamente ligada circular que pode guardar um item de tipo parametrizável (inclua um construtor).

[0,5 valores]

template <typename I>
struct Nó {
 Nó* anterior;
 Nó* seguinte;
 I item;
 Nó(Nó* a, Nó* s, const I& item = I());
};
template <typename I>
inline Nó::Nó(Nó* a, Nó* s, const I& i)
 : anterior(a), seguinte(s), item(i) {
}

Questão 5.2

Preencha o procedimento-modelo abaixo de modo a que este insira um novo item i na lista duplamente ligada cujo primeiro nó é apontado por primeiro (que é igual a 0 [zero] caso a lista esteja vazia). Tenha atenção ao caso particular de a lista estar vazia!

template <typename I>
void põeNoInício(Nó*& primeiro, const I& i) {
 if(primeiro == 0) {
 primeiro = new Nó(0, 0, i);
 primeiro->anterior = primeiro;
 primeiro->seguinte = primeiro;
 } else {
 primeiro = new Nó(primeiro->anterior, primeiro, i);
 primeiro->anterior->seguinte = primeiro;
 primeiro->seguinte->anterior = primeiro;
 }
}

[1,5 valores]

Questão 5.3

Preencha o procedimento-modelo abaixo de modo a que este remova o nó apontado por nó da lista duplamente ligada cujo primeiro nó é apontado por primeiro (garante-se que a lista não está vazia e que o nó a remover está de facto na lista). Tenha atenção aos casos particulares (lista com um único nó e nó a remover é o primeiro).

template <typename I>
void remove(Nó*& primeiro, Nó* nó) {
 if(primeiro->anterior == primeiro) {
 //Lista com um único nó (primeiro == nó):
 delete primeiro;
 primeiro = 0;
 } else {
 nó->anterior->seguinte = nó->seguinte;
 nó->seguinte->anterior = nó->anterior;
 if(nó == primeiro)
 //Se se estiver a remover o primeiro:
 primeiro = nó->seguinte;
 delete nó;
 }
}

[2 valores]

Questão 5.4

Preencha o procedimento-modelo abaixo de modo a que este passe todos os nós da lista duplamente ligada cujo primeiro nó é apontado por primeiro para a posição seguinte à que ocupam, passando o último para a primeira posição (não tem qualquer efeito se a lista tiver menos de dois nós).

template <typename I>
void rodaÀDireita(Nó*& primeiro) {
if(primeiro != 0)
primeiro = primeiro->anterior;
}

[1,5 valores]

// Apresenta-se aqui a implementação completa incluindo um programa de teste:
template <typename I>
struct Nó {
 Nó* anterior;
 Nó* seguinte;
 I item;
 Nó(Nó* a, Nó* s, const I& item = I());
};
template <typename I>
inline Nó::Nó(Nó* a, Nó* s, const I& i)
 : anterior(a), seguinte(s), item(i) {
}
template <typename I>
 void põeNoInício(No*& primeiro, const I& i) {
 if(primeiro == 0) {
 primeiro = new Nó(0, 0, i);
 primeiro->anterior = primeiro;
 primeiro->seguinte = primeiro;
 } else {
 primeiro = new Nó(primeiro->anterior, primeiro, i);
 primeiro->anterior->seguinte = primeiro;
 primeiro->seguinte->anterior = primeiro;
 }
}
template <typename I>
void remove(Nó*& primeiro, Nó* nó) {
 if(primeiro->anterior == primeiro) {
 //Lista com um único nó (primeiro == nó):
 delete primeiro;
 primeiro = 0;
 } else {
 nó->anterior->seguinte = nó->seguinte;
 nó->seguinte->anterior = nó->anterior;
 if(nó == primeiro)
 //Se se estiver a remover o primeiro:
 primeiro = nó->seguinte;
 delete nó;
 }
}
template <typename I>
void rodaÀDireita(Nó*& primeiro) {
 if(primeiro != 0)
 primeiro = primeiro->anterior;
}
#include <iostream>
template <typename I>
void mostra(const Nó* primeiro) {
 if(primeiro == 0)
 std::cout << "Vazia!" << std::endl;
 else {
 for(const Nó* nó = primeiro; nó != primeiro->anterior;
 nó = nó->seguinte)
 std::cout << nó->item << ' ';
 std::cout << primeiro->anterior->item << std::endl;
 }
}
int main() {
 Nó<int>* primeiro = 0;
 põeNoInício(primeiro, 1);
 remove(primeiro, primeiro);
 mostra(primeiro);
 põeNoInício(primeiro, 4);
 põeNoInício(primeiro, 3);
 põeNoInício(primeiro, 2);
 põeNoInício(primeiro, 1);
 mostra(primeiro);
 remove(primeiro, primeiro->seguinte);
 mostra(primeiro);
 remove(primeiro, primeiro->anterior);
 mostra(primeiro);
 remove(primeiro, primeiro);
 mostra(primeiro);
 remove(primeiro, primeiro);
 mostra(primeiro);
 põeNoInício(primeiro, 4);
 põeNoInício(primeiro, 3);
 põeNoInício(primeiro, 2);
 põeNoInício(primeiro, 1);
 rodaÀDireita(primeiro);
 mostra(primeiro);
}

Questão 6

Explique sucintamente as vantagens e desvantagens da utilização de listas ligadas por oposição à utilização de matrizes para a implementação do conceito de lista.

[1 valor]

Ver aula prática 5, Secção 1.3.