Javier Correa Santos
Quiz by , created more than 1 year ago

Quiz on Analisis y diseño de algoritmos, created by Javier Correa Santos on 01/07/2015.

355
1
0
Javier Correa Santos
Created by Javier Correa Santos over 9 years ago
Close

Analisis y diseño de algoritmos

Question 1 of 57

1

¿Cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int lineal(int n)
{ int resultado = 1;
while(false){ resultado = resultado * n;
} return resultado;

Select one of the following:

  • O(1)

  • O(log n)

  • O(n2)

  • O(n log n)

Explanation

Question 2 of 57

1

¿Qué devuelve el siguiente algoritmo recursivo?
static int metodoRecurH(int n)
{ if (n < 10) return n;
else return (n % 10) + metodoRecurH(n / 10); }

Select one of the following:

  • El múltiplo de 10 más cercano a n

  • La suma de los dígitos de n

  • El menor múltiplo de 10 que divide a n

  • La cantidad de dígitos de n

  • El mayor múltiplo de 10 que divide a n

Explanation

Question 3 of 57

1

¿Cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int metodoH(int n)
{ int resultado = 0; int i = 1;
while (i <= n) { for (int f = n; f > 0; f--)
{ resultado = resultado + (i * i * i) + (f * f * f); } i++; }
return resultado; }

Select one of the following:

  • O(n)

  • o(n2)

  • O(log n)

  • O(n log n)

Explanation

Question 4 of 57

1

Teniendo en cuenta la regla del máximo, el orden que más se ajusta
T(n )=5 \sqrt n + 23\log n + 3n \log n

Select one of the following:

  • O(5\sqrt n)

  • O(nlogn)

  • O(log n)

  • O(n2)

Explanation

Question 5 of 57

1

Responde Verdadero o Falso a la siguiente afirmación: "Una operación elemental es aquella cuyo tiempo de ejecución puede acotarse inferiormente por una constante que solo dependerá de la implementación particular usada."

Select one of the following:

  • True
  • False

Explanation

Question 6 of 57

1

El orden que más se ajusta al tiempo de ejecución en el caso peor del Ordenamiento por Selección es:

Select one of the following:

  • o(n2)

  • o(n)

  • o(2n)

  • o(nlogn)

Explanation

Question 7 of 57

1

Teniendo en cuenta la regla del máximo, el orden que más se ajusta
T(n )=5nsqrt n + 23\log n + 3n log n

Select one of the following:

  • O(nsqrt n + nlog n)

  • O(nsqrt n)

  • O(n )

  • O(log n)

Explanation

Question 8 of 57

1

El orden que más se ajusta al tiempo de ejecución en el caso peor de la Ordenación por Fusión o Mergesort es:

Select one of the following:

  • O(n2)

  • O(n)

  • O(log n)

  • O( n logn)

Explanation

Question 9 of 57

1

Para demostrar la corrección de un algoritmo es muy importante, en ocasiones, definir el conjunto de casos que deben considerarse, o lo que es lo mismo:

Select one of the following:

  • Su eficiencia en el caso medio

  • Su principio de invarianza

  • Su dominio de definición

  • Su eficiencia en el peor caso

Explanation

Question 10 of 57

1

¿Qué representa el valor devuelto por el algoritmo siguiente?
static int metodoY(int m, int n) {
int i, resul = 1;
if (n < m)
i = n;
else
i = m;
while (i > 1) {
if ((m % i == 0) && (n % i == 0)) {
resul = i;
}
i--;
}
return resul;
}

Select one of the following:

  • El valor primo más cercano a n

  • El máximo común divisor de m y n

  • El resto entero de la división m/n

  • El mínimo valor entre m y n

  • El valor primo más cercano a m

Explanation

Question 11 of 57

1

Diremos que t(n ) está en Omega de f(n ) si t(n ) está acotada inferiormente por un múltiplo real positivo de f(n ) para todo n suficientemente grande. Esta afirmacion es...

Select one of the following:

  • True
  • False

Explanation

Question 12 of 57

1

El orden que más se ajusta al tiempo de ejecución en el caso peor de la Ordenación por Montículo o Heapsort es:

Select one of the following:

  • O(log n)

  • O(n)

  • O(n log n)

  • O(n2)

Explanation

Question 13 of 57

1

¿Cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int cubico(int n) {
return n * n * n;
}

Select one of the following:

  • O(1)

  • O(n)

  • O(n2)

Explanation

Question 14 of 57

1

Asumiendo que n < m, ¿cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int metodoConocido(int m, int n) {
int i;
int out = 1;
if (n < m) {
i = n;
} else {
i = m;
}
while (i > 1) {
if ((m % i == 0) && (n % i == 0)) {
out = i;
}
i--;
}
return out;
}

Select one of the following:

  • Cuadrático, O(n^2)

  • Exponencial, O(2^n)

  • Lineal, O(n )

  • Logarítmico, O(\log n) Incorrecta

Explanation

Question 15 of 57

1

Teniendo en cuenta la regla del máximo, el orden que más se ajusta a T(n )=5 \sqrt n + 23\log n + 3n \log n es:

Select one of the following:

  • O(n log n)

  • O(\sqrt n)

  • O(log n)

  • O(1)

Explanation

Question 16 of 57

1

Teniendo en cuenta la regla del máximo, el orden que más se ajusta a T(n )=5 \sqrt n + 23\log n + 35 es:

Select one of the following:

  • O(sqrt n)

  • O(n)

  • O(log n)

Explanation

Question 17 of 57

1

¿Cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int metodoF(int[] array) {
int resultado = array[0];
int n = array.length;
for (int i = 1; i < n; i++) {
if (array[i] > resultado) {
resultado = array[i];
}
}
return resultado;
}

Select one of the following:

  • O(n)

  • O(n log n)

  • O(log n)

  • O(n2)

Explanation

Question 18 of 57

1

El orden que más se ajusta al tiempo de ejecución en el caso peor del Ordenamiento por Inserción es:

Select one of the following:

  • O(log n)

  • o(n)

  • O(n2)

  • O(2n)

Explanation

Question 19 of 57

1

El principio de invarianza dice que dos implementaciones distintas de un mismo algoritmo (en ordenadores distintos o con distintos lenguajes de programación), no diferirán en su eficiencia más que en una constante multiplicativa.

Select one of the following:

  • True
  • False

Explanation

Question 20 of 57

1

¿Cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int metodoRecurM(int n)
{ if (n == 1) return 1;
else return n * metodoRecurM(n - 1); }

Select one of the following:

  • O(n2)

  • O(n)

  • O(log N)

  • O (n log n)

Explanation

Question 21 of 57

1

En el siguiente algoritmo que devuelve el j-ésimo término de la sucesión de Fibonacci, la instrucción que falta es:
static int Fibonacci(final int j)
{ int n = 1, p = 0;
for (int i = 0; i <= j; i++) {
/** Instrucción faltante */
n = p - n; } return p; }

Select one of the following:

  • p = i + j

  • p = 2 - i

  • p = p + n

  • n = p + n

Explanation

Question 22 of 57

1

¿Qué devuelve el siguiente algoritmo recursivo?
static int metodoRecursivoC(int n) {
if (n < 10) { return 1; }
else { return 1 + metodoRecursivoC(n / 10); } }

Select one of the following:

  • El mayor múltiplo de 10 que divide a n

  • El múltiplo de 10 más cercano a n

  • El menor múltiplo de 10 que divide a n

  • La suma de los dígitos de n

  • La cantidad de dígitos de n

Explanation

Question 23 of 57

1

Un algoritmo requiere un tiempo del orden de t(O(n )) para una función dada t si existe una constante multiplicativa c y una implementación del algoritmo capaz de resolver todos los casos de tamaño n en un tiempo que no sea superior a c*t(O(n )) segundos. A esto se le llama:

Select one of the following:

  • Notación Asintótica

  • Dominio de Definición

  • Computabilidad del Algoritmo

  • Principio de Invarianza

Explanation

Question 24 of 57

1

Aquella instrucción que se ejecuta por lo menos con tanta frecuencia como cualquier instrucción del algoritmo es una instrucción

Select one of the following:

  • clave

  • barómetro

  • termómetro

  • compleja

  • recursiva

Explanation

Question 25 of 57

1

El orden que más se ajusta al tiempo de ejecución en el caso peor del cálculo de determinantes por el método de Gauss-Jordan cuando utilizamos una matriz de n x n es:

Select one of the following:

  • O(n3)

  • O(n2)

  • o(n)

  • O(nlogn)

Explanation

Question 26 of 57

1

¿Cuál es el orden que más se ajusta al tiempo de ejecución en el caso peor del siguiente algoritmo?
static int exponencial(int n) {
int exp = 1;
for (int e = 0; e < n; e++) {
exp = exp * 2;
}
return exp;
}

Select one of the following:

  • O(n)

  • O(n2)

  • O(log n)

Explanation

Question 27 of 57

1

Dentro de un algoritmo voraz, la función de selección es

Select one of the following:

  • La función que comprueba si un cierto conjunto de candidatos es factible.

  • La función que indica en cualquier momento cuál es el elemento más prometedor de los candidatos restantes.

  • La función que da el valor de la solución que se ha intentado optimizar.

  • La función que comprueba si un cierto conjunto de candidatos constituye una solución.

Explanation

Question 28 of 57

1

La técnica en la que simplemente seleccionamos elementos de un conjunto de candidatos para dar solución a un problema, de manera que los candidatos desechados no vuelven a ser considerados y los incorporados a la solución permanecen en ella hasta el final del algoritmo, se conoce como:

Select one of the following:

  • Programación Dinámica

  • Algoritmos voraces

  • Divide y Vencerás

  • Backtracking

Explanation

Question 29 of 57

1

Para recorrer un grafo conexo G podemos seleccionar cualquier nodo v como punto de partida, marcarlo como visitado, y luego visitar todos los nodos adyacentes a v. Solamente cuando no queden nodos
adyacentes a v se procede a visitar nodos más alejados. Este recorrido se conoce como:

Select one of the following:

  • Recorrido en distancia

  • Recorrido en anchura

  • Recorrido por aristas

  • Recorrido en profundidad

Explanation

Question 30 of 57

1

Si concebimos un problema en términos de un grafo, la técnica que realiza una búsqueda ciega en profundidad dentro de dicho grafo, mediante un algoritmo recursivo, se conoce como:

Select one of the following:

  • Algoritmos voraces

  • Divide y Vencerás

  • Programación Dinámica

  • Backtracking

Explanation

Question 31 of 57

1

Si utilizamos un algoritmo voraz para resolver el problema de "devolver cambio en monedas", este algoritmo puede no funcionar adecuadamente si:
A) No existen monedas de un cierto valor
B) El número de monedas de cada valor es limitado
C) El sistema monetario solo tiene monedas de 5 céntimos.
D) El sistema monetario solo tiene monedas de 1 y 5 céntimos.

