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

A complexidade de espaço mede:

  1. AA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  2. BO número de linhas de código
  3. CO espaço em disco do arquivo do programa depois de compilado
  4. DO tamanho físico do computador
2.Fácil

Qual estratégia de projeto o merge sort usa?

  1. AProgramação dinâmica
  2. BForça bruta
  3. CDivisão e conquista
  4. DEscolha gulosa
3.Fácil

O que é um algoritmo?

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

O limite inferior para ordenação baseada em comparações no pior caso é:

  1. AΩ(n²)
  2. BΩ(n)
  3. CΩ(log n)
  4. DΩ(n log n)
5.Média

A recorrência T(n) = 2T(n/2) + O(n) tem como solução:

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

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

  1. AO(n)
  2. BO(2ⁿ)
  3. CO(n log n)
  4. DO(n²)
7.Difícil

O que o teorema de Cook–Levin estabeleceu?

  1. AO problema da parada é indecidível
  2. BTodo problema NP pode ser resolvido em tempo exponencial
  3. CO problema da satisfatibilidade booleana (SAT) é NP-completo
  4. DP é diferente de NP
8.Difícil

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 √n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)

Gabarito

  1. 1. A · A quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  2. 2. C · Divisão e conquista
  3. 3. D · Uma sequência finita de passos bem definidos que resolve um problema
  4. 4. D · Ω(n log n)
  5. 5. A · O(n log n)
  6. 6. B · O(2ⁿ)
  7. 7. C · O problema da satisfatibilidade booleana (SAT) é NP-completo
  8. 8. B · O(n log n)

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