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é notación describe una cota inferior del crecimiento?

  1. AΘ (Theta grande)
  2. BO (O grande)
  3. Co (o pequeña)
  4. DΩ (Omega grande)
2.Fácil

¿Qué complejidad suele tener un algoritmo con dos bucles anidados que se ejecutan n veces cada uno?

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

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

  1. AEl tiempo que tarda con la entrada más pequeña
  2. BEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
  3. CEl tiempo máximo que tarda entre todas las entradas de tamaño n
  4. DEl tiempo que tarda en un ordenador lento
4.Media

Con monedas de 1, 3 y 4 y una cantidad de 6, ¿cuántas monedas usa el método voraz de «la moneda más grande primero», comparado con el óptimo?

  1. AEl voraz usa 3 monedas; el óptimo es 3
  2. BEl voraz usa 3 monedas; el óptimo es 2
  3. CEl voraz usa 4 monedas; el óptimo es 3
  4. DEl voraz usa 2 monedas; el óptimo es 2
5.Media

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

  1. AElegir la actividad que termina antes y repetir con las compatibles
  2. BElegir primero la actividad más corta
  3. CElegir primero la actividad con menos solapamientos y repetir con las compatibles
  4. DElegir la actividad que empieza antes
6.Media

¿Qué algoritmo de ordenación es estable?

  1. AQuicksort (versión in situ habitual)
  2. BHeap sort
  3. CMerge sort
  4. DOrdenamiento por selección (versión habitual)
7.Difícil

¿Qué afirmación sobre seleccionar el k-ésimo elemento más pequeño de un array no ordenado es correcta?

  1. ALa selección solo es posible en O(n²)
  2. BLa selección siempre necesita Ω(n log n) porque requiere ordenar
  3. CQuickselect se ejecuta en O(log n) en el peor caso, porque solo hace recursión en un lado del pivote
  4. DQuickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso
8.Difícil

Los caminos simples más cortos pueden hallarse en tiempo polinómico. ¿Qué se sabe de hallar el camino simple más largo entre dos vértices en un grafo general?

  1. AEs NP-difícil
  2. BPuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo
  3. CSiempre puede resolverse en O(V + E)
  4. DEs indecidible

Soluciones

  1. 1. D · Ω (Omega grande)
  2. 2. A · O(n²)
  3. 3. C · El tiempo máximo que tarda entre todas las entradas de tamaño n
  4. 4. B · El voraz usa 3 monedas; el óptimo es 2
  5. 5. A · Elegir la actividad que termina antes y repetir con las compatibles
  6. 6. C · Merge sort
  7. 7. D · Quickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso
  8. 8. A · Es NP-difícil

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