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. AOrdenamiento por inserción
2. BQuicksort
3. COrdenamiento de burbuja
4. DMerge sort

¿Qué notación describe una cota superior del crecimiento?

1. AOmega pequeña (little omega)
2. BTheta grande (Big Theta)
3. CO grande (Big O)
4. DOmega grande (Big Omega)

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

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

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

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

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

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

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

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

El problema de la parada demuestra que:

1. AAlgunos programas se ejecutan más rápido en ordenadores más rápidos, así que la parada depende del hardware
2. BTodo programa acaba deteniéndose
3. CNingún algoritmo puede decidir, para todo programa y toda entrada, si el programa se detiene
4. DHay que evitar los bucles

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²)
2. BΘ(n^{log₂ 7}), aproximadamente n^2,81
3. CΘ(n³)
4. DΘ(n² log n)