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é estrategia de diseño usa merge sort?

  1. AProgramación dinámica
  2. BElección voraz
  3. CFuerza bruta
  4. DDivide y vencerás
2.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(n log n)
  4. DO(log n)
3.Fácil

¿Qué es un algoritmo de fuerza bruta?

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

¿Cuál es la solución de la recurrencia T(n) = T(n − 1) + O(n)?

  1. AO(n²)
  2. BO(n log n)
  3. CO(2ⁿ)
  4. DO(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(log n)
  2. BO(n²)
  3. CO(n log n)
  4. DO(n)
6.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 4 monedas; el óptimo es 3
  3. CEl voraz usa 3 monedas; el óptimo es 2
  4. DEl voraz usa 2 monedas; el óptimo es 2
7.Difícil

Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:

  1. AΘ(n³)
  2. BΘ(n² log n)
  3. CΘ(n²)
  4. DΘ(n log n)
8.Difícil

¿Qué estableció el teorema de Cook-Levin?

  1. ATodo problema NP puede resolverse en tiempo exponencial
  2. BEl problema de la parada es indecidible
  3. CEl problema de satisfacibilidad booleana (SAT) es NP-completo
  4. DP no es igual a NP

Soluciones

  1. 1. D · Divide y vencerás
  2. 2. D · O(log n)
  3. 3. D · Uno que prueba todas las soluciones candidatas posibles
  4. 4. A · O(n²)
  5. 5. D · O(n)
  6. 6. C · El voraz usa 3 monedas; el óptimo es 2
  7. 7. A · Θ(n³)
  8. 8. C · El problema de satisfacibilidad booleana (SAT) es NP-completo

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