Lista de exercícios de Algoritmos e complexidade com respostas

Quais são as três etapas de um algoritmo de divisão e conquista?

1. AChutar, verificar, repetir
2. BDividir, conquistar, combinar
3. COrdenar, buscar, retornar
4. DLer, calcular, escrever

Quanto é log₂ 1024?

1. A12
2. B32
3. C512
4. D10

O que significa uma operação rodar em tempo O(1)?

1. ASempre leva exatamente um segundo
2. BSó pode ser executada uma vez
3. CProcessa exatamente um elemento por segundo de tempo de execução
4. DSeu tempo de execução não cresce com o tamanho da entrada

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

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

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

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

Por que muitas rotinas de ordenação de bibliotecas passam para o insertion sort em subarrays muito pequenos?

1. AO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
2. BAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos
3. CO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes
4. DO insertion sort é O(n log n) no pior caso

Como é classificado o problema do caixeiro-viajante?

1. AEstá em P, porque o algoritmo de Dijkstra o resolve visitando cada cidade uma única vez
2. BA versão de decisão está em P, mas a versão de otimização é NP-completa
3. CÉ indecidível
4. DA versão de decisão é NP-completa e a versão de otimização é NP-difícil

Qual é o custo amortizado de incrementar um contador binário, sabendo que um incremento pode inverter muitos bits?

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