Lista de exercícios de Algoritmos e complexidade com respostas

Qual algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

1. ABubble sort (ordenação por bolha)
2. BHeap sort
3. CMerge sort (ordenação por intercalação)
4. DQuicksort

A complexidade de espaço mede:

1. AO tamanho físico do computador
2. BO número de linhas de código
3. CA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
4. DO espaço em disco do arquivo do programa depois de compilado

Qual destas cresce mais devagar quando n fica grande?

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(n²)

Você ordena um array de n elementos uma vez e depois responde a k consultas de pertinência com busca binária. Qual é o custo total?

1. AO(n + k)
2. BO(k n log n)
3. CO(n log n + k log n)
4. DO(nk)

Um quicksort usa sempre o primeiro elemento como pivô. Com qual entrada ele apresenta o comportamento de pior caso?

1. AUm array em ordem aleatória
2. BUm array com todos os elementos diferentes
3. CUm array que já está ordenado
4. DUm array de tamanho 2

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 3 moedas; o ótimo é 2
2. BO guloso usa 3 moedas; o ótimo é 3
3. CO guloso usa 4 moedas; o ótimo é 3
4. DO guloso usa 2 moedas; o ótimo é 2

A multiplicação de Karatsuba satisfaz T(n) = 3T(n/2) + O(n). Qual é a solução?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), cerca de n^1,585

Qual definição da classe P está correta?

1. AProblemas de decisão solúveis por um algoritmo determinístico em tempo polinomial
2. BProblemas que exigem tempo exponencial em qualquer computador
3. CProblemas cujas soluções podem ser verificadas, mas nunca encontradas, em tempo polinomial
4. DProblemas que podem ser resolvidos em paralelo