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ánta memoria adicional usa un merge sort estándar basado en arrays?

  1. AO(n²)
  2. BO(log n)
  3. CO(1)
  4. DO(n)
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

Acceder a un elemento de un array por su índice requiere:

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

Ordenas una vez un array de n elementos y después respondes a k consultas de pertenencia con búsqueda binaria. ¿Cuál es el coste total?

  1. AO(nk)
  2. BO(n log n + k log n)
  3. CO(n + k)
  4. DO(k n log n)
5.Media

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para j = 1 hasta i: hacer trabajo O(1)?

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

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

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

¿Cómo se clasifica el problema del viajante?

  1. AEstá en P porque el algoritmo de Dijkstra lo resuelve visitando cada ciudad una vez
  2. BLa versión de decisión está en P, pero la de optimización es NP-completa
  3. CLa versión de decisión es NP-completa y la de optimización es NP-difícil
  4. DEs indecidible
8.Difícil

Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:

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

Soluciones

  1. 1. D · O(n)
  2. 2. D · Unas log₂ n
  3. 3. B · O(1)
  4. 4. B · O(n log n + k log n)
  5. 5. C · O(n²)
  6. 6. A · O(log n)
  7. 7. C · La versión de decisión es NP-completa y la de optimización es NP-difícil
  8. 8. B · Θ(n³)

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