Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuáles son los tres pasos de un algoritmo de divide y vencerás?

1. ADividir, vencer, combinar
2. BOrdenar, buscar, devolver
3. CAdivinar, comprobar, repetir
4. DLeer, calcular, escribir

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

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

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

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

¿Qué afirmación sobre una función recursiva sin un caso base alcanzable es correcta?

1. AEl compilador siempre la convierte en un bucle que termina sin problemas
2. BSigue llamándose a sí misma hasta que se desborda la pila de llamadas
3. CSe ejecuta en tiempo O(1)
4. DDevuelve 0 automáticamente

¿Cuánto espacio de pila usa una función factorial recursiva sencilla fact(n) = n × fact(n − 1)?

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

¿Qué mide el análisis amortizado?

1. AEl coste esperado con entradas aleatorias
2. BEl coste medio por operación a lo largo de una secuencia de operaciones del peor caso
3. CEl coste de la única operación más cara de toda la secuencia
4. DEl coste de un algoritmo con la mejor entrada

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para (j = i; j ≤ n; j = j + i) hacer trabajo O(1)?

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

Tomar los dos extremos de cada arista de un emparejamiento maximal da un recubrimiento de vértices. ¿Cómo de bueno es este recubrimiento?

1. AComo mucho el doble del tamaño de un recubrimiento de vértices mínimo
2. BComo mucho log n veces el mínimo
3. CDe calidad desconocida respecto al óptimo
4. DSiempre es un recubrimiento de vértices mínimo