Progra

Repositorio de Preguntas Tipo ECAES Tema FUNCIONES RECURSIVAS Por Ing. Hugo Humberto Morales P. UNIVERSIDAD TECNOLÓGICA DE PEREIRA Maestría En Enseñanza de las Matemáticas
28 de agosto de 2009
1. Cuál es la formula que genera la siguiente secuencia de enteros: 0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, .... A.) f (0) = 0 f (1) = 1 f (n) = 4f (n − 1) − 2f (n − 2), n ≥ 2 B.) f (0) = 0 f (1) = 1 f(n) = 2f (n − 1) + 2f (n − 2), n ≥ 2 C.) f (0) = 0 f (1) = 1 f (n) = f (n − 1) + 4f (n − 2), n ≥ 2 D.) f (n) = 2n − 1, n ≥ 0 E.) f (0) = 0 f (1) = 1 f (2) = 2 f (n) = 2f (n − 1) + 2f (n − 2) + 2f (n − 3), n≥3 2. Sea la siguiente definición recursiva, donde n es un número entero no negativo:  0   f (n) = 1    f (n − 2) + f (n − 1) ¿Cuál es el resultado de f (5)? A.) 2 B.) 3 C.) 4 1 si n = 0 sin = 1 si n > 1 D.) 5 E.) 6 3. Sea la siguiente definición recursiva, donde n es un número entero no negativo:  0   f (n) = 1    f (n − 2) + f (n − 1) si n = 0 si n = 1 si n > 1

¿Cuál es la expresión que mejor representa la complejidad en el mejor de los casos de f (n)?, es decir, ¿cuál es la mínima cantidad de llamados que se hacen a la función f para calcular el resultado cuando éstarecibe el valor n? A.) Ω(1) B.) Ω(log n) C.) Ω(n) D.) Ω(n2 ) E.) Ω(2
n/2

)

4. Sea la siguiente definición recursiva, donde n es un número entero no negativo:  0   f (n) = 1    f (n − 2) + f (n − 1) si n = 0 si n = 1 si n > 1

¿Cuál es la expresión que mejor representa la complejidad en el peor de los casos de f (n)?, es decir, ¿cuál es la máxima cantidad de llamados que se hacen a lafunción f para calcular el resultado cuando ésta recibe el valor n?

A.) O(1) B.) O(log n) C.) O(n) D.) O(n ) E.) O(2n ) 5. Sea la siguiente definición recursiva, donde n es un número entero no negativo:  0   f (n) = 1    g(n, 2, 0, 1)  a + b g(n, i, a, b) =  g(n, i + 1, b, a + b) si n = 0 si n = 1 si n > 1 si i = n si i < n
2

7. Sea la siguiente función recursiva, donde n es unnúmero entero no negativo:  3   f (n) = −2    3 · f (n − 2) − 2 · f (n − 1) ¿Cuál es el valor de f (4)? A.) 10 B.) 18 C.) -32 D.) 103 E.) 200 8. Sea la siguiente definición recursiva, donde n es un número entero no negativo:  3   f (n) = −2    g(n, 2, 3, − 2)  3 · a − 2 · b g(n, i, a, b) =  g(n, i + 1, b, 3 · a − 2 · b) si n = 0 si n = 1 si n > 1 si i = n si i < n si n = 0 si n = 1 sin > 1

¿Cuál es el resultado de f (5)? A.) 2 B.) 3 C.) 4 D.) 5 E.) 6 6. Sea la siguiente definición recursiva, donde n es un número entero no negativo:  0   f (n) = 1    g(n, 2, 0, 1)  a + b g(n, i, a, b) =  g(n, i + 1, b, a + b) si n = 0 si n = 1 si n > 1 si i = n si i < n

¿Cuál es el resultado de f (4)? A.) 10 B.) 18 C.) -32 D.) 103 E.) 200 9. Sea la siguiente función recursiva: P(1) = 1 P (n) = 2P ( n ) + n, donde n = 2m , para m ≥ 1. 2 ¿Cuál es el valor para P (32)?

¿Cuál es la expresión que mejor representa la complejidad de la función g, la cual es la misma complejidad de la función f (n)?, es decir, ¿cuál es la expresión que mejor representa la cantidad de llamados que se hacen a la función g cuando la función f recibe un valor n > 1? A.) Θ(1) B.) Θ(log n) C.)Θ(n) D.) Θ(n2 ) E.) Θ(2n ) 2

A.) 192 B.) 120 C.) 32 D.) 320 E.) 80 10. Sea la siguiente función recursiva: P (1) = 1 P (n) = 5P ( n ) + n, donde n = 5m y m ≥ 1. 5 ¿Cuál es el valor para P (125)?

A.) 25 B.) 125 C.) 250 D.) 500 E.) 1000 11. Sea la siguiente función recursiva: T (0) = 1 T (n) = T (n − 1) + 2n , para n > 1 ¿Cuál es el valor para T (4)? A.) 4 B.) 31 C.) 10 D.) 32 E.) 9 12. Sea lasiguiente definición recursiva:  1   f (m, n) =    m ∗ f (m, n − 1) si n = 0

14. Sea la siguiente definición recursiva:  1   f (m, n) =    n ∗ f (m, n − 1) si n = 0

si n > 0

¿Cuál es el resultado de f (2, 3)? A.) 8 B.) 9 C.) 6 D.) 12 E.) 2 15. Sea la siguiente definición recursiva:  1   f (m, n) =    n ∗ f (m, n − 1) si n = 0

si n > 0

¿Cuál es el resultado...