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é es la memoización?

  1. ALiberar memoria cuando una función termina
  2. BGuardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas
  3. CConvertir automáticamente la recursión en un bucle equivalente para que no haga falta pila de llamadas
  4. DEscribir comentarios junto a cada línea de código
2.Fácil

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

  1. A1 segundo
  2. B4 segundos
  3. C8 segundos
  4. D2 segundos
3.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)
4.Media

Una función ejecuta un bucle de n iteraciones y después, por separado, otro bucle de n iteraciones. ¿Cuál es su complejidad temporal?

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

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

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

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

  1. AExponencial
  2. BLineal
  3. CLogarítmica
  4. DConstante
7.Difícil

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

  1. AElegir siempre el primer elemento
  2. BUsar recursión solo en el lado izquierdo
  3. CElegir el pivote de forma uniformemente aleatoria
  4. DOrdenar la entrada antes de ejecutar quicksort
8.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(n) por incremento
  3. CO(log n) por incremento
  4. DO(1) por incremento

Soluciones

  1. 1. B · Guardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas
  2. 2. B · 4 segundos
  3. 3. A · O(n²)
  4. 4. C · O(n)
  5. 5. A · O(log n)
  6. 6. A · Exponencial
  7. 7. C · Elegir el pivote de forma uniformemente aleatoria
  8. 8. D · O(1) por incremento

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