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 significa uma operação rodar em tempo O(1)?

  1. AProcessa exatamente um elemento por segundo de tempo de execução
  2. BSeu tempo de execução não cresce com o tamanho da entrada
  3. CSó pode ser executada uma vez
  4. DSempre leva exatamente um segundo
2.Fácil

Qual destas cresce mais devagar quando n fica grande?

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

Qual é a complexidade de tempo para encontrar o maior valor num array não ordenado de n números?

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

O que significa um problema ter subestrutura ótima?

  1. AO problema pode ser resolvido em tempo constante
  2. BO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas
  3. CTodos os subproblemas têm o mesmo tamanho
  4. DUma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
5.Média

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

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

A programação dinâmica é útil quando um problema tem:

  1. AUm único laço
  2. BNenhum subproblema, de modo que pode ser resolvido em um único passo
  3. CSubproblemas sobrepostos e subestrutura ótima
  4. DApenas entradas aleatórias
7.Difícil

A multiplicação de Karatsuba satisfaz T(n) = 3T(n/2) + O(n). Qual é a solução?

  1. AΘ(n²)
  2. BΘ(n3)
  3. CΘ(nlog₂ 3), cerca de n1,585
  4. DΘ(n log n)
8.Difícil

Qual é a complexidade de tempo para construir um heap binário a partir de n elementos não ordenados com o método bottom-up?

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

Gabarito

  1. 1. B · Seu tempo de execução não cresce com o tamanho da entrada
  2. 2. B · O(log n)
  3. 3. D · O(n)
  4. 4. D · Uma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
  5. 5. B · O(n²)
  6. 6. C · Subproblemas sobrepostos e subestrutura ótima
  7. 7. C · Θ(nlog₂ 3), cerca de n1,585
  8. 8. C · O(n)

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