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. AIntercambia repetidamente elementos vecinos que están en el orden incorrecto
  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. DInserta cada elemento en una parte ordenada creciente mediante desplazamientos
2.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(1)
  2. BO(n²)
  3. CO(n)
  4. DO(log n)
3.Fácil

¿Qué notación describe una cota inferior del crecimiento?

  1. AΩ (Omega grande)
  2. BO (O grande)
  3. CΘ (Theta grande)
  4. Do (o pequeña)
4.Media

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

  1. AElegir la actividad que empieza antes
  2. BElegir la actividad que termina antes y repetir con las compatibles
  3. CElegir primero la actividad más corta
  4. DElegir primero la actividad con menos solapamientos y repetir con las compatibles
5.Media

Ordenas una vez un array de n elementos y después respondes a k consultas de pertenencia con búsqueda binaria. ¿Cuál es el coste total?

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

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

  1. AO(2ⁿ)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
7.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(2ⁿ) y espacio O(1)
  2. BTiempo O(log n) y espacio O(n)
  3. CTiempo O(n) y espacio O(n)
  4. DTiempo O(n) y espacio O(1)
8.Difícil

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

  1. ALos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
  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. CLos problemas indecidibles están en NP, mientras que los intratables están en P
  4. DAmbos significan que el problema no tiene ningún algoritmo

Soluciones

  1. 1. B · Busca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  2. 2. C · O(n)
  3. 3. A · Ω (Omega grande)
  4. 4. B · Elegir la actividad que termina antes y repetir con las compatibles
  5. 5. A · O(n log n + k log n)
  6. 6. C · O(n)
  7. 7. D · Tiempo O(n) y espacio O(1)
  8. 8. B · Un problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento

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