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

¿Qué es un algoritmo de fuerza bruta?

  1. AUno que adivina una respuesta al azar
  2. BUno que siempre usa recursión
  3. CUno que se ejecuta en muchos procesadores
  4. DUno que prueba todas las soluciones candidatas posibles
2.Fácil

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

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

¿Qué es la recursión?

  1. AUna función que se llama a sí misma con entradas más pequeñas
  2. BUn método de ordenación
  3. CUn bucle que nunca termina
  4. DUn tipo de estructura de datos
4.Media

¿Cuál es la complejidad temporal del algoritmo de Bellman-Ford en un grafo con V vértices y E aristas?

  1. AO(V + E)
  2. BO(V × E)
  3. CO(V³ × E)
  4. DO(E log V)
5.Media

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

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

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

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

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

  1. ALos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
  2. BUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento
  3. CLos problemas indecidibles están en NP, mientras que los intratables están en P
  4. DAmbos significan que el problema no tiene ningún algoritmo
8.Difícil

¿Qué técnica proporciona a quicksort un tiempo de ejecución esperado de O(n log n) para cualquier entrada?

  1. AOrdenar la entrada antes de ejecutar quicksort
  2. BUsar recursión solo en el lado izquierdo
  3. CElegir siempre el primer elemento
  4. DElegir el pivote de forma uniformemente aleatoria

Soluciones

  1. 1. D · Uno que prueba todas las soluciones candidatas posibles
  2. 2. C · O(n)
  3. 3. A · Una función que se llama a sí misma con entradas más pequeñas
  4. 4. B · O(V × E)
  5. 5. B · Los caminos más cortos en número de aristas desde el nodo inicial
  6. 6. C · Los logaritmos en distintas bases solo difieren en un factor constante
  7. 7. B · 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. D · Elegir el pivote de forma uniformemente aleatoria

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