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

Um algoritmo O(n) leva 3 segundos para n = 1 milhão. Quanto tempo leva, aproximadamente, para n = 2 milhões?

  1. A12 segundos
  2. B9 segundos
  3. C3 segundos
  4. D6 segundos
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 é o caso base de uma função recursiva?

  1. AO caso com a maior entrada, que é tratado antes de quaisquer chamadas recursivas
  2. BUm caso respondido diretamente, sem fazer outra chamada recursiva
  3. CA primeira linha da função
  4. DA chamada que usa mais memória
4.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)
  2. BO(n³)
  3. CO(n²)
  4. DO(n log n)
5.Média

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

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

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

O problema da parada mostra que:

  1. ATodo programa acaba parando
  2. BLaços devem ser evitados
  3. CNenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para
  4. DAlguns programas rodam mais rápido em computadores mais rápidos, então a parada depende do hardware
8.Difícil

Usando o teorema mestre, T(n) = 8T(n/2) + O(n²) tem como solução:

  1. AΘ(n²)
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(n log n)

Gabarito

  1. 1. D · 6 segundos
  2. 2. C · O(n²)
  3. 3. B · Um caso respondido diretamente, sem fazer outra chamada recursiva
  4. 4. C · O(n²)
  5. 5. A · O(n)
  6. 6. C · O(n log n)
  7. 7. C · Nenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para
  8. 8. B · Θ(n³)

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