Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es la recursión?

1. AUn bucle que nunca termina
2. BUn tipo de estructura de datos
3. CUna función que se llama a sí misma con entradas más pequeñas
4. DUn método de ordenación

¿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 el tiempo de ejecución del ordenamiento por cuentas (counting sort) para n enteros en el rango de 0 a k?

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

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

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

La complejidad temporal de Fibonacci recursivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) es:

1. ALineal
2. BLogarítmica
3. CConstante
4. DExponencial

¿Por qué muchas rutinas de ordenación de las bibliotecas cambian al ordenamiento por inserción para subarrays muy pequeños?

1. AEl ordenamiento por inserción usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes
2. BEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
3. CLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
4. DEl ordenamiento por inserción es O(n log n) en el peor caso

¿Qué técnica proporciona a quicksort un tiempo de ejecución esperado de O(n log n) para cualquier entrada?

1. AElegir siempre el primer elemento
2. BUsar recursión solo en el lado izquierdo
3. COrdenar la entrada antes de ejecutar quicksort
4. DElegir el pivote de forma uniformemente aleatoria

¿Por qué la búsqueda media en una tabla hash es O(1) pero el peor caso es O(n)?

1. ALas funciones hash son lentas
2. BMuchas claves pueden colisionar en el mismo bucket
3. CLas claves deben ordenarse primero
4. DLos arrays tienen acceso O(n)