# Exercícios MT1

Questões de exames antigos de Algoritmos e Estruturas de Dados, com resolução.

Página: https://resumos.rgo.pt/cadeiras/aed/exercicios-mt1/

## Classes e polimorfismo em C++

Despacho dinâmico apenas em membros-função virtuais

Teste 1 (CI1), 2016/17

```
class Function {
public:
   virtual float evaluate(float x)=0;
   string info();
};
class Double: public Function {
public:
   float evaluate(float x);
   string info();
};
Function *f = new Double();
float value = f->evaluate(4.0);
string info = f->info();
```

Considere o código acima (as classes Function e Double estão parcialmente definidas). Indique o que acontece na execução das duas últimas instruções.

Solução

value é o resultado de `Double::evaluate()` e info é o resultado de `Function::info()`.

A tabela de funções virtuais só inclui membros-função declarados virtual. Assim, `f->evaluate(4.0)` faz despacho dinâmico para `Double::evaluate()`, mas `f->info()` resolve estaticamente para `Function::info()`.

*   **O código está incorreto, devido à atribuição inválida (=0) na declaração de Function::evaluate.** A sintaxe =0 declara um membro-função virtual puro, que é válida e torna a classe abstrata.
*   **value = 0 e info é o resultado da invocação de Function::info().** value não fica 0; como evaluate é virtual, é invocada Double::evaluate().
*   **value é o resultado de Double::evaluate() e info é o resultado de Double::info().** info não é declarada virtual em Function, logo não há despacho dinâmico para Double::info().
*   **value é o resultado de Double::evaluate() e info é o resultado de Function::info().** evaluate é virtual, logo a chamada através de Function\* invoca Double::evaluate(); info não é virtual, logo usa a implementação da classe estática do apontador.
*   **Nenhuma das possibilidades anteriores.** A quarta opção descreve corretamente o comportamento.

Objetos de uma classe abstrata

Teste 1 (CI1), 2016/17

Shape é uma classe abstrata. É correto afirmar que:

Solução

Não é possível criar objetos da classe Shape.

A instanciação de uma classe abstrata é impedida pelo compilador devido à presença de membros-função virtuais puros. A sua utilidade está em definir uma interface comum para as classes derivadas.

*   **Todos os membros-função da classe Shape devem ser abstratos.** Basta um membro-função virtual puro para a classe ser abstrata; os restantes podem ter implementação.
*   **Só é possível criar objetos da classe Shape se estes forem constantes.** A constante não altera o facto de a classe ser abstrata.
*   **Shape pode ser uma classe base, mas não uma classe derivada.** Uma classe abstrata pode ser base e também derivar de outra classe.
*   **Não é possível criar objetos da classe Shape.** Uma classe abstrata tem pelo menos um membro-função virtual puro e não pode ser instanciada; serve apenas como base de classes concretas.
*   **Nenhuma das possibilidades anteriores.** A quarta opção está correta.

Invocação polimórfica através de apontador da classe base

Teste 1 (CI1), 2017/18

```
class Pessoa {
public:
   virtual void info() { /* ... */ }
};
class Estudante: public Pessoa {
public:
   void info() { /* ... */ }
};
class Mestrando: public Estudante {
public:
   void info() { /* ... */ }
};
int main() {
   Pessoa *p = new Mestrando();
   p->info();
}
```

Considere o código acima (incompleto). A instrução `p->info()` resulta em:

Solução

É invocada `Mestrando::info()`.

Como info() é declarada virtual em Pessoa e redefinida em Estudante e Mestrando, a chamada através de Pessoa\* usa a tabela virtual do objeto concreto (Mestrando).

*   **Invocação de Pessoa::info().** O tipo estático do apontador não decide; o despacho é dinâmico.
*   **Invocação de Estudante::info().** O objeto criado é Mestrando, que redefine info().
*   **Invocação de Mestrando::info().** info() é virtual e o objeto apontado é um Mestrando, logo a versão mais derivada é invocada.
*   **O programa está errado, pois o método virtual void info() não pode ter implementação.** Um método virtual pode ter implementação na classe base.
*   **Nenhuma das possibilidades anteriores.** A terceira opção está correta.

Atribuições entre classes genéricas base e derivada

Teste 1 (CI1), 2018/19

```
template <class T> class Auto { };
template <class T> class AutoOne: public Auto<T> { };

I.    Auto<string> a = AutoOne<string>();
II.   AutoOne<string> b = Auto<string>();
III.  Auto<string> c = AutoOne<int>();
```

