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

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

  1. A1 segundo
  2. B2 segundos
  3. C4 segundos
  4. D8 segundos
2.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
3.Fácil

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

  1. AO(n log n)
  2. BO(n)
  3. CO(log n)
  4. DO(1)
4.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(dn log k)
  2. BO(n²)
  3. CO(n log n)
  4. DO(d(n + k))
5.Media

La búsqueda en anchura (BFS) en un grafo no ponderado encuentra:

  1. ALos caminos más cortos en grafos que contienen aristas con pesos negativos
  2. BLos caminos más cortos en número de aristas desde el nodo inicial
  3. CEl árbol de expansión mínima
  4. DUn orden topológico en todos los grafos
6.Media

¿Cuál es la solución de la recurrencia T(n) = T(n − 1) + O(1)?

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

¿Qué afirmación sobre la notación o pequeña es correcta?

  1. A2n = o(n), porque 2n crece despacio
  2. Bn² = o(n)
  3. Cn = o(n), porque toda función es o pequeña de sí misma
  4. Dn = o(n²), pero n no es o(n)
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. APuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo
  2. BEs indecidible
  3. CEs NP-difícil
  4. DSiempre puede resolverse en O(V + E)

Soluciones

  1. 1. C · 4 segundos
  2. 2. B · El array debe estar ordenado
  3. 3. C · O(log n)
  4. 4. D · O(d(n + k))
  5. 5. B · Los caminos más cortos en número de aristas desde el nodo inicial
  6. 6. A · O(n)
  7. 7. D · n = o(n²), pero n no es o(n)
  8. 8. C · Es NP-difícil

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