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

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

  1. AConstante
  2. BCuadrático
  3. CLogarítmico
  4. DLineal
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(1)
  3. CO(n log n)
  4. DO(n²)
3.Fácil

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

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

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

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

¿Cuál es la complejidad temporal amortizada de añadir al final de un array dinámico que duplica su capacidad cuando está lleno?

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

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

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

La ordenación topológica solo es posible en:

  1. AGrafos dirigidos acíclicos (DAG)
  2. BGrafos completos
  3. CGrafos con pesos negativos
  4. DGrafos no dirigidos
8.Difícil

Tomar los dos extremos de cada arista de un emparejamiento maximal da un recubrimiento de vértices. ¿Cómo de bueno es este recubrimiento?

  1. AComo mucho el doble del tamaño de un recubrimiento de vértices mínimo
  2. BDe calidad desconocida respecto al óptimo
  3. CSiempre es un recubrimiento de vértices mínimo
  4. DComo mucho log n veces el mínimo

Soluciones

  1. 1. D · Lineal
  2. 2. A · O(n)
  3. 3. A · O(n²)
  4. 4. D · O(log n)
  5. 5. A · O(1)
  6. 6. B · O(n²)
  7. 7. A · Grafos dirigidos acíclicos (DAG)
  8. 8. A · Como mucho el doble del tamaño de un recubrimiento de vértices mínimo

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