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

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

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

¿Qué es un algoritmo de fuerza bruta?

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

¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?

  1. AO(n log n)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
4.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(V × E)
  3. CO(E log V)
  4. DO(V³ × E)
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(dn log k)
  2. BO(n log n)
  3. CO(d(n + k))
  4. DO(n²)
6.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)
7.Difícil

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

  1. ALos arrays tienen acceso O(n)
  2. BLas funciones hash son lentas
  3. CLas claves deben ordenarse primero
  4. DMuchas claves pueden colisionar en el mismo bucket
8.Difícil

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

  1. AΘ(n2)
  2. BΘ(n³)
  3. CΘ(nlog₂ 7), aproximadamente n2,81
  4. DΘ(n² log n)

Soluciones

  1. 1. C · Busca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
  2. 2. C · Uno que prueba todas las soluciones candidatas posibles
  3. 3. C · O(log n)
  4. 4. B · O(V × E)
  5. 5. C · O(d(n + k))
  6. 6. A · O(n³)
  7. 7. D · Muchas claves pueden colisionar en el mismo bucket
  8. 8. C · Θ(nlog₂ 7), aproximadamente n2,81

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