Fundamentos de Algoritmia Exam Past Paper PDF January 2022

Fundamentos de Algoritmia Examen de enero Curso 2021/2022 Nombre:.....................................................................................

Fundamentos de Algoritmia Examen de enero Curso 2021/2022 Nombre:................................................................................................ Observaciones: En el test, para cada pregunta hay una única respuesta correcta. Cada respuesta correcta vale 0,1 puntos y cada respuesta incorrecta resta 0,033 puntos. 1. Dada la especificación {𝑣.𝑠𝑖𝑧𝑒 ≥ 0} fun xxx(vector 𝑣) dev int 𝑟 {𝑟 = max 𝑝, 𝑞 ∶ 0 ≤ 𝑝 ≤ 𝑞 ≤ 𝑣.𝑠𝑖𝑧𝑒 ∧ ∀𝑖 ∶ 𝑝 ≤ 𝑖 < 𝑞 ∶ 𝑣[𝑖] = 0 ∶ 𝑞 − 𝑝} y el vector de entrada 𝑣 = [5, 4, 0, 4, 3, 0, 0, 0, 0, 5, 3, 0, 0, 5], ¿cuál es el valor de 𝑟 según la especificación? (a) 𝑟 = 7. (b) 𝑟 = 0. (c) 𝑟 = 4. (d) Ninguna de las anteriores. ⑤òž!. c 2. Un algoritmo óptimo que busca el máximo en un vector ordenado de 𝑛 elementos tiene complejidad en el caso peor: (a) 𝛩(log 𝑛). (b) 𝛩(1). (c) 𝛩(𝑛). (d) Ninguna de las anteriores. ⑤òž!. b 3. Indica la complejidad del siguiente algoritmo: int c = 0; for (int i = 1; i < n; i *= 2) for (int j = 0; j < m+2; ++j) c += 4; (a) 𝛩(1). (b) 𝛩(𝑚 log 𝑛). (c) 𝛩(𝑛𝑚). b (d) Ninguna de las anteriores. ⑤òž!. 4. Dado un vector 𝑎 de 𝑛 enteros, con 𝑛 ≥ 1, y una variable booleana 𝑏, el predicado 𝑏 = ∃𝑤 ∶ 0 ≤ 𝑤 < 𝑛 ∶ (∃𝑘 ∶ 0 ≤ 𝑘 ∶ 𝑎[𝑤] = 2 ∗ 𝑘 + 1) significa que la variable 𝑏 toma el valor cierto si y solo si: (a) Hay al menos una posición en el vector que contiene un número impar positivo. (b) Nunca toma el valor cierto. (c) Todas las posiciones del vector son impares. (d) Ninguna de las anteriores. ⑤òž!. a 1 5. Dada la especificación {𝑎.𝑠𝑖𝑧𝑒 ≥ 0} fun contarPares(vector 𝑎) dev int 𝑐 {𝑐 = #𝑖 ∶ 0 ≤ 𝑖 < 𝑎.𝑠𝑖𝑧𝑒 ∶ 𝑎[𝑖] % 2 = 0} y el siguiente algoritmo: int contarPares(vector const& a) { int c=0; int k=-1; while (k -N; --i) ++k; (a) 𝑓 (𝑖, 𝑁) = 𝑖. (b) 𝑓 (𝑖, 𝑁) = 𝑖 + 𝑁. (c) 𝑓 (𝑖, 𝑁) = 𝑖 − 𝑁. (d) 𝑓 (𝑖, 𝑁) = 𝑁 − 𝑖 ⑤òž!. b 10. Indica el coste de un algoritmo cuya recurrencia es: 𝑐0 si 𝑛 == 0 𝑇(𝑛) = { 𝑇(𝑛 − 1) + 𝑛 si 𝑛 > 0 (a) O(𝑛). (c) O(𝑛 log 𝑛). (b) O(𝑛2 ). (d) Ninguna de las anteriores. ⑤òž!. c 1 2 3 4 5 6 7 8 9 10 3  Fundamentos de Algoritmia Examen de enero. Tipo B Curso 2022/2023 Nombre:................................................................................................. Observaciones: En el test, para cada pregunta hay una única respuesta correcta. Cada respuesta correcta vale 0,1 puntos y cada respuesta incorrecta resta 0,033 puntos. 1. Indica la complejidad del siguiente algoritmo: int c = 0; for (int j = 0; j < n+2; j+=2) for (int i = 1; i < m; i *= 3) c += 4; (a) 𝛩(1). (b) 𝛩(𝑛 log 𝑚). (c) 𝛩(𝑚 log 𝑛). b (d) Ninguna de las anteriores. ⑤òž!. 2. Para calcular el mínimo de los valores de un vector de tamaño 𝑛 que contiene números enteros perte- necientes al intervalo [1..1000]: (a) Un algoritmo eficiente ordena el vector y obtiene el elemento en la posición 0. (b) Se puede calcular utilizando divide y vencerás con una complejidad 𝛩(log 𝑛). (c) La mejor complejidad que se puede obtener es del orden 𝛩(𝑛). (d) Si el vector es vacío el mínimo es siempre 0. ⑤òž!. c 3. Dada la especificación {𝑛 = longitud(𝑣)} fun foo(int 𝑣[], int 𝑛) dev int 𝑟 {𝑟 = max 𝑝, 𝑞 ∶ 0 ≤ 𝑝 ≤ 𝑞 ≤ 𝑛 ∧ ∀𝑖 ∶ 𝑝 ≤ 𝑖 < 𝑞 − 1 ∶ 𝑣[𝑖 + 1] = 𝑣[𝑖] + 1 ∶ 𝑞 − 𝑝} y el vector de entrada 𝑣 = [5, 1, 2, 4, 6, 7, 8, 9, 10, 12, 11, 0], ¿cuál es el valor de 𝑟 según la especificación? (a) 𝑟 = 4. (b) 𝑟 = 7. (c) 𝑟 = 5. (d) Ninguna de las anteriores. ⑤ò!. c 4. ¿Cuál de los siguientes predicados especifica que un vector 𝑎 de 𝑛 elementos está ordenado de forma creciente? (a) ∃𝑤 ∶ 0 ≤ 𝑤 < 𝑛 − 1 ∶ 𝑎[𝑤] ≤ 𝑎[𝑤 + 1]. (b) ∀𝑤 ∶ 0 ≤ 𝑤 < 𝑛 − 1 ∶ 𝑎[𝑤] ≤ 𝑎[𝑤 + 1]. (c) ∀𝑤 ∶ 0 ≤ 𝑤 < 𝑛 ∶ 𝑎[𝑤] ≤ 𝑎[𝑤 + 1]. (d) Ninguna de las anteriores. b ⑤òž!. 1  5. Indica cuál de las propiedades es un invariante del siguiente bucle: int y=1; int j=n; while (j>0) { y=y*x; j--; } (a) 𝑦 = 𝑥𝑗. (b) 𝑦 = 𝑥𝑛−𝑗. (c) 0 < 𝑗 ≤ 𝑛. (d) Ninguna. ⑤òž!. b 6. Indica cuál de las siguientes respuestas no es correcta respecto al algoritmo de búsqueda binaria que comprueba si un valor se encuentra en una secuencia de valores. (a) La búsqueda binaria en un vector ordenado siempre es más eficiente que la búsqueda secuencial para secuencias de valores grandes. (b) El algoritmo de búsqueda binaria solo se puede aplicar sobre secuencias de valores ordenadas. (c) Si la secuencia de valores no está ordenada es más eficiente ordenarla y buscar el elemento con búsqueda binaria que realizar una búsqueda secuencial. (d) La búsqueda binaria sobre un vector vacío siempre devuelve como resultado false. ⑤òž!. c 7. Dados dos algoritmos 𝐴 y 𝐵 con órdenes de complejidad 𝛩(𝑓 (𝑛)) y 𝛩(𝑔(𝑛)) respectivamente, si 𝛩(𝑓 (𝑛)) ⊂ 𝛩(𝑔(𝑛)): (a) El algoritmo 𝐴 siempre tiene un tiempo de ejecución mayor que el algoritmo 𝐵, independientemente del tamaño de entrada. (b) El algoritmo 𝐴 siempre tiene un tiempo de ejecución menor que el algoritmo 𝐵 independientemente del tamaño de entrada. (c) El algoritmo 𝐴 tiene un tiempo de ejecución menor que el algoritmo 𝐵 solo para tamaños de entrada grandes. (d) El tamaño de entrada a partir del cual el algoritmo 𝐴 tiene un tiempo de ejecución menor que el algoritmo 𝐵 depende de la constante multiplicativa del algoritmo. ⑱ d 8. Indica el coste de un algoritmo cuya recurrencia es: 𝑐0 si 𝑛 = 0 𝑇(𝑛) = { 2𝑇(𝑛/2) + 𝑛 si 𝑛 > 0 (a) O(𝑛2 ). (b) O(𝑛 log 𝑛). (c) O(𝑛). (d) Ninguna. ⑤òž!. b 9. Un algoritmo que obtiene las combinaciones de 𝑘 elementos que pueden formarse con 𝑛 elementos diferentes utilizando la técnica de vuelta atrás tiene complejidad: (a) 𝛩(𝑛). (b) 𝛩(𝑛 ∗ 𝑘). (c) 𝛩(𝑛𝑘 ). (d) 𝛩(𝑘 𝑛 ). c ⑤òž!. 10. El orden en el que se recorren las ramas del árbol de exploración en un algoritmo de vuelta atrás influye en las podas que se realizan y por lo tanto en el tiempo de ejecución del algoritmo: (a) Nunca. (b) Siempre. (c) Nunca podría influir en los problemas de optimización. d (d) Solo podría influir en los problemas de optimización. ⑤òž!. 2  Fundamentos de Algoritmia Examen de junio Curso 2021/2022 Nombre:................................................................................................ Observaciones: En el test, para cada pregunta hay una única respuesta correcta. Cada respuesta correcta vale 0,1 puntos y cada respuesta incorrecta resta 0,033 puntos. 1. Si la precondición de un algoritmo es false, ¿qué afirmación es correcta? (a) Cualquier postcondición será válida. (b) Si se ejecuta el algoritmo dicha ejecución no terminará. (c) Si se ejecuta el algoritmo se producirá un error en tiempo de ejecución. ⑤òž!. a (d) Ninguna postcondición será válida. 2. Indica cuál de las siguientes afirmaciones es incorrecta: (a) 𝑂(log 𝑛) ⊂ 𝑂(𝑛). (b) 𝑂(2𝑛 ) ⊂ 𝑂(𝑛2 ). (c) 2 ∈ 𝑂(1). b ⑤ò!. (d) 𝑛 log(𝑛) ∈ 𝑂(𝑛2 ). 3. Indica la complejidad del siguiente algoritmo: int c = 0; for (int i = 0; i < n; i += 2) c += 1; for (int j = 0; j < n ; ++j) c += 3; (a) 𝛩(log 𝑛). (b) 𝛩(𝑛). (c) 𝛩(𝑛2 ). ⑤òž!. b (d) Ninguna de las anteriores. 4. ¿Qué significa el siguiente predicado para un vector no vacío de naturales? ∀𝑖 ∶ 1 ≤ 𝑖 < 𝑣.size() ∶ 𝑣[𝑖 − 1] ≠ 𝑣[𝑖] (a) Todos los valores del vector son diferentes. (b) No existen dos valores iguales en el vector. (c) Los valores del vector están ordenados en orden creciente. ⑤òž!. d (d) Ninguna de las anteriores. 1 5. Dada la especificación {0 ≤ 𝑎.𝑠𝑖𝑧𝑒} fun contarImpares(vector 𝑎) dev (int 𝑐) {𝑐 = #𝑖 ∶ 0 ≤ 𝑖 < 𝑎.𝑠𝑖𝑧𝑒 ∶ 𝑎[𝑖] % 2 = 1} y el siguiente algoritmo: int contarImPares(std::vector const& a) { int c = 0; int k = a.size()-1; while (k >= 0) { if (a[k] % 2 == 1) {c = c + 1;} k = k - 1; } return c; } indica si el algoritmo es correcto con respecto a la especificación y en tal caso cuál es el invariante que permite demostrar la corrección del bucle. (a) Es correcto con invariante {−1 ≤ 𝑘 < 𝑎.𝑠𝑖𝑧𝑒 ∧ 𝑐 = #𝑖 ∶ 0 ≤ 𝑖 < 𝑘 ∶ 𝑎[𝑖] % 2 = 1}. (b) Es correcto con invariante {−1 ≤ 𝑘 ≤ 𝑎.𝑠𝑖𝑧𝑒 ∧ 𝑐 = #𝑖 ∶ 𝑘 ≤ 𝑖 < 𝑎.𝑠𝑖𝑧𝑒 ∶ 𝑎[𝑖] % 2 = 1}. (c) Es correcto con invariante {−1 ≤ 𝑘 ≤ 𝑎.𝑠𝑖𝑧𝑒 ∧ 𝑐 = #𝑖 ∶ 𝑘 < 𝑖 < 𝑎.𝑠𝑖𝑧𝑒 ∶ 𝑎[𝑖] % 2 = 1}. ⑤òž!. c (d) Ninguna de las anteriores. 6. Indica cuál de las siguientes propiedades sobre los órdenes de complejidad no es correcta, siendo 𝑓 y 𝑔 funciones de coste cualesquiera: (a) O(𝑓 + 𝑔) = O(max(𝑓 , 𝑔)). (b) O(𝑐.𝑓 ) = 𝑐.O(𝑓 ) (c) O(log𝑎 𝑓 ) = O(log𝑏 𝑓 ) d ⑤òž!. (d) Ninguna de las anteriores. 7. Indica cuál es una función de cota para este algoritmo: {x > 0 } int i = x; while (i >= 0) { if (i%2 == 1) {i = i + 1;} i = i - 1; {𝑖%2 = 1} } (a) 𝑖 + 1 (b) 𝑥 + 𝑖 (c) 𝑚𝑎𝑥(0, 𝑖 − 1) (d) Ninguna de las anteriores. ⑤òž!. d 8. Dados los algoritmos de búsqueda lineal y de búsqueda binaria, indica cual de las siguientes afirma- ciones es cierta (𝑛 indica el número de elementos del vector en que se realiza la búsqueda): (a) Ambos algoritmos tienen el mismo orden de complejidad en el caso peor. (b) El algoritmo de búsqueda lineal tiene coste O(1) y el de búsqueda binaria 𝑂(log(𝑛)). d (c) Ambos algoritmos se pueden aplicar sobre los mismos vectores de entrada. ⑤òž!. (d) Ninguna de las anteriores. 2  9. La siguiente especificación: 𝑃 ∶ 𝑣.𝑠𝑖𝑧𝑒 ≥ 0 ∧ 𝑣 = 𝑉 void f (vector v) 𝑄 ∶ ∀𝑘 ∶ 0 ≤ 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 − 1 ∶ 𝑣[𝑘] ≤ 𝑣[𝑘 + 1] ∧ 𝑝𝑒𝑟𝑚𝑢𝑡𝑎𝑐𝑖𝑜𝑛(𝑣, 𝑉) siendo el predicado 𝑝𝑒𝑟𝑚𝑢𝑡𝑎𝑐𝑖𝑜𝑛(𝑣, 𝑤) ≡ 𝑣.𝑠𝑖𝑧𝑒() = 𝑤.𝑠𝑖𝑧𝑒() ∧ ∀𝑘 ∶ 0 ≤ 𝑘 < 𝑣.𝑠𝑖𝑧𝑒() ∶ (#𝑥 ∶ 0 ≤ 𝑥 < 𝑣.𝑠𝑖𝑧𝑒() ∶ 𝑣[𝑥] = 𝑣[𝑘]) = (#𝑥 ∶ 0 ≤ 𝑥 < 𝑣.𝑠𝑖𝑧𝑒() ∶ 𝑤[𝑥] = 𝑣[𝑘]) Se puede implementar con el siguiente algoritmo (a) Algoritmo quicksort o de ordenación rápida. (b) Algoritmo de partición. (c) Algoritmo de búsqueda binaria. ⑤òž!. a (d) Ninguna de las anteriores. 10. Indica el coste de un algoritmo cuya recurrencia es: 𝑐0 𝑛≤2 𝑇(𝑛) = { 𝑇(𝑛/2) + 𝑐1 𝑖𝑓 𝑛>2 if (a) O(log 𝑛) (b) O(𝑛) (c) O(𝑛 log 𝑛) ⑤òž!. a (d) O(𝑛2 ) 1 2 3 4 5 6 7 8 9 10 3 10/1/25, 8:00 Repaso test general: Revisión del intento | CVUCM-Moodle CVEX1 Comenzado el viernes, 20 de diciembre de 2024, 08:43 Estado Finalizado Finalizado en viernes, 20 de diciembre de 2024, 09:03 Tiempo empleado 19 minutos 51 segundos Calificación 4,67 de 10,00 (46,67%) Pregunta 1 Correcta Se puntúa 1,00 sobre 1,00 Indica la complejidad del siguiente algoritmo int f(int n, int m){ int z = 0; for (int i = -10; i v[j]%10) j-- ; i++; } Seleccione una: a. 𝑛−𝑖+1 Cierto. La variable 𝑗 empieza en 𝑛 y disminuye en algunas ocasiones, mientras que la variable 𝑖 aumenta desde el. valor 0 en cada iteración del bucle. En el caso peor, la 𝑗 no disminuye nunca por lo que el bucle para cuando 𝑖 = 𝑗 = 𝑛 , por lo tanto la expresión 𝑛 − 𝑖 + 1 es una cota válida b. 𝑛 − 𝑗 + 1. c. 𝑛 − 𝑖 − 5. d. Ninguna de las anteriores. a. Cierto. La variable 𝑗 empieza en 𝑛 y disminuye en algunas ocasiones, mientras que la variable 𝑖 aumenta desde el valor 0 en cada iteración del bucle. En el caso peor, la 𝑗 no disminuye nunca por lo que el bucle para cuando 𝑖 = 𝑗 = 𝑛, por lo tanto la expresión 𝑛 − 𝑖 + 1 es una cota válida b. Falso. La variable j no decrece en todas las iteraciones, depende de los valores del vector 𝑣. Además, para que la expresión sea una función de cota válida, debe decrecer en cada iteración y esto no está garantizado. Por ello no puede ser una función de cota. c. Falso. Si 𝑛 ≤ 4, el valor inicial de i es 0, y esta expresión comienza siendo negativa, por lo que no es una cota válida d. Falso. La respuesta correcta es: 𝑛 − 𝑖 + 1. La respuesta correcta es: 𝑛 − 𝑖 + 1. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=872802&cmid=154968 2/10 10/1/25, 8:00 Repaso test general: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 3 Incorrecta Se puntúa -0,33 sobre 1,00 Tenemos la siguiente función con su especificación: 𝑃: {0 ≤ 𝑘 ≤ 𝑛 < 𝑣.𝑠𝑖𝑧𝑒 ( ) } int f(const vector& v, const int k, const int n) 𝑄: {#𝑎, 𝑏: 0 ≤ 𝑎 < 𝑏 ≤ 𝑛 ∧ 𝑏 − 𝑎 + 1 = 𝑘: 𝑆 ( 𝑣, 𝑎, 𝑏 ) } donde, 𝑆 ( 𝑣, 𝑎, 𝑏 ) = ∀𝑗: 𝑎 ≤ 𝑗 < 𝑏: 𝑣[𝑗] ≤ 𝑣[𝑗 + 1]. ¿Cuál de las siguientes combinaciones de parámetros de entrada y salida satisfacen esta especificiación? Seleccione una: a. Llamada 𝑓 ( [3, 3, 4, 5], 3, 4 ) con resultado 2 b. Llamada 𝑓 ( [1, 2, 3, 4, 5], 1, 3 ) con resultado 4 c. Llamada 𝑓 ( [1, 1, 9, 0, 3, 4, 4], 2, 5 ) con resultado 4 d. Ninguna de las anteriores.  Falso. La respuesta correcta es: Llamada 𝑓 ( [1, 1, 9, 0, 3, 4, 4], 2, 5 ) con resultado 4 a. Falso. Para que la entrada cumpla la precondición los valores k y n deben cumplir que son mayores o iguales que 0 y ser menores que v.size(). En este caso tenemos 0 ≤ 3 ≤ 4𝑜𝑡 < 4. La llamada es incorrecta puesto que no cumple la precondición. b. Falso. Para que la entrada cumpla la precondición los valores k y n deben cumplir que son mayores o iguales que 0 y ser menores que v.size(). En este caso se cumple 0 ≤ 1 ≤ 3 < 5. Por otro lado, la postcondición indica que el resultado es el número de intervalos [a, b] tales que 3 = 𝑛 ≥ 𝑏 > 𝑎 ≥ 0 de longitud 𝑘 = 1 (𝑏 − 𝑎 + 1 = 1). No hay valores posibles para 𝑎 y 𝑏 que cumplan estas condiciones porque para que sea un intervalo de longitud 1 deben ser 𝑎 = 𝑏 y se obliga que 𝑎 < 𝑏. Por ello la cantidad de intervalos es 0 y no 4. Es resultado no cumple la postcondición. c. Cierto. Para que la entrada cumpla la precondición los valores k y n deben cumplir que son mayores o iguales que 0 y ser menores que v.size(). En este caso se cumple 0 ≤ 2 ≤ 5 < 7. Por otro lado, la postcondición indica que el resultado es el número de intervalos [a, b] con 5 = 𝑛 ≥ 𝑏 > 𝑎 ≥ 0 tales que su longitud es k (𝑏 − 𝑎 + 1 = 𝑘) y en los que los valores del vector son crecientes. Para el vector [1, 1, 9, 0, 3, 4, 4] hay 4 intervalos así. Por ello se cumple también la postcondición d. Falso. La respuesta correcta es: Llamada 𝑓 ( [1, 1, 9, 0, 3, 4, 4], 2, 5 ) con resultado 4 La respuesta correcta es: Llamada 𝑓 ( [1, 1, 9, 0, 3, 4, 4], 2, 5 ) con resultado 4 https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=872802&cmid=154968 3/10 10/1/25, 8:00 Repaso test general: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 4 Correcta Se puntúa 1,00 sobre 1,00 Indica cuál de las siguientes afirmaciones es incorrecta Seleccione una: 𝐥𝐨𝐠 𝑛 a. 𝛺 ( 𝐥𝐨𝐠 𝑛 ) ⊆ 𝛺 ( 𝑛 )  Cierto. Por el teorema del límite, como lim = 0, 𝛺 ( 𝐥𝐨𝐠 𝑛 ) ⊈ 𝛺 ( 𝑛 ). 𝑛→∞ 𝑛 b. 𝛩 ( 𝑛2 ) = 𝛩 ( 2 * 𝑛2 ) c. 𝑂 ( 𝐥𝐨𝐠 𝑛 ) ⊆ 𝑂 ( 𝑛4 ) d. Ninguna de las anteriores. 𝐥𝐨𝐠 𝑛 a. Cierto. Por el teorema del límite, como lim = 0, 𝛺 ( 𝐥𝐨𝐠 𝑛 ) ⊈ 𝛺 ( 𝑛 ). 𝑛→∞ 𝑛 2 * 𝑛2 b. Falso. Por el teorema del límite, como lim = 2, 𝛩 ( 2 * 𝑛2 ) = 𝛩 ( 𝑛2 ). 𝑛 → ∞ 𝑛2 𝑛 4 c. Falso. Por el teorema del límite, como lim = ∞, por lo que 𝑂 ( 𝐥𝐨𝐠 𝑛 ) ⊆ 𝑂 ( 𝑛4 ). 𝑛 → ∞ 𝐥𝐨𝐠 𝑛 d. Falso. La respuesta correcta es: 𝛺 ( 𝐥𝐨𝐠 𝑛 ) ⊆ 𝛺 ( 𝑛 ) La respuesta correcta es: 𝛺 ( 𝐥𝐨𝐠 𝑛 ) ⊆ 𝛺 ( 𝑛 ) https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=872802&cmid=154968 4/10 10/1/25, 8:00 Repaso test general: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 5 Correcta Se puntúa 1,00 sobre 1,00 Dado el siguiente código, 0 < 𝑟 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ) , 0 ≤ 𝑓 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ) y 𝑣 es un vector de enteros que cumple ∀𝑖: 0 ≤ 𝑖 < 𝑟: 𝑣[𝑖] = 0: int n = 0, i = r, j = 0, a = r; while (a < f){ if(v[a]%2 == 0) ++i; else ++j; if(v[a-r] == 0) --i; else --j; if(i < j) ++n; ++a; } ¿Cuál de estas propiedades es un invariante de este bucle? Seleccione una: a. 𝑟≤𝑎v[i]) {i=j;} j=j+1; } return i; indica si el algoritmo es correcto con respecto a la especificación y en tal caso cuál es el invariante que permite demostrar la corrección del bucle. Seleccione una: a. Es correcto con invariante 0 ≤ 𝑖 < 𝑗 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 0 ≤ 𝑘 < 𝑗: 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 0 ≤ 𝑙 < 𝑖: 𝑣[𝑙] < 𝑣[𝑖] ). b. Es correcto con invariante 0 ≤ 𝑖 < 𝑗 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑙: 0 ≤ 𝑙 < 𝑖: 𝑣[𝑙] < 𝑣[𝑖] ). c. Es correcto con invariante 0 ≤ 𝑖 < 𝑗 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 0 ≤ 𝑘 < 𝑗: 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 0 ≤ 𝑙 < 𝑖: 𝑣[𝑙] < 𝑣[𝑖] ).  Cierto. d. Ninguna de las anteriores. a. Falso. El último valor de j es v.size() por lo que debería ser 0 ≤ 𝑖 < 𝑗 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ). b. Falso. Este invariante no permite demostrar la parte de la postcondición que dice que i es una posición del máximo de todo vector. Hay que añadir ( ∀𝑘: 0 ≤ 𝑘 < 𝑗: 𝑣[𝑘] ≤ 𝑣[𝑖] ). c. Cierto. d. Falso. La respuesta correcta es: Es correcto con invariante 0 ≤ 𝑖 < 𝑗 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 0 ≤ 𝑘 < 𝑗: 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 0 ≤ 𝑙 < 𝑖: 𝑣[𝑙] < 𝑣[𝑖] ). La respuesta correcta es: Es correcto con invariante 0 ≤ 𝑖 < 𝑗 ≤ 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 0 ≤ 𝑘 < 𝑗: 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 0 ≤ 𝑙 < 𝑖: 𝑣[𝑙] < 𝑣[𝑖] ). https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=750784&cmid=150524 5/10 10/1/25, 7:57 Tema 3: Diseño y análisis de algoritmos iterativos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 5 Incorrecta Se puntúa -0,33 sobre 1,00 Indica cuál de las siguientes es una función de cota para este bucle: int i=0; bool encontrado=false; while (i0) {encontrado=true;} else {i=i+1;} } Seleccione una: a. Ninguna de ellas. b. 𝑖 + 1 c. 𝑛−𝑖+1  Incorrecta. La variable 𝑖 no siempre se incrementa, por lo que 𝑛 − 𝑖 + 1 no decrece en todas las vueltas del bucle. d. 𝑖 a. Correcta. Puesto que la variable 𝑖 no se incrementa cuando la variable booleana se hace cierta, una función de cota podría ser: 𝑛 − 𝑖 + ( 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑜?0: 1 ). Dicha función decrece estrictamente en aquellas vueltas en las que 𝑖 se incrementa en 1. También decrece estrictamente cuando 𝑖 no crece, ya que en ese caso encontrado se hace cierto y la función pasa de valer 𝑛 − 𝑖 + 1 a 𝑛 − 𝑖. b. Incorrecta. La variable 𝑖 no decrece en cada vuelta. c. Incorrecta. La variable 𝑖 no siempre se incrementa, por lo que 𝑛 − 𝑖 + 1 no decrece en todas las vueltas del bucle. d. Incorrecta. La variable 𝑖 no decrece en cada vuelta. La respuesta correcta es: Ninguna de ellas. Pregunta 6 Correcta Se puntúa 1,00 sobre 1,00 La precondición más débil en: {??} int x=0; int y=1/x; {𝐭𝐫𝐮𝐞} es 𝐟𝐚𝐥𝐬𝐞. Seleccione una: a. Verdadero  b. Falso Verdadero. Para que la segunda asignación esté bien definida es necesario que 𝑥 ≠ 0, pero la instrucción anterior le asigna el valor 0. Al hacer la sustitución, el predicado 0 ≠ 0 equivale a 𝐟𝐚𝐥𝐬𝐞. La respuesta correcta es: Verdadero https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=750784&cmid=150524 6/10 10/1/25, 7:57 Tema 3: Diseño y análisis de algoritmos iterativos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 7 Correcta Se puntúa 1,00 sobre 1,00 Dada la siguiente especificación {𝑣.𝑠𝑖𝑧𝑒 ( ) > 0} fun ultimoMaximo(vector v) dev (int i) {0 ≤ 𝑖 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 0 ≤ 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 𝑖 < 𝑙 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑙] < 𝑣[𝑖] ) } y el siguiente algoritmo como cuerpo de la función i=v.size()-1; int j=v.size()-2; while (j >= 0){ if (v[j]>v[i]) {i=j;} j=j-1; } return i; indica si el algoritmo es correcto con respecto a la especificación y en tal caso cual es el invariante que permite demostrar la corrección del bucle. Seleccione una: a. Es correcto con invariante  Cierto. −1 ≤ 𝑗 < 𝑖 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 𝑗 < 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 𝑖 < 𝑙 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑙] < 𝑣[𝑖] ). b. Es correcto con invariante −1 ≤ 𝑗 < 𝑖 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 𝑗 ≤ 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 𝑖 < 𝑙 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑙] < 𝑣[𝑖] ). c. Es correcto con invariante −1 ≤ 𝑗 < 𝑖 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 𝑗 < 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑘] ≤ 𝑣[𝑖] ). d. Ninguna de las anteriores. a. Cierto. b. Falso. Este invariante está mal definido cuando 𝑗 = − 1. c. Falso. Este invariante no garantiza la parte de la postcondición que dice que 𝑖 es la última posición del máximo del vector. Hay que añadir ( ∀𝑙: 𝑖 < 𝑙 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑙] < 𝑣[𝑖] ). d. Falso. La respuesta correcta es: Es correcto con invariante −1 ≤ 𝑗 < 𝑖 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 𝑗 < 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 𝑖 < 𝑙 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑙] < 𝑣[𝑖] ). La respuesta correcta es: Es correcto con invariante −1 ≤ 𝑗 < 𝑖 < 𝑣.𝑠𝑖𝑧𝑒 ( ) ∧ ( ∀𝑘: 𝑗 < 𝑘 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑘] ≤ 𝑣[𝑖] ) ∧ ( ∀𝑙: 𝑖 < 𝑙 < 𝑣.𝑠𝑖𝑧𝑒 ( ) : 𝑣[𝑙] < 𝑣[𝑖] ). https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=750784&cmid=150524 7/10 10/1/25, 7:57 Tema 3: Diseño y análisis de algoritmos iterativos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 8 Incorrecta Se puntúa -0,33 sobre 1,00 Dada la siguiente especificación: {0 < 𝑛 ≤ 𝑙𝑜𝑛𝑔𝑖𝑡𝑢𝑑 ( 𝑎 ) } fun maximo(int a[ ], int n) dev (int m) {𝑚 = max 𝑖: 0 ≤ 𝑖 < 𝑛: 𝑎[𝑖]} y el siguiente invariante: {0 ≤ 𝑘 < 𝑛 ∧ 𝑚 = max 𝑖: 𝑘 ≤ 𝑖 < 𝑛: 𝑎[𝑖] } indica qué expresiones colocar en lugar de los ? para que el siguiente algoritmo sea correcto con respecto a la especificación dada y el bucle tenga como invariante el indicado: k=? ; m=?; while (?) { if (m=0) b. Inicialización: k=n-1;m=a[n-1]; Condición del while: (k>0) c. Inicialización: k=n;m=a[n-1]; Condición del while: (k>1)  Falso. Según el invariante 𝑘 no puede tomar el valor 𝑛. d. Ninguna de las anteriores. a. Falso. Según el invariante 𝑘 no puede tomar el valor 𝑛. b. Cierto. Si 𝑘 vale 𝑛 − 1 inicialmente, el máximo está bien definido, siendo 𝑖 = 𝑛 − 1 el único índice en el rango, por lo que 𝑚 ha de valer 𝑎[𝑛 − 1]. c. Falso. Según el invariante 𝑘 no puede tomar el valor 𝑛. d. Falso. La respuesta correcta es: Inicialización: k=n-1;m=a[n-1]; Condición del while: (k>0) La respuesta correcta es: Inicialización: k=n-1;m=a[n-1]; Condición del while: (k>0) https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=750784&cmid=150524 8/10 10/1/25, 7:57 Tema 3: Diseño y análisis de algoritmos iterativos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 9 Correcta Se puntúa 1,00 sobre 1,00 Indica cuál es la precondición más débil: {??} x = y; y = x; {𝑥 = 3 ∧ 𝑦 = 4} Seleccione una: a. 𝐟𝐚𝐥𝐬𝐞  Cierto. Al sustituir en la postcondición y por x y luego x por y se obtiene 𝑦 = 3 ∧ 𝑦 = 4. b. 𝑦 = 𝑥 c. 𝑦≠𝑥 d. Ninguna de las anteriores. a. Cierto. Al sustituir en la postcondición y por x y luego x por y se obtiene 𝑦 = 3 ∧ 𝑦 = 4. b. Falso. Al sustituir en la postcondición y por x y luego x por y se obtiene 𝑦 = 3 ∧ 𝑦 = 4, así que la precondición más débil es 𝐟𝐚𝐥𝐬𝐞. c. Falso. Al sustituir en la postcondición y por x y luego x por y se obtiene 𝑦 = 3 ∧ 𝑦 = 4, así que la precondición más débil es 𝐟𝐚𝐥𝐬𝐞. d. Falso. La respuesta correcta es: 𝐟𝐚𝐥𝐬𝐞 La respuesta correcta es: 𝐟𝐚𝐥𝐬𝐞 https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=750784&cmid=150524 9/10 10/1/25, 7:57 Tema 3: Diseño y análisis de algoritmos iterativos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 10 Correcta Se puntúa 1,00 sobre 1,00 Dada la siguiente especificación {0 ≤ 𝑛 ≤ 𝑙𝑜𝑛𝑔𝑖𝑡𝑢𝑑 ( 𝑣 ) } fun numProd (int v[ ], int n) dev (int l) {𝑙 = #𝑖: 0 ≤ 𝑖 < 𝑛: 𝑣[𝑖] = ( 𝛱𝑗: 0 ≤ 𝑗 < 𝑖: 𝑣[𝑗] ) } Se ha escrito el siguiente fragmento de código como cuerpo de dicha función: int k=0, p=1; l=0; while (kb) { m = mcd(a-b,b);} else {m=mcd(a,b-a);} return m; } Seleccione una: a. Recursión múltiple. b. Recursión  Cierto. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y es final porque el lineal final. resultado de la llamada recursiva en cada alternativa es el resultado de la función. c. Ninguna de las anteriores. a. Falso. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y por tanto cada invocación a la función genera una sola llamada recursiva. b. Cierto. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y es final porque el resultado de la llamada recursiva en cada alternativa es el resultado de la función. c. Falso. La respuesta correcta es: Recursión lineal final. La respuesta correcta es: Recursión lineal final. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 1/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 2 Parcialmente correcta Se puntúa 0,25 sobre 1,00 La generalización es una técnica que se utiliza para: Seleccione una o más de una: a. Diseñar algoritmos recursivos. b. Obtener versiones recursivas finales de funciones recursivas lineales no finales. c. Mejorar la eficiencia de los  Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la algoritmos recursivos. eficiencia de los algoritmos recursivos. d. Disponer de funciones más generales que la que se deseaba. a. Correcta. Añadir parámetros adicionales permite definir recursivamente algunos algoritmos, por ejemplo la búsqueda binaria o los métodos de ordenación quicksort y mergesort en los que se añade como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo. b. Correcta. Generar versiones recursivas finales a partir de versiones no finales requiere añadir un parámetro adicional acumulador. c. Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la eficiencia de los algoritmos recursivos. d. Correcta. Añadir parámetros adicionales permite disponer de versiones más generales, por ejemplo en los métodos de ordenación quicksort y mergesort, el hecho de añadir como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo nos permite ordenar un segmento cualquiera del vector y en particular todo el vector. Las respuestas correctas son: Diseñar algoritmos recursivos., Obtener versiones recursivas finales de funciones recursivas lineales no finales., Mejorar la eficiencia de los algoritmos recursivos., Disponer de funciones más generales que la que se deseaba. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 2/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 3 Correcta Se puntúa 1,00 sobre 1,00 ¿En qué casos no termina este algoritmo recursivo ? int f(int x) { int resultado; if (x==0) {resultado=0;} else {resultado = f(x-2);} return resultado; } Seleccione una: a. Solo en los positivos impares. b. Solamente en los números  Cierto. No termina en los números positivos impares, ya que al restar dos en cada llamada negativos y en los positivos recursiva no se alcanza el caso base 0. Tampoco en los enteros negativos. impares. c. Solo en los positivos pares d. Ninguna de las anteriores. a. Falso. Tampoco termina en los números negativos. b. Cierto. No termina en los números positivos impares, ya que al restar dos en cada llamada recursiva no se alcanza el caso base 0. Tampoco en los enteros negativos. c. Falso. En los positivos pares sí termina. d. Falso. La respuesta correcta es: Solamente en los números negativos y en los positivos impares. La respuesta correcta es: Solamente en los números negativos y en los positivos impares. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 3/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 4 Correcta Se puntúa 1,00 sobre 1,00 Indica a qué orden de complejidad pertenece 𝑇 ( 𝑛 ) definida por la recurrencia: 𝑇 ( 𝑛 ) = 𝑐0 si 𝑛 ≤ 1 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 si 𝑛 > 1 Seleccione una: a. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 )  Cierto. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). b. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝐥𝐨𝐠 𝑛 ) c. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝑛 𝐥𝐨𝐠 𝑛 ) d. Ninguna de las anteriores. a. Cierto. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). b. Falso. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). Por tanto 𝑇 ( 𝑛 ) i̸𝑛𝑂 ( 𝐥𝐨𝐠 𝑛 ) \not in O(\textbf{log } n). c. Falso. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). Por tanto 𝑇 ( 𝑛 ) i̸𝑛𝑂 ( 𝑛 𝐥𝐨𝐠 𝑛 ) \not in O( n\ \textbf{log } n). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 4/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 5 Incorrecta Se puntúa -0,33 sobre 1,00 Indica cuál es la afirmación correcta acerca de este algoritmo de búsqueda binaria en el que la precondición es 0 ≤ 𝑐 ≤ 𝑓 + 1 ≤ 𝑙𝑜𝑛𝑔𝑖𝑡𝑢𝑑 ( 𝑣 ) : int f(int v[], int x, int c, int f) { int resultado; if (c>f) {resultado = c-1;} else { int m = (c+f)/2; if (v[m] > x) {resultado = f(v,x,c,m);} else {resultado = f(v,x,m,f);} } return resultado; } Seleccione una: a. Solo termina si 𝑐 < 𝑓. b. Nunca termina. c. Solo termina si 𝑐 > 𝑓. d. Ninguna de las anteriores.  Falso. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. a. Falso. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. b. Falso. En los casos en que 𝑐 > 𝑓 el algoritmo termina. c. Cierto. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. d. Falso. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 5/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 6 Incorrecta Se puntúa -0,33 sobre 1,00 El caso mejor del algoritmo quicksort que usa el primer elemento del segmento como pivote y la fase de partición reparte los elementos en menores o iguales y mayores o iguales, se da cuando: Seleccione una: a. El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. b. Los  Falso. El caso en que los elementos ya están ordenados es uno de los casos peores porque genera una única elementos ya llamada recursiva con todos los elementos excepto el pivote. El coste en este caso está en 𝑂 ( 𝑛2 ) , siendo n el están número de elementos del array. ordenados. c. El último elemento es la mediana del array. d. Ninguna de las anteriores. a. Cierto. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. Esto sucede por ejemplo en este array: 4,1,3,2,6,5,7. b. Falso. El caso en que los elementos ya están ordenados es uno de los casos peores porque genera una única llamada recursiva con todos los elementos excepto el pivote. El coste en este caso está en 𝑂 ( 𝑛2 ) , siendo n el número de elementos del array. c. Falso. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. d. Falso. La respuesta correcta es: El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. La respuesta correcta es: El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. Pregunta 7 Incorrecta Se puntúa -0,33 sobre 1,00 En los algoritmos recursivos en los que se reduce el tamaño del problema por sustracción: 𝑇 ( 𝑛 ) = 𝑐0 si 0 ≤ 𝑛 ≤ 𝑛0 𝑇 ( 𝑛 ) = 𝑎𝑇 ( 𝑛 − 𝑏 ) + 𝑐𝑛𝑘 si 𝑛 > 𝑛0 Seleccione una: a. Si 𝑎 = 1 el coste es logarítmico. b. Si a>1, es siempre exponencial por muy grande que sea b. c. Para que sea polinómico es necesario que b>a. d. Ninguna de las anteriores.  Falso. La respuesta correcta es: Si a>1, es siempre exponencial por muy grande que sea b. a. Falso. En caso de que 𝑎 = 1 el coste está en 𝛩 ( 𝑛𝑘 + 1 ) , no es logarítmico sino polinómico. b. Cierto. En caso de que 𝑎 > 1 el coste está en 𝛩 ( 𝑎𝑛/𝑏 ) , y es por tanto exponencial independientemente del valor de b. c. Falso. Para que sea polinómico es necesario que a=1, independientemente del valor de b. d. Falso. La respuesta correcta es: Si a>1, es siempre exponencial por muy grande que sea b. La respuesta correcta es: Si a>1, es siempre exponencial por muy grande que sea b. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 6/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 8 Incorrecta Se puntúa -0,33 sobre 1,00 Dada la siguiente recurrencia, indica la respuesta correcta: 𝑇 ( 𝑛 ) = 3𝑛2 si 𝑛 ≤ 1 𝑇 ( 𝑛 ) = 3𝑇 ( 𝑛/2 ) + 𝑛2 si 𝑛 > 1 Seleccione una: a. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) b. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛 ) c. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛𝐥𝐨𝐠23 ) d. Ninguna de las anteriores.  Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) a. Cierto. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛 ). b. Falso. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛 ). c. Falso. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛𝐥𝐨𝐠23 ). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) Pregunta 9 Incorrecta Se puntúa -0,33 sobre 1,00 Indica cual de las siguientes recurrencias representa el coste del algoritmo mergesort: Seleccione una: a. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 b. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 − 1 ) + 𝑐′ si 𝑛 > 1 c. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 − 1 ) + 𝑐′𝑛 si 𝑛 > 1 d. Ninguna de las anteriores.  Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 a. Cierto. En cada llamada a la función se general dos llamadas recursivas de la mitad de tamaño y se invierte un coste lineal en el tamaño del segmento para realizar la mezcla. b. Falso. El tamaño de las llamadas recursivas es la mitad del tamaño de la llamada original, debería ser 2𝑇 ( 𝑛/2 ) , no 2𝑇 ( 𝑛 − 1 ). El coste adicional a las llamadas recursivas, que se debe fundamentalmente al algoritmo de mezcla, es lineal en el tamaño del problema n=f- c+1, no constante. Debería ser 𝑐′𝑛. c. Falso. El tamaño de las llamadas recursivas es la mitad del tamaño de la llamada original, debería ser 2𝑇 ( 𝑛/2 ) , no 2𝑇 ( 𝑛 − 1 ). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 7/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 10 Correcta Se puntúa 1,00 sobre 1,00 Indica la menor función 𝑓 ( 𝑛 ) que cumple que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝑓 ( 𝑛 ) ) : 𝑇(1) = 1 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑛 si 𝑛 > 1 Seleccione una: a. 𝐥𝐨𝐠 𝑛 b. 𝑛3 c. 𝑛 𝐥𝐨𝐠 𝑛 d. Ninguna de las anteriores.  Cierto. La respuesta correcta es: 𝑛2 a. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝐥𝐨𝐠 𝑛 ). b. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛3 ). c. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛 𝐥𝐨𝐠 𝑛 ). d. Cierto. La respuesta correcta es: 𝑛2 La respuesta correcta es: Ninguna de las anteriores. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813958&cmid=150525 8/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Comenzado el viernes, 15 de noviembre de 2024, 13:44 Estado Finalizado Finalizado en viernes, 15 de noviembre de 2024, 13:45 Tiempo empleado 1 minutos 2 segundos Calificación 2,75 de 10,00 (27,5%) Pregunta 1 Sin contestar Se puntúa como 0 sobre 1,00 En los algoritmos recursivos en los que se reduce el tamaño del problema por sustracción: 𝑇 ( 𝑛 ) = 𝑐0 si 0 ≤ 𝑛 ≤ 𝑛0 𝑇 ( 𝑛 ) = 𝑎𝑇 ( 𝑛 − 𝑏 ) + 𝑐𝑛𝑘 si 𝑛 > 𝑛0 Seleccione una: a. Si 𝑎 = 1, el coste es lineal. b. Para que sea polinómico es necesario que b>a. c. El coste siempre es polinómico. d. Ninguna de las anteriores. a. Falso. En caso de que 𝑎 = 1 el coste está en 𝛩 ( 𝑛𝑘 + 1 ). Por tanto si 𝑘 > 0 no es lineal. b. Falso. Para que sea polinómico es necesario que a=1, independientemente del valor de b. c. Falso. En caso de que 𝑎 > 1 el coste está en 𝛩 ( 𝑎𝑛/𝑏 ) , y es por tanto exponencial. d. Cierto. La respuesta correcta es: Si a>1, es siempre exponencial por muy grande que sea b. La respuesta correcta es: Ninguna de las anteriores. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 1/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 2 Sin contestar Se puntúa como 0 sobre 1,00 Dada la siguiente recurrencia, indica la respuesta correcta: 𝑇 ( 𝑛 ) = 3𝑛2 si 𝑛 ≤ 1 𝑇 ( 𝑛 ) = 3𝑇 ( 𝑛/2 ) + 𝑛2 si 𝑛 > 1 Seleccione una: a. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 𝐥𝐨𝐠 𝑛 ) b. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) c. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛𝐥𝐨𝐠23 ) d. Ninguna de las anteriores. a. Falso. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛2 𝐥𝐨𝐠 𝑛 ). b. Cierto. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛 ). c. Falso. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛𝐥𝐨𝐠23 ). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) Pregunta 3 Correcta Se puntúa 1,00 sobre 1,00 El caso mejor del algoritmo quicksort que usa el primer elemento del segmento como pivote y la fase de partición reparte los elementos en menores o iguales y mayores o iguales, se da cuando: Seleccione una: a. Los elementos están ordenados a la inversa. b. Los elementos ya están ordenados. c. El primer elemento de  Cierto. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como cada segmento con el que pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas se realiza una llamada es recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. Esto sucede la mediana del mismo. por ejemplo en este array: 4,1,3,2,6,5,7. d. Ninguna de las anteriores. a. Falso. El caso en que los elementos están ordenados a la inversa es uno de los casos peores porque genera una única llamada recursiva con todos los elementos excepto el pivote. El coste en este caso está en 𝑂 ( 𝑛2 ) , siendo n el número de elementos del array. b. Falso. El caso en que los elementos ya están ordenados es uno de los casos peores porque genera una única llamada recursiva con todos los elementos excepto el pivote. El coste en este caso está en 𝑂 ( 𝑛2 ) , siendo n el número de elementos del array. c. Cierto. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. Esto sucede por ejemplo en este array: 4,1,3,2,6,5,7. d. Falso. La respuesta correcta es: El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. La respuesta correcta es: El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 2/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 4 Sin contestar Se puntúa como 0 sobre 1,00 Indica la menor función 𝑓 ( 𝑛 ) que cumple que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝑓 ( 𝑛 ) ) : 𝑇(1) = 1 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑛 si 𝑛 > 1 Seleccione una: a. 2𝑛 b. 𝐥𝐨𝐠 𝑛 c. 𝑛2 d. Ninguna de las anteriores. a. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 2𝑛 ). b. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝐥𝐨𝐠 𝑛 ). c. Cierto. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ). d. Falso. La respuesta correcta es: 𝑛2 La respuesta correcta es: 𝑛2 https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 3/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 5 Correcta Se puntúa 1,00 sobre 1,00 Indica cuál es la afirmación correcta acerca de este algoritmo de búsqueda binaria en el que la precondición es 0 ≤ 𝑐 ≤ 𝑓 + 1 ≤ 𝑙𝑜𝑛𝑔𝑖𝑡𝑢𝑑 ( 𝑣 ) : int f(int v[], int x, int c, int f) { int resultado; if (c>f) {resultado = c-1;} else { int m = (c+f)/2; if (v[m] > x) {resultado = f(v,x,c,m);} else {resultado = f(v,x,m,f);} } return resultado; } Seleccione una: a. Los únicos casos en que no termina son cuando 𝑓 = 𝑐. b. Solo termina si 𝑐 < 𝑓. c. Solo  Cierto. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por termina tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un si 𝑐 > 𝑓 caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita.. d. Ninguna de las anteriores. a. Falso. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. b. Falso. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. c. Cierto. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. d. Falso. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 4/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 6 Sin contestar Se puntúa como 0 sobre 1,00 Indica cual de las siguientes recurrencias representa el coste del algoritmo mergesort: Seleccione una: a. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′ si 𝑛 > 1 b. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 − 1 ) + 𝑐′𝑛 si 𝑛 > 1 c. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 d. Ninguna de las anteriores. a. Falso. El coste adicional a las llamadas recursivas, que se debe fundamentalmente al algoritmo de mezcla, es lineal en el tamaño del problema n=f-c+1, no constante. Debería ser 𝑐′𝑛, no 𝑐′. b. Falso. El tamaño de las llamadas recursivas es la mitad del tamaño de la llamada original, debería ser 2𝑇 ( 𝑛/2 ) , no 2𝑇 ( 𝑛 − 1 ). c. Cierto. En cada llamada a la función se general dos llamadas recursivas de la mitad de tamaño y se invierte un coste lineal en el tamaño del segmento para realizar la mezcla. d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 Pregunta 7 Parcialmente correcta Se puntúa 0,25 sobre 1,00 La generalización es una técnica que se utiliza para: Seleccione una o más de una: a. Disponer de funciones más generales que la que se deseaba. b. Diseñar algoritmos recursivos. c. Mejorar la eficiencia de los  Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la algoritmos recursivos. eficiencia de los algoritmos recursivos. d. Obtener versiones recursivas finales de funciones recursivas lineales no finales. a. Correcta. Añadir parámetros adicionales permite disponer de versiones más generales, por ejemplo en los métodos de ordenación quicksort y mergesort, el hecho de añadir como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo nos permite ordenar un segmento cualquiera del vector y en particular todo el vector. b. Correcta. Añadir parámetros adicionales permite definir recursivamente algunos algoritmos, por ejemplo la búsqueda binaria o los métodos de ordenación quicksort y mergesort en los que se añade como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo. c. Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la eficiencia de los algoritmos recursivos. d. Correcta. Generar versiones recursivas finales a partir de versiones no finales requiere añadir un parámetro adicional acumulador. Las respuestas correctas son: Disponer de funciones más generales que la que se deseaba., Diseñar algoritmos recursivos., Mejorar la eficiencia de los algoritmos recursivos., Obtener versiones recursivas finales de funciones recursivas lineales no finales. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 5/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 8 Incorrecta Se puntúa -0,50 sobre 1,00 ¿Qué tipo de recursión es la de esta función? int mcd(int a, int b) { int m; if (a==b) { m = a;} else if (a>b) { m = mcd(a-b,b);} else {m=mcd(a,b-a);} return m; } Seleccione una: a. Recursión lineal no  Falso. Se trata de recursión lineal final, ya que el resultado de la llamada recursiva en cada alternativa es el final. resultado de la función. b. Recursión múltiple. c. Ninguna de las anteriores. a. Falso. Se trata de recursión lineal final, ya que el resultado de la llamada recursiva en cada alternativa es el resultado de la función. b. Falso. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y por tanto cada invocación a la función genera una sola llamada recursiva. c. Cierto. La respuesta correcta es: Recursión lineal final. La respuesta correcta es: Ninguna de las anteriores. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 6/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 9 Sin contestar Se puntúa como 0 sobre 1,00 Indica a qué orden de complejidad pertenece 𝑇 ( 𝑛 ) definida por la recurrencia: 𝑇 ( 𝑛 ) = 𝑐0 si 𝑛 ≤ 1 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 si 𝑛 > 1 Seleccione una: a. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝐥𝐨𝐠 𝑛 ) b. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) c. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝑛2 ) d. Ninguna de las anteriores. a. Falso. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). Por tanto 𝑇 ( 𝑛 ) i̸𝑛𝑂 ( 𝐥𝐨𝐠 𝑛 ) \not in O(\textbf{log } n). b. Cierto. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). c. Falso. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). Por tanto 𝑇 ( 𝑛 ) i̸𝑛𝑂 ( 𝑛2 ) \not in O( n^2). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 7/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 10 Correcta Se puntúa 1,00 sobre 1,00 ¿En qué casos no termina este algoritmo recursivo ? int f(int x) { int resultado; if (x==0) {resultado=0;} else {resultado = f(x-2);} return resultado; } Seleccione una: a. No termina en ningún caso. b. Solamente en los números  Cierto. No termina en los números positivos impares, ya que al restar dos en cada llamada negativos y en los positivos recursiva no se alcanza el caso base 0. Tampoco en los enteros negativos. impares. c. Siempre termina, pues el argumento de la llamada decrece. d. Ninguna de las anteriores. a. Falso. Sí termina en los números positivos pares. b. Cierto. No termina en los números positivos impares, ya que al restar dos en cada llamada recursiva no se alcanza el caso base 0. Tampoco en los enteros negativos. c. Falso. No siempre termina, por ejemplo en los números negativos al restar dos en cada llamada recursiva no se alcanza el caso base 0. d. Falso. La respuesta correcta es: Solamente en los números negativos y en los positivos impares. La respuesta correcta es: Solamente en los números negativos y en los positivos impares. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813967&cmid=150525 8/8 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Comenzado el viernes, 15 de noviembre de 2024, 13:46 Estado Finalizado Finalizado en viernes, 15 de noviembre de 2024, 13:46 Tiempo empleado 48 segundos Calificación 4,75 de 10,00 (47,5%) Pregunta 1 Sin contestar Se puntúa como 0 sobre 1,00 Indica a qué orden de complejidad pertenece 𝑇 ( 𝑛 ) definida por la recurrencia: 𝑇 ( 𝑛 ) = 𝑐0 si 𝑛 ≤ 1 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 si 𝑛 > 1 Seleccione una: a. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) b. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝑛2 ) c. 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝐥𝐨𝐠 𝑛 ) d. Ninguna de las anteriores. a. Cierto. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). b. Falso. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). Por tanto 𝑇 ( 𝑛 ) i̸𝑛𝑂 ( 𝑛2 ) \not in O( n^2). c. Falso. Puesto que 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≤ 2𝑇 ( 𝑛 − 1 ) + 𝑐1 , aplicando el teorema de la división con a=2, b=1, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ). Análogamente, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑇 ( 𝑛 − 2 ) + 𝑐1 ≥ 2𝑇 ( 𝑛 − 2 ) + 𝑐1 y aplicando el teorema de la división con a=2, b=2, k=0, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛺 ( 2𝑛/2 ). Por tanto 𝑇 ( 𝑛 ) i̸𝑛𝑂 ( 𝐥𝐨𝐠 𝑛 ) \not in O(\textbf{log } n). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝑂 ( 2𝑛 ) https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 1/7 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 2 Correcta Se puntúa 1,00 sobre 1,00 El caso mejor del algoritmo quicksort que usa el primer elemento del segmento como pivote y la fase de partición reparte los elementos en menores o iguales y mayores o iguales, se da cuando: Seleccione una: a. El último elemento es la mediana del array. b. Los elementos están ordenados a la inversa. c. El primer elemento de  Cierto. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como cada segmento con el que pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas se realiza una llamada es recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. Esto sucede la mediana del mismo. por ejemplo en este array: 4,1,3,2,6,5,7. d. Ninguna de las anteriores. a. Falso. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. b. Falso. El caso en que los elementos están ordenados a la inversa es uno de los casos peores porque genera una única llamada recursiva con todos los elementos excepto el pivote. El coste en este caso está en 𝑂 ( 𝑛2 ) , siendo n el número de elementos del array. c. Cierto. El caso mejor se da cuando en cada llamada recursiva, el primer elemento que se usa como pivote queda colocado en la mitad del segmento después de la partición generando dos llamadas recursivas de la mitad de tamaño, y eso sucede cuando es la mediana del segmento. Esto sucede por ejemplo en este array: 4,1,3,2,6,5,7. d. Falso. La respuesta correcta es: El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. La respuesta correcta es: El primer elemento de cada segmento con el que se realiza una llamada es la mediana del mismo. Pregunta 3 Sin contestar Se puntúa como 0 sobre 1,00 Indica cual de las siguientes recurrencias representa el coste del algoritmo mergesort: Seleccione una: a. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′ si 𝑛 > 1 b. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 c. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 − 1 ) + 𝑐′ si 𝑛 > 1 d. Ninguna de las anteriores. a. Falso. El coste adicional a las llamadas recursivas, que se debe fundamentalmente al algoritmo de mezcla, es lineal en el tamaño del problema n=f-c+1, no constante. Debería ser 𝑐′𝑛, no 𝑐′. b. Falso. En cada llamada a la función se general dos llamadas recursivas de la mitad de tamaño, así que debería ser 2𝑇 ( 𝑛/2 ). c. Falso. El tamaño de las llamadas recursivas es la mitad del tamaño de la llamada original, debería ser 2𝑇 ( 𝑛/2 ) , no 2𝑇 ( 𝑛 − 1 ). El coste adicional a las llamadas recursivas, que se debe fundamentalmente al algoritmo de mezcla, es lineal en el tamaño del problema n=f- c+1, no constante. Debería ser 𝑐′𝑛. d. Cierto. La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 La respuesta correcta es: Ninguna de las anteriores. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 2/7 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 4 Sin contestar Se puntúa como 0 sobre 1,00 Indica la menor función 𝑓 ( 𝑛 ) que cumple que 𝑇 ( 𝑛 ) ∈ 𝑂 ( 𝑓 ( 𝑛 ) ) : 𝑇(1) = 1 𝑇 ( 𝑛 ) = 𝑇 ( 𝑛 − 1 ) + 𝑛 si 𝑛 > 1 Seleccione una: a. 2𝑛 b. 𝑛2 c. 𝑛3 d. Ninguna de las anteriores. a. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 2𝑛 ). b. Cierto. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ). c. Falso. Aplicando el teorema de la resta con a=1, b=1 y k=1, tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛3 ). d. Falso. La respuesta correcta es: 𝑛2 La respuesta correcta es: 𝑛2 Pregunta 5 Correcta Se puntúa 1,00 sobre 1,00 ¿Qué tipo de recursión es la de esta función? int mcd(int a, int b) { int m; if (a==b) { m = a;} else if (a>b) { m = mcd(a-b,b);} else {m=mcd(a,b-a);} return m; } Seleccione una: a. Recursión  Cierto. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y es final porque el lineal final. resultado de la llamada recursiva en cada alternativa es el resultado de la función. b. Recursión múltiple. c. Ninguna de las anteriores. a. Cierto. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y es final porque el resultado de la llamada recursiva en cada alternativa es el resultado de la función. b. Falso. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y por tanto cada invocación a la función genera una sola llamada recursiva. c. Falso. La respuesta correcta es: Recursión lineal final. La respuesta correcta es: Recursión lineal final. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 3/7 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 6 Sin contestar Se puntúa como 0 sobre 1,00 Dada la siguiente recurrencia, indica la respuesta correcta: 𝑇 ( 𝑛 ) = 3𝑛2 si 𝑛 ≤ 1 𝑇 ( 𝑛 ) = 3𝑇 ( 𝑛/2 ) + 𝑛2 si 𝑛 > 1 Seleccione una: a. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛𝐥𝐨𝐠23 ) b. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) c. 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 𝐥𝐨𝐠 𝑛 ) d. Ninguna de las anteriores. a. Falso. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛𝐥𝐨𝐠23 ). b. Cierto. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛 ). c. Falso. Aplicando el teorema de la división con a=3, b=2 y k=2, como 3 < 22 tenemos que 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) ≠ 𝛩 ( 𝑛2 𝐥𝐨𝐠 𝑛 ). d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) La respuesta correcta es: 𝑇 ( 𝑛 ) ∈ 𝛩 ( 𝑛2 ) Pregunta 7 Correcta Se puntúa 1,00 sobre 1,00 ¿En qué casos no termina este algoritmo recursivo ? int f(int x) { int resultado; if (x==0) {resultado=0;} else {resultado = f(x-2);} return resultado; } Seleccione una: a. Solo en los números negativos. b. No termina en ningún caso. c. Solamente en los números  Cierto. No termina en los números positivos impares, ya que al restar dos en cada llamada negativos y en los positivos recursiva no se alcanza el caso base 0. Tampoco en los enteros negativos. impares. d. Ninguna de las anteriores. a. Falso. Tampoco termina en los números positivos impares, ya que al restar dos en cada llamada recursiva no se alcanza el caso base 0. b. Falso. Sí termina en los números positivos pares. c. Cierto. No termina en los números positivos impares, ya que al restar dos en cada llamada recursiva no se alcanza el caso base 0. Tampoco en los enteros negativos. d. Falso. La respuesta correcta es: Solamente en los números negativos y en los positivos impares. La respuesta correcta es: Solamente en los números negativos y en los positivos impares. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 4/7 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 8 Parcialmente correcta Se puntúa 0,75 sobre 1,00 La generalización es una técnica que se utiliza para: Seleccione una o más de una: a. Mejorar la eficiencia de los  Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la algoritmos recursivos. eficiencia de los algoritmos recursivos. b. Disponer de  Correcta. Añadir parámetros adicionales permite disponer de versiones más generales, por ejemplo en los funciones más métodos de ordenación quicksort y mergesort, el hecho de añadir como parámetros adicionales los extremos generales que del segmento del vector en que actúa el algoritmo nos permite ordenar un segmento cualquiera del vector y la que se en particular todo el vector. deseaba. c. Diseñar  Correcta. Añadir parámetros adicionales permite definir recursivamente algunos algoritmos, por ejemplo la algoritmos búsqueda binaria o los métodos de ordenación quicksort y mergesort en los que se añade como parámetros recursivos. adicionales los extremos del segmento del vector en que actúa el algoritmo. d. Obtener versiones recursivas finales de funciones recursivas lineales no finales. a. Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la eficiencia de los algoritmos recursivos. b. Correcta. Añadir parámetros adicionales permite disponer de versiones más generales, por ejemplo en los métodos de ordenación quicksort y mergesort, el hecho de añadir como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo nos permite ordenar un segmento cualquiera del vector y en particular todo el vector. c. Correcta. Añadir parámetros adicionales permite definir recursivamente algunos algoritmos, por ejemplo la búsqueda binaria o los métodos de ordenación quicksort y mergesort en los que se añade como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo. d. Correcta. Generar versiones recursivas finales a partir de versiones no finales requiere añadir un parámetro adicional acumulador. Las respuestas correctas son: Mejorar la eficiencia de los algoritmos recursivos., Disponer de funciones más generales que la que se deseaba., Diseñar algoritmos recursivos., Obtener versiones recursivas finales de funciones recursivas lineales no finales. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 5/7 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 9 Sin contestar Se puntúa como 0 sobre 1,00 En los algoritmos recursivos en los que se reduce el tamaño del problema por sustracción: 𝑇 ( 𝑛 ) = 𝑐0 si 0 ≤ 𝑛 ≤ 𝑛0 𝑇 ( 𝑛 ) = 𝑎𝑇 ( 𝑛 − 𝑏 ) + 𝑐𝑛𝑘 si 𝑛 > 𝑛0 Seleccione una: a. Si a>1, es siempre exponencial por muy grande que sea b. b. Si 𝑎 = 1 el coste es logarítmico. c. El coste siempre es exponencial. d. Ninguna de las anteriores. a. Cierto. En caso de que 𝑎 > 1 el coste está en 𝛩 ( 𝑎𝑛/𝑏 ) , y es por tanto exponencial independientemente del valor de b. b. Falso. En caso de que 𝑎 = 1 el coste está en 𝛩 ( 𝑛𝑘 + 1 ) , no es logarítmico sino polinómico. c. Falso. En caso de que 𝑎 = 1 el coste está en 𝛩 ( 𝑛𝑘 + 1 ) , y es por tanto polinómico. d. Falso. La respuesta correcta es: Si a>1, es siempre exponencial por muy grande que sea b. La respuesta correcta es: Si a>1, es siempre exponencial por muy grande que sea b. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 6/7 10/1/25, 7:57 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 10 Correcta Se puntúa 1,00 sobre 1,00 Indica cuál es la afirmación correcta acerca de este algoritmo de búsqueda binaria en el que la precondición es 0 ≤ 𝑐 ≤ 𝑓 + 1 ≤ 𝑙𝑜𝑛𝑔𝑖𝑡𝑢𝑑 ( 𝑣 ) : int f(int v[], int x, int c, int f) { int resultado; if (c>f) {resultado = c-1;} else { int m = (c+f)/2; if (v[m] > x) {resultado = f(v,x,c,m);} else {resultado = f(v,x,m,f);} } return resultado; } Seleccione una: a. Nunca termina. b. Siempre termina. c. Solo  Cierto. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por termina tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un si 𝑐 > 𝑓 caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita.. d. Ninguna de las anteriores. a. Falso. En los casos en que 𝑐 > 𝑓 el algoritmo termina. b. Falso. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. c. Cierto. El algoritmo no termina en todos aquellos casos en los que 𝑐 ≤ 𝑓. El punto medio cumple 𝑐 ≤ 𝑚 ≤ 𝑓 y por tanto las llamadas recursivas (con c,m y m,f) de nuevo cumplen que 𝑐 ≤ 𝑓. Luego, si inicialmente 𝑐 ≤ 𝑓 se llegará a un caso base en el que 𝑐 = 𝑚 = 𝑓, que repetidamente se invocará a sí mismo, generando una recursión infinita. d. Falso. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. La respuesta correcta es: Solo termina si 𝑐 > 𝑓. https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813969&cmid=150525 7/7 10/1/25, 7:58 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Comenzado el viernes, 15 de noviembre de 2024, 13:51 Estado Finalizado Finalizado en viernes, 15 de noviembre de 2024, 14:08 Tiempo empleado 17 minutos 24 segundos Calificación 0,00 de 10,00 (0%) Pregunta 1 Sin contestar Se puntúa como 0 sobre 1,00 Indica cual de las siguientes recurrencias representa el coste del algoritmo mergesort: Seleccione una: a. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 − 1 ) + 𝑐′𝑛 si 𝑛 > 1 b. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 − 1 ) + 𝑐′ si 𝑛 > 1 c. 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 d. Ninguna de las anteriores. a. Falso. El tamaño de las llamadas recursivas es la mitad del tamaño de la llamada original, debería ser 2𝑇 ( 𝑛/2 ) , no 2𝑇 ( 𝑛 − 1 ). b. Falso. El tamaño de las llamadas recursivas es la mitad del tamaño de la llamada original, debería ser 2𝑇 ( 𝑛/2 ) , no 2𝑇 ( 𝑛 − 1 ). El coste adicional a las llamadas recursivas, que se debe fundamentalmente al algoritmo de mezcla, es lineal en el tamaño del problema n=f- c+1, no constante. Debería ser 𝑐′𝑛. c. Cierto. En cada llamada a la función se general dos llamadas recursivas de la mitad de tamaño y se invierte un coste lineal en el tamaño del segmento para realizar la mezcla. d. Falso. La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 La respuesta correcta es: 𝑇 ( 𝑛 ) = 𝑐 si 𝑛 ≤ 1, 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛/2 ) + 𝑐′𝑛 si 𝑛 > 1 https://cvex1.ucm.es/moodle/mod/quiz/review.php?attempt=813973&cmid=150525 1/7 10/1/25, 7:58 Tema 4: Diseño y análisis de algoritmos recursivos: Revisión del intento | CVUCM-Moodle CVEX1 Pregunta 2 Sin contestar Se puntúa como 0 sobre 1,00 La generalización es una técnica que se utiliza para: Seleccione una o más de una: a. Obtener versiones recursivas finales de funciones recursivas lineales no finales. b. Mejorar la eficiencia de los algoritmos recursivos. c. Diseñar algoritmos recursivos. d. Disponer de funciones más generales que la que se deseaba. a. Correcta. Generar versiones recursivas finales a partir de versiones no finales requiere añadir un parámetro adicional acumulador. b. Correcta. Añadir parámetros y/o resultados adicionales puede ayudar a mejorar la eficiencia de los algoritmos recursivos. c. Correcta. Añadir parámetros adicionales permite definir recursivamente algunos algoritmos, por ejemplo la búsqueda binaria o los métodos de ordenación quicksort y mergesort en los que se añade como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo. d. Correcta. Añadir parámetros adicionales permite disponer de versiones más generales, por ejemplo en los métodos de ordenación quicksort y mergesort, el hecho de añadir como parámetros adicionales los extremos del segmento del vector en que actúa el algoritmo nos permite ordenar un segmento cualquiera del vector y en particular todo el vector. Las respuestas correctas son: Obtener versiones recursivas finales de funciones recursivas lineales no finales., Mejorar la eficiencia de los algoritmos recursivos., Diseñar algoritmos recursivos., Disponer de funciones más generales que la que se deseaba. Pregunta 3 Sin contestar Se puntúa como 0 sobre 1,00 ¿Qué tipo de recursión es la de esta función? int mcd(int a, int b) { int m; if (a==b) { m = a;} else if (a>b) { m = mcd(a-b,b);} else {m=mcd(a,b-a);} return m; } Seleccione una: a. Recursión lineal final. b. Recursión múltiple. c. Ninguna de las anteriores. a. Cierto. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y es final porque el resultado de la llamada recursiva en cada alternativa es el resultado de la función. b. Falso. Se trata de recursión lineal porque en cada alternativa hay una única llamada recursiva y por tanto cada invocación a la función genera una sola llamada recursiva.