Considere as classes genéricas acima. Que atribuições estão corretas?

Solução

Apenas a atribuição I está correta.

Existe conversão implícita de AutoOne para Auto (derivada para base), mas não o contrário, nem entre AutoOne e Auto, pois são instanciações de templates com tipos distintos.

*   **I, II e III.** II e III são inválidas.
*   **II apenas.** II é inválida: não se pode converter base em derivada implicitamente.
*   **I apenas.** A conversão derivada-para-base é válida (I); base-para-derived (II) e entre instanciações com tipos diferentes (III) não compilam.
*   **I e II apenas.** II não compila.
*   **Nenhuma das possibilidades anteriores.** A opção I é válida.

Classe abstrata: definição e utilidade

Teste 1 (CI1), 2017/18

Defina o conceito de classe abstrata. Qual a utilidade de uma classe abstrata?

Solução

Uma classe abstrata é uma classe com pelo menos um membro-função virtual puro, que não pode ser instanciada. Serve de base/interface para hierarquias de classes, permitindo despacho polimórfico através de apontadores ou referências da classe base.

O virtual puro (=0) obriga as classes derivadas a fornecerem a sua implementação, garantindo o contrato da interface definida na classe base.

Confere a tua resposta:

*   A resposta indica que uma classe abstrata contém pelo menos um membro-função virtual puro (declarado com =0).
*   A resposta afirma que não é possível criar objetos dessa classe.
*   A resposta indica a utilidade: definir uma interface comum que as classes derivadas concretizam, permitindo polimorfismo.

## Complexidade temporal

Complexidade de ciclo aninhado com passo geométrico

Teste 1 (CI1), 2016/17

```
void function1(vector<int> &v1) {
   for (int i=0; i<v1.size(); i++)
      for (int j=1; j<v1.size(); j*=2)
         cout << i << " - " << j << endl;
}
```

Indique a complexidade temporal da função acima.

Solução

O(n log n).

Para cada um dos n valores de i, o ciclo interior executa cerca de log₂(n) iterações (j = 1, 2, 4, ...). O número total de impressões é, portanto, Θ(n log n).

*   **O(log n).** O ciclo exterior alone já executa n iterações.
*   **O(n).** Falta contar o ciclo interior, que também itera.
*   **O(n log n).** O ciclo exterior dá n iterações e o interior, com j\*=2, dá O(log n); o total é O(n log n).
*   **O(n²).** O ciclo interior não é linear, pois j cresce geometricamente.
*   **Nenhuma das anteriores.** A terceira opção está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#contar-opera%C3%A7%C3%B5es)

Tempo de um algoritmo O(n²) ao duplicar a entrada

Teste 1 (CI1), 2016/17

A complexidade temporal de um algoritmo é $O(n^2)$. Este algoritmo apresentou um tempo de execução de 10 segundos para um conjunto de dados de entrada de tamanho $n$. Se o tamanho dos dados de entrada for duplicado, quanto tempo demorará (aproximadamente) a execução deste algoritmo?

Solução

40 segundos (aproximadamente).

Num algoritmo Θ(n²), duplicar o tamanho da entrada quadruplica o número de operações básicas: 10 s × 4 = 40 s.

*   **10 segundos.** O tempo não fica igual.
*   **20 segundos.** Duplicar n não duplica o tempo num algoritmo quadrático.
*   **40 segundos.** Se n passa para 2n, o custo passa de c·n² para c·(2n)² = 4·c·n², ou seja, 4 vezes mais: 40 segundos.
*   **100 segundos.** Seria 10× o tempo original, não 4×.
*   **Nenhuma das anteriores.** A terceira opção está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#limites-assint%C3%B3ticos)

Complexidade com ciclo exterior de tamanho fixo

Teste 1 (CI1), 2017/18

```
int funcaoQQ(vector<int> &v) {
   int ct=0;
   for (int i=0; i<10; i++) {
      for (int j=v.size()-1; j>i; j/=2)
         if (v[i]<v[j]) ct++;
   }
   return ct;
}
```

Indique a complexidade temporal da função acima.

Solução

O(log n).

O ciclo exterior repete-se um número fixo de vezes (10), pelo que é uma constante. Em cada iteração, o ciclo interior divide j por 2, executando O(log n) passos. O total é 10·O(log n) = O(log n).

