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é es la recursión?

  1. AUn bucle que nunca termina
  2. BUna función que se llama a sí misma con entradas más pequeñas
  3. CUn método de ordenación
  4. DUn tipo de estructura de datos
2.Fácil

¿Cuál es la O grande de 3n² + 5n + 2?

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

¿Qué exige la búsqueda binaria de su entrada?

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

¿Qué afirmación sobre una función recursiva sin un caso base alcanzable es correcta?

  1. AEl compilador siempre la convierte en un bucle que termina sin problemas
  2. BDevuelve 0 automáticamente
  3. CSe ejecuta en tiempo O(1)
  4. DSigue llamándose a sí misma hasta que se desborda la pila de llamadas
5.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)
6.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(n log n)
  3. CO(d(n + k))
  4. DO(dn log k)
7.Difícil

¿Qué afirmación sobre P y NP es correcta?

  1. ANP significa «no polinómico»
  2. BSe ha demostrado que P ≠ NP
  3. CLas soluciones de los problemas NP no se pueden verificar rápidamente
  4. DTodo problema de P también está en NP
8.Difícil

¿Qué algoritmo encuentra un árbol de expansión mínima añadiendo repetidamente la arista más barata que no forme un ciclo?

  1. AAlgoritmo de Dijkstra
  2. BAlgoritmo de Prim empezando desde un nodo
  3. CFloyd-Warshall
  4. DAlgoritmo de Kruskal

Soluciones

  1. 1. B · Una función que se llama a sí misma con entradas más pequeñas
  2. 2. A · O(n²)
  3. 3. B · El array debe estar ordenado
  4. 4. D · Sigue llamándose a sí misma hasta que se desborda la pila de llamadas
  5. 5. A · O(n³)
  6. 6. C · O(d(n + k))
  7. 7. D · Todo problema de P también está en NP
  8. 8. D · Algoritmo de Kruskal

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