Lista de exercícios de Algoritmos e complexidade com respostas

Qual classe de complexidade cresce mais rápido para n grande?

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

Qual destes tempos de execução é polinomial?

1. AO(2ⁿ)
2. BO(n!)
3. CO(n³)
4. DO(nⁿ)

O que é recursão?

1. AUm laço que nunca termina
2. BUm método de ordenação
3. CUma função que chama a si mesma com entradas menores
4. DUm tipo de estrutura de dados

Qual é a complexidade de tempo de: for i = 1 to n: for j = 1 to i: faça trabalho O(1)?

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

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

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

Por que o algoritmo de Dijkstra pode dar resultados errados quando alguns pesos de aresta são negativos?

1. ASó funciona em grafos não dirigidos
2. BEntra num laço infinito a cada aresta negativa
3. CUm vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto
4. DNúmeros negativos não podem ser armazenados numa fila de prioridade

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

1. AFunções hash são lentas
2. BArrays têm acesso O(n)
3. CMuitas chaves podem colidir no mesmo bucket
4. DAs chaves precisam ser ordenadas primeiro