*   **O(log n).** O ciclo exterior tem 10 iterações (constante) e o interior O(log n), logo o total é O(log n).
*   **O(n).** O ciclo exterior não depende de n.
*   **O(n log n).** Seria se o ciclo exterior iterasse n vezes; aqui itera 10.
*   **O(n²).** Nenhum ciclo é quadrático.
*   **Nenhuma das anteriores.** A primeira opção está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#contar-opera%C3%A7%C3%B5es)

Complexidade de ciclo aninhado com divisão por 2

Teste 1 (CI1), 2018/19

```
int funcaoQQ2(vector<int> &vec) {
   int ct=0;
   for (int i=0; i<vec.size(); i++) {
      cout << vec[i];
      for (int j=vec.size(); j>i; j/=2)
         if (vec[i]<vec[j]) ct++;
   }
   return ct;
}
```

Indique a complexidade temporal do fragmento de código acima (no enunciado original faltava o `int` na declaração de `i`, aqui normalizado).

Solução

O(N log N).

Para cada i, o ciclo interior começa em N e divide j por 2 até j ≤ i, num total de O(log N) iterações. Ao fim de N iterações do ciclo exterior, o custo total é O(N log N).

*   **O(N).** O ciclo interior também contribui.
*   **O(log N).** O ciclo exterior já é O(N).
*   **O(N log N).** O ciclo exterior itera N vezes e o interior O(log N) vezes; o total é O(N log N).
*   **O(N²).** O ciclo interior não é linear.
*   **Nenhuma das anteriores.** A terceira opção está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#contar-opera%C3%A7%C3%B5es)

Comparação assintótica de função exponencial com polinomial

Teste 1 (CI1 teórica), 2022/23

Considere as funções $f(n)=2^{n/2}$ e $g(n)=n^2$. Qual das afirmações é verdadeira?

Solução

$f(n)inOmega(g(n))$, mas não $O(g(n))$ nem $Theta(g(n))$.

Toda função exponencial com base > 1 domina qualquer polinomial. Assim, $lim_{n oinfty} 2^{n/2}/n^2 = +infty$, o que mostra que f é Ω de g mas não O de g.

*   **$f(n)inTheta(g(n))$.** Para ser Θ, f teria de ser simultaneamente O e Ω de g; não é O de g.
*   **$f(n)$ não é $Theta$, $O$ ou $Omega$ de $g(n)$.** f é Ω de g.
*   **$f(n)in O(g(n))$.** A exponencial cresce mais depressa que o polinomial, logo f não é limitada superiormente por g.
*   **$f(n)inOmega(g(n))$.** 2^(n/2) cresce mais depressa que n², logo existe c tal que f(n) ≥ c·g(n) para n suficientemente grande.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#limites-assint%C3%B3ticos)

Complexidade da soma recursiva por divisão em duas metades

Teste 1 (CI1 teórica), 2022/23

```
int sum(int a, int b) {
   if (a==b) return a;
   int middle = (b-a)/2 + a;
   return sum(a, middle) + sum(middle+1, b);
}
```

A função recursiva acima calcula a soma dos inteiros entre a e b. Qual é a sua complexidade temporal?

Solução

$Theta(n)$.

Cada chamada divide o intervalo em duas metades e faz trabalho constante, pelo que T(n) = 2T(n/2) + O(1). Pelo teorema mestre (caso 2), ou somando os níveis da árvore de recorrência (n folhas e custo total proporcional a n), obtém-se Θ(n).

*   **$Theta(2^n)$.** A árvore de recorrência não tem 2^n folhas.
*   **$Theta(n \log n)$.** Cada nível trabalha O(1) por nó e há n folhas, não n log n de trabalho total.
*   **$Theta(\log n)$.** Há n chamadas no último nível.
*   **$Theta(n)$.** A recorrência T(n)=2T(n/2)+O(1) resolve-se para Θ(n): a árvore tem n folhas e o trabalho por nível decresce geometricamente.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#recorr%C3%AAncias-e-espa%C3%A7o)

## Pesquisa e ordenação

Custo de inserir num vetor ordenado

Teste 1 (CI1), 2017/18

A inserção de um elemento num vetor ordenado (mantendo a ordenação) é realizada pelo seguinte algoritmo: uso de pesquisa binária para localizar a posição onde deve ser inserido o novo elemento; inserir o novo elemento nessa posição. Qual a complexidade temporal deste algoritmo?

Solução

O(N).

