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é es un algoritmo de fuerza bruta?

  1. AUno que se ejecuta en muchos procesadores
  2. BUno que siempre usa recursión
  3. CUno que prueba todas las soluciones candidatas posibles
  4. DUno que adivina una respuesta al azar
2.Fácil

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

  1. ADivide el array en mitades y las mezcla
  2. BIntercambia repetidamente elementos vecinos que están en el orden incorrecto
  3. CInserta cada elemento en una parte ordenada creciente mediante desplazamientos
  4. DBusca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
3.Fácil

El tiempo de ejecución de un algoritmo es O(n). ¿Cómo se llama este crecimiento?

  1. ALineal
  2. BLogarítmico
  3. CCuadrático
  4. DConstante
4.Media

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

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

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

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

¿Cuál es la complejidad temporal de calcular el n-ésimo número de Fibonacci con una tabla ascendente (bottom-up)?

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

El problema de la parada demuestra que:

  1. ATodo programa acaba deteniéndose
  2. BNingún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene
  3. CAlgunos programas se ejecutan más rápido en ordenadores más rápidos, así que la parada depende del hardware
  4. DHay que evitar los bucles
8.Difícil

¿Cómo se clasifica el problema del viajante?

  1. AEstá en P porque el algoritmo de Dijkstra lo resuelve visitando cada ciudad una vez
  2. BLa versión de decisión está en P, pero la de optimización es NP-completa
  3. CLa versión de decisión es NP-completa y la de optimización es NP-difícil
  4. DEs indecidible

Soluciones

  1. 1. C · Uno que prueba todas las soluciones candidatas posibles
  2. 2. D · Busca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  3. 3. A · Lineal
  4. 4. A · O(n²)
  5. 5. A · O(V × E)
  6. 6. B · O(n)
  7. 7. B · Ningún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene
  8. 8. C · La versión de decisión es NP-completa y la de optimización es NP-difícil

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