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 funciona el ordenamiento por selección?

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

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por inserción?

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

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

  1. A1 segundo
  2. B2 segundos
  3. C8 segundos
  4. D4 segundos
4.Media

¿Es correcto decir que un algoritmo O(n²) también es O(n³)?

  1. ANo, porque O grande debe dar siempre el ritmo de crecimiento exacto de la función
  2. BNo, porque n³ es menor que n² para n grande
  3. CSí, porque O grande es una cota superior y n² no crece más deprisa que n³
  4. DSí, pero solo si n es menor que 100
5.Media

¿Qué mide el análisis amortizado?

  1. AEl coste esperado con entradas aleatorias
  2. BEl coste medio por operación a lo largo de una secuencia de operaciones del peor caso
  3. CEl coste de un algoritmo con la mejor entrada
  4. DEl coste de la única operación más cara de toda la secuencia
6.Media

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

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

¿Cuál es la diferencia entre un problema indecidible y uno intratable?

  1. ALos problemas indecidibles están en NP, mientras que los intratables están en P
  2. BUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  3. CAmbos significan que el problema no tiene ningún algoritmo
  4. DLos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
8.Difícil

La multiplicación de Karatsuba cumple T(n) = 3T(n/2) + O(n). ¿Cuál es la solución?

  1. AΘ(n3)
  2. BΘ(nlog₂ 3), aproximadamente n1,585
  3. CΘ(n log n)
  4. DΘ(n²)

Soluciones

  1. 1. C · Busca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  2. 2. B · O(n²)
  3. 3. D · 4 segundos
  4. 4. C · Sí, porque O grande es una cota superior y n² no crece más deprisa que n³
  5. 5. B · El coste medio por operación a lo largo de una secuencia de operaciones del peor caso
  6. 6. D · Ω(n log n)
  7. 7. B · Un problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  8. 8. B · Θ(nlog₂ 3), aproximadamente n1,585

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