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

O que é um algoritmo?

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

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

  1. A1 segundo
  2. B4 segundos
  3. C2 segundos
  4. D8 segundos
3.Fácil

Qual é a complexidade de tempo do merge sort no pior caso?

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

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

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

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

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

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

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

Qual limite está correto para log(n!)?

  1. AΘ(n)
  2. BΘ(n²)
  3. CΘ(log n)
  4. DΘ(n log n)
8.Difícil

O que decorreria se alguém encontrasse um algoritmo de tempo polinomial para um problema NP-completo?

  1. ASó aquele problema passaria para P
  2. BTodo problema em NP poderia ser resolvido em tempo polinomial, então P = NP
  3. CTodos os algoritmos de tempo exponencial passariam imediatamente a rodar em tempo linear
  4. DO problema da parada se tornaria decidível

Gabarito

  1. 1. C · Uma sequência finita de passos bem definidos que resolve um problema
  2. 2. B · 4 segundos
  3. 3. B · O(n log n)
  4. 4. C · O(n²)
  5. 5. A · Ω(n log n)
  6. 6. C · Cerca de log₂ n
  7. 7. D · Θ(n log n)
  8. 8. B · Todo problema em NP poderia ser resolvido em tempo polinomial, então P = NP

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