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

¿Cómo se llama un crecimiento O(2ⁿ)?

  1. ALogarítmico
  2. BPolinómico
  3. CExponencial
  4. DLineal
2.Fácil

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

  1. AO grande (Big O)
  2. BOmega grande (Big Omega)
  3. CTheta grande (Big Theta)
  4. DOmega pequeña (little omega)
3.Fácil

¿Cuál es la complejidad temporal de la búsqueda lineal en un array no ordenado de n elementos (peor caso)?

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

¿Cuánto espacio de pila usa una función factorial recursiva sencilla fact(n) = n × fact(n − 1)?

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

Con monedas de 1, 3 y 4 y una cantidad de 6, ¿cuántas monedas usa el método voraz de «la moneda más grande primero», comparado con el óptimo?

  1. AEl voraz usa 3 monedas; el óptimo es 3
  2. BEl voraz usa 2 monedas; el óptimo es 2
  3. CEl voraz usa 3 monedas; el óptimo es 2
  4. DEl voraz usa 4 monedas; el óptimo es 3
6.Media

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

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

Para demostrar que un problema nuevo X es NP-difícil, ¿qué hay que hacer?

  1. AReducir en tiempo polinómico X a un problema NP-difícil conocido
  2. BReducir en tiempo polinómico un problema NP-difícil conocido a X
  3. CDemostrar que X puede verificarse en tiempo polinómico
  4. DDemostrar que X no tiene algoritmo polinómico para entradas pequeñas
8.Difícil

¿Qué técnica proporciona a quicksort un tiempo de ejecución esperado de O(n log n) para cualquier entrada?

  1. AOrdenar la entrada antes de ejecutar quicksort
  2. BUsar recursión solo en el lado izquierdo
  3. CElegir siempre el primer elemento
  4. DElegir el pivote de forma uniformemente aleatoria

Soluciones

  1. 1. C · Exponencial
  2. 2. A · O grande (Big O)
  3. 3. D · O(n)
  4. 4. D · O(n)
  5. 5. C · El voraz usa 3 monedas; el óptimo es 2
  6. 6. A · O(2ⁿ)
  7. 7. B · Reducir en tiempo polinómico un problema NP-difícil conocido a X
  8. 8. D · Elegir el pivote de forma uniformemente aleatoria

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