Lista de exercícios de Algoritmos e complexidade com respostas

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 que leva com a menor entrada
3. CO tempo máximo que ele leva entre todas as entradas de tamanho n
4. DO tempo esperado que leva com uma entrada aleatória de tamanho n

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

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

1. ABubble sort
2. BMerge sort
3. CQuicksort
4. DInsertion sort

A busca em largura (BFS) em um grafo não ponderado encontra:

1. AUma ordenação topológica em todos os grafos
2. BCaminhos mínimos em grafos que contêm arestas com pesos negativos
3. CCaminhos mínimos em número de arestas a partir do nó inicial
4. DA árvore geradora mínima

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

1. ANo máximo o dobro do tamanho de uma cobertura de vértices mínima
2. BSempre uma cobertura de vértices mínima
3. CNo máximo log n vezes o mínimo
4. DDe qualidade desconhecida em relação ao ótimo

Por que a busca média em uma tabela hash é O(1), mas o pior caso é O(n)?

1. AMuitas chaves podem colidir no mesmo bucket
2. BAs chaves precisam ser ordenadas primeiro
3. CFunções hash são lentas
4. DArrays têm acesso O(n)