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

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

  1. AOmega grande (Big Omega)
  2. BO grande (Big O)
  3. CTheta grande (Big Theta)
  4. DOmega pequeña (little omega)
2.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 n
  3. CUnas n / 2
  4. DUnas log₂ n
3.Fácil

¿Cuánto vale log₂ 1024?

  1. A12
  2. B32
  3. C512
  4. D10
4.Media

Un algoritmo voraz (greedy):

  1. AToma la mejor decisión local en cada paso
  2. BSiempre da la solución óptima
  3. CSolo usa recursión
  4. DPrueba todas las soluciones posibles
5.Media

La programación dinámica es útil cuando un problema tiene:

  1. ASolo entradas aleatorias
  2. BUn único bucle
  3. CNingún subproblema en absoluto, así que puede resolverse en un solo paso
  4. DSubproblemas superpuestos y subestructura óptima
6.Media

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

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

¿Cuál de estos problemas de satisfacibilidad se sabe que es resoluble en tiempo polinómico?

  1. ASAT general sobre fórmulas en forma normal conjuntiva
  2. BLa satisfacibilidad de circuitos
  3. C2-SAT, donde cada cláusula tiene como mucho dos literales
  4. D3-SAT, donde cada cláusula tiene exactamente tres literales
8.Difícil

¿Cuál es la solución de la recurrencia T(n) = 2T(n/2) + n log n?

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n log² n)
  4. DΘ(n)

Soluciones

  1. 1. B · O grande (Big O)
  2. 2. D · Unas log₂ n
  3. 3. D · 10
  4. 4. A · Toma la mejor decisión local en cada paso
  5. 5. D · Subproblemas superpuestos y subestructura óptima
  6. 6. A · O(n)
  7. 7. C · 2-SAT, donde cada cláusula tiene como mucho dos literales
  8. 8. C · Θ(n log² n)

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