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

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

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

¿Cuál es el tiempo de ejecución del ordenamiento por cuentas (counting sort) para n enteros en el rango de 0 a k?

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

La complejidad espacial mide:

  1. ALa cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  2. BEl tamaño físico del ordenador
  3. CEl espacio en disco del archivo del programa una vez compilado
  4. DEl número de líneas de código
4.Media

¿Cuál es la complejidad temporal de quicksort en el peor caso?

  1. AO(log n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
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 usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes
  2. BLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
  3. CEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
  4. DEl ordenamiento por inserción es O(n log n) en el peor caso
6.Media

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

  1. AAlgoritmo de Dijkstra
  2. BBúsqueda en profundidad (DFS)
  3. CBellman-Ford es necesario en todos los casos
  4. DAlgoritmo de Kruskal
7.Difícil

¿Cuál es la complejidad temporal de construir un montículo binario a partir de n elementos sin ordenar con el método ascendente (bottom-up)?

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

El problema de la parada demuestra que:

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

Soluciones

  1. 1. B · O(log n)
  2. 2. A · O(n + k)
  3. 3. A · La cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  4. 4. C · O(n²)
  5. 5. C · El ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
  6. 6. A · Algoritmo de Dijkstra
  7. 7. C · O(n)
  8. 8. D · Ningún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene

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