Localizar a posição com pesquisa binária custa O(log N), mas a posição de inserção obriga a deslocar todos os elementos à direita, uma operação O(N). O custo total é dominado por O(N).

*   **O(log N).** A pesquisa binária é O(log N), mas a inserção exige deslocar elementos.
*   **O(N log N).** O deslocamento é linear, não logarítmico.
*   **O(N²).** Não há dois ciclos aninhados.
*   **O(N).** A pesquisa binária custa O(log N), mas inserir na posição correta desloca até N elementos, com custo O(N) dominante.
*   **Nenhuma das anteriores.** A quarta opção está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/pesquisa-ordenacao/#pesquisa-bin%C3%A1ria-com-limites)

Trocas inúteis da ordenação por seleção num vetor decrescente

Teste 1 (CI1), 2018/19

O algoritmo de ordenação por seleção é usado na ordenação, por ordem crescente, de um vetor de 100 elementos. Considerando que o vetor está inicialmente ordenado por ordem decrescente {100, 99, 98, ..., 1}, quantas trocas inúteis são realizadas, aproximadamente? (uma troca inútil ocorre quando um elemento é trocado com ele próprio, logo o vetor não se altera).

Solução

Aproximadamente 50 trocas inúteis.

Numa ordenação por seleção, a cada passo i procura-se o mínimo do sufixo v\[i..99\] e troca-se com v\[i\]. Num vetor decrescente, a segunda metade do vetor já fica ordenada por ordem crescente à medida que os menores vão sendo colocados à frente; a partir de cerca de i = 50, o mínimo já está na posição i e a troca é inútil. Total: ≈ n/2 = 50.

*   **100.** Nem todas as iterações fazem troca inútil.
*   **50.** Na primeira metade o elemento mínimo ainda não está no sítio; a partir de i ≈ 50 o mínimo do sufixo já está na posição i e a troca é consigo próprio.
*   **0.** Há várias trocas consigo próprio na segunda metade.
*   **6.** O valor não depende de logaritmos.
*   **Nenhuma das anteriores.** A segunda opção está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#ordena%C3%A7%C3%B5es-elementares)

Invariante útil do bubblesort decrescente

Teste 1 (CI1 teórica), 2022/23

```
void bubblesort(vector<int> &v) {
   for (unsigned i=0; i<v.size()-1; i++)
      for (unsigned j=0; j<v.size()-i-1; j++)
         if (v[j] < v[j+1])
            swap(v[j], v[j+1]);
}
```

Está a ordenar-se um vetor de inteiros por ordem decrescente com o bubblesort acima. Qual das seguintes condições é um invariante útil no início de cada iteração do ciclo com a variável i, para provar a correção do algoritmo?

Solução

Os maiores i números de todo o vetor estão nas últimas i posições e estão ordenados.

Como a ordenação é decrescente e a comparação troca quando v\[j\] < v\[j+1\], o maior elemento remanescente acaba na última posição ainda não fixada a cada passagem. Assim, no início da iteração i, as posições v\[n-i..n-1\] contêm os i maiores valores, por ordem decrescente, e nunca mais saem de lá.

*   **Os mais pequenos i números de todo o vetor estão nas primeiras i posições e estão ordenados.** Isso seria o invariante da ordenação crescente, não da decrescente.
*   **Os maiores i números de todo o vetor estão nas primeiras i posições e estão ordenados.** Os maiores elementos vão para o fim do vetor nesta implementação decrescente.
*   **Os mais pequenos i números de todo o vetor estão nas últimas i posições e estão ordenados.** Numa ordenação decrescente, os menores é que ficam no fim, mas o invariante do ciclo exterior refere-se aos maiores i números.
*   **Os maiores i números de todo o vetor estão nas últimas i posições e estão ordenados.** A cada passagem do ciclo interior, o maior elemento da parte não processada sobe para a última posição livre; no início da iteração i do ciclo exterior, as últimas i posições contêm os maiores i elementos, ordenados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#contrato-e-invariante)

Pior caso do Quicksort

Teste 1 (CI1), 2017/18

O algoritmo de ordenação Quicksort possui complexidade temporal $O(n\log n)$ no caso médio, mas pode, no pior caso, apresentar complexidade temporal $O(n^2)$. Explique porquê.

Solução

O pior caso acontece quando, em cada partição, um dos lados fica vazio: o pivô é o menor ou o maior elemento. A recorrência fica T(n) = T(n-1) + Θ(n), que resolve para Θ(n²). Exemplo: vetor já ordenado com o pivô escolhido no primeiro elemento.

