AL 4-5-6

Description

AL 4-5-6
John Balusman
Quiz by John Balusman, updated more than 1 year ago
John Balusman
Created by John Balusman over 5 years ago
23
0

Resource summary

Question 1

Question
¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?
Answer
  • 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.

Question 2

Question
¿cuál de las siguientes afirmaciones es cierta sobre el quicksort?
Answer
  • No contestar.
  • 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.

Question 3

Question
¿cuál de las siguientes afirmaciones sobre el algoritmo voraz que resuelve el problema de la mochila es falsa?
Answer
  • El primer material elegido sera siempre el que tenga un mayor precio.
  • No contestar.
  • 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.

Question 4

Question
¿cuál de las siguientes afirmaciones es cierta para el algoritmo recursivo de las torres de Hanoi?
Answer
  • 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 contestar.
  • No se puede evitar la repetición de llamadas recursivas y su complejidad es O(N^2).

Question 5

Question
¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo RECURSIVO del juego de la rayuela?
Answer
  • Siempre será de O(log N).
  • Siempre será de O(2^N).
  • No contestar.
  • Siempre será de O(N^2).
  • Si se controlan las llamadas repetidas pueden ser de O(N).

Question 6

Question
La primera versión del algoritmo recursivo para la exponenciación se basa en el siguiente caso general:
Answer
  • No contestar.
  • 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.

Question 7

Question
¿Cuál de las siguientes afirmaciones es cierta?
Answer
  • 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.
  • No contestar.
  • 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.

Question 8

Question
¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo recursivo de las torres de hanoi para N discos?
Answer
  • No contestar.
  • 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.

Question 9

Question
En el algoritmo del plano de la ciudad. ?cuál de las siguientes planteamientos es el mas eficiente y correcto?
Answer
  • 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

Question 10

Question
¿Cuál de las siguientes afirmaciones es cierta?
Answer
  • No contestar.
  • 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.

Question 11

Question
¿Cúal de las siguientes afirmaciones es cierta sobre el algoritmo que resuelve el problema de la planificaciones de tareas a plazo fijo?
Answer
  • No contestar.
  • 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.

Question 12

Question
¿Cuál de las siguientes condiciones no tiene porqué cumplirse a la hora de aplicar el método de divide y vencerás.?
Answer
  • Se ha de seleccionar de forma conveniente cuando se usa el algoritmo básico en vez de seguir descomponiendo el problema.
  • No contestar.
  • 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.

Question 13

Question
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?
Answer
  • 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

Question 14

Question
¿Cuál de las siguientes afirmaciones es falsa sobre el algoritmo voraz que resuelve el problema del viajante de comercio?
Answer
  • 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.

Question 15

Question
¿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?
Answer
  • 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.

Question 16

Question
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo voraz que resuelve el problema del viajante de comercio?
Answer
  • La solución tienen n lados. (n= número de nodos)
  • 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)

Question 17

Question
¿Cuál de la siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
Answer
  • Todas las respuestas restantes son falsas.
  • Es de O(n)
  • Es de O(n logn)
  • Es de O(n^2)

Question 18

Question
¿Cuál de las siguientes afirmaciones sobre el algoritmo voraz que resuelve el problema de la mochila es cierta?
Answer
  • 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.

Question 19

Question
El principal inconveniente de la recursividad es:
Answer
  • 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.

Question 20

Question
¿Cuál de las siguientes afirmaciones es cierta?
Answer
  • 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.
  • Todo algoritmo recursivo hace uso del montón (heap) para almacenar las llamadas recursivas.
  • Un algoritmo recursivo que posea un solo esquema condicional con una sola llamada recursiva puede ser de orden exponencial.

Question 21

Question
¿Cuál de la siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
Answer
  • 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)

Question 22

Question
Cuando un ordenador ejecuta un procedimiento recursivo:
Answer
  • 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.

Question 23

Question
En el algoritmo del plano de la ciudad ¿Cuál de los siguientes planteamientos es el más eficiente y correcto?
Answer
  • 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 (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 (1,0) = 1, caminos (0,1) = 1

Question 24

Question
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:
Answer
  • 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

Question 25

Question
¿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?
Answer
  • 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

Question 26

Question
¿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?
Answer
  • 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

Question 27

Question
¿Cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
Answer
  • 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)

Question 28

Question
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?
Answer
  • 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

Question 29

Question
¿Cual de las siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
Answer
  • 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
  • Es de O(n^2)

Question 30

Question
¿Cuál de las siguientes afirmaciones es falsa sobre el divide y vencerás?
Answer
  • 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

Question 31

Question
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?
Answer
  • 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

Question 32

Question
En la primera versión del algoritmo para multiplicar enteros grandes ¿cuál de las siguientes afirmaciones es cierta?
Answer
  • Es de O(n)
  • Es de O(log n)
  • Es de O(2^n)
  • Es de O(n^2)

Question 33

Question
¿cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
Answer
  • 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.

Question 34

Question
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?
Answer
  • 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.

Question 35

Question
¿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?
Answer
  • 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

Question 36

Question
¿cuál de las siguientes afirmaciones es falsa sobre los algoritmos voraces?
Answer
  • 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

Question 37

Question
¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
Answer
  • 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

Question 38

Question
En un algoritmo recursivo la clave de su diseño es:
Answer
  • 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

Question 39

Question
En el algoritmo de la búsqueda binaria o dicotómica, ¿cuál de las siguientes afirmaciones es cierta?
Answer
  • 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

Question 40

Question
¿cuál de las siguientes afirmaciones es falsa sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
Answer
  • 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

Question 41

Question
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:
Answer
  • 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
Show full summary Hide full summary

Similar

Contenido Lógica y Representación II
Luis Carlos Puerta Arroyave
Algoritmia_01
Giacomo Gallo
ALGORITMIA
cesar sanchez
Introducción
Yaneisy Tersek
Evaluación de Algoritmia
Sneiders Rocha
Contenido Lógica y Representación II
Andrés Moreno
Algorítmia
Eduardo Bandera
Algorítmia
Jose Miguel Torr
Algoritmia
Alejandro Serrano
algoritmia
Giacomo Gallo
Algoritmia
Toño Cano Morale