Select one of the following:

  • A

  • B

  • A y B

  • C y D

Explanation

Question 32 of 57

1

¿Cuáles de las siguientes carácterísticas son propias de los algoritmos voraces?
A) Se utilizan para resolver problemas de optimización.
B) Son fáciles de implementar
C) Permiten resolver correctamente cualquier problema de optimización.
D) En cada paso seleccionan la opción más prometedora de las presentes y reconsideran las selecciones pasadas para mantenerlas o deshacerlas. Seleccione una:

Select one of the following:

  • A

  • B

  • B y D

  • A y B

Explanation

Question 33 of 57

1

Dado un grafo, el algoritmo que encuentra un árbol de recubrimiento mínimo haciéndolo crecer de forma natural desde una raíz arbitraria, y donde en cada fase se añade una nueva rama al árbol ya construido, hasta que se han alcanzado todos los nodos, se conoce como:

Select one of the following:

  • Algoritmo de Kruskal

  • Algoritmo de Euclides

  • Algoritmo de Prim

  • Algoritmo de Dijkstra

Explanation

Question 34 of 57

1

Dentro de un algoritmo voraz, la función de objetivo es

Select one of the following:

  • La función que da el valor de la solución que se ha intentado optimizar.

  • La función que indica en cualquier momento cuál es el elemento más prometedor de los candidatos restantes.

  • La función que comprueba si un cierto conjunto de candidatos constituye una solución.

  • La función que comprueba si un cierto conjunto de candidatos es factible.

