Lista de exercícios de Algoritmos e complexidade com respostas

Quanta memória extra usa um merge sort padrão baseado em arrays?

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

Qual é o O grande de 3n² + 5n + 2?

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

O que a busca binária exige da sua entrada?

1. AO tamanho do array deve ser uma potência de dois
2. BO array deve estar ordenado
3. CO array deve conter só números positivos
4. DO array não pode ter mais de 1000 elementos

Como o algoritmo de Prim constrói uma árvore geradora mínima?

1. AOrdena todas as arestas por peso e adiciona cada uma, a menos que forme um ciclo na floresta
2. BExecuta uma busca em largura e mantém a árvore da BFS
3. CRemove a aresta mais cara até não restarem ciclos
4. DFaz crescer uma árvore a partir de um vértice inicial, adicionando a aresta mais barata que sai da árvore

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

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

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

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

Como n! e 2ⁿ se comparam para n grande?

1. A2ⁿ cresce mais rápido que n!
2. Bn! é O(n²)
3. CCrescem no mesmo ritmo
4. Dn! cresce mais rápido que 2ⁿ

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

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