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 classe de complexidade cresce mais rápido para n grande?

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

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

  1. A2 segundos
  2. B1 segundo
  3. C4 segundos
  4. D8 segundos
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)
  2. BO(1)
  3. CO(log n)
  4. DO(n log n)
4.Média

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

  1. ABellman-Ford é necessário em todos os casos
  2. BAlgoritmo de Dijkstra
  3. CAlgoritmo de Kruskal
  4. DBusca em profundidade (DFS)
5.Média

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

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

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

Como n! e 2ⁿ se comparam para n grande?

  1. An! cresce mais rápido que 2ⁿ
  2. BCrescem no mesmo ritmo
  3. Cn! é O(n²)
  4. D2ⁿ cresce mais rápido que n!
8.Difícil

Qual afirmação sobre a notação o pequeno está correta?

  1. An = o(n²), mas n não é o(n)
  2. Bn = o(n), já que toda função é o pequeno de si mesma
  3. C2n = o(n), porque 2n cresce devagar
  4. Dn² = o(n)

Gabarito

  1. 1. B · O(2ⁿ)
  2. 2. C · 4 segundos
  3. 3. A · O(n)
  4. 4. B · Algoritmo de Dijkstra
  5. 5. B · O(n³)
  6. 6. D · O(n²)
  7. 7. A · n! cresce mais rápido que 2ⁿ
  8. 8. A · n = o(n²), mas n não é o(n)

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