Explanation

Question 35 of 57

1

Para recorrer un grafo conexo G podemos seleccionar cualquier nodo v como punto de partida y marcarlo como visitado. Si hay algún nodo adyacente a v, que no haya sido visitado, se invoca recursivamente el procedimiento sobre dicho nodo. Al volver de la llamada recursiva, si hay otro nodo adyacente a v que no haya sido visitado, se vuelve a aplicar el procedimiento. Seguiremos así hasta que no queden nodos sin visitar. Este recorrido se conoce como

Select one of the following:

  • Recorrido en anchura

  • Recorrido en profundidad

Explanation

Question 36 of 57

1

En grafos muy densos el algoritmo de Kruskal es más eficiente que el de Prim. Esta afirmación es:

Select one of the following:

  • True
  • False

Explanation

Question 37 of 57

1

Supongamos que tenemos que pagar cierta cantidad utilizando el menor número posible de monedas. Para resolver el problema empezamos con las manos vacías y vamos añadiendo a las monedas seleccionadas siempre la mayor posible sin sobrepasar la cantidad que nos resta por pagar. Así hasta que no quede nada por pagar. Esta manera de actuar es un ejemplo de:

Select one of the following:

  • Voraces

  • Backtraking

  • Divide y Vencerás

  • Programación dinámica

