Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué significa que una operación se ejecute en tiempo O(1)?

1. AProcesa exactamente un elemento por segundo de tiempo de ejecución
2. BSolo puede ejecutarse una vez
3. CSiempre tarda exactamente un segundo
4. DSu tiempo de ejecución no crece con el tamaño de la entrada

¿Qué notación describe una cota superior del crecimiento?

1. AOmega pequeña (little omega)
2. BOmega grande (Big Omega)
3. CO grande (Big O)
4. DTheta grande (Big Theta)

¿Qué describe el tiempo de ejecución en el caso promedio?

1. AEl valor intermedio entre los tiempos de ejecución del mejor y del peor caso
2. BEl tiempo para una entrada de longitud media
3. CEl tiempo esperado según una distribución dada de las entradas de tamaño n
4. DEl tiempo en el ordenador más común

La programación dinámica es útil cuando un problema tiene:

1. AUn único bucle
2. BNingún subproblema en absoluto, así que puede resolverse en un solo paso
3. CSolo entradas aleatorias
4. DSubproblemas superpuestos y subestructura óptima

¿Qué algoritmo de ordenación es estable?

1. AHeap sort
2. BOrdenamiento por selección (versión habitual)
3. CMerge sort
4. DQuicksort (versión in situ habitual)

Un algoritmo voraz (greedy):

1. ASiempre da la solución óptima
2. BSolo usa recursión
3. CPrueba todas las soluciones posibles
4. DToma la mejor decisión local en cada paso

¿En qué variante del problema de la mochila la regla voraz «tomar los objetos por orden de valor por unidad de peso» da siempre una respuesta óptima?

1. AEn ninguna de las dos
2. BLa mochila fraccionaria, en la que los objetos pueden dividirse
3. CEn ambas variantes
4. DLa mochila 0/1, en la que los objetos deben tomarse siempre enteros

Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n³)