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 en el peor caso del ordenamiento por inserción?

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

¿Cuánta memoria adicional usa un merge sort estándar basado en arrays?

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

El tiempo de ejecución de un algoritmo es O(n). ¿Cómo se llama este crecimiento?

  1. ALineal
  2. BCuadrático
  3. CLogarítmico
  4. DConstante
4.Media

¿Cuál es la complejidad temporal de: para i = 1 hasta n: (j = 1; mientras j < n: j = j × 2)?

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

¿Por qué suele omitirse la base del logaritmo en la notación O grande, como en O(log n)?

  1. ALos logaritmos en distintas bases solo difieren en un factor constante
  2. BTodos los logaritmos en informática tienen base 10, así que va implícita
  3. CLos logaritmos siempre se redondean a enteros
  4. DLa base solo importa para n pequeño
6.Media

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

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

¿Cuál es el coste amortizado de incrementar un contador binario, sabiendo que un incremento puede cambiar muchos bits?

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

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

  1. ALas soluciones de los problemas NP no se pueden verificar rápidamente
  2. BNP significa «no polinómico»
  3. CTodo problema de P también está en NP
  4. DSe ha demostrado que P ≠ NP

Soluciones

  1. 1. D · O(n²)
  2. 2. C · O(n)
  3. 3. A · Lineal
  4. 4. C · O(n log n)
  5. 5. A · Los logaritmos en distintas bases solo difieren en un factor constante
  6. 6. A · O(2ⁿ)
  7. 7. D · O(1) por incremento
  8. 8. C · Todo problema de P también está en NP

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