Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es el caso base de una función recursiva?

1. ALa llamada que usa más memoria
2. BUn caso que se resuelve directamente sin hacer otra llamada recursiva
3. CEl caso con la entrada más grande, que se trata antes de cualquier llamada recursiva
4. DLa primera línea de la función

Un bucle empieza con i = 1 y duplica i en cada iteración hasta que i > n. ¿Cuántas iteraciones ejecuta?

1. AUnas n²
2. BUnas log₂ n
3. CUnas n
4. DUnas n / 2

¿Qué es un algoritmo de fuerza bruta?

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

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

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

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

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

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

1. ALa programación dinámica solo funciona con problemas de grafos, no con arreglos
2. BMerge sort ya es O(n)
3. CMerge sort no tiene estructura recursiva
4. DSus subproblemas no se solapan, así que no hay nada que reutilizar

¿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)
2. BO(n²)
3. CO(n √n)
4. DO(n log 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. BDe calidad desconocida respecto al óptimo
3. CSiempre es un recubrimiento de vértices mínimo
4. DComo mucho log n veces el mínimo