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 O grande de 3n² + 5n + 2?

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

¿Cuánta memoria adicional usa un merge sort estándar basado en arrays?

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

¿Qué complejidad suele tener un algoritmo con dos bucles anidados que se ejecutan n veces cada uno?

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

¿Cuál es la complejidad temporal del algoritmo estándar de programación dinámica para la subsecuencia común más larga de dos cadenas de longitudes m y n?

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

¿Cuál es la complejidad temporal amortizada de añadir al final de un array dinámico que duplica su capacidad cuando está lleno?

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

La recurrencia T(n) = 2T(n/2) + O(n) tiene como solución:

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

¿Cuál es el coste amortizado de incrementar un contador binario, sabiendo que un incremento puede cambiar muchos bits?

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

¿Qué afirmación sobre seleccionar el k-ésimo elemento más pequeño de un array no ordenado es correcta?

  1. ALa selección solo es posible en O(n²)
  2. BQuickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso
  3. CQuickselect se ejecuta en O(log n) en el peor caso, porque solo hace recursión en un lado del pivote
  4. DLa selección siempre necesita Ω(n log n) porque requiere ordenar

Soluciones

  1. 1. A · O(n²)
  2. 2. A · O(n)
  3. 3. B · O(n²)
  4. 4. B · O(mn)
  5. 5. D · O(1)
  6. 6. A · O(n log n)
  7. 7. C · O(1) por incremento
  8. 8. B · Quickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso

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