Explanation

Question 38 of 57

1

Un algoritmo voraz que permite determinar la longitud del camino mínimo desde un nodo de un grafo a cada uno de los demás nodos, es el:

Select one of the following:

  • Algoritmo de Euclides

  • Algoritmo de Dijkstra

  • Algoritmo de Kruskal

  • Algoritmo de Prim

Explanation

Question 39 of 57

1

Los algoritmos de Backtracking suelen recorrer el grafo con las posibles soluciones utilizando un:

Select one of the following:

  • Recorrido en profundidad

  • Recorrido en anchura

Explanation

Question 40 of 57

1

Dado un grafo, el algoritmo que encuentra un árbol de recubrimiento mínimo creando primero un bosque de árboles (varias componentes conexas) y haciéndolo crecer al azar hasta que al final todas las componentes del bosque se fusionan en un único árbol, se conoce como:

Select one of the following:

  • Algoritmo de Prim

  • Algoritmo de Euclides

  • Algoritmo de Kruskal

  • Algoritmo de Dijkstra

Explanation

Question 41 of 57

1

La implementación del algoritmo de Prim ofrecida en el libro de la asignatura es menos eficiente que el algoritmo de Kruskal cuando se trabaja con grafos dispersos. Esta afirmación es:

Select one of the following:

  • True
  • False

Explanation

Question 42 of 57

1

En grafos muy densos el orden del algoritmo de Kruskal es:

Select one of the following:

  • n^2\log n

  • n(\log n^2)

  • n^2

  • n\log n

Explanation

Question 43 of 57

1

La selección de un umbral incorrecto a la hora de aplicar el enfoque Divide y Vencerás puede afectar el orden del algoritmo resultante.

Select one of the following:

  • True
  • False

Explanation

Question 44 of 57

1

Para que sea factible aplicar el enfoque de Divide y Vencerás es importante que:

Select one of the following:

  • Se pueda descomponer el problema original en subproblemas y recomponer las soluciones parciales de forma bastante eficiente.

  • El tamaño del problema original debe ser par, para que se pueda dividir por dos

  • El orden de la parte no recursiva sea lineal o cuadrático.

  • Los subproblemas del problema original sean de distinto tamaño.

Explanation

Question 45 of 57

1

Supongamos que tenemos que pagar cierta cantidad utilizando el menor número posible de monedas. Para resolver el problema utilizamos una tabla con las soluciones más eficientes, donde hay una fila para cada valor de moneda posible y una columna para cada una de las cantidades que van de 0 hasta la cantidad N que tenemos que pagar. La tabla nos permite determinar el menor número de monedas a devolver en base a las solucines almacenadas para menores cantidades de dinero. Esta manera de actuar es un ejemplo de:

Select one of the following:

  • Programación Dinámica

  • Algoritmos voraces

  • Divide y Vencerás

  • Backtracking

Explanation

Question 46 of 57

1

De los siguientes algoritmos de Divide y Vencerás, indica el que constituye un ejemplo de reducción:

Select one of the following:

  • Quicksort

  • Búsqueda de la Mediana

  • Búsqueda Binaria

  • Ordenación por fusión

Explanation

Question 47 of 57

1

El algoritmo de ordenación que divide el vector en dos partes (de tamaño lo más parecido posible), ordena recursivamente esas mitades, y luego las mezcla para obtener el vector ordenado, se conoce como

Select one of the following:

  • Ordenación por selección

  • Ordenación por fusión

  • Ordenación por inserción

  • Quicksort

