CREAR TEST

TEST BORRADO, QUIZÁS LE INTERESE: ALG-P1

COMENTARIOS	ESTADÍSTICAS	RÉCORDS

REALIZAR TEST

Título del Test: ALG-P1 Descripción: Algoritmia Primer Parcial Autor: DAM OTROS TESTS DEL AUTOR Fecha de Creación: 21/06/2024 Categoría: Universidad Número Preguntas: 52

COMPARTE EL TEST

COMENTAR

No hay ningún comentario sobre este test.

Temario:

Sea la siguiente relación de recurrencia, ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n^2 g(n) = n g(n) = 1. ¿Pertenece 3n^2 a O(n^3)? Sí, pero sólo si se toma c > 3. No. Ninguna de las otras dos opciones son verdaderas. Las siguientes funciones calculan el valor de la potencia n-ésima de dos. ¿Cuál es más eficiente en cuanto a coste temporal? La primera, pot2_1(n), es más eficiente que la otra. La segunda, pot2_2(n), es más eficiente que la otra. Las dos funciones son equivalentes en cuanto a coste temporal. La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica. Di cuál de las siguientes afirmaciones es FALSA. Si g(n) ∈ Θ(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica. Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal en el mejor caso del algoritmo de ordenación Quicksort. Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Sin tener en cuenta el espacio que ocupa la pila de recursión, ¿cuál es la complejidad espacial del algoritmo Quicksort? O(n) O(1) O(n log n). Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función? Θ(n^2*log2 n) Θ(n^2) Θ(5^log2 n). Si f ∉ O(g1) y f ∈ O(g2) entonces siempre se cumplirá: f ∈ Ω(g1 + g2) f ∉ O(max(g1, g2)) f ∈ Ω(min(g1, g2)). De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. Θ(log2 n) = Θ(log3 n) Θ((log n)^2) = Θ((log n)^3) Θ(log n^2) = Θ(log n^3). Si f ∈ Θ(g1) y f ∈ Θ(g2) entonces: f ∈ Θ(g1 + g2) f ∈ Θ(g1 · g2) f ∉ Θ(max(g1, g2)). Tenemos una lista ordenada de tamaño No y una lista desordenada de tamaño Nd, queremos obtener una lista ordenada con todos los elementos. ¿Cuál sería la complejidad de insertar, uno a uno, todos los elementos de la lista desordenada en la ordenada? O(No · Nd + Nd^2) O(Nd · No) O(Nd log No). La complejidad temporal (o coste temporal asintótico) en el mejor de los casos... Las otras dos opciones son ambas verdaderas. ...es una función de la talla, o tamaño del problema, que tiene que estar definida para todos los posibles valores de ésta. ...es el tiempo que tarda el algoritmo en resolver la talla más pequeña que se le puede presentar. Si f ∉ O(g1) y f ∈ O(g2) entonces solo a veces se cumplirá: f ∈ Ω(min(g1, g2)) f ∈ O(max(g1, g2)) f ∈ Ω(max(g1, g2)). Tenemos un vector desordenado y queremos obtener los tres elementos más pequeños. ¿Cuál sería la complejidad temporal más ajustada para hacerlo? (sin pérdida de generalidad puedes suponer que en el vector todos los elementos son distintos) Cuadrática con la longitud del vector. Lineal con la longitud del vector. El logaritmo de la longitud del vector. De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. O(2^log2 n) ⊂ O(n^2) ⊂ O(n!) O(n^2) ⊂ O(2^log2 n) ⊂ O(2^n) O(4^log2 n) ⊂ O(n) ⊂ O(2^n). Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función? Θ(n^2 log n) Θ(n^2) Θ(n^3). La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica. Di cuál de las siguientes afirmaciones es CIERTA: Si g(n) ∈ O(n) la relación de recurrencia representa la complejidad temporal en el mejor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector (estudiado en clase). Si g(n) ∈ O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación por inserción binaria. Si g(n) ∈ O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica en el peor de los casos. Si f ∈ Θ(g1) y f ∈ Θ(g2) entonces solo a veces se cumplirá: Las otras dos opciones son ambas ciertas. f^2 ∈ Θ(g1 · g2) f ∈ Θ(max(g1, g2)) . Si f(n) ∈ O(n^2), ¿podemos decir siempre que f(n) ∈ O(n^3)? Sí, ya que n^2 ∈ O(n3) No, ya que n^2 ∉ O(n3) Sólo para valores bajos de n. Las siguientes funciones calculan el valor de la potencia n-ésima de dos. ¿Cuál es más eficiente en cuanto a coste temporal? Las dos funciones son equivalentes en cuanto a coste temporal. La primera, pot2_1(n), es más eficiente que la otra. La segunda, pot2_2(n), es más eficiente que la otra. ¿Qué tienen en común los algoritmos de ordenación Quicksort y Mergesort? El número de llamadas recursivas que hacen en el mejor de los casos. La complejidad temporal de la división en subproblemas. La complejidad temporal de la combinación de las soluciones parciales. La complejidad temporal en el mejor de los casos de un algoritmo recursivo... ...coincide con el valor del caso base de la ecuación de recurrencia que expresa la complejidad temporal del algoritmo. ...es la complejidad temporal de las instancias que están en el caso base. ...ninguna de las otras dos opciones es cierta. ¿Cuál de las siguientes relaciones de recurrencia expresa mejor la complejidad espacial del algoritmo Mergesort? T(n) = n + T(n - 1) para n > 1 T(n) = 1 para n <= 1 T(n) = n + 2T(n/2) para n > 1 T(n) = 1 para n <= 1 T(n) = n + T(n/2) para n > 1 T(n) = 1 para n <= 1. Tenemos un vector ordenado de tamaño No y un vector desordenado de tamaño Nd y queremos obtener un vector ordenado con todos los elementos. ¿Qué será más rápido? Insertar los elementos del vector desordenado (uno a uno) en el vector ordenado. Depende de si No > Nd o no. Ordenar el desordenado y luego mezclar las listas. Si f ∉ O(g1) y f ∈ O(g2) entonces siempre se cumplirá: lim (f(n) / g2(n)) = 0 n->inf lim (f(n) / g1(n)) = inf n->inf Las otras dos opciones son ambas ciertas. Si f1(n) ∈ O(g1(n)) y f2(n) ∈ O(g2(n)) entonces... f1(n) + f2(n) ∈ O(g1(n) + g2(n)) Las dos anteriores son ciertas. f1(n) + f2(n) ∈ O(max(g1(n), g2(n))). Si f(n) ∈ O(n^3), ¿puede pasar que f(n) ∈ O(n^2)? Sólo para valores bajos de n. Es perfectamente posible, ya que O(n^2) ⊂ O(n^3). No, porque n^3 ∉ O(n^2). Una de las prácticas de laboratorio consistió en el cálculo empírico de la complejidad temporal promedio del algoritmo de ordenación de vectores Quicksort tomando como centinela el elemento del vector que ocupa la posición central. ¿Cuál es el orden de complejidad que se obtuvo? n (log n)^2 n log n n^2. ¿Qué tiene que valer b en la relación de recurrencia para que T(n) = 2^n? 1 2 Ninguna de las otras dos opciones es correcta. ¿Pertenece 3n^2 a O(n^3)? No. Sí. Solo para c = 6 y No = 1. Si f ∈ Ω(g1) y f ∈ Ω(g2) entonces... f ∈ Ω(g1 · g2) f ∈ Ω(g1 + g2) f ∉ Ω(min(g1, g2)). Si f ∈ Θ(g1) y f ∈ Θ(g2) entonces... f ∈ Θ(g1 · g2) f ∈ Θ(max(g1, g2)) f ∈ Θ(g1 + g2). De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. Θ(log2 n) = Θ(log3 n) Θ((log n)^2) = Θ((log n)^3) log n^3 ∉ Θ(log3 n). Si f ∉ O(g1) y f ∈ O(g2) entonces NO siempre se cumplirá: f ∈ O(max(g1, g2)) f ∈ Ω(g1 + g2) f ∈ Ω(min(g1, g2)). ¿Cuál de los siguientes algoritmos de ordenación necesita un espacio de almacenamiento adicional al vector que se ordena con complejidad O(n)? Quicksort. Mergesort. Bubblesort. Con respecto a la complejidad temporal de la siguiente función, ¿cuál de las siguientes afirmaciones es cierta? La complejidad temporal en el mejor de los casos es constante. Las otras dos afirmaciones son ambas falsas. El coste temporal exacto de la función es O(n). Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función? Θ(n^2 log n) Θ(n^3 log n) Θ(n^3). Sea la siguiente relación de recurrencia, si T(n) = Θ(n^2) ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n g(n) = n^2 g(n) = n^3. ¿Qué nos proporciona la media entre el coste temporal asintótico (o complejidad temporal) en el peor caso y el coste temporal asintótico en el mejor caso? En general, nada de interés. El coste temporal promedio. El coste temporal asintótico en el caso medio. La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica. Di cuál de las siguientes afirmaciones es CIERTA: Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Si g(n) ∈ Θ(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación mediante inserción binaria. Si g(n) ∈ Θ(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica. Si f(n) ∈ Θ(n^2), ¿podemos decir siempre que f(n) ∈ O(n^3)? No, ya que n^2 ∉ O(n^3) Sí, ya que n^2 ∈ Ω(n^3) Sí, ya que n^2 ∈ O(n^3). Se quieren ordenar números distintos comprendidos entre y . Para ello se usa un array de booleanos que se inicializan primero a false. A continuación se recorren los números cambiando los valores del elemento del vector de booleanos correspondiente a su número a true. Por último se recorre el vector de booleanos escribiendo los índices de los elementos del vector de booleanos que son true. ¿Es este algoritmo más rápido (asintóticamente) que el Mergesort? Sólo si d log d > k · n (donde es una constante que depende de la implementación). No, ya que este algoritmo ha de recorrer varias veces el vector de booleanos. Sí, ya que el Mergesort es y este es O(n log n) y este es O(n). Di cuál de estos resultados de coste temporal asintótico es FALSO: La ordenación de un vector usando el algoritmo Mergesort requiere en el peor caso un tiempo en O(n^2). La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo en O(n^2). La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O(log n). De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. O(2^log2 n) ⊆ O(n^2) ⊂ O(n!) O(n^2) ⊂ O(2^log2 n) ⊂ O(2^n) O(4^log2 n) ⊆ O(n^2) ⊂ O(2^n). ¿Qué tiene que valer k en la siguiente relación de recurrencia para que T(n) = n log n? 0 1 log n. ¿Qué se entiende por tamaño del problema? La cantidad de espacio en memoria que se necesita para codificar una instancia de ese problema. El valor máximo que puede tomar una instancia cualquiera de ese problema. El número de parámetros que componen el problema. La relación de recurrencia T(n) = 1 + T(n - 1) si n > 1; T(1) = 1... Expresa la complejidad temporal asintótica en el peor de los casos del algoritmo de búsqueda binaria. Ninguna de las otras dos opciones es cierta. Expresa el número de llamadas recursivas que hace el algoritmo Quicksort en el peor de los casos. De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. O(2^log2 n) ⊆ O(n^2) ⊂ O(2^n) O(n^2) ⊂ O(2^log2 n) ⊂ O(2^n) O(4^log2 n) ⊆ O(n^2) ⊂ O(2^n). Para que la complejidad de un algoritmo presente caso mejor y peor distintos... ...es condición necesaria y suficiente que existan instancias distintas del problema con el mismo tamaño. ...es condición suficiente que existan instancias distintas del problema con el mismo tamaño. ...es condición necesaria que existan instancias distintas del problema con el mismo tamaño. La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica. Di cuál de las siguientes afirmaciones es CIERTA: Si g(n) ∈ O(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Si g(n) ∈ O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación mediante inserción binaria. Si g(n) ∈ O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica. Sea la siguiente relación de recurrencia, ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n^2 g(n) = n log n g(n) = n. ¿En qué caso la complejidad temporal de Quicksort es la misma que la del algoritmo de ordenación por inserción? En el caso mejor. En ningún caso. En el caso peor. ¿Cuál de las siguientes relaciones de recurrencia expresa mejor el número de llamadas recursivas que hace el algoritmo Mergesort? T(n) = 1 + T(n - 1) para n > 1 T(n) = 1 para n <= 1 T(n) = 1 + 2T(n/2) para n > 1 T(n) = 1 para n <= 1 T(n) = n + 2T(n/2) para n > 1 T(n) = 1 para n <= 1.

Denunciar Test