Pseudocódigo Avanzado: Recursión y Análisis de Complejidad
Nombre: ___________________________
Fecha: ____________________________
Puntaje: __________________________
1.
¿Cuál es la característica esencial de una función recursiva?
Llamarse a sí misma
Utilizar un bucle
Devolver un valor entero
2.
En una función recursiva, ¿qué condición evita que ocurra un bucle infinito?
Caso base
Caso recursivo
Parámetro por valor
Retorno explícito
3.
¿Qué estructura de datos utiliza implícitamente el mecanismo de recursión para gestionar las llamadas pendientes?
Pila (stack)
Cola (queue)
Lista enlazada
Árbol binario
4.
En la función recursiva factorial, el caso base para n=0 retorna el valor ___.
Respuesta: ____________________________________________
5.
¿Qué tipo de recursión se presenta cuando una función se llama a sí misma más de una vez en el mismo paso recursivo?
Recursión lineal
Recursión en árbol
Recursión de cola
Recursión indirecta
6.
Complejidad temporal de la función recursiva factorial (sin optimización) para entrada n:
O(n)
O(n^2)
O(2^n)
7.
Dada la recurrencia T(n) = T(n-1) + c, con T(0)=c, ¿cuál es su complejidad asintótica?
O(1)
O(log n)
O(n^2)
O(n)
8.
Para la secuencia de Fibonacci recursiva clásica, su complejidad temporal es aproximadamente:
O(n)
O(n^2)
O(log n)
O(2^n)
9.
La complejidad espacial de la función recursiva factorial (sin optimización) es O(___). (Expresa con la notación asintótica, ej: n, n^2, log n)
Respuesta: ____________________________________________
10.
¿Cuál de las siguientes estrategias permite reducir la complejidad temporal de Fibonacci recursivo de exponencial a lineal?
Recursión de cola
Recursión anidada
Memoización
División y vencerás
11.
En recursión de cola, la llamada recursiva es la última operación. ¿Qué ventaja principal ofrece?
Menor uso de memoria
Mayor legibilidad
Evita el caso base
12.
Analiza el siguiente pseudocódigo recursivo: funcion misterio(n): si n=0: retornar 0; sino retornar n + misterio(n-1). ¿Qué calcula?
n!
n^2
Suma 1..n
2^n
13.
En la función recursiva suma_digitos(n), el caso base ocurre cuando n < 10, y se retorna ___.
Respuesta: ____________________________________________
14.
¿Cuál de los siguientes algoritmos típicamente NO se implementa de forma recursiva?
Recorrido de árbol binario
Búsqueda binaria
Euclides
Ordenamiento por burbuja
15.
La complejidad temporal de la función de Ackermann (A(m,n)) es:
O(m*n)
O(2^(m+n))
Extremadamente rápida (superexponencial)
O(m log n)
16.
En el análisis de complejidad, notación Theta (Θ) se usa para:
Cota superior asintótica
Cota inferior asintótica
Cota ajustada asintótica
17.
¿Cuál es la complejidad temporal del siguiente algoritmo recursivo? funcion f(n): si n<=1: retornar 1; sino retornar f(n/2) + f(n/2). (Asumiendo que la suma es O(1))
O(log n)
O(n log n)
O(n)
O(2^n)
18.
La recursión indirecta ocurre cuando:
Una función se llama a sí misma
Dos o más funciones se llaman mutuamente
La llamada recursiva no es la última instrucción
Se usa una pila explícita
19.
Para el algoritmo recursivo que calcula la potencia x^n con la estrategia de exponenciación rápida, su complejidad temporal es O(___).
Respuesta: ____________________________________________
20.
En el análisis de la complejidad espacial de la recursión, ¿cuál de los siguientes factores determina principalmente el espacio ocupado en la pila?
Número de llamadas recursivas simultáneas
Tamaño de los parámetros
Número de variables locales
Tipo de recursión (lineal o árbol)