Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué algoritmo de ordenación intercambia repetidamente elementos adyacentes que están en el orden incorrecto?

1. AOrdenamiento de burbuja (bubble sort)
2. BOrdenamiento por montículos (heap sort)
3. COrdenamiento por mezcla (merge sort)
4. DQuicksort

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

1. AInserta cada elemento en una parte ordenada creciente mediante desplazamientos
2. BIntercambia repetidamente elementos vecinos que están en el orden incorrecto
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é es un algoritmo de fuerza bruta?

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

¿Qué significa que un problema tenga subestructura óptima?

1. AEl problema puede resolverse en tiempo constante
2. BTodos los subproblemas tienen el mismo tamaño
3. CUna solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas
4. DEl problema tiene exactamente una solución óptima, que comparten todos sus subproblemas

¿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(n²)
3. CO(log n)
4. DO(n)

La cota inferior para la ordenación basada en comparaciones en el peor caso es:

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

¿Cuáles son los costes de tiempo y espacio de calcular el n-ésimo número de Fibonacci con un bucle que guarda solo los dos últimos valores?

1. ATiempo O(n) y espacio O(n)
2. BTiempo O(2ⁿ) y espacio O(1)
3. CTiempo O(n) y espacio O(1)
4. DTiempo O(log n) y espacio O(n)

¿Cómo se comparan n! y 2ⁿ para n grande?

1. A2ⁿ crece más deprisa que n!
2. BCrecen al mismo ritmo
3. Cn! crece más deprisa que 2ⁿ
4. Dn! es O(n²)