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ál es la complejidad temporal de hallar el valor más grande de un array no ordenado de n números?

  1. AO(1)
  2. BO(n)
  3. CO(log n)
  4. DO(n log n)
2.Fácil

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por inserción?

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

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

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

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n²)
  4. DΩ(n)
5.Media

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

  1. AElegir primero la actividad más corta
  2. BElegir primero la actividad con menos solapamientos y repetir con las compatibles
  3. CElegir la actividad que termina antes y repetir con las compatibles
  4. DElegir la actividad que empieza antes
6.Media

¿Cuál es la complejidad temporal de: para i = 1 hasta n: (j = 1; mientras j < n: j = j × 2)?

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

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

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

¿Por qué la búsqueda media en una tabla hash es O(1) pero el peor caso es O(n)?

  1. ALas claves deben ordenarse primero
  2. BMuchas claves pueden colisionar en el mismo bucket
  3. CLas funciones hash son lentas
  4. DLos arrays tienen acceso O(n)

Soluciones

  1. 1. B · O(n)
  2. 2. C · O(n²)
  3. 3. A · O(n²)
  4. 4. A · Ω(n log n)
  5. 5. C · Elegir la actividad que termina antes y repetir con las compatibles
  6. 6. A · O(n log n)
  7. 7. A · Θ(n³)
  8. 8. B · Muchas claves pueden colisionar en el mismo bucket

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