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 en el mejor caso del ordenamiento por inserción, sobre un array ya ordenado?

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

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

  1. A4 segundos
  2. B2 segundos
  3. C8 segundos
  4. D1 segundo
3.Fácil

La complejidad espacial mide:

  1. AEl número de líneas de código
  2. BLa cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  3. CEl espacio en disco del archivo del programa una vez compilado
  4. DEl tamaño físico del ordenador
4.Media

La recurrencia T(n) = 2T(n/2) + O(n) tiene como solución:

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

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

  1. AΩ(log n)
  2. BΩ(n log n)
  3. CΩ(n)
  4. DΩ(n²)
6.Media

¿Por qué suele omitirse la base del logaritmo en la notación O grande, como en O(log n)?

  1. ALa base solo importa para n pequeño
  2. BLos logaritmos en distintas bases solo difieren en un factor constante
  3. CTodos los logaritmos en informática tienen base 10, así que va implícita
  4. DLos logaritmos siempre se redondean a enteros
7.Difícil

¿Cuál de estos problemas de satisfacibilidad se sabe que es resoluble en tiempo polinómico?

  1. A3-SAT, donde cada cláusula tiene exactamente tres literales
  2. B2-SAT, donde cada cláusula tiene como mucho dos literales
  3. CLa satisfacibilidad de circuitos
  4. DSAT general sobre fórmulas en forma normal conjuntiva
8.Difícil

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

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

Soluciones

  1. 1. D · O(n)
  2. 2. A · 4 segundos
  3. 3. B · La cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  4. 4. A · O(n log n)
  5. 5. B · Ω(n log n)
  6. 6. B · Los logaritmos en distintas bases solo difieren en un factor constante
  7. 7. B · 2-SAT, donde cada cláusula tiene como mucho dos literales
  8. 8. B · Problemas de decisión cuyas respuestas afirmativas pueden verificarse en tiempo polinómico dado un certificado

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