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ánto vale log₂ 1024?

  1. A32
  2. B512
  3. C12
  4. D10
2.Fácil

¿Cómo funciona el ordenamiento por selección?

  1. AInserta cada elemento en una parte ordenada creciente mediante desplazamientos
  2. BBusca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  3. CDivide el array en mitades y las mezcla
  4. DIntercambia repetidamente elementos vecinos que están en el orden incorrecto
3.Fácil

¿Qué clase de complejidad crece más rápido para n grande?

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

¿Cuál es la complejidad temporal de quicksort en el peor caso?

  1. AO(n log n)
  2. BO(n²)
  3. CO(log n)
  4. DO(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 complejidad temporal de calcular el n-ésimo número de Fibonacci con una tabla ascendente (bottom-up)?

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

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

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

¿Está 22n en O(2ⁿ)?

  1. ASí, porque ambos son exponenciales
  2. BNo, porque 22n crece más despacio que 2ⁿ
  3. CSí, porque los factores constantes del exponente se ignoran siempre en la notación O grande
  4. DNo, porque 22n = 4ⁿ y 4ⁿ / 2ⁿ = 2ⁿ crece sin límite

Soluciones

  1. 1. D · 10
  2. 2. B · Busca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  3. 3. D · O(2ⁿ)
  4. 4. B · O(n²)
  5. 5. B · Unos log₂ n
  6. 6. D · O(n)
  7. 7. D · Θ(n log² n)
  8. 8. D · No, porque 22n = 4ⁿ y 4ⁿ / 2ⁿ = 2ⁿ crece sin límite

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