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é exige la búsqueda binaria de su entrada?

  1. ALa longitud del array debe ser una potencia de dos
  2. BEl array no debe tener más de 1000 elementos
  3. CEl array debe estar ordenado
  4. DEl array solo debe contener números positivos
2.Fácil

¿Cuáles son los tres pasos de un algoritmo de divide y vencerás?

  1. ALeer, calcular, escribir
  2. BAdivinar, comprobar, repetir
  3. CDividir, vencer, combinar
  4. DOrdenar, buscar, devolver
3.Fácil

¿Qué estrategia de diseño usa merge sort?

  1. AProgramación dinámica
  2. BElección voraz
  3. CDivide y vencerás
  4. DFuerza bruta
4.Media

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

  1. AΩ(n)
  2. BΩ(log n)
  3. CΩ(n²)
  4. DΩ(n log n)
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(n²)
  2. BO(d(n + k))
  3. CO(dn log k)
  4. DO(n log n)
6.Media

¿Aproximadamente cuántas comparaciones necesita la búsqueda binaria en el peor caso en un array ordenado de 1,000,000 de elementos?

  1. AUnas 100
  2. BUnas 20
  3. CUnas 500,000
  4. DUnas 1,000
7.Difícil

El problema de la mochila 0/1 resuelto con programación dinámica requiere un tiempo O(nW). ¿Por qué se llama pseudopolinómico?

  1. AW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
  2. BPorque solo funciona para W = 0
  3. CPorque n siempre es pequeño
  4. DPorque el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
8.Difícil

El algoritmo de programación dinámica de Held-Karp resuelve exactamente el problema del viajante. ¿Cuál es su tiempo de ejecución para n ciudades?

  1. AO(n² 2ⁿ)
  2. BO(2n²)
  3. CO(n!)
  4. DO(n³)

Soluciones

  1. 1. C · El array debe estar ordenado
  2. 2. C · Dividir, vencer, combinar
  3. 3. C · Divide y vencerás
  4. 4. D · Ω(n log n)
  5. 5. B · O(d(n + k))
  6. 6. B · Unas 20
  7. 7. A · W es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
  8. 8. A · O(n² 2ⁿ)

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