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)

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por inserción?

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

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

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

En el problema de selección de actividades, ¿qué regla voraz da siempre el número máximo de actividades que no se solapan?

1. AElegir la actividad que empieza antes
2. BElegir la actividad que termina antes y repetir con las compatibles
3. CElegir primero la actividad con menos solapamientos y repetir con las compatibles
4. DElegir primero la actividad más corta

Un algoritmo voraz (greedy):

1. ASiempre da la solución óptima
2. BSolo usa recursión
3. CPrueba todas las soluciones posibles
4. DToma la mejor decisión local en cada paso

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

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

¿Qué definición de la clase P es correcta?

1. AProblemas cuyas soluciones pueden comprobarse, pero nunca hallarse, en tiempo polinómico
2. BProblemas que pueden resolverse en paralelo
3. CProblemas que necesitan tiempo exponencial en cualquier ordenador
4. DProblemas de decisión resolubles por un algoritmo determinista en tiempo polinómico

¿Por qué el algoritmo de Dijkstra puede dar resultados erróneos cuando algunos pesos de arista son negativos?

1. AUn vértice se da por cerrado al extraerlo, pero una arista negativa posterior aún podría darle un camino más corto
2. BLos números negativos no pueden guardarse en una cola de prioridad
3. CSolo funciona con grafos no dirigidos
4. DEntra en un bucle infinito con cada arista negativa