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 complejidad temporal en el peor caso del ordenamiento por inserción?

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

¿Qué algoritmo de ordenación intercambia repetidamente elementos adyacentes que están en el orden incorrecto?

  1. AQuicksort
  2. BOrdenamiento por montículos (heap sort)
  3. COrdenamiento por mezcla (merge sort)
  4. DOrdenamiento de burbuja (bubble sort)
3.Fácil

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

  1. APolinómico
  2. BLineal
  3. CLogarítmico
  4. DExponencial
4.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(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
5.Media

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

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

¿Cuál es la complejidad temporal del algoritmo de Bellman-Ford en un grafo con V vértices y E aristas?

  1. AO(V + E)
  2. BO(V³ × E)
  3. CO(V × E)
  4. DO(E log V)
7.Difícil

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

  1. AΘ(n2)
  2. BΘ(nlog₂ 7), aproximadamente n2,81
  3. CΘ(n³)
  4. DΘ(n² log n)
8.Difícil

¿Qué cota es correcta para log(n!)?

  1. AΘ(n)
  2. BΘ(n²)
  3. CΘ(log n)
  4. DΘ(n log n)

Soluciones

  1. 1. D · O(n²)
  2. 2. D · Ordenamiento de burbuja (bubble sort)
  3. 3. D · Exponencial
  4. 4. A · O(1)
  5. 5. B · O(n)
  6. 6. C · O(V × E)
  7. 7. B · Θ(nlog₂ 7), aproximadamente n2,81
  8. 8. D · Θ(n log n)

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