1.Fácil
¿Qué es el caso base de una función recursiva?
- AEl caso con la entrada más grande, que se trata antes de cualquier llamada recursiva
- BLa primera línea de la función
- CLa llamada que usa más memoria
- DUn caso que se resuelve directamente sin hacer otra llamada recursiva
2.Fácil
¿Cuál es la complejidad temporal en el peor caso del ordenamiento por inserción?
- AO(n log n)
- BO(n²)
- CO(n)
- DO(log n)
3.Fácil
¿Cuál es la complejidad temporal de la búsqueda en profundidad en un grafo almacenado como listas de adyacencia?
- AO(E log V)
- BO(V × E)
- CO(V²)
- DO(V + E)
4.Media
¿Cuál es el tiempo de ejecución del radix sort LSD sobre n enteros de d dígitos en base k?
- AO(n²)
- BO(dn log k)
- CO(n log n)
- DO(d(n + k))
5.Media
¿Cuál es la complejidad temporal de quicksort en el peor caso?
- AO(n)
- BO(log n)
- CO(n²)
- DO(n log n)
6.Media
La cota inferior para la ordenación basada en comparaciones en el peor caso es:
- AΩ(n log n)
- BΩ(log n)
- CΩ(n²)
- DΩ(n)
7.Difícil
Usando el teorema maestro, T(n) = 8T(n/2) + O(n²) tiene como solución:
- AΘ(n³)
- BΘ(n²)
- CΘ(n² log n)
- DΘ(n log n)
8.Difícil
¿Cuál es el coste amortizado de incrementar un contador binario, sabiendo que un incremento puede cambiar muchos bits?
- AO(log n) por incremento
- BO(1) por incremento
- CO(n) por incremento
- DO(n log n) por incremento
Soluciones
- 1. D · Un caso que se resuelve directamente sin hacer otra llamada recursiva
- 2. B · O(n²)
- 3. D · O(V + E)
- 4. D · O(d(n + k))
- 5. C · O(n²)
- 6. A · Ω(n log n)
- 7. A · Θ(n³)
- 8. B · O(1) por incremento
Soluciones completas paso a paso: practica este tema en examproblems.com.