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 problema suele llamarse tratable si:

  1. APuede resolverse en tiempo constante
  2. BNo tiene solución
  3. CPuede resolverse en tiempo polinómico
  4. DSolo puede resolverse probando todas las posibilidades
2.Fácil

¿Cuál es la complejidad temporal en el mejor caso del ordenamiento por inserción, sobre un array ya ordenado?

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

¿Qué es un algoritmo de fuerza bruta?

  1. AUno que prueba todas las soluciones candidatas posibles
  2. BUno que adivina una respuesta al azar
  3. CUno que se ejecuta en muchos procesadores
  4. DUno que siempre usa recursión
4.Media

Con monedas de 1, 3 y 4 y una cantidad de 6, ¿cuántas monedas usa el método voraz de «la moneda más grande primero», comparado con el óptimo?

  1. AEl voraz usa 3 monedas; el óptimo es 3
  2. BEl voraz usa 2 monedas; el óptimo es 2
  3. CEl voraz usa 4 monedas; el óptimo es 3
  4. DEl voraz usa 3 monedas; el óptimo es 2
5.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 primero la actividad más corta
  2. BElegir la actividad que empieza antes
  3. CElegir primero la actividad con menos solapamientos y repetir con las compatibles
  4. DElegir la actividad que termina antes y repetir con las compatibles
6.Media

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

  1. AAlgoritmo de Kruskal
  2. BAlgoritmo de Dijkstra
  3. CBellman-Ford es necesario en todos los casos
  4. DBúsqueda en profundidad (DFS)
7.Difícil

¿Cómo se clasifica el problema del viajante?

  1. ALa versión de decisión es NP-completa y la de optimización es NP-difícil
  2. BEs indecidible
  3. CLa versión de decisión está en P, pero la de optimización es NP-completa
  4. DEstá en P porque el algoritmo de Dijkstra lo resuelve visitando cada ciudad una vez
8.Difícil

¿En qué variante del problema de la mochila la regla voraz «tomar los objetos por orden de valor por unidad de peso» da siempre una respuesta óptima?

  1. ALa mochila 0/1, en la que los objetos deben tomarse siempre enteros
  2. BEn ninguna de las dos
  3. CEn ambas variantes
  4. DLa mochila fraccionaria, en la que los objetos pueden dividirse

Soluciones

  1. 1. C · Puede resolverse en tiempo polinómico
  2. 2. B · O(n)
  3. 3. A · Uno que prueba todas las soluciones candidatas posibles
  4. 4. D · El voraz usa 3 monedas; el óptimo es 2
  5. 5. D · Elegir la actividad que termina antes y repetir con las compatibles
  6. 6. B · Algoritmo de Dijkstra
  7. 7. A · La versión de decisión es NP-completa y la de optimización es NP-difícil
  8. 8. D · La mochila fraccionaria, en la que los objetos pueden dividirse

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