Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué algoritmo de ordenación elige un pivote y divide el array en elementos menores y mayores?

1. AMerge sort
2. BQuicksort
3. COrdenamiento por inserción
4. DOrdenamiento de burbuja

¿Cuánta memoria adicional usa un merge sort estándar basado en arrays?

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

¿Cuál de estas crece más despacio a medida que n se hace grande?

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

¿Cuál es la complejidad temporal de quicksort en el peor caso?

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

Un quicksort usa siempre el primer elemento como pivote. ¿Con qué entrada muestra su comportamiento de peor caso?

1. AUn array de longitud 2
2. BUn array en orden aleatorio
3. CUn array que ya está ordenado
4. DUn array con todos sus elementos distintos

¿Por qué muchas rutinas de ordenación de las bibliotecas cambian al ordenamiento por inserción para subarrays muy pequeños?

1. AEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
2. BLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
3. CEl ordenamiento por inserción usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes
4. DEl ordenamiento por inserción es O(n log n) en el peor caso

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

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

¿Qué algoritmo encuentra un árbol de expansión mínima añadiendo repetidamente la arista más barata que no forme un ciclo?

1. AAlgoritmo de Dijkstra
2. BFloyd-Warshall
3. CAlgoritmo de Prim empezando desde un nodo
4. DAlgoritmo de Kruskal