Lista de exercícios de Algoritmos e complexidade com respostas

Lista de exercícios de Algoritmos e complexidade grátis para imprimir: 8 exercícios do nível fácil ao nível de prova, com gabarito. Imprima ou salve como PDF.

Nova lista de exercíciosPratique on-line com dicas

Para professores: pode imprimir, copiar e usar em aula gratuitamente. Cada nova folha tem novos valores e o seu próprio gabarito. Agradecemos um link para o ExamProblems na página da sua disciplina.

Nome: ____________________   Data: ____________

1.Fácil

Qual destes tempos de execução é polinomial?

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

Qual é o O grande de 3n² + 5n + 2?

  1. AO(5n)
  2. BO(3n²)
  3. CO(n²)
  4. DO(n³)
3.Fácil

O que é recursão?

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

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

  1. AO(2ⁿ)
  2. BO(n)
  3. CO(n²)
  4. DO(log n)
5.Média

Você ordena um array de n elementos uma vez e depois responde a k consultas de pertinência com busca binária. Qual é o custo total?

  1. AO(n log n + k log n)
  2. BO(nk)
  3. CO(k n log n)
  4. DO(n + k)
6.Média

Quantos níveis tem a recursão do merge sort para um array de n elementos?

  1. ACerca de log₂ n
  2. BCerca de n / 2
  3. CCerca de √n
  4. DCerca de n
7.Difícil

Qual técnica dá ao quicksort um tempo de execução esperado O(n log n) para qualquer entrada?

  1. AOrdenar a entrada antes de executar o quicksort
  2. BUsar recursão apenas no lado esquerdo
  3. CEscolher o pivô de forma uniformemente aleatória
  4. DSempre escolher o primeiro elemento
8.Difícil

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

  1. AFloyd-Warshall
  2. BAlgoritmo de Dijkstra
  3. CAlgoritmo de Kruskal
  4. DAlgoritmo de Prim a partir de um nó

Gabarito

  1. 1. D · O(n³)
  2. 2. C · O(n²)
  3. 3. C · Uma função que chama a si mesma com entradas menores
  4. 4. B · O(n)
  5. 5. A · O(n log n + k log n)
  6. 6. A · Cerca de log₂ n
  7. 7. C · Escolher o pivô de forma uniformemente aleatória
  8. 8. C · Algoritmo de Kruskal

Soluções completas passo a passo: pratique este tópico em examproblems.com.