Hoja de ejercicios de Algoritmos y complejidad con soluciones

Hoja de ejercicios de Algoritmos y complejidad gratis e imprimible: 8 problemas desde nivel fácil hasta nivel de examen, con soluciones. Imprímela o guárdala como PDF.

Nueva hoja de ejerciciosPractica en línea con pistas

Para docentes: pueden imprimirla, copiarla y usarla en clase gratis. Cada hoja nueva tiene valores nuevos y su propia clave de respuestas. Agradecemos un enlace a ExamProblems en la página de tu curso.

Nombre: ____________________   Fecha: ____________

1.Fácil

¿Cuánto vale log₂ 1024?

  1. A12
  2. B32
  3. C10
  4. D512
2.Fácil

¿Cuál es la O grande de 3n² + 5n + 2?

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

Un bucle empieza con i = 1 y duplica i en cada iteración hasta que i > n. ¿Cuántas iteraciones ejecuta?

  1. AUnas n²
  2. BUnas log₂ n
  3. CUnas n
  4. DUnas n / 2
4.Media

¿Cuál es la complejidad temporal de multiplicar dos matrices n × n con el triple bucle estándar?

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

¿Es correcto decir que un algoritmo O(n²) también es O(n³)?

  1. ANo, porque O grande debe dar siempre el ritmo de crecimiento exacto de la función
  2. BSí, pero solo si n es menor que 100
  3. CSí, porque O grande es una cota superior y n² no crece más deprisa que n³
  4. DNo, porque n³ es menor que n² para n grande
6.Media

¿Cuál es la complejidad temporal amortizada de añadir al final de un array dinámico que duplica su capacidad cuando está lleno?

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

¿Qué afirmación sobre P y NP es correcta?

  1. ATodo problema de P también está en NP
  2. BSe ha demostrado que P ≠ NP
  3. CLas soluciones de los problemas NP no se pueden verificar rápidamente
  4. DNP significa «no polinómico»
8.Difícil

Los caminos simples más cortos pueden hallarse en tiempo polinómico. ¿Qué se sabe de hallar el camino simple más largo entre dos vértices en un grafo general?

  1. AEs indecidible
  2. BEs NP-difícil
  3. CPuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo
  4. DSiempre puede resolverse en O(V + E)

Soluciones

  1. 1. C · 10
  2. 2. B · O(n²)
  3. 3. B · Unas log₂ n
  4. 4. D · O(n³)
  5. 5. C · Sí, porque O grande es una cota superior y n² no crece más deprisa que n³
  6. 6. C · O(1)
  7. 7. A · Todo problema de P también está en NP
  8. 8. B · Es NP-difícil

Soluciones completas paso a paso: practica este tema en examproblems.com.