Lista de exercícios de Algoritmos e complexidade com respostas

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

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

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

1. AÔmega grande (Big Omega)
2. BTheta grande (Big Theta)
3. CÔmega pequeno (little omega)
4. DO grande (Big O)

Qual estratégia de projeto o merge sort usa?

1. AForça bruta
2. BDivisão e conquista
3. CEscolha gulosa
4. DProgramação dinâmica

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

Qual é a solução da recorrência T(n) = 2T(n − 1) + O(1)?

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

Quantos níveis tem a recursão do merge sort para um array de n elementos?

1. ACerca de n / 2
2. BCerca de n
3. CCerca de √n
4. DCerca de log₂ n

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

1. AÉ sempre solúvel em O(V + E)
2. BÉ indecidível
3. CPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
4. DÉ NP-difícil

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

1. AAlgoritmo de Dijkstra
2. BFloyd-Warshall
3. CAlgoritmo de Kruskal
4. DAlgoritmo de Prim a partir de um nó