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 problema suele llamarse tratable si:

  1. APuede resolverse en tiempo polinómico
  2. BNo tiene solución
  3. CPuede resolverse en tiempo constante
  4. DSolo puede resolverse probando todas las posibilidades
2.Fácil

¿Qué notación describe una cota superior del crecimiento?

  1. AOmega grande (Big Omega)
  2. BO grande (Big O)
  3. COmega pequeña (little omega)
  4. DTheta grande (Big Theta)
3.Fácil

¿Cuánta memoria adicional usa un merge sort estándar basado en arrays?

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

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

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

¿Qué calcula el algoritmo de Floyd-Warshall y con qué rapidez?

  1. ALos caminos más cortos desde un vértice origen hasta todos los demás en O(V + E)
  2. BUn orden topológico en O(V²)
  3. CUn árbol de expansión mínima en O(E log V)
  4. DLos caminos más cortos entre todos los pares de vértices en O(V³)
6.Media

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

  1. AConstante
  2. BLogarítmica
  3. CExponencial
  4. DLineal
7.Difícil

¿Por qué la búsqueda media en una tabla hash es O(1) pero el peor caso es O(n)?

  1. ALas funciones hash son lentas
  2. BMuchas claves pueden colisionar en el mismo bucket
  3. CLos arrays tienen acceso O(n)
  4. DLas claves deben ordenarse primero
8.Difícil

¿Cuál es la diferencia entre un problema indecidible y uno intratable?

  1. AUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  2. BLos problemas indecidibles están en NP, mientras que los intratables están en P
  3. CLos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
  4. DAmbos significan que el problema no tiene ningún algoritmo

Soluciones

  1. 1. A · Puede resolverse en tiempo polinómico
  2. 2. B · O grande (Big O)
  3. 3. B · O(n)
  4. 4. B · O(n²)
  5. 5. D · Los caminos más cortos entre todos los pares de vértices en O(V³)
  6. 6. C · Exponencial
  7. 7. B · Muchas claves pueden colisionar en el mismo bucket
  8. 8. A · Un problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento

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