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 3 segundos para n = 1 millón. ¿Aproximadamente cuánto tarda para n = 2 millones?

  1. A9 segundos
  2. B12 segundos
  3. C3 segundos
  4. D6 segundos
2.Fácil

¿Cuál es la complejidad temporal en el mejor caso del ordenamiento por inserción, sobre un array ya ordenado?

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

¿Qué complejidad suele tener un algoritmo con dos bucles anidados que se ejecutan n veces cada uno?

  1. AO(n²)
  2. BO(2n)
  3. CO(log n)
  4. DO(n)
4.Media

¿Cuál es la complejidad temporal de calcular el n-ésimo número de Fibonacci con una tabla ascendente (bottom-up)?

  1. AO(log n)
  2. BO(n²)
  3. CO(2ⁿ)
  4. DO(n)
5.Media

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

  1. AO(n²)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n)
6.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. BEl árbol de expansión mínima
  3. CLos caminos más cortos en número de aristas desde el nodo inicial
  4. DUn orden topológico en todos los grafos
7.Difícil

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

  1. AUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  2. BLos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
  3. CAmbos significan que el problema no tiene ningún algoritmo
  4. DLos problemas indecidibles están en NP, mientras que los intratables están en P
8.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. CTodo problema de P también está en NP
  4. DLas soluciones de los problemas NP no se pueden verificar rápidamente

Soluciones

  1. 1. D · 6 segundos
  2. 2. D · O(n)
  3. 3. A · O(n²)
  4. 4. D · O(n)
  5. 5. A · O(n²)
  6. 6. C · Los caminos más cortos en número de aristas desde el nodo inicial
  7. 7. A · 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. C · Todo problema de P también está en NP

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