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 de hallar el valor más grande de un array no ordenado de n números?

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

¿Qué clase de complejidad crece más rápido para n grande?

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

¿Cuál de estas crece más despacio a medida que n se hace grande?

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

¿Cuántos niveles tiene la recursión de merge sort para un array de n elementos?

  1. AUnos n
  2. BUnos √n
  3. CUnos log₂ n
  4. DUnos n / 2
5.Media

¿Qué algoritmo de ordenación es estable?

  1. AMerge sort
  2. BQuicksort (versión in situ habitual)
  3. CHeap sort
  4. DOrdenamiento por selección (versión habitual)
6.Media

¿Qué mide el análisis amortizado?

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

El problema de la parada demuestra que:

  1. ATodo programa acaba deteniéndose
  2. BNingún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene
  3. CAlgunos programas se ejecutan más rápido en ordenadores más rápidos, así que la parada depende del hardware
  4. DHay que evitar los bucles
8.Difícil

¿Qué técnica proporciona a quicksort un tiempo de ejecución esperado de O(n log n) para cualquier entrada?

  1. AElegir el pivote de forma uniformemente aleatoria
  2. BElegir siempre el primer elemento
  3. CUsar recursión solo en el lado izquierdo
  4. DOrdenar la entrada antes de ejecutar quicksort

Soluciones

  1. 1. B · O(n)
  2. 2. C · O(2ⁿ)
  3. 3. C · O(log n)
  4. 4. C · Unos log₂ n
  5. 5. A · Merge sort
  6. 6. C · El coste medio por operación a lo largo de una secuencia de operaciones del peor caso
  7. 7. B · Ningún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene
  8. 8. A · Elegir el pivote de forma uniformemente aleatoria

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