Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué describe el tiempo de ejecución en el caso promedio?

1. AEl tiempo en el ordenador más común
2. BEl valor intermedio entre los tiempos de ejecución del mejor y del peor caso
3. CEl tiempo para una entrada de longitud media
4. DEl tiempo esperado según una distribución dada de las entradas de tamaño n

¿Qué significa f(n) = Θ(g(n))?

1. Af crece estrictamente más despacio que g
2. Bf crece al mismo ritmo que g, acotada por arriba y por abajo por múltiplos constantes de g
3. Cf es siempre menor que g para todo n, así que g la acota por arriba pero nunca por abajo
4. Df crece estrictamente más deprisa que g

¿Cómo funciona el ordenamiento por selección?

1. AInserta cada elemento en una parte ordenada creciente mediante desplazamientos
2. BDivide el array en mitades y las mezcla
3. CBusca repetidamente el mínimo de la parte no ordenada y lo intercambia hacia el principio
4. DIntercambia repetidamente elementos vecinos que están en el orden incorrecto

¿Qué calcula el algoritmo de Floyd-Warshall y con qué rapidez?

1. ALos caminos más cortos entre todos los pares de vértices en O(V³)
2. BLos caminos más cortos desde un vértice origen hasta todos los demás en O(V + E)
3. CUn árbol de expansión mínima en O(E log V)
4. DUn orden topológico en O(V²)

¿Qué significa que un problema tenga subestructura óptima?

1. AEl problema puede resolverse en tiempo constante
2. BEl problema tiene exactamente una solución óptima, que comparten todos sus subproblemas
3. CUna solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas
4. DTodos los subproblemas tienen el mismo tamaño

¿Aproximadamente cuántas comparaciones necesita la búsqueda binaria en el peor caso en un array ordenado de 1,000,000 de elementos?

1. AUnas 1,000
2. BUnas 20
3. CUnas 100
4. DUnas 500,000

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

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

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. ASiempre es un recubrimiento de vértices mínimo
2. BComo mucho el doble del tamaño de un recubrimiento de vértices mínimo
3. CComo mucho log n veces el mínimo
4. DDe calidad desconocida respecto al óptimo