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. AHeap sort
2. BQuicksort
3. CMerge sort (ordenação por intercalação)
4. DBubble sort (ordenação por bolha)

Qual notação descreve um limite inferior de crescimento?

1. AΩ (Ômega grande)
2. BΘ (Theta grande)
3. CO (O grande)
4. Do (o pequeno)

Quanto é log₂ 1024?

1. A10
2. B512
3. C12
4. D32

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. AO merge sort já é O(n)
2. BSeus subproblemas não se sobrepõem, então não há nada para reaproveitar
3. CO merge sort não tem estrutura recursiva
4. DA programação dinâmica só funciona em problemas de grafos, não em vetores

A recorrência T(n) = 2T(n/2) + O(n) tem como solução:

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

Qual é a complexidade de tempo para construir um heap binário a partir de n elementos não ordenados com o método bottom-up?

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

O problema da parada mostra que:

1. ATodo programa acaba parando
2. BAlguns programas rodam mais rápido em computadores mais rápidos, então a parada depende do hardware
3. CLaços devem ser evitados
4. DNenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para