Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es un algoritmo?

1. AUn lenguaje de programación diseñado para escribir fórmulas matemáticas
2. BUna secuencia finita de pasos bien definidos que resuelve un problema
3. CCualquier programa informático con interfaz gráfica
4. DUna estructura de datos que almacena números

¿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. CLa llamada que usa más memoria
4. DUn caso que se resuelve directamente sin hacer otra llamada recursiva

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

1. AEl tiempo que tarda con la entrada más pequeña
2. BEl tiempo máximo que tarda entre todas las entradas de tamaño n
3. CEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
4. DEl tiempo que tarda en un ordenador lento

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

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

¿Cuál es la complejidad temporal amortizada de añadir al final de un array dinámico que duplica su capacidad cuando está lleno?

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

¿Cuál es la complejidad temporal de calcular el n-ésimo número de Fibonacci con una tabla ascendente (bottom-up)?

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

¿Cuál es la complejidad temporal de: para i = 1 hasta n: para (j = i; j ≤ n; j = j + i) hacer trabajo O(1)?

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

¿Qué afirmación sobre la notación o pequeña es correcta?

1. A2n = o(n), porque 2n crece despacio
2. Bn = o(n), porque toda función es o pequeña de sí misma
3. Cn² = o(n)
4. Dn = o(n²), pero n no es o(n)