Lista de exercícios de Algoritmos e complexidade com respostas

Como funciona o selection sort?

1. AEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente
2. BTroca repetidamente elementos vizinhos que estão na ordem errada
3. CInsere cada elemento numa parte ordenada crescente por deslocamento
4. DDivide o array em metades e as intercala

O que significa f(n) = Θ(g(n))?

1. Af é sempre menor que g para todo n, então g a limita por cima, mas nunca por baixo
2. Bf cresce no mesmo ritmo que g, limitada por cima e por baixo por múltiplos constantes de g
3. Cf cresce estritamente mais rápido que g
4. Df cresce estritamente mais devagar que g

Qual é a complexidade de tempo do merge sort no pior caso?

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

Qual algoritmo de ordenação é estável?

1. ASelection sort (versão típica)
2. BHeap sort
3. CMerge sort
4. DQuicksort (versão in-place típica)

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

Por que qualquer busca baseada em comparações num array ordenado precisa de Ω(log n) comparações no pior caso?

1. AUma árvore de decisão com n resultados possíveis precisa ter profundidade de pelo menos log₂ n
2. BA busca binária é o único algoritmo possível e precisa de log₂ n comparações
3. CTodo elemento precisa ser comparado pelo menos uma vez
4. DCada comparação leva tempo logarítmico

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

1. ATempo O(n) e espaço O(n)
2. BTempo O(2ⁿ) e espaço O(1)
3. CTempo O(n) e espaço O(1)
4. DTempo O(log n) e espaço O(n)