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 de la búsqueda binaria en un array ordenado?

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

¿Qué exige la búsqueda binaria de su entrada?

  1. ALa longitud del array debe ser una potencia de dos
  2. BEl array debe estar ordenado
  3. CEl array no debe tener más de 1000 elementos
  4. DEl array solo debe contener números positivos
3.Fácil

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por mezcla (merge sort)?

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

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

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

El algoritmo de programación dinámica de Held-Karp resuelve exactamente el problema del viajante. ¿Cuál es su tiempo de ejecución para n ciudades?

  1. AO(n² 2ⁿ)
  2. BO(n³)
  3. CO(2n²)
  4. DO(n!)
8.Difícil

¿Cuál es el coste amortizado de incrementar un contador binario, sabiendo que un incremento puede cambiar muchos bits?

  1. AO(n) por incremento
  2. BO(n log n) por incremento
  3. CO(1) por incremento
  4. DO(log n) por incremento

Soluciones

  1. 1. D · O(log n)
  2. 2. B · El array debe estar ordenado
  3. 3. A · O(n log n)
  4. 4. A · O(n³)
  5. 5. C · O(n log n)
  6. 6. C · O(2ⁿ)
  7. 7. A · O(n² 2ⁿ)
  8. 8. C · O(1) por incremento

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