¿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 primera tarea que se ejecuta siempre será la que obtiene un mayor beneficio.
Una solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1, 3,2,5
La solución obtenida no tiene porqué ser óptima
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)
Es de O(n^2)
Los subvectores resultantes no se ordenan independientemente, contrariamente a lo que ocurre en el quicksort.
En el juego de la 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) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 4
Caso General: caminos(n) = caminos(n+1) + caminos(n+2) + caminos (n+3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 4
Caso General: caminos(n) = caminos(n-1) + caminos(n-2) + caminos (n-3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 3
Caso General: caminos(n) = caminos(n-1) + caminos(n-2) + caminos (n-3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 6
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).
Siempre se producirán llamadas recursivas repetidas que se pueden evitar.
Son de complejidad O(N*N).
No siempre tienen porqué producirse llamadas recursivas repetidas.
¿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 de N
El número de llamadas recursivas es del orden de 2^N
El número de llamadas recursivas es del orden de N^2
El número de llamadas recursivas es del orden de 2*N
¿Cual de las siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
Si los subvectores resultantes fuesen de un tamaño muy dispar, el algoritmo sería de O(n log n).
Cada llamada al algoritmo genera a lo sumo 3 llamadas recursivas.
La clave de su eficiencia estriba en dividir los vectores es subvectores de tamaño similar.
La parte correspondiente a la fusión de los subvectores resultantes es de O(n log n)
¿Cuál de las siguientes afirmaciones sobre el algoritmo de los k-menores es falsa?
Obtiene los k menores elementos del vector, aunque éstos no tienen por qué estar ordenados.
Obtiene los k menores elementos de un vector totalmente ordenados.
En cada llamada al algoritmo se genera a lo sumo una llamada recursiva.
Obtiene los n-k (siendo n el número de elementos del vector) mayores elementos del vector, aunque éstos no tienen porqué estar ordenados.
¿cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
Suelen ser algoritmos de O(n^3)
El problema se subdivide en problemas del mismo carácter que el original
Siempre proporcionan soluciones óptimas.
La solución se obtiene a trozos seleccionando en cada paso el mejor de los trozos no seleccionados.
¿Cuál 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 todos 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 el caso medio dentro los casos posibles.
Las comparaciones que usan ambos algoritmos son las mismas en el mejor de los casos posibles.
¿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.
¿Cuál de las siguientes afirmaciones es cierta?
Todo algoritmo recursivo hace uso del montón (heap) para almacenar las llamadas recursivas.
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.
Un algoritmo recursivo que posea un solo esquema condicional con una sola llamada recursiva p orden exponencial.
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.
En el algoritmo de la búsqueda binaria o dicotómica, ¿cuál de las siguientes afirmaciones es cierta?
El problema de partida se descompone en 3 subproblemas, de los cuales dos de ellos tienen solución inmediata.
El problema de partida se descompone en 2 subproblemas, de los cuales 1 de ellos tiene solución inmediata.
Ninguna de las respuestas restantes es cierta
El problema de partida se descompone en tantos subproblemas como elementos tenga el vector, y todos ellos tienen solución inmediata.
Indica cuál de las siguientes afirmaciones es falsa en el algoritmo recursivo para obtener el término n-ésimo de la sucesión de Fibonacci.
Si no se controla la repetición de llamadas recursivas, el número de llamadas es de orden 2^N
Si no se controla la repetición de llamadas recursivas, el número de llamadas es de orden N*N
Si se controla la repetición de llamadas recursivas mediante una tabla el cálculo de cualquier término es inmediato.
Si se controla la repetición de llamadas recursivas mediante una tabla, el número de llamadas es de orden N
En el algoritmo del plano de la ciudad, si además se permitiese un movimiento en diagonal en dirección noreste. ¿Cuál 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
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
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, 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
descomponer el problema en subproblemas similares al de partida para datos más simples que los del 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?
Es de O(n log n)
Es de O(n)
El principal inconveniente de la recursividad es:
La dificultad a la hora de implementar una versión recursiva.
El uso ineficiente de la memoria.
La recursividad no plantea ningún inconveniente.
La posible repetición de llamadas recursivas
En el algoritmo del plano de la ciudad ¿Cuál de las siguientes planteamientos es el más eficiente y correcto?
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(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(x,0) = 1, caminos(0,y) = 1
¿Cuál de las siguientes afirmaciones es falsa sobre el divide y vencerás?
Los subproblemas resultantes se aplican a un ámbito más reducido de los datos que el problema original.
Suele dar lugar a algoritmos recursivos.
Divide el problema en subproblemas
El problema a resolver se divide en subproblemas que no son del mismo tipo que el original.
¿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?
La solución proporcionada no tiene porqué ser óptima.
El tiempo que el médico pasa en la consulta puede variar en función del orden de atención a los pacientes.
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.
¿Cuál de las siguientes afirmaciones sobre la primera versión del algoritmo recursivo para la exponenciación es cierta, cuando los números se pueden multiplicar directamente?
Es de O(log n)
¿cuál de las siguientes afirmaciones es cierta sobre el quicksort?
Da lo mismo seleccionar como pivote al extremo izquierdo o al elemento central del vector que se está tratando
Los subvectores resultantes del algoritmo de la partición no se pueden ordenar por separado.
Divide siempre al vector en dos subvectores del mismo tamaño.
La mejor opción es seleccionar como pivote al elemento central del vector o subvector que se va a ordenar.
¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
La solución obtenida es óptima.
Una solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1,2,2,3
Una solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1, 3,2,3, 5
La primera tarea en ejecutar será siempre la que tenga un plazo menor.
El candidato seleccionado en una fase no influye en la selección de los candidatos en fases posteriores.
A priori no se sabe cuántos candidatos formarán parte de la solución.
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.
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo voraz sobre el problema del viajante de comercio?
La solución tiene n lados
La solución tiene n lados (n - número de nodos)
Todas las respuestas son falsas
En la solución puede haber más de dos lados que confluyen entrando y saliendo de un nodo
¿Cuál de las siguientes afirmaciones es falsa sobre el algoritmo voraz sobre el problema del viajante de comercio?
La solución obtenida es óptima
Todas las respuestas son ciertas
Todos los nodos tendrán un lado de salida y uno de entrada
¿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?
La mejor opción en cada etapa es seleccionar siempre al paciente no atendido que requiere un mayor tiempo de atención
El tiempo que el médico pasa en la consulta es siempre el mismo, independientemente de los pacientes
El paciente atendido en primer lugar no es aquel que requiere menor tiempo de atencion
La solución proporcionada se basa en un algoritmo voraz
Cuando un ordenador ejecuta un proceso recursivo…
Realiza cálculos secuenciales basados en la iteración, simulando las llamadas recursivas haciendo uso de la pila
Realiza cálculos secuenciales basados en la iteración, simulando las llamadas recursivas haciendo uso del monton
Realiza cálculos recursivos haciendo uso del montón.
Realiza cálculos recursivos haciendo uso de la pila.
¿Cuál de las siguientes afirmaciones es cierta sobre recursividad?
Un procedimiento recursivo requiere de más memoria que uno iterativo
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 esquema iterativo para generar todas las llamadas recursivas
Ninguna de las respuestas es correcta
En la primera versión del algoritmo para multiplicar enteros grandes, ¿cuál de las siguientes afirmaciones es cierta?
Si convertimos números enteros a doubles y los multiplicamos obtendremos el resultado aproximado
El número de llamadas a recursivas se puede reducir a 3 usando sumas y restas
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de las torres de Hanoi?
No se puede evitar las llamadas recursivas y su complejidad es O(2^n)
No se puede evitar las llamadas recursivas y su complejidad es O(n^2)
Se puede evitar las llamadas recursivas y su complejidad es O(n)
Se puede evitar las llamadas recursivas y su complejidad es O(n^2)
¿Cuál de las siguientes afirmaciones es cierta sobre algoritmo kruskal?
En cada etapa se selecciona el lado más pequeño no seleccionado sin realizar ninguna comprobación adicional
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 l-1 lados más pequeños del grafo
¿Cuál de las siguientes afirmaciones es cierta sobre los algoritmos vistos en clase para calcular el mínimo y máximo elemento de un vector?
Las versiones mejoradas pueden reducir su complejidad algorítmica pero no el tiempo de ejecución del algoritmo
Las versiones mejoradas pueden reducir el tiempo de ejecución del algoritmo pero no su complejidad algorítmica
Las versiones mejoradas pueden reducir el tiempo de ejecución del algoritmo y su complejidad
Las versiones mejoradas no reducen el tiempo de ejecución ni su complejidad algorítmica
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... sabiendo que el número de cifras de u es n y que n es par.
w=u/10^n/2 y x=u%(10^n/2)
RESPUESTA VACÍA
RESPUESTA VACÍA 2
RESPUESTA VACÍA 3
