Lista de exercícios de Algoritmos e complexidade com respostas

Qual algoritmo de ordenação escolhe um pivô e particiona o array em elementos menores e maiores?

1. AMerge sort
2. BBubble sort
3. CInsertion sort
4. DQuicksort

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

1. AO grande (Big O)
2. BÔmega grande (Big Omega)
3. CÔmega pequeno (little omega)
4. DTheta grande (Big Theta)

O que é memoização?

1. AArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
2. BEscrever comentários ao lado de cada linha de código
3. CLiberar memória depois que uma função retorna
4. DConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas

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 4 moedas; o ótimo é 3
3. CO guloso usa 2 moedas; o ótimo é 2
4. DO guloso usa 3 moedas; o ótimo é 2

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(mn log n)
2. BO(2^m+n)
3. CO(m + n)
4. DO(mn)

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

Como é classificado o problema do caixeiro-viajante?

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

Qual técnica dá ao quicksort um tempo de execução esperado O(n log n) para qualquer entrada?

1. AOrdenar a entrada antes de executar o quicksort
2. BSempre escolher o primeiro elemento
3. CUsar recursão apenas no lado esquerdo
4. DEscolher o pivô de forma uniformemente aleatória