Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es un algoritmo de fuerza bruta?

1. AUno que siempre usa recursión
2. BUno que prueba todas las soluciones candidatas posibles
3. CUno que se ejecuta en muchos procesadores
4. DUno que adivina una respuesta al azar

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

1. ASiempre tarda exactamente un segundo
2. BSolo puede ejecutarse una vez
3. CSu tiempo de ejecución no crece con el tamaño de la entrada
4. DProcesa exactamente un elemento por segundo de tiempo de ejecución

¿Cuál es la complejidad temporal de la búsqueda en profundidad en un grafo almacenado como listas de adyacencia?

1. AO(V + E)
2. BO(E log V)
3. CO(V × E)
4. DO(V²)

¿Por qué suele omitirse la base del logaritmo en la notación O grande, como en O(log n)?

1. ALos logaritmos en distintas bases solo difieren en un factor constante
2. BTodos los logaritmos en informática tienen base 10, así que va implícita
3. CLos logaritmos siempre se redondean a enteros
4. DLa base solo importa para n pequeño

Una función ejecuta un bucle de n iteraciones y después, por separado, otro bucle de n iteraciones. ¿Cuál es su complejidad temporal?

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

¿Cuál es la solución de la recurrencia T(n) = 2T(n − 1) + O(1)?

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

El problema de la mochila 0/1 resuelto con programación dinámica requiere un tiempo O(nW). ¿Por qué se llama pseudopolinómico?

1. APorque el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
2. BPorque solo funciona para W = 0
3. CW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
4. DPorque n siempre es pequeño

¿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 Kruskal
2. BFloyd-Warshall
3. CAlgoritmo de Prim empezando desde un nodo
4. DAlgoritmo de Dijkstra