Explanation

Question 48 of 57

1

La técnica que consiste en descomponer el problema en un cierto número de subcasos más pequeños para resolverlos sucesiva e independientemente, y luego combinar todos los resultados para obtener la solución del problema original, se conoce como:

Select one of the following:

  • Algoritmos voraces

  • Backtracking

  • Divide y Vencerás

  • Programación Dinámica

Explanation

Question 49 of 57

1

El algoritmo de ordenación que selecciona como pivote uno de los elementos del vector para crear una partición donde los elementos más pequeños quedan a la izquierda y el resto a la derecha, y luego ambas partes se ordenan recursivamente en sucesivas llamadas, se conoce como:

Select one of the following:

  • Ordenación por inserción

  • Ordenación por selección

  • Ordenación por fusión

  • Quicksort

Explanation

Question 50 of 57

1

La siguiente implementación de Fibonacci se puede ver como un ejemplo de: funcion FibIter ( n)
i:=1; j:=1; para k:=1 hasta n hacer
j := i+j; i := j-i;
devolver j;

Select one of the following:

  • Algoritmos voraces

  • Programación Dinámica

  • Backtracking

  • Divide y Vencerás

Explanation

Question 51 of 57

1

La técnica ascendente que evita realizar dos veces el mismo cálculo, manteniendo una tabla de resultados conocidos que se va rellenando a medida que se resuelven los subcasos, se conoce como:

Select one of the following:

  • Algoritmos voraces

  • Backtracking

  • Divide y Vencerás

  • Programación Dinámica

Explanation

Question 52 of 57

1

Al igual que los algoritmos voraces, la técnica de programación dinámica tampoco reconsidera decisiones previamente descartadas. Esta afirmación es:

Select one of the following:

  • True
  • False

Explanation

Question 53 of 57

1

¿Cuáles de las siguientes carácterísticas son propias de la técnica de "Divide y Vencerás"?
A) Empieza por el caso completo, que luego se va dividiendo en subcasos más y más pequeños a medida que progresa el algoritmo
B) Es una técnica de refinamiento progresivo
C) Empieza por los subcasos más pequeños y sencillos, cuyas soluciones se van combinando para obtener las respuestas de subcasos de tamaños cada vez mayores
D) La posibilidad de aplicar la técnica depende en gran medida del Principio de Optimalidad
E) Es una técnica ascendente.

Select one of the following:

  • C, D y E

  • A y B

  • B y D

  • C y E

Explanation

Question 54 of 57

1

¿Cuáles de las siguientes características son propias de "Programación Dinámica"? A) Empieza por el caso completo, que luego se va dividiendo en subcasos más y más pequeños a medida que progresa el algoritmo. B) Es una técnica de refinamiento progresivo C) Empieza por los subcasos más pequeños y sencillos, cuyas soluciones se van combinando para obtener las respuestas de subcasos de tamaños cada vez mayores. D) La posibilidad de aplicar la técnica depende en gran medida del Principio de Optimalidad E) Es una técnica ascendente

Select one of the following:

  • C, D y E

  • A, B y D

  • C y E

  • A y B

Explanation

Question 55 of 57

1

El algoritmo de ordenación que divide el vector en dos partes (de tamaño lo más parecido posible), ordena recursivamente esas mitades, y luego las mezcla para obtener el vector ordenado, se conoce como

Select one of the following:

  • Ordenación por selección

  • Quicksort

  • Ordenación por inserción

  • Ordenación por fusión

Explanation

Question 56 of 57

1

El algoritmo de ordenación que selecciona como pivote uno de los elementos del vector para crear una partición donde los elementos más pequeños quedan a la izquierda y el resto a la derecha, y luego ambas partes se ordenan recursivamente en sucesivas llamadas, se conoce como

Select one of the following:

  • Ordenación por fusión

  • Ordenación por inserción

  • Ordenación por selección

  • Quicksort

Explanation

Question 57 of 57

1

La implementación de Fibonacci siguiente se puede ver como un ejemplo de: función FibRec( n) si n<2 entonces devolver n sino delvolver FibRec(n-1) + FibRec(n-2)

Select one of the following:

  • Programación Dinámica

  • Algoritmos voraces

  • Backtracking

  • Divide y Vencerás

Explanation

Previous
Next