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é describe el tiempo de ejecución en el caso promedio?

  1. AEl valor intermedio entre los tiempos de ejecución del mejor y del peor caso
  2. BEl tiempo en el ordenador más común
  3. CEl tiempo para una entrada de longitud media
  4. DEl tiempo esperado según una distribución dada de las entradas de tamaño n
2.Fácil

¿Cuánto vale log₂ 1024?

  1. A512
  2. B32
  3. C10
  4. D12
3.Fácil

Un problema suele llamarse tratable si:

  1. ASolo puede resolverse probando todas las posibilidades
  2. BPuede resolverse en tiempo polinómico
  3. CPuede resolverse en tiempo constante
  4. DNo tiene solución
4.Media

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

  1. AEjecuta una búsqueda en anchura y se queda con el árbol BFS
  2. BHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol
  3. COrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque
  4. DElimina la arista más cara hasta que no quedan ciclos
5.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 usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes
  3. CLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
  4. DEl ordenamiento por inserción es O(n log n) en el peor caso
6.Media

Un quicksort usa siempre el primer elemento como pivote. ¿Con qué entrada muestra su comportamiento de peor caso?

  1. AUn array de longitud 2
  2. BUn array en orden aleatorio
  3. CUn array con todos sus elementos distintos
  4. DUn array que ya está ordenado
7.Difícil

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

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

Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:

  1. AΘ(n log n)
  2. BΘ(n² log n)
  3. CΘ(n²)
  4. DΘ(n³)

Soluciones

  1. 1. D · El tiempo esperado según una distribución dada de las entradas de tamaño n
  2. 2. C · 10
  3. 3. B · Puede resolverse en tiempo polinómico
  4. 4. B · Hace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol
  5. 5. A · El ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
  6. 6. D · Un array que ya está ordenado
  7. 7. C · Un problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  8. 8. D · Θ(n³)

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