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

¿Qué es la memoización?

  1. AGuardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas
  2. BEscribir comentarios junto a cada línea de código
  3. CLiberar memoria cuando una función termina
  4. DConvertir automáticamente la recursión en un bucle equivalente para que no haga falta pila de llamadas
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(n²)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
4.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)
5.Media

¿Cuántos niveles tiene la recursión de merge sort para un array de n elementos?

  1. AUnos √n
  2. BUnos log₂ n
  3. CUnos n
  4. DUnos n / 2
6.Media

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

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

¿Cómo se comparan n! y 2ⁿ para n grande?

  1. A2ⁿ crece más deprisa que n!
  2. BCrecen al mismo ritmo
  3. Cn! crece más deprisa que 2ⁿ
  4. Dn! es O(n²)
8.Difícil

¿Cuáles son los costes de tiempo y espacio de calcular el n-ésimo número de Fibonacci con un bucle que guarda solo los dos últimos valores?

  1. ATiempo O(n) y espacio O(1)
  2. BTiempo O(log n) y espacio O(n)
  3. CTiempo O(n) y espacio O(n)
  4. DTiempo O(2ⁿ) y espacio O(1)

Soluciones

  1. 1. B · O grande (Big O)
  2. 2. A · Guardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas
  3. 3. C · O(n)
  4. 4. A · O(2ⁿ)
  5. 5. B · Unos log₂ n
  6. 6. A · O(n)
  7. 7. C · n! crece más deprisa que 2ⁿ
  8. 8. A · Tiempo O(n) y espacio O(1)

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