Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cómo funciona el ordenamiento por selección?

1. AIntercambia repetidamente elementos vecinos que están en el orden incorrecto
2. BInserta cada elemento en una parte ordenada creciente mediante desplazamientos
3. CDivide el array en mitades y las mezcla
4. DBusca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio

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

1. ASiempre tarda exactamente un segundo
2. BSu tiempo de ejecución no crece con el tamaño de la entrada
3. CProcesa exactamente un elemento por segundo de tiempo de ejecución
4. DSolo puede ejecutarse una vez

¿Qué es la recursión?

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

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

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

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

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

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

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

¿Por qué la búsqueda media en una tabla hash es O(1) pero el peor caso es O(n)?

1. ALos arrays tienen acceso O(n)
2. BLas claves deben ordenarse primero
3. CMuchas claves pueden colisionar en el mismo bucket
4. DLas funciones hash son lentas

El ordenamiento por inserción se ejecuta en O(n) con una entrada ordenada. ¿Contradice esto la cota inferior Ω(n log n) de la ordenación por comparaciones?

1. ASí, pero solo para arrays de menos de 100 elementos
2. BSí, así que la cota inferior es errónea
3. CNo, la cota inferior se aplica al peor caso entre todas las entradas, no a cada entrada
4. DNo, porque el ordenamiento por inserción no es una ordenación por comparaciones