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(n²)
  2. BO(n log n)
  3. CO(n)
  4. DO(1)
2.Fácil

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

  1. A1 segundo
  2. B8 segundos
  3. C4 segundos
  4. D2 segundos
3.Fácil

¿Qué describe el tiempo de ejecución en el caso promedio?

  1. AEl tiempo esperado según una distribución dada de las entradas de tamaño n
  2. BEl valor intermedio entre los tiempos de ejecución del mejor y del peor caso
  3. CEl tiempo en el ordenador más común
  4. DEl tiempo para una entrada de longitud media
4.Media

¿Cuál es la complejidad temporal del algoritmo de Bellman-Ford en un grafo con V vértices y E aristas?

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V³ × E)
  4. DO(V + E)
5.Media

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

  1. AO(log n)
  2. BO(n)
  3. CO(n log n)
  4. DO(n²)
6.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²)
7.Difícil

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

  1. AΘ(n2)
  2. BΘ(n² log n)
  3. CΘ(nlog₂ 7), aproximadamente n2,81
  4. DΘ(n³)
8.Difícil

Para demostrar que un problema nuevo X es NP-difícil, ¿qué hay que hacer?

  1. ADemostrar que X no tiene algoritmo polinómico para entradas pequeñas
  2. BDemostrar que X puede verificarse en tiempo polinómico
  3. CReducir en tiempo polinómico X a un problema NP-difícil conocido
  4. DReducir en tiempo polinómico un problema NP-difícil conocido a X

Soluciones

  1. 1. C · O(n)
  2. 2. C · 4 segundos
  3. 3. A · El tiempo esperado según una distribución dada de las entradas de tamaño n
  4. 4. B · O(V × E)
  5. 5. C · O(n log n)
  6. 6. B · O(n)
  7. 7. C · Θ(nlog₂ 7), aproximadamente n2,81
  8. 8. D · Reducir en tiempo polinómico un problema NP-difícil conocido a X

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