Lista de exercícios de Algoritmos e complexidade com respostas

O que é um algoritmo?

1. AQualquer programa de computador com interface gráfica
2. BUma linguagem de programação criada para escrever fórmulas matemáticas
3. CUma estrutura de dados que armazena números
4. DUma sequência finita de passos bem definidos que resolve um problema

Quanto é log₂ 1024?

1. A512
2. B10
3. C32
4. D12

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. BCerca de n
3. CCerca de log₂ n
4. DCerca de n / 2

A programação dinâmica é útil quando um problema tem:

1. ASubproblemas sobrepostos e subestrutura ótima
2. BNenhum subproblema, de modo que pode ser resolvido em um único passo
3. CApenas entradas aleatórias
4. DUm único laço

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

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

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

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

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

1. An! é O(n²)
2. B2ⁿ cresce mais rápido que n!
3. Cn! cresce mais rápido que 2ⁿ
4. DCrescem no mesmo ritmo

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

1. ASim, portanto o limite inferior está errado
2. BNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada
3. CSim, mas só para arrays com menos de 100 elementos
4. DNão, porque o insertion sort não é uma ordenação por comparação