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 de estos tiempos de ejecución es polinómico?

  1. AO(n³)
  2. BO(n!)
  3. CO(2ⁿ)
  4. DO(nⁿ)
2.Fácil

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

  1. AEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
  2. BEl tiempo máximo que tarda entre todas las entradas de tamaño n
  3. CEl tiempo que tarda en un ordenador lento
  4. DEl tiempo que tarda con la entrada más pequeña
3.Fácil

¿Cómo funciona el ordenamiento por selección?

  1. AInserta cada elemento en una parte ordenada creciente mediante desplazamientos
  2. BBusca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  3. CIntercambia repetidamente elementos vecinos que están en el orden incorrecto
  4. DDivide el array en mitades y las mezcla
4.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)
  3. CO(n³)
  4. DO(n² log n)
5.Media

¿Cuál es el tiempo de ejecución del radix sort LSD sobre n enteros de d dígitos en base k?

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

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

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

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para (j = i; j ≤ n; j = j + i) hacer trabajo O(1)?

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

Soluciones

  1. 1. A · O(n³)
  2. 2. B · El tiempo máximo que tarda entre todas las entradas de tamaño n
  3. 3. B · Busca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  4. 4. C · O(n³)
  5. 5. B · O(d(n + k))
  6. 6. D · O(n)
  7. 7. A · Θ(n³)
  8. 8. A · O(n log n)

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