Test
Cuestionario 4,5 y 6
Preguntas del test (34)
1¿Cuál de las siguientes afirmaciones es falsa sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
- ALa primera tarea en ejecutar no tiene porqué ser la que tenga un plazo menor.
- BLa primera tarea que se ejecuta siempre será la que obtiene un mayor beneficio.
- CUna solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1, 3,2,5
- DLa solución obtenida no tiene porqué ser óptima
2Cual de las siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
- ALos subvectores resultantes pueden ser de un tamaño muy dispar, lo mismo que ocurre en el quicksort. (*)
- BLa fusión de los subvectores resultantes es de O(n log n)
- CEs de O(n^2)
- DLos subvectores resultantes no se ordenan independientemente, contrariamente a lo que ocurre en el quicksort.
3En 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:
- ACaso General: caminos(n) = caminos(n-1) + caminos(n-2) + caminos (n-3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 4
- BCaso General: caminos(n) = caminos(n+1) + caminos(n+2) + caminos (n+3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 4
- CCaso General: caminos(n) = caminos(n-1) + caminos(n-2) + caminos (n-3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 3
- DCaso General: caminos(n) = caminos(n-1) + caminos(n-2) + caminos (n-3) Casos elementales: caminos(1) = 1, caminos(2) = 2, caminos(3) = 6
4En 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:
- ASon de complejidad O(N).
- BSiempre se producirán llamadas recursivas repetidas que se pueden evitar.
- CSon de complejidad O(N*N).
- DNo siempre tienen porqué producirse llamadas recursivas repetidas.
5¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo recursivo de las torres de Hanoi para N discos?
- AEl número de llamadas recursivas es del orden de N
- BEl número de llamadas recursivas es del orden de 2^N
- CEl número de llamadas recursivas es del orden de N^2
- DEl número de llamadas recursivas es del orden de 2*N
6¿Cual de las siguientes afirmaciones es cierta sobre el método de ordenación por fusión?
- ASi los subvectores resultantes fuesen de un tamaño muy dispar, el algoritmo sería de O(n log n).
- BCada llamada al algoritmo genera a lo sumo 3 llamadas recursivas.
- CLa clave de su eficiencia estriba en dividir los vectores es subvectores de tamaño similar.
- DLa parte correspondiente a la fusión de los subvectores resultantes es de O(n log n)
7¿Cuál de las siguientes afirmaciones sobre el algoritmo de los k-menores es falsa?
- AObtiene los k menores elementos del vector, aunque éstos no tienen por qué estar ordenados.
- BObtiene los k menores elementos de un vector totalmente ordenados.
- CEn cada llamada al algoritmo se genera a lo sumo una llamada recursiva.
- DObtiene los n-k (siendo n el número de elementos del vector) mayores elementos del vector, aunque éstos no tienen porqué estar ordenados.
8¿cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
- ASuelen ser algoritmos de O(n^3)
- BEl problema se subdivide en problemas del mismo carácter que el original
- CSiempre proporcionan soluciones óptimas.
- DLa solución se obtiene a trozos seleccionando en cada paso el mejor de los trozos no seleccionados.
9¿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?
- ALas comparaciones que usan ambos algoritmos son las mismas en todos los casos posibles.
- BLas comparaciones que usan ambos algoritmos son las mismas en el peor de los casos posibles.
- CLas comparaciones que usan ambos algoritmos son las mismas en el caso medio dentro los casos posibles.
- DLas comparaciones que usan ambos algoritmos son las mismas en el mejor de los casos posibles.
10¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?
- AProporciona siempre una solución óptima.
- BVa seleccionando los lados de la solución en orden decreciente de pesos.
- CPuede haber ciclos en la solución.
- DProporciona las distancias mínimas en un grafo conexo no dirigido.
11¿Cuál de las siguientes afirmaciones es cierta?
- ATodo algoritmo recursivo hace uso del montón (heap) para almacenar las llamadas recursivas.
- BSiempre 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.
- CUn algoritmo recursivo que posea un solo esquema condicional con una sola llamada recursiva p orden exponencial.
- DSi tenemos un algoritmo recursivo, sólo se debe traducir a iterativo en caso de que la versión iterativa sea mucho más eficiente.
12En el algoritmo de la búsqueda binaria o dicotómica, ¿cuál de las siguientes afirmaciones es cierta?
- AEl problema de partida se descompone en 3 subproblemas, de los cuales dos de ellos tienen solución inmediata.
- BEl problema de partida se descompone en 2 subproblemas, de los cuales 1 de ellos tiene solución inmediata.
- CNinguna de las respuestas restantes es cierta
- DEl problema de partida se descompone en tantos subproblemas como elementos tenga el vector, y todos ellos tienen solución inmediata.
13Indica 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.
- ASi no se controla la repetición de llamadas recursivas, el número de llamadas es de orden 2^N
- BSi no se controla la repetición de llamadas recursivas, el número de llamadas es de orden N*N
- CSi se controla la repetición de llamadas recursivas mediante una tabla el cálculo de cualquier término es inmediato.
- DSi se controla la repetición de llamadas recursivas mediante una tabla, el número de llamadas es de orden N
14En 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?
- ACaso 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
- BCaso 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
- CCaso 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
- DCaso 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
15En un algoritmo recursivo la clave de su diseño es:
- Adescomponer el problema en subproblemas similares al de partida para los mismos datos del problema original
- Bdescomponer el problema en subproblemas, que no tienen porqué ser similares al de partida, para datos más simples que los del problema original
- Cdescomponer el problema en subproblemas, que no tienen porqué ser similares al de partida, para los mismos datos del problema original
- Ddescomponer el problema en subproblemas similares al de partida para datos más simples que los del problema original
16En el algoritmo de la búsqueda binaria o dicotómica para un vector de n elementos, ¿cuál de las siguientes afirmaciones es cierta?
- AEs de O(n^2)
- BEs de O(n log n)
- CNinguna de las respuestas restantes es cierta
- DEs de O(n)
17El principal inconveniente de la recursividad es:
- ALa dificultad a la hora de implementar una versión recursiva.
- BEl uso ineficiente de la memoria.
- CLa recursividad no plantea ningún inconveniente.
- DLa posible repetición de llamadas recursivas
18 En el algoritmo del plano de la ciudad ¿Cuál de las siguientes planteamientos es el más eficiente y correcto?
- ACaso General: caminos(x,y) = caminos(x-1,y) + caminos(x,y-1) Casos elementales:
caminos(1,0) = 1, caminos(0,1) = 1 - BCaso General: caminos(x,y) = caminos(x+1,y) + caminos(x,y+1) Casos elementales: caminos(x,0) = 1, caminos(0,y) = 1
- CCaso General: caminos(x,y) = caminos(x+1,y) + caminos(x,y+1) Casos elementales: caminos(1,0) = 1, caminos(0,1) = 1
- DCaso General: caminos(x,y) = caminos(x-1,y) + caminos(x,y-1) Casos elementales:
caminos(x,0) = 1, caminos(0,y) = 1
- ACaso General: caminos(x,y) = caminos(x-1,y) + caminos(x,y-1) Casos elementales:
19¿Cuál de las siguientes afirmaciones es falsa sobre el divide y vencerás?
- ALos subproblemas resultantes se aplican a un ámbito más reducido de los datos que el problema original.
- BSuele dar lugar a algoritmos recursivos.
- CDivide el problema en subproblemas
- DEl problema a resolver se divide en subproblemas que no son del mismo tipo que el original.
20¿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?
- ALa solución proporcionada no tiene porqué ser óptima.
- BEl tiempo que el médico pasa en la consulta puede variar en función del orden de atención a los pacientes.
- CEl paciente atendido en primer lugar es aquel que requiere más tiempo de atención.
- DLa mejor opción en cada etapa es seleccionar siempre al paciente no atendido que requiera un menor tiempo de atención.
21¿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?
- AEs de O(log n)
- BEs de O(n)
- CEs de O(n^2)
- DEs de O(n log n)
22¿cuál de las siguientes afirmaciones es cierta sobre el quicksort?
- ADa lo mismo seleccionar como pivote al extremo izquierdo o al elemento central del vector que se está tratando
- BLos subvectores resultantes del algoritmo de la partición no se pueden ordenar por separado.
- CDivide siempre al vector en dos subvectores del mismo tamaño.
- DLa mejor opción es seleccionar como pivote al elemento central del vector o subvector que se va a ordenar.
23¿cuál de las siguientes afirmaciones es cierta sobre el algoritmo que resuelve el problema de la planificación de tareas a plazo fijo?
- ALa solución obtenida es óptima.
- BUna solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1,2,2,3
- CUna solución posible, si se reflejan solo los tiempos de ejecución podría ser: 1, 3,2,3, 5
- DLa primera tarea en ejecutar será siempre la que tenga un plazo menor.
24¿cuál de las siguientes afirmaciones es cierta sobre los algoritmos voraces?
- AEl candidato seleccionado en una fase no influye en la selección de los candidatos en fases posteriores.
- BA priori no se sabe cuántos candidatos formarán parte de la solución.
- CLa función que se usa para seleccionar el candidato no tiene nada que ver con la función objetivo del problema en cuestión.
- DUn candidato ya seleccionado puede ser desechado en etapas posteriores.
25¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo voraz sobre el problema del viajante de comercio?
- ALa solución tiene n lados
- BLa solución tiene n lados (n - número de nodos)
- CTodas las respuestas son falsas
- DEn la solución puede haber más de dos lados que confluyen entrando y saliendo de un nodo
26¿Cuál de las siguientes afirmaciones es falsa sobre el algoritmo voraz sobre el problema del viajante de comercio?
- ALa solución obtenida es óptima
- BTodas las respuestas son ciertas
- CLa solución tiene n lados
- DTodos los nodos tendrán un lado de salida y uno de entrada
27¿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?
- ALa mejor opción en cada etapa es seleccionar siempre al paciente no atendido que requiere un mayor tiempo de atención
- BEl tiempo que el médico pasa en la consulta es siempre el mismo, independientemente de los pacientes
- CEl paciente atendido en primer lugar no es aquel que requiere menor tiempo de atencion
- DLa solución proporcionada se basa en un algoritmo voraz
28Cuando un ordenador ejecuta un proceso recursivo…
- ARealiza cálculos secuenciales basados en la iteración, simulando las llamadas recursivas haciendo uso de la pila
- BRealiza cálculos secuenciales basados en la iteración, simulando las llamadas recursivas haciendo uso del monton
- CRealiza cálculos recursivos haciendo uso del montón.
- DRealiza cálculos recursivos haciendo uso de la pila.
29¿Cuál de las siguientes afirmaciones es cierta sobre recursividad?
- AUn procedimiento recursivo requiere de más memoria que uno iterativo
- BUn procedimiento recursivo se implementa usando exclusivamente un caso general de descomposición.
- CUn procedimiento recursivo con una sola llamada siempre ha de tener un esquema iterativo para generar todas las llamadas recursivas
- DNinguna de las respuestas es correcta
30En la primera versión del algoritmo para multiplicar enteros grandes, ¿cuál de las siguientes afirmaciones es cierta?
- ANinguna de las respuestas es correcta
- BSi convertimos números enteros a doubles y los multiplicamos obtendremos el resultado aproximado
- CEl número de llamadas a recursivas se puede reducir a 3 usando sumas y restas
- DEs de O(n^2)
31¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de las torres de Hanoi?
- ANo se puede evitar las llamadas recursivas y su complejidad es O(2^n)
- BNo se puede evitar las llamadas recursivas y su complejidad es O(n^2)
- CSe puede evitar las llamadas recursivas y su complejidad es O(n)
- DSe puede evitar las llamadas recursivas y su complejidad es O(n^2)
32¿Cuál de las siguientes afirmaciones es cierta sobre algoritmo kruskal?
- AEn cada etapa se selecciona el lado más pequeño no seleccionado sin realizar ninguna comprobación adicional
- BLa solución tiene l-1 lados (l - número de lados)
- CLa solución tiene n-1 lados (n - número de nodos)
- DLa solución contendrá a los l-1 lados más pequeños del grafo
33¿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?
- ALas versiones mejoradas pueden reducir su complejidad algorítmica pero no el tiempo de ejecución del algoritmo
- BLas versiones mejoradas pueden reducir el tiempo de ejecución del algoritmo pero no su complejidad algorítmica
- CLas versiones mejoradas pueden reducir el tiempo de ejecución del algoritmo y su complejidad
- DLas versiones mejoradas no reducen el tiempo de ejecución ni su complejidad algorítmica
34En 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.
- Aw=u/10^n/2 y x=u%(10^n/2)
- BRESPUESTA VACÍA
- CRESPUESTA VACÍA 2
- DRESPUESTA VACÍA 3
Información
- Descripción
- ALGORITMICA
- Autor
- F. A. M.
- Idioma
- Español
- Visitas
- 397
- Etiquetas
- Valoración
- Aún sin valoraciones Valora este test