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

La complejidad espacial mide:

  1. AEl número de líneas de código
  2. BLa cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  3. CEl tamaño físico del ordenador
  4. DEl espacio en disco del archivo del programa una vez compilado
2.Fácil

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

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

¿Qué notación describe una cota inferior del crecimiento?

  1. AO (O grande)
  2. Bo (o pequeña)
  3. CΩ (Omega grande)
  4. DΘ (Theta grande)
4.Media

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

  1. ALineal
  2. BExponencial
  3. CConstante
  4. DLogarítmica
5.Media

¿Cuál es la complejidad temporal de calcular el n-ésimo número de Fibonacci con una tabla ascendente (bottom-up)?

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

¿Cuánto espacio de pila usa una función factorial recursiva sencilla fact(n) = n × fact(n − 1)?

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

¿Qué dos cosas hay que demostrar para probar que un problema de decisión X es NP-completo?

  1. AQue X no tiene algoritmo polinómico y que X es decidible
  2. BQue X está en P y que X se reduce a SAT
  3. CQue X se reduce a un problema de P y que X está en NP
  4. DQue X está en NP y que un problema NP-completo conocido se reduce a X en tiempo polinómico
8.Difícil

El algoritmo de programación dinámica de Held-Karp resuelve exactamente el problema del viajante. ¿Cuál es su tiempo de ejecución para n ciudades?

  1. AO(n² 2ⁿ)
  2. BO(n³)
  3. CO(n!)
  4. DO(2n²)

Soluciones

  1. 1. B · La cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  2. 2. C · O(n²)
  3. 3. C · Ω (Omega grande)
  4. 4. B · Exponencial
  5. 5. D · O(n)
  6. 6. C · O(n)
  7. 7. D · Que X está en NP y que un problema NP-completo conocido se reduce a X en tiempo polinómico
  8. 8. A · O(n² 2ⁿ)

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