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

Quais são as três etapas de um algoritmo de divisão e conquista?

  1. AOrdenar, buscar, retornar
  2. BChutar, verificar, repetir
  3. CDividir, conquistar, combinar
  4. DLer, calcular, escrever
2.Fácil

Como se chama o crescimento O(2ⁿ)?

  1. ALogarítmico
  2. BLinear
  3. CExponencial
  4. DPolinomial
3.Fácil

Qual é a complexidade de tempo da busca em profundidade num grafo armazenado como listas de adjacência?

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V²)
  4. DO(V × E)
4.Média

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

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

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

  1. AO compilador sempre a transforma em um laço que termina com segurança
  2. BEla continua chamando a si mesma até a pilha de chamadas estourar
  3. CEla retorna 0 automaticamente
  4. DEla roda em tempo O(1)
7.Difícil

Um problema é NP-completo se ele:

  1. AEstá fora de NP, mas é mais difícil que todos os problemas NP, como o problema da parada
  2. BÉ impossível de resolver
  3. CEstá em NP e todo problema NP se reduz a ele em tempo polinomial
  4. DPode ser resolvido em tempo polinomial
8.Difícil

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

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

Gabarito

  1. 1. C · Dividir, conquistar, combinar
  2. 2. C · Exponencial
  3. 3. A · O(V + E)
  4. 4. B · O(n²)
  5. 5. B · O(n log n)
  6. 6. B · Ela continua chamando a si mesma até a pilha de chamadas estourar
  7. 7. C · Está em NP e todo problema NP se reduz a ele em tempo polinomial
  8. 8. D · n = o(n²), mas n não é o(n)

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