¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?
La solución tiene l-1 lados, (l = número de lados).
La solución tiene n-1 lados, (n = número de nodos).
la solución contendrá a los n-1 lados mas pequeños del grafo.
No contestar.
En cada etapa se selecciona el lado mas pequeño aún no seleccionado sin realizar ninguna comprobación adicional.
¿cuál de las siguientes afirmaciones es cierta sobre el quicksort?
La mejor opción es seleccionar como pivote al elemento central del vector o subvector que se va a ordenar.
Da lo mismo seleccionar como pivote el extremo izquierdo o al elemento central del vector que se esta tratando.
Divide siempre al vector en dos subvectores del mismo tamaño
Los subvectores resultantes del algoritmo de la partición no se pueden ordenar por separado.
¿cuál de las siguientes afirmaciones sobre el algoritmo voraz que resuelve el problema de la mochila es falsa?
El primer material elegido sera siempre el que tenga un mayor precio.
La causa de que sea óptimo es que los materiales sean particionables.
LA solución es una permutación de los materiales disponibles.
Puede que el ultimo material seleccionado no se seleccione en su totalidad.
¿cuál de las siguientes afirmaciones es cierta para el algoritmo recursivo de las torres de Hanoi?
No se puede evitar la repetición de llamadas recursivas y su complejidad es de O(2^N).
Se puede evitar la repetición de llamadas recursivas y entonces su complejidad sería O(N).
Se puede evitar la repetición de llamadas recursivas y entonces su complejidad sería O(N^2).
No se puede evitar la repetición de llamadas recursivas y su complejidad es O(N^2).
¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo RECURSIVO del juego de la rayuela?
Siempre será de O(log N).
Siempre será de O(2^N).
Siempre será de O(N^2).
Si se controlan las llamadas repetidas pueden ser de O(N).
La primera versión del algoritmo recursivo para la exponenciación se basa en el siguiente caso general:
a^n= (a^(n/2))^2 si n es impar y a^n = a*(a^((n-1)/2))^2 si n es par.
a^n= (a^(n/2))^2 si n es par y a^n = a*(a^((n-1)/2))^2 si n es impar.
a^n= (a^(n/2))^2 independientemente del valor de n.
a^n = a*(a^((n-1)/2))^2 independientemente del valor de n.
¿Cuál de las siguientes afirmaciones es cierta?
Si tenemos un algoritmo recursivo, sólo se debe de traducir a iterativo en caso de que la versión iterativa sea mucho mas eficiente.
Un algoritmo recursivo que posea un solo esquema condicional con una cosa llamada recursiva puede ser de orden exponencial.
Siempre hay que buscar una versión iterativa a la hora de resolver cualquier tipo de problema, ya que ésta siempre será mucho más simple de obtener.
Todo algoritmo recursivo hace uso del montón (heap) para almacenar las llamadas recursivas.
¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo recursivo de las torres de hanoi para N discos?
El número de llamadas recursivas es del orden 2^N.
El número de llamadas recursivas es del orden N^2.
El número de llamadas recursivas es del orden N.
El número de llamadas recursivas es del orden N*2.
En el algoritmo del plano de la ciudad. ?cuál de las siguientes planteamientos es el mas eficiente y correcto?
Caso General: caminos(x,y) = caminos(x+1,y) + caminos(x,y+1) Casos elementales: caminos(x,0) = 1, caminos(0,y) = 1
Caso General: caminos(x,y) = caminos(x-1,y) + caminos(x,y-1) Casos elementales: caminos(x,0) = 1, caminos(0,y) = 1
Caso General: caminos(x,y) = caminos(x-1,y) + caminos(x,y-1) Casos elementales: caminos(1,0) = 1, caminos(0,1) = 1
Caso General: caminos(x,y) = caminos(x+1,y) + caminos(x,y+1) Casos elementales: caminos(1,0) = 1, caminos(0,1) = 1
Un procedimiento recursivo se implementa usando exclusivamente un caso general de descomposición.
Un procedimiento recursivo con una sola llamada, siempre ha de tener un es que,a iterativo para generar todas las llamadas recursivas.
Un procedimiento recursivo siempre será mas rápido que uno iterativo.
Un procedimiento recursivo requiere de más memoria que uno iterativo.
¿Cúal de las siguientes afirmaciones es cierta sobre el algoritmo que resuelve el problema de la planificaciones de tareas a plazo fijo?
Para comprobar si un conjunto de tareas es factible, es necesario comprobar todas las permutaciones posibles de ese conjunto de tareas.
Para comprobar si un conjunto de tareas es factible, basta comprobar si la permutación que contiene a las tareas en orden creciente de plazos es factible.
Para comprobar si un conjunto de tareas es factible, basta comprobar si una permutación aleatoria de ese conjunto es factible.
Para comprobar si un conjunto de tareas es factible, basta comprobar si la permutación que contiene a las tareas en orden decreciente de beneficios es factible.
¿Cuál de las siguientes condiciones no tiene porqué cumplirse a la hora de aplicar el método de divide y vencerás.?
Se ha de seleccionar de forma conveniente cuando se usa el algoritmo básico en vez de seguir descomponiendo el problema.
Se aplica en problemas de optimización.
Los subproblemas han de ser aproximadamente del mismo tamaño.
Ha de ser posible la descomposición del problema en subproblemas y recomponer las soluciones de estos subproblemas de manera eficiente.
En el algoritmo del plano de la ciudad, si además se permitiese un movimiento en diagonal en dirección noroeste. ¿Cúal de las siguientes afirmaciones sería cierta?
Caso General: caminos(x,y) = caminos (x+1,y) + caminos (x,y+1) + caminos (x+1,y+1) Casos elementales : caminos (x,0) = 1, caminos (0,y) = 1, caminos (x,x) = 1
Caso General: caminos(x,y) = caminos (x+1,y) + caminos (x,y+1) + caminos (x+1,y+1) Casos elementales : caminos (x,0) = 1, caminos (0,y) = 1
Caso General: caminos(x,y) = caminos (x-1,y) + caminos (x,y-1) + caminos (x-1,y-1) Casos elementales : caminos (x,0) = 1, caminos (0,y) = 1, caminos (x,x) = 1
Caso General: caminos(x,y) = caminos (x-1,y) + caminos (x,y-1) + caminos (x-1,y-1) Casos elementales : caminos (x,0) = 1, caminos (0,y) = 1
¿Cuál de las siguientes afirmaciones es falsa sobre el algoritmo voraz que resuelve el problema del viajante de comercio?
La solución tienen n lados. (n= número de nodos)
La solución tiene un ciclo.
Todos los nodos tendrán un lado de la salida y uno de entrada.
La solución obtenida es optima.
¿Cuál de las siguientes afirmaciones es falsa sobre el problema de la minimización de los tiempos de espera si se aplica a una consulta médica?
El paciente atendido en primer lugar es aquel que requiere menor tiempo de atención.
La solución proporcionada se basa en un algoritmo voraz.
El tiempo que el médico pasa en la consulta es siempre el mismo, independientemente de como se atiendan a los pacientes.
La mejor opción en cada etapa es seleccionar siempre al paciente no atendido que requiera un mayor tiempo de atención.
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo voraz que resuelve el problema del viajante de comercio?
En la solución puede haber más de dos lados que confluyan (entren o salgan) en un nodo.
En cada etapa se selecciona el lado más pequeño aún no seleccionado sin realizar ninguna comprobación adicional.
La solución tiene l lados. (l= número de lados)
¿Cuál de la siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
Todas las respuestas restantes son falsas.
Es de O(n)
Es de O(n logn)
Es de O(n^2)
¿Cuál de las siguientes afirmaciones sobre el algoritmo voraz que resuelve el problema de la mochila es cierta?
Todos los materiales seleccionados, se seleccionan en su totalidad.
Aunque haya materiales suficientes, puede que la mochila no se llene totalmente.
Solo proporcionan una solución óptima cuando los materiales son particionables.
Puede que haya más de un material seleccionado que no se seleccione en su totalidad.
El principal inconveniente de la recursividad es:
La posible repetición de llamadas recursivas.
La dificultad a la hora de implementar una versión recursiva.
La recursividad no plantea ningún inconveniente.
El uso ineficiente de la memoria.
Si tenemos un algoritmo recursivo, sólo se debe traducir a iterativo en caso de que la versión iterativa sea mucho más eficiente.
Siempre hay que buscar una versión iterativa a la hora de resolver cualquier tipo de problema, ya que ésta siempre será mucho más simple de obetner.
Un algoritmo recursivo que posea un solo esquema condicional con una sola llamada recursiva puede ser de orden exponencial.
Cada llamada al algoritmo genera a lo sumo 3 llamadas recursivas.
Si los subvectores resultantes fuesen de tamaño muy dispar, el algoritmo sería de O(n log n)
La clave de su eficiencia estriba en dividir los vectores en subvectores de tamaño similar.
La parte correspondiente a la fusión de los subvectores resultantes es de O(n log n)
Cuando un ordenador ejecuta un procedimiento recursivo:
Realiza cálculos recursivos haciendo uso del montón.
Realiza cálculos recursivos haciendo uso de la pila.
Realiza cálculos secuenciales basados en la iteración, simulando las llamadas recursivas haciendo uso del montón (heap)
Realiza cálculos secuenciales basados en la iteración, simulando las llamadas recursivas haciendo uso de la pila.
En el algoritmo del plano de la ciudad ¿Cuál de los siguientes planteamientos es el más eficiente y correcto?
Caso General: caminos(x,y) = caminos (x-1,y) + caminos (x,y-1) + caminos (x+1,y-1) Casos elementales : caminos (1,0) = 1, caminos (0,1) = 1
Caso General: caminos(x,y) = caminos (x+1,y) + caminos (x,y+1) + caminos (x+1,y+1) Casos elementales : caminos (1,0) = 1, caminos (0,1) = 1
En el juego de rayuela se permite saltar de 1 en 1 o de 2 en 2. Si además se permitiese saltar de 3 en 3, indica cuál de las siguientes afirmaciones sería cierta:
Caso general: caminos(n)=caminos(n-1)+caminos(n-2)+caminos(n-3) Caso elementales: caminos(1)=1, caminos(2)=2, caminos(3)=4
Caso general: caminos(n)=caminos(n-1)+caminos(n-2)+caminos(n-3) Caso elementales: caminos(1)=1, caminos(2)=2, caminos(3)=6
Caso general: caminos(n)=caminos(n-1)+caminos(n-2)+caminos(n-3) Caso elementales: caminos(1)=1, caminos(2)=2, caminos(3)=3
Caso general: caminos(n)=caminos(n+1)+caminos(n+2)+caminos(n+3) Caso elementales: caminos(1)=1, caminos(2)=2, caminos(3)=4
¿Cuál de las siguientes afirmaciones es cierta sobre el problema de la minimización de los tiempos de espera si se aplica a una consulta médica?
El tiempo que más afecta al tiempo global es el del último paciente
El tiempo que más afecta al tiempo global es el del primer paciente
El tiempo global se afectado de igual forma por el tiempo de cada paciente
El tiempo que más afecta al tiempo global es el del paciente que se atiende en el lugar medio
¿Cuál de las siguientes afirmaciones es cierta sobre el problema de minimización de los tiempos de espera si se aplica a una consulta médica?
El paciente atendido en primer lugar es aquel que requiere más tiempo de atención.
La mejor opción en cada etapa es seleccionar siempre al paciente no atendido que requiera un menor tiempo de atención
El tiempo que el médico pasa en la consulta puede variar en función del orden de atención a los pacientes
La solución proporcionada no tiene por que ser óptima
¿Cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
La solución se obtiene a trozos seleccionando en cada paso el mejor de los trozos no seleccionados
Siempre proporcionan soluciones óptimas
El problema se subdivide en problemas del mismo carácter que el original
Suelen ser algoritmos de O(n^3)
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?
Proporciona siempre una solución óptima
Va seleccionando los lados de la solución en orden decreciente de pesos
Puede haber ciclos en la solución
Proporciona las distancias mínimas en un grafo conexo no dirigido
¿Cual de las siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
Los subvectores resultantes pueden ser de un tamaño muy dispar, lo mismo que ocurre en el quicksort
La fusión de los subvectores resultantes es de O(n log n)
Los subvectores resultantes no se ordenan independientemente, contrariamente a lo que ocurre en el quicksort
¿Cuál de las siguientes afirmaciones es falsa sobre el divide y vencerás?
El problema a resolver se divide en subproblemas que no tienen porqué ser del mismo tipo que el original
Divide el problema en subproblemas
Suele dar lugar a algoritmos recursivos
Los subproblemas resultantes se aplican a un ámbito más reducido de los datos que el problema original
En el algoritmo de la búsqueda binaria o dicotómica para un vector de n elementos, ¿cuál de las siguientes afirmaciones es cierta?
El mejor caso posible se da siempre que el elemento a buscar se repite varias veces
El peor caso posible se cuando el elemento a buscar no está en el vector
El peor caso posible se da cuando el elemento a buscar es el central
El mejor caso posible se da cuando el elemento a buscar ocupa la primera o la última posición
En la primera versión del algoritmo para multiplicar enteros grandes ¿cuál de las siguientes afirmaciones es cierta?
Es de O(log n)
Es de O(2^n)
¿cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
La función que se usa para seleccionar el candidato no tiene nada que ver con la función objetivo del problema en cuestión.
Un candidato ya seleccionado puede ser desechado en etapas posteriores
A priori no se sabe cuántos candidatos formarán parte de la solución.
El candidato seleccionado en una fase no influye en la selección de los candidatos en fases posteriores.
En el algoritmo para multiplicar enteros grandes, si descomponemos el primer multiplicando u en dos partes w y x, siendo w la más significativa ¿cómo se obtienen w y x sabiendo que el número de cifras de u es n y que n es par?
w = E(u /10^(n/2)), x = u mod 10^(n/2) donde E es la parte entera y mod es el operador módulo de la división.
w = u mod (n/2), x= E(u/(n/2)) donde E es la parte entera y mod es el operador módulo de la división.
w = E(u / (n/2)), x = u mod(n/2) donde E es la parte entera y mod es el operador módulo de la división.
w = u mod 10^(n/2), x = E(u / 10^(n/2)), donde E es la parte entera y mod es el operador módulo de la división.
¿Cual de las siguientes afirmaciones es cierta sobre los 2 algoritmos iterativos (no el recursivo) vistos en clase para calcular el máximo y el mínimo elemento de un vector?
Las comparaciones que usan ambos algoritmos son las mismas en el mejor de los casos posibles
Las comparaciones que usan ambos algoritmos son las mismas en el caso medio dentro de los casos posibles
Las comparaciones que usan ambos algoritmos son las mismas en el peor de los casos posibles
Las comparaciones que usan ambos algoritmos son las mismas en todos los casos posibles
¿cuál de las siguientes afirmaciones es falsa sobre los algoritmos voraces?
La solución siempre es una permutación del conjunto de candidatos inicial
Suelen ser algoritmos cuyo orden está entre O(n^2) y O(n^3)
Obtienen la solución a trozos
En algunos tipos de problemas, cuya solución utiliza dicho método, proporciona la solución óptima
¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
para comprobar si un conjunto de tareas es factible, basta comprobar si una permutación aleatoria de ese conjunto es factible
para comprobar si un conjunto de tareas es factible, basta comprobar si la permutación que contiene a las tareas en orden decreciente de beneficios es factible
para comprobar si un conjunto de tareas es factible, es necesario comprobar todas las permutaciones posibles de ese conjunto de tareas
para comprobar si un conjunto de tareas es factible, basta comprobar si la permutación que contiene a las tareas en orden creciente de plazos es factible
En un algoritmo recursivo la clave de su diseño es:
Descomponer el problema en subproblemas similares al de partida para los mismos datos del problema original
Descomponer el problema en subproblemas similares al de partida para datos más simples que los del problema original
Descomponer el problema en subproblemas, que no tienen porqué ser similares al de partida, para datos más simples que los del problema original
Descomponer el problema en subproblemas, que no tienen porqué ser similares al de partida, para los mismos datos del problema original
En el algoritmo de la búsqueda binaria o dicotómica, ¿cuál de las siguientes afirmaciones es cierta?
Ninguna de las respuestas es correcta
El problema de partida se descompone en tantos subproblemas como elementos tenga el vector, y todos ellos tienen una solución inmediata
El problema de partida se descompone en 3 subproblemas, de los cuales dos de ellos tienen una solución inmediata
El problema de partida se descompone en 2 subproblemas, de los cuales 1 de ellos tiene solución inmediata
¿cuál de las siguientes afirmaciones es falsa sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
La primera tarea en ejecutar no tiene porqué ser la que tenga un plazo menor
La solución obtenida no tiene porqué ser óptima
Una solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1, 3, 2, 5
La primera tarea que se ejecuta siempre será la que obtiene un mayor beneficio
En todo algoritmo recursivo que contenga dos llamadas recursivas, como por ejemplo el de la sucesión de Fibonacci o el de las torres de Hanoi:
Son de complejidad O(N*N)
Son de complejidad O(N)
No siempre tienen porqué producirse llamadas recursivas repetidas
Siempre se producirán llamadas recursivas repetidas que se pueden evitar
