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 mezcla (merge sort)
3. COrdenamiento por montículos (heap sort)
4. DQuicksort

¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?

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

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por inserción?

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

¿Qué mide el análisis amortizado?

1. AEl coste de la única operación más cara de toda la secuencia
2. BEl coste esperado con entradas aleatorias
3. CEl coste de un algoritmo con la mejor entrada
4. DEl coste medio por operación a lo largo de una secuencia de operaciones del peor caso

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

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

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

1. ALa programación dinámica solo funciona con problemas de grafos, no con arreglos
2. BMerge sort no tiene estructura recursiva
3. CSus subproblemas no se solapan, así que no hay nada que reutilizar
4. DMerge sort ya es O(n)

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

1. An! es O(n²)
2. Bn! crece más deprisa que 2ⁿ
3. C2ⁿ crece más deprisa que n!
4. DCrecen al mismo ritmo

¿Qué afirmación sobre seleccionar el k-ésimo elemento más pequeño de un array no ordenado es correcta?

1. ALa selección solo es posible en O(n²)
2. BLa selección siempre necesita Ω(n log n) porque requiere ordenar
3. CQuickselect se ejecuta en O(n) esperado, y la mediana de medianas garantiza O(n) en el peor caso
4. DQuickselect se ejecuta en O(log n) en el peor caso, porque solo hace recursión en un lado del pivote