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 de estas crece más despacio a medida que n se hace grande?

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

¿Qué estrategia de diseño usa merge sort?

  1. AElección voraz
  2. BDivide y vencerás
  3. CProgramación dinámica
  4. DFuerza bruta
3.Fácil

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

  1. AEl tiempo máximo que tarda entre todas las entradas de tamaño n
  2. BEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
  3. CEl tiempo que tarda con la entrada más pequeña
  4. DEl tiempo que tarda en un ordenador lento
4.Media

¿Cuál es la complejidad temporal del algoritmo estándar de programación dinámica para la subsecuencia común más larga de dos cadenas de longitudes m y n?

  1. AO(mn)
  2. BO(2m+n)
  3. CO(mn log n)
  4. DO(m + n)
5.Media

En un array ordenado buscas dos elementos que sumen un valor objetivo moviendo un puntero desde cada extremo hacia dentro. ¿Cuál es la complejidad temporal?

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

¿Qué afirmación sobre una función recursiva sin un caso base alcanzable es correcta?

  1. AEl compilador siempre la convierte en un bucle que termina sin problemas
  2. BSigue llamándose a sí misma hasta que se desborda la pila de llamadas
  3. CDevuelve 0 automáticamente
  4. DSe ejecuta en tiempo O(1)
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

El problema de la parada demuestra que:

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

Soluciones

  1. 1. B · O(log n)
  2. 2. B · Divide y vencerás
  3. 3. A · El tiempo máximo que tarda entre todas las entradas de tamaño n
  4. 4. A · O(mn)
  5. 5. A · O(n)
  6. 6. B · Sigue llamándose a sí misma hasta que se desborda la pila de llamadas
  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. A · Ningún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene

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