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 de la búsqueda en profundidad en un grafo almacenado como listas de adyacencia?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V²)
2.Fácil

La complejidad espacial mide:

  1. AEl espacio en disco del archivo del programa una vez compilado
  2. BLa cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  3. CEl tamaño físico del ordenador
  4. DEl número de líneas de código
3.Fácil

Un bucle empieza con i = 1 y duplica i en cada iteración hasta que i > n. ¿Cuántas iteraciones ejecuta?

  1. AUnas n
  2. BUnas n²
  3. CUnas n / 2
  4. DUnas log₂ n
4.Media

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para j = 1 hasta i: hacer trabajo O(1)?

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

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

  1. ABúsqueda en profundidad (DFS)
  2. BAlgoritmo de Dijkstra
  3. CAlgoritmo de Kruskal
  4. DBellman-Ford es necesario en todos los casos
6.Media

¿Cuál es la complejidad temporal del algoritmo estándar de programación dinámica para la subsecuencia común más larga de dos cadenas de longitudes m y n?

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

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

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

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

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

Soluciones

  1. 1. B · O(V + E)
  2. 2. B · La cantidad de memoria que necesita un algoritmo a medida que crece la entrada
  3. 3. D · Unas log₂ n
  4. 4. D · O(n²)
  5. 5. B · Algoritmo de Dijkstra
  6. 6. D · O(mn)
  7. 7. A · O(1) por incremento
  8. 8. C · Grafos dirigidos acíclicos (DAG)

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