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

¿Cuánto vale log₂ 1024?

1. A32
2. B512
3. C10
4. D12

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por mezcla (merge sort)?

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

Con monedas de 1, 3 y 4 y una cantidad de 6, ¿cuántas monedas usa el método voraz de «la moneda más grande primero», comparado con el óptimo?

1. AEl voraz usa 4 monedas; el óptimo es 3
2. BEl voraz usa 3 monedas; el óptimo es 3
3. CEl voraz usa 2 monedas; el óptimo es 2
4. DEl voraz usa 3 monedas; el óptimo es 2

La recurrencia T(n) = 2T(n/2) + O(n) tiene como solución:

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

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

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

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

1. AΘ(n^{log₂ 7}), aproximadamente n^2,81
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n²)

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

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