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 é a complexidade de tempo da busca em profundidade num grafo armazenado como listas de adjacência?

  1. AO(V²)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(E log V)
2.Fácil

Qual classe de complexidade cresce mais rápido para n grande?

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

Qual é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

  1. AO(n²)
  2. BO(n + k)
  3. CO(n log n)
  4. DO(k log n)
4.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)
  4. DO(n log n)
5.Média

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

É correto dizer que um algoritmo O(n²) também é O(n³)?

  1. ASim, mas só se n for menor que 100
  2. BNão, porque o O grande deve sempre dar a taxa de crescimento exata da função
  3. CSim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
  4. DNão, porque n³ é menor que n² para n grande
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

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

Gabarito

  1. 1. C · O(V + E)
  2. 2. D · O(2ⁿ)
  3. 3. B · O(n + k)
  4. 4. B · O(2ⁿ)
  5. 5. D · O(n)
  6. 6. C · Sim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
  7. 7. D · Θ(n log n)
  8. 8. B · O(n)

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