Lista de exercícios de Algoritmos e complexidade com respostas

Um problema costuma ser chamado de tratável se:

1. APode ser resolvido em tempo polinomial
2. BSó pode ser resolvido testando todas as possibilidades
3. CPode ser resolvido em tempo constante
4. DNão tem solução

O que descreve o tempo de execução de um algoritmo no pior caso?

1. AO tempo que leva num computador lento
2. BO tempo esperado que leva com uma entrada aleatória de tamanho n
3. CO tempo que leva com a menor entrada
4. DO tempo máximo que ele leva entre todas as entradas de tamanho n

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

1. AInsertion sort
2. BBubble sort
3. CQuicksort
4. DMerge sort

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

1. AEscolher a atividade que começa mais cedo
2. BEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis
3. CEscolher primeiro a atividade mais curta
4. DEscolher a atividade que termina mais cedo e repetir com as compatíveis

O limite inferior para ordenação baseada em comparações no pior caso é:

1. AΩ(n²)
2. BΩ(n)
3. CΩ(n log n)
4. DΩ(log n)

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

1. AAlgoritmo de Kruskal
2. BBellman-Ford é necessário em todos os casos
3. CBusca em profundidade (DFS)
4. DAlgoritmo de Dijkstra

Como o algoritmo de Bellman–Ford detecta um ciclo de peso negativo alcançável a partir da origem?

1. AExecuta o algoritmo de Dijkstra duas vezes e compara os dois resultados de distância
2. BVerifica se alguma aresta tem peso negativo
3. CApós V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada
4. DConta os ciclos com busca em profundidade

Qual afirmação sobre selecionar o k-ésimo menor elemento de um array não ordenado está correta?

1. AO quickselect roda em O(log n) no pior caso, porque faz recursão em apenas um lado do pivô
2. BO quickselect roda em O(n) esperado, e a mediana das medianas garante O(n) no pior caso
3. CA seleção só é possível em O(n²)
4. DA seleção sempre exige Ω(n log n), porque requer ordenação