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. BOrdenamiento por inserción
3. COrdenamiento de burbuja
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)

Un algoritmo O(n²) tarda 1 segundo para n = 1000. ¿Aproximadamente cuánto tarda para n = 2000?

1. A8 segundos
2. B1 segundo
3. C2 segundos
4. D4 segundos

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

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

¿Cuál es la complejidad temporal de multiplicar dos matrices n × n con el triple bucle estándar?

1. AO(n)
2. BO(n²)
3. CO(n³)
4. DO(n² log 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

Un problema es NP-completo si:

1. AEstá fuera de NP pero es más difícil que todos los problemas NP, como el problema de la parada
2. BSe puede resolver en tiempo polinómico
3. CEstá en NP y todo problema NP se reduce a él en tiempo polinómico
4. DEs imposible de resolver

Para demostrar que un problema nuevo X es NP-difícil, ¿qué hay que hacer?

1. ADemostrar que X puede verificarse en tiempo polinómico
2. BReducir en tiempo polinómico X a un problema NP-difícil conocido
3. CReducir en tiempo polinómico un problema NP-difícil conocido a X
4. DDemostrar que X no tiene algoritmo polinómico para entradas pequeñas