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

Un algoritmo O(n) tarda 3 segundos para n = 1 millón. ¿Aproximadamente cuánto tarda para n = 2 millones?

  1. A6 segundos
  2. B3 segundos
  3. C9 segundos
  4. D12 segundos
2.Fácil

¿Qué significa que una operación se ejecute en tiempo O(1)?

  1. ASolo puede ejecutarse una vez
  2. BSu tiempo de ejecución no crece con el tamaño de la entrada
  3. CProcesa exactamente un elemento por segundo de tiempo de ejecución
  4. DSiempre tarda exactamente un segundo
3.Fácil

¿Qué es un algoritmo?

  1. AUna estructura de datos que almacena números
  2. BCualquier programa informático con interfaz gráfica
  3. CUna secuencia finita de pasos bien definidos que resuelve un problema
  4. DUn lenguaje de programación diseñado para escribir fórmulas matemáticas
4.Media

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

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

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

  1. AMerge sort no tiene estructura recursiva
  2. BLa programación dinámica solo funciona con problemas de grafos, no con arreglos
  3. CMerge sort ya es O(n)
  4. DSus subproblemas no se solapan, así que no hay nada que reutilizar
6.Media

¿Aproximadamente cuántas comparaciones necesita la búsqueda binaria en el peor caso en un array ordenado de 1,000,000 de elementos?

  1. AUnas 100
  2. BUnas 1,000
  3. CUnas 20
  4. DUnas 500,000
7.Difícil

¿Por qué la búsqueda media en una tabla hash es O(1) pero el peor caso es O(n)?

  1. ALas claves deben ordenarse primero
  2. BMuchas claves pueden colisionar en el mismo bucket
  3. CLas funciones hash son lentas
  4. DLos arrays tienen acceso O(n)
8.Difícil

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

  1. AUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  2. BLos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
  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. A · 6 segundos
  2. 2. B · Su tiempo de ejecución no crece con el tamaño de la entrada
  3. 3. C · Una secuencia finita de pasos bien definidos que resuelve un problema
  4. 4. D · Sí, porque O grande es una cota superior y n² no crece más deprisa que n³
  5. 5. D · Sus subproblemas no se solapan, así que no hay nada que reutilizar
  6. 6. C · Unas 20
  7. 7. B · Muchas claves pueden colisionar en el mismo bucket
  8. 8. A · 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.