Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

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

¿Qué es un algoritmo?

1. AUna estructura de datos que almacena números
2. BUna secuencia finita de pasos bien definidos que resuelve un problema
3. CCualquier programa informático con interfaz gráfica
4. DUn lenguaje de programación diseñado para escribir fórmulas matemáticas

¿Qué significa que una operación se ejecute en tiempo O(1)?

1. ASolo puede ejecutarse una vez
2. BProcesa exactamente un elemento por segundo de tiempo de ejecución
3. CSiempre tarda exactamente un segundo
4. DSu tiempo de ejecución no crece con el tamaño de la entrada

¿Cuál es la complejidad temporal del algoritmo estándar de programación dinámica para la subsecuencia común más larga de dos cadenas de longitudes m y n?

1. AO(mn)
2. BO(m + n)
3. CO(mn log n)
4. DO(2^m+n)

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

1. AAlgoritmo de Kruskal
2. BBellman-Ford es necesario en todos los casos
3. CBúsqueda en profundidad (DFS)
4. DAlgoritmo de Dijkstra

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

1. AOrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque
2. BElimina la arista más cara hasta que no quedan ciclos
3. CHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol
4. DEjecuta una búsqueda en anchura y se queda con el árbol BFS

¿Qué cota es correcta para log(n!)?

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

¿Qué se deduciría si alguien hallara un algoritmo de tiempo polinómico para un problema NP-completo?

1. ATodo problema de NP podría resolverse en tiempo polinómico, así que P = NP
2. BEl problema de la parada se volvería decidible
3. CTodos los algoritmos de tiempo exponencial pasarían de inmediato a ejecutarse en tiempo lineal
4. DSolo ese problema pasaría a P