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

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

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

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

  1. ASiempre tarda exactamente un segundo
  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. DSolo puede ejecutarse una vez
3.Fácil

La complejidad espacial mide:

  1. AEl tamaño físico del ordenador
  2. BLa cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  3. CEl espacio en disco del archivo del programa una vez compilado
  4. DEl número de líneas de código
4.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 la única operación más cara de toda la secuencia
  4. DEl coste de un algoritmo con la mejor entrada
5.Media

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

  1. AExponencial
  2. BLogarítmica
  3. CConstante
  4. DLineal
6.Media

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para j = 1 hasta i: hacer trabajo O(1)?

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

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para (j = i; j ≤ n; j = j + i) hacer trabajo O(1)?

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

¿Por qué la búsqueda binaria no da un tiempo O(log n) en una lista simplemente enlazada?

  1. ALas listas enlazadas no pueden ordenarse
  2. BLas comparaciones entre nodos de una lista enlazada son más lentas
  3. CLa búsqueda binaria necesita al menos el doble de memoria
  4. DLlegar al elemento central lleva O(n) pasos, porque no hay acceso directo por índice

Soluciones

  1. 1. B · Ordenamiento de burbuja (bubble sort)
  2. 2. B · Su tiempo de ejecución no crece con el tamaño de la entrada
  3. 3. B · La cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  4. 4. B · El coste medio por operación a lo largo de una secuencia de operaciones del peor caso
  5. 5. A · Exponencial
  6. 6. C · O(n²)
  7. 7. D · O(n log n)
  8. 8. D · Llegar al elemento central lleva O(n) pasos, porque no hay acceso directo por índice

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