Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál es la complejidad temporal en el mejor caso del ordenamiento por inserción, sobre un array ya ordenado?

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

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

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

¿Cuánto vale log₂ 1024?

1. A12
2. B512
3. C32
4. D10

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

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

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

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

¿Qué algoritmo encuentra los caminos más cortos desde un origen en un grafo con pesos de aristas no negativos?

1. AAlgoritmo de Dijkstra
2. BBúsqueda en profundidad (DFS)
3. CBellman-Ford es necesario en todos los casos
4. DAlgoritmo de Kruskal

¿Qué afirmación sobre P y NP es correcta?

1. ATodo problema de P también está en NP
2. BSe ha demostrado que P ≠ NP
3. CNP significa «no polinómico»
4. DLas soluciones de los problemas NP no se pueden verificar rápidamente

¿Qué algoritmo encuentra un árbol de expansión mínima añadiendo repetidamente la arista más barata que no forme un ciclo?

1. AFloyd-Warshall
2. BAlgoritmo de Dijkstra
3. CAlgoritmo de Kruskal
4. DAlgoritmo de Prim empezando desde un nodo