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

¿Qué clase de complejidad crece más rápido para n grande?

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

¿Qué es un algoritmo?

  1. AUn lenguaje de programación diseñado para escribir fórmulas matemáticas
  2. BUna estructura de datos que almacena números
  3. CCualquier programa informático con interfaz gráfica
  4. DUna secuencia finita de pasos bien definidos que resuelve un problema
3.Fácil

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por inserción?

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

¿Por qué muchas rutinas de ordenación de las bibliotecas cambian al ordenamiento por inserción para subarrays muy pequeños?

  1. AEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
  2. BEl ordenamiento por inserción es O(n log n) en el peor caso
  3. CLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
  4. DEl ordenamiento por inserción usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes
5.Media

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

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

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

  1. ABellman-Ford es necesario en todos los casos
  2. BAlgoritmo de Kruskal
  3. CAlgoritmo de Dijkstra
  4. DBúsqueda en profundidad (DFS)
7.Difícil

¿Está 22n en O(2ⁿ)?

  1. ANo, porque 22n crece más despacio que 2ⁿ
  2. BSí, porque ambos son exponenciales
  3. CNo, porque 22n = 4ⁿ y 4ⁿ / 2ⁿ = 2ⁿ crece sin límite
  4. DSí, porque los factores constantes del exponente se ignoran siempre en la notación O grande
8.Difícil

¿Cuál es el tiempo de ejecución del algoritmo de Dijkstra con un montículo binario en un grafo con V vértices y E aristas?

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

Soluciones

  1. 1. C · O(2ⁿ)
  2. 2. D · Una secuencia finita de pasos bien definidos que resuelve un problema
  3. 3. B · O(n²)
  4. 4. A · El ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
  5. 5. D · O(n log n)
  6. 6. C · Algoritmo de Dijkstra
  7. 7. C · No, porque 22n = 4ⁿ y 4ⁿ / 2ⁿ = 2ⁿ crece sin límite
  8. 8. B · O((V + E) log V)

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