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. AQuicksort
2. BBubble sort
3. CMerge sort
4. DInsertion sort

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

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

Qual estratégia de projeto o merge sort usa?

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

Qual é a complexidade de tempo do algoritmo de Bellman–Ford num grafo com V vértices e E arestas?

1. AO(V³ × E)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

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

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

O que a análise amortizada mede?

1. AO custo da operação individual mais cara em qualquer ponto da sequência
2. BO custo médio por operação ao longo de uma sequência de operações de pior caso
3. CO custo esperado sobre entradas aleatórias
4. DO custo de um algoritmo com a melhor entrada

A ordenação topológica só é possível para:

1. AGrafos não dirigidos
2. BGrafos acíclicos dirigidos (DAG)
3. CGrafos completos
4. DGrafos com pesos negativos

Qual é a complexidade de tempo para construir um heap binário a partir de n elementos não ordenados com o método bottom-up?

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