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. ATheta grande (Big Theta)
  2. BOmega grande (Big Omega)
  3. CO grande (Big O)
  4. DOmega pequeña (little omega)
2.Fácil

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

  1. A1 segundo
  2. B4 segundos
  3. C2 segundos
  4. D8 segundos
3.Fácil

Un algoritmo O(n) tarda 3 segundos para n = 1 millón. ¿Aproximadamente cuánto tarda para n = 2 millones?

  1. A3 segundos
  2. B9 segundos
  3. C6 segundos
  4. D12 segundos
4.Media

¿Qué algoritmo de ordenación es estable?

  1. AQuicksort (versión in situ habitual)
  2. BOrdenamiento por selección (versión habitual)
  3. CHeap sort
  4. DMerge sort
5.Media

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

  1. ALa programación dinámica solo funciona con problemas de grafos, no con arreglos
  2. BMerge sort no tiene estructura recursiva
  3. CMerge sort ya es O(n)
  4. DSus subproblemas no se solapan, así que no hay nada que reutilizar
6.Media

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

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

¿Qué cota es correcta para log(n!)?

  1. AΘ(log n)
  2. BΘ(n)
  3. CΘ(n²)
  4. DΘ(n log n)
8.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. B2-SAT, donde cada cláusula tiene como mucho dos literales
  3. C3-SAT, donde cada cláusula tiene exactamente tres literales
  4. DLa satisfacibilidad de circuitos

Soluciones

  1. 1. C · O grande (Big O)
  2. 2. B · 4 segundos
  3. 3. C · 6 segundos
  4. 4. D · Merge sort
  5. 5. D · Sus subproblemas no se solapan, así que no hay nada que reutilizar
  6. 6. B · O(n³)
  7. 7. D · Θ(n log n)
  8. 8. B · 2-SAT, donde cada cláusula tiene como mucho dos literales

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