Examen de Complejidad (1/5) PDF

## Examen de Complejidad (1/5) **Comenzado el**: jueves, 4 de julio de 2024, 16:26 **Estado**: Finalizado **Finalizado en**: jueves, 4 de julio de 2024, 16:26 **Tiempo empleado**: 5 segundos **Calificación**: 0,00 de 10,00 (0%) ### Pregunta 1 **Sea A un array ordenado de n enteros que se vuelca e...

## Examen de Complejidad (1/5) **Comenzado el**: jueves, 4 de julio de 2024, 16:26 **Estado**: Finalizado **Finalizado en**: jueves, 4 de julio de 2024, 16:26 **Tiempo empleado**: 5 segundos **Calificación**: 0,00 de 10,00 (0%) ### Pregunta 1 **Sea A un array ordenado de n enteros que se vuelca en un árbol binario ordenado, y sea x un entero a buscar dentro del árbol binario. Entonces, la complejidad de ese algoritmo de búsqueda es:** **Seleccione una:** a. Es independiente del algoritmo de volcado del array. Siempre es logarítmica, pues en una búsqueda en un ABO siempre tenemos una ecuación de recurrencia de la forma T(n)=T(n/2)+1;T(1)=0(1), que al resolverla nos proporciona una complejidad logarítmica. b. Depende del algoritmo de volcado del array. Será lineal A si se vuelca de forma lineal, y logarítmica si se sigue una estrategia divide y vencerás, tomando como pivote A[N/2]. c. Depende del algoritmo de volcado. Será lineal si A se vuelca de forma lineal, y logarítmica si se sigue un algoritmo puro de backtracking para localizar el elemento x dentro del árbol. d. Depende del algoritmo de volcado. Si empieza desde el final será logarítmica y si se empieza desde el principio será lineal. **Respuesta incorrecta.** La respuesta correcta es: Depende del algoritmo de volcado del array. Será lineal A si se vuelca de forma lineal, y logarítmica si se sigue una estrategia divide y vencerás, tomando como pivote A[N/2]. ### Pregunta 2 **Considerando la siguiente función, algoritmo típico de búsqueda en un vector:** ```python módulo pertenece (Les vector de N enteros, x es entero) devuelve entero variables i es entero encontrado es boolean inicio i-0 fin encontrado - falso mientras((i < N)&&(!encontrado )) hacer si L[i] = = x entonces encontrado -cierto si no i-i + 1 finsi finmientras si encontrado entonces retorna i si no finsi retorna 0 ``` **Supongamos que todos los elementos son distintos y que x está en el vector. Entonces, el número medio de comparaciones con elementos del vector es:** **Seleccione una:** a. n b. 1 c. (n+1)/2 d. n/2 **Respuesta incorrecta.** La respuesta correcta es: (n+1)/2 ### Pregunta 3 **Sea A un vector de n elementos y supongamos que todos los elementos de A son distintos. Considera el siguiente algoritmo.** ```python módulo ordena (var A es vector de n enteros); variables i, j, x: es entero for (i = 2; i<=N; i++) { X=A[i]; A[0]=X; j=i-1; (2) while (X<A[j]) { (3) A[j+1]=A[j]; j=j-1 } } A[j+1]=X; finmódulo ``` **Nos interesa medir cuántas veces se ejecuta la instrucción n.º 3. Entonces, el caso mejor se obtiene cuando** **Seleccione una:** a. Los datos vienen dispuestos en orden inverso, que se ejecuta exactamenre n² veces. b. Los datos vienen ordenados ascendentemente, que se ejecuta exactamente n² veces. c. Los datos vienen ordenados ascendentemente, que se ejecuta exactamente 0 veces. d. Los datos vienen dispuestos en orden inverso, que se ejecuta exactamente n - i veces. **Respuesta incorrecta.** La respuesta correcta es: Los datos vienen ordenados ascendentemente, que se ejecuta exactamente 0 veces. ### Pregunta 4 **Considerando el siguiente algoritmo. Si consideramos como medida significativa el número de comparaciones con respecto a los elementos del vector (instrucción nº 2), entonces el algoritmo es:** ```python módulo ordena (var A es vector de n enteros); variables i, j, x: es entero for (i = 2; i<=N; i++) { X=A[i]; A[0]=X; j=i-1; (2) while (X<A[j]) { (3) A[j+1]=A[j]; j = j-1 } } A[j+1]=X; finmódulo ``` **Seleccione una:** a. Ω(1) y O(n²) b. θ(n²) c. Ω(n) y O(n²) d. θ(n) **Respuesta incorrecta.** La respuesta correcta es: Ω(n) y O(n²) ### Pregunta 5 **¿Con qué algoritmo de ordenación clásico se corresponde el pseudocódigo del siguiente ejemplo?** ```python módulo ordena (var A es vector de n enteros); variables i, j, x: es entero for (i = 2; i<=N; i++) { X=A[i]; A[0]=X; j=i-1; (2) while (X<A[j]) { (3) A[j+1]=A[j]; } j = j-1 A[j+1]=X; } finmódulo ``` **Seleccione una:** a. Ordenación por el método de inserción directa. b. Ordenación por el método de la burbuja c. Ordenación por el método de selección directa. d. Ordenación por el método de inserción binaria. **Respuesta incorrecta.** La respuesta correcta es: Ordenación por el método de inserción directa. ### Pregunta 6 **¿Cuál es el orden de complejidad del algoritmo siguiente?** ```python {Q} = {n=N} fun H (n:ent) devuelve (q:ent) var p:ent; p=1; mientras p<100 hacer { ffun n = 2*n; p = p+1; finmientras; q= n div p; dev q {R} = {q = N X 2100 div 100} ``` **Seleccione una:** a. Ω(p) y O(n) b. 0(1) c. θ(n) d. θ(p) **Respuesta incorrecta.** La respuesta correcta es: 0(1) ### Pregunta 7 **Sea V un vector de N elementos y supongamos que todos los elementos de V son distintos. Considera el algoritmo siguiente:** ```python for (i=1; i<N; i++) { (1) X=V[i]; Izq=0; Der=i-1; while (Izq <= Der) { Medio = (Izq+Der)/2; (2) if (X<V[Medio]) Der Medio-1; else } Izq = Medio + 1; } } for(j=i-1; j>=Izq; j--) { (3) V[j+1] = V[j]; V[Izq]=X; ``` **Si tomamos como medida significativa el número de comparaciones con elementos del vector (instrucción 2), entonces el algoritmo tiene un coste:** **Seleccione una:** a. Ω(log(n)) y O(n) b. θ(n) c. O(log(n)) d. (n*log (n)) **Respuesta incorrecta.** La respuesta correcta es: (n*log (n)) ### Pregunta 8 **Considera el siguiente algoritmo:** ```python Ordena (vector V[N] de enteros) int i, j, aux; for (i=1; i < N; i++) { for (j=0; j < N-i; j++) { (2) if (V[j] > V[j+1]) { aux = V[j]; (3) V[j] = V[j+1]; V[j+1] = aux; } } } ``` **Nos interesa medir cuántas veces se ejecuta la instrucción nº 3. Entonces, el caso mejor se obtiene cuando** **Seleccione una:** a. Cuando los datos vienen dispuestos en orden inverso, que se ejecuta del orden de n² veces b. Cuando los datos vienen ordenados ascendentemente, que se ejecuta 0 veces c. Cuando los datos vienen ordenados ascendentemente, que se ejecuta del orden de n² veces d. Cuando los datos vienen ordenados ascendentemente, que se ejecuta del orden de n veces **Respuesta incorrecta.** La respuesta correcta es: Cuando los datos vienen ordenados ascendentemente, que se ejecuta 0 veces ### Pregunta 9 **Considera el algoritmo siguiente. Si consideramos como medida significativa el número de comparaciones con respecto a los elementos del vector (instrucción nº 2), entonces el algoritmo es:** ```python Ordena (vector V[N] de enteros) int i, j, aux; for (i=1; i < N; i++) { for (j=0; j < N-i; j++) { (2) if (V[j] > V[j+1]) { aux = V[j]; (3) V[j] = V[j+1]; V[j+1] = aux; } } } ``` **Seleccione una:** a. θ(η) b. Ω(n) y O(n²) c. θ (п²) d. Ω (1) y O(n²) **Respuesta incorrecta.** La respuesta correcta es: 0 (n²) ### Pregunta 10 **¿Con qué algoritmo de ordenación clásico se corresponde el siguiente pseudocódigo?** ```python Ordena (vector V[N] de enteros) int i, j, aux; for (i=1; i < N; i++) { for (j=0; j < N-i; j++) { (2) if (V[j] > V[j+1]) { aux = V[j]; (3) V[j] = V[j+1]; V[j+1] = aux; } } } ``` **Seleccione una:** a. Ordenación por el método de la burbuja b. Ordenación por el método de inserción directa c. Ordenación por el método de inserción binaria d. Ordenación por el método de selección directa **Respuesta incorrecta.** La respuesta correcta es: Ordenación por el método de la burbuja