Lista de exercícios de Algoritmos e complexidade com respostas

Qual estratégia de projeto o merge sort usa?

1. ADivisão e conquista
2. BForça bruta
3. CProgramação dinâmica
4. DEscolha gulosa

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

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

Acessar um elemento de um array pelo índice leva:

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

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

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

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

1. AUma ordenação topológica em O(V²)
2. BUma árvore geradora mínima em O(E log V)
3. CCaminhos mínimos entre todos os pares de vértices em O(V³)
4. DCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 3 moedas; o ótimo é 3
2. BO guloso usa 3 moedas; o ótimo é 2
3. CO guloso usa 4 moedas; o ótimo é 3
4. DO guloso usa 2 moedas; o ótimo é 2

Qual é a complexidade de tempo de: for i = 1 to n: for (j = i; j ≤ n; j = j + i) faça trabalho O(1)?

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

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

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