Exercícios MT1

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.

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.

É 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.

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.

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.

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.

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.

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.

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.

$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.

$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.

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.

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.

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.

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²).

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).

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.

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.