Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

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

O que é o caso base de uma função recursiva?

1. AA chamada que usa mais memória
2. BO caso com a maior entrada, que é tratado antes de quaisquer chamadas recursivas
3. CUm caso respondido diretamente, sem fazer outra chamada recursiva
4. DA primeira linha da função

O que é um algoritmo?

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

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

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

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

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

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

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

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

Qual definição da classe NP está correta?

1. AProblemas que não são polinomiais
2. BProblemas que nenhum algoritmo consegue resolver
3. CProblemas que não podem ser resolvidos em tempo polinomial
4. DProblemas de decisão cujas respostas "sim" podem ser verificadas em tempo polinomial dado um certificado