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 bucle empieza con i = 1 y duplica i en cada iteración hasta que i > n. ¿Cuántas iteraciones ejecuta?

  1. AUnas n²
  2. BUnas log₂ n
  3. CUnas n / 2
  4. DUnas n
2.Fácil

Acceder a un elemento de un array por su índice requiere:

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

¿Qué es la recursión?

  1. AUn bucle que nunca termina
  2. BUn método de ordenación
  3. CUn tipo de estructura de datos
  4. DUna función que se llama a sí misma con entradas más pequeñas
4.Media

Ordenas una vez un array de n elementos y después respondes a k consultas de pertenencia con búsqueda binaria. ¿Cuál es el coste total?

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

¿Cuál es la complejidad temporal de quicksort en el peor caso?

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

¿Cuál es la complejidad temporal de multiplicar dos matrices n × n con el triple bucle estándar?

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

¿Qué definición de la clase NP es correcta?

  1. AProblemas que ningún algoritmo puede resolver
  2. BProblemas que no pueden resolverse en tiempo polinómico
  3. CProblemas de decisión cuyas respuestas afirmativas pueden verificarse en tiempo polinómico dado un certificado
  4. DProblemas que no son polinómicos
8.Difícil

¿Qué se deduciría si alguien hallara un algoritmo de tiempo polinómico para un problema NP-completo?

  1. ASolo ese problema pasaría a P
  2. BTodos los algoritmos de tiempo exponencial pasarían de inmediato a ejecutarse en tiempo lineal
  3. CEl problema de la parada se volvería decidible
  4. DTodo problema de NP podría resolverse en tiempo polinómico, así que P = NP

Soluciones

  1. 1. B · Unas log₂ n
  2. 2. B · O(1)
  3. 3. D · Una función que se llama a sí misma con entradas más pequeñas
  4. 4. C · O(n log n + k log n)
  5. 5. B · O(n²)
  6. 6. D · O(n³)
  7. 7. C · Problemas de decisión cuyas respuestas afirmativas pueden verificarse en tiempo polinómico dado un certificado
  8. 8. D · Todo problema de NP podría resolverse en tiempo polinómico, así que P = NP

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