Cada partição custa Θ(n) para colocar o pivô no sítio, mas se um lado tem tamanho 0 e o outro n-1, a árvore de recursão degenera numa lista com n níveis, dando um total de n + (n-1) + ... + 1 = Θ(n²).

Confere a tua resposta:

*   A resposta indica que o pior caso ocorre quando a partição é sempre maximamente desbalanceada (o pivô é o menor ou o maior elemento do intervalo).
*   A resposta apresenta a recorrência T(n) = T(n-1) + Θ(n) (ou equivalente) e conclui Θ(n²).
*   A resposta dá um exemplo de entrada que provoca esse caso, como um vetor já ordenado com o pivô escolhido no primeiro elemento.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#quicksort-e-parti%C3%A7%C3%A3o)

## Estruturas de dados lineares

Estrutura adequada ao botão "voltar" de um browser

Teste 1 (CI1 teórica), 2022/23

Qualquer browser possui a funcionalidade de retorno à página visitada anteriormente. Na implementação desta (e apenas desta) funcionalidade, qual a estrutura de dados que considera mais adequada (eficiente em tempo e espaço)?

Solução

Pilha (stack).

A cada nova página faz-se push; o botão "voltar" faz pop, devolvendo a página visitada mais recentemente. É a disciplina LIFO, implementada de forma eficiente e económica com uma pilha.

*   **Fila.** A fila dá o primeiro a entrar, não o último.
*   **Lista duplamente ligada.** Gasta mais memória do que o necessário para esta função.
*   **Lista simplesmente ligada.** Também funciona, mas a pilha é a estrutura natural e mais simples.
*   **Pilha.** A página "anterior" é sempre a última visitada: comportamento LIFO, com push/pop em O(1).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/listas-pilhas-filas/#aplica%C3%A7%C3%B5es-de-pilhas)

Operações em O(1) numa lista simplesmente ligada com cabeça e cauda

Teste 1 (CI1 teórica), 2022/23

Considere a estrutura lista implementada por uma lista simplesmente ligada com referências para o início e o fim (primeiro e último nó). Quais das seguintes operações podem ser realizadas em tempo O(1)?

*   I. inserir um elemento no início da lista
*   II. inserir um elemento no fim da lista
*   III. remover o primeiro elemento (início) da lista
*   IV. remover o último elemento (fim) da lista

Solução

I, II e III apenas.

Inserir no início (I), inserir no fim graças à cauda (II) e remover o primeiro (III) são operações locais, em O(1). Remover o último (IV) exige o nó anterior ao último, que numa lista simplesmente ligada obriga a percorrer a lista inteira: O(n).

*   **I, II e IV, apenas.** IV não é O(1) numa lista simplesmente ligada.
*   **I e II, apenas.** Falta a III, que também é O(1).
*   **I, II e III, apenas.** Com apontador para a cauda, inserir no fim é O(1); remover o último exigiria percorrer a lista para atualizar a cauda, logo é O(n).
*   **I e III, apenas.** II também é O(1) graças à referência para o fim.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/listas-pilhas-filas/#lista-simplesmente-ligada)

## Árvores binárias de pesquisa

Árvore binária de pesquisa resultante de uma sequência de inserções

Teste 1 (CI1 teórica), 2022/23

Se introduzir a sequência 10, 15, 7, 9, 17, 12 numa árvore binária de pesquisa, a árvore resultante:

Solução

Não é completa, e é equilibrada.

Inserindo por ordem: 10 é a raiz; 15 fica à direita; 7 à esquerda; 9 à direita de 7; 17 à direita de 15; 12 à esquerda de 15. A subárvore de 7 tem apenas o filho direito 9, pelo que o nível 2 não está preenchido da esquerda para a direita e a árvore não é completa. Em qualquer nó, as alturas das duas subárvores diferem no máximo de 1 (raiz: 1 e 2), logo a árvore é equilibrada.

*   **Não é completa, e é equilibrada.** O nó 7 só tem filho direito (9), logo a árvore não é completa; mas as alturas das subárvores de cada nó diferem no máximo de 1, logo é equilibrada.
*   **É completa, e não é equilibrada.** Não é completa nem está desiquilibrada.
*   **Não é completa e não é equilibrada.** A árvore é equilibrada.
*   **É completa e equilibrada.** Não é completa.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/arvores-pesquisa/#ordem-de-inser%C3%A7%C3%A3o-e-altura)