Test UNED PREDA - Examenes 2012-2016

Dado el grafo no dirigido de la figura, la aplicación del algoritmo de cálculo de los puntos de articulación (y de su árbol de recubrimiento asociado) da como resultado el vector bajo[] siguiente: [1,1,3,1,5,5,5]. [1,2,3,4,1,6,7]. [1,3,3,1,1,3,3]. Ninguna de las anteriores.

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado con programación dinámica. Supongamos que se dispone de 5 objetos con pesos: 1,3,4,5,7 y beneficios: 2,5,10,14,15 respectivamente, y un volumen máximo de 8. Identifica cuál de las siguientes respuestas correspondería al contenido de la tabla de resultados parciales en la fila correspondiente al objeto de peso 5, si dichos objetos se consideran en orden creciente de pesos. 0 2 2 5 10 12 12 15 15. 0 2 2 5 10 14 16 16 19. 0 2 2 5 10 12 14 16 19. Ninguna de las anteriores.

Dado el siguiente grafo dirigido: Se pide detallar el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=7, tomando como nodo origen el nodo 1. [10,15,12,6,15,7]. [10, ∞, ∞,6,15,7]. [10,∞,∞,6,∞,∞]. Ninguna de las anteriores.

En un problema de mochila con objetos fraccionables tenemos n = 8 objetos disponibles. Los pesos de los objetos son w= (8, 7, 6, 5, 4, 3, 2, 1) y los beneficios son v= (10, 9, 8, 7, 6, 5, 4, 3). ¿Cuál es el beneficio óptimo para este ejemplo, suponiendo que la capacidad de la mochila es M = 9?. 12. 15. 16.5. Ninguna de las anteriores.

Considérese el vector v[1..n] = [6,5,5,2,5,5,3,2,2] cuál de las siguientes opciones es cierta: El vector v es un montículo de máximos. El vector v no es un montículo de máximos porque el elemento v[4] = 2 debe ser flotado. El vector v no es un montículo de máximos porque el elemento v[4] = 2 debe ser hundido. Ninguna de las anteriores.

Se dispone de un vector, V, que almacena números enteros en orden estrictamente creciente, y se desea averiguar si existe algún elemento que cumpla V[i]=i. ¿Cuál sería la estrategia más eficiente para resolver el problema?. Algoritmo voraz. Divide y vencerás. Programación dinámica. Ninguna de las anteriores es aplicable al problema.

Una empresa de mensajería tiene n repartidores con distintas velocidades según el tipo de envío. Se trata de asignar los próximos n envíos, uno a cada repartidor, minimizando el tiempo total de todos los envíos. Para ello se conoce de antemano la tabla de tiempos T[1..n,1..n] en la que el valor tij corresponde al tiempo que emplea el repartidor i en realizar el envío j. Se pide: Voraz. Dinámica. Vuelta atrás. Ramificación y poda. Divide y vencerás.

Identifique cuál de las siguientes secuencias de código implementa un recorrido en anchura de una componente conexa de un grafo: a. b. c. ninguna de las opciones.

En una carrera de coches por el desierto uno de los principales problemas es el abastecimiento de gasolina. Uno de los participantes está decidido a ganar y ha calculado que con el tanque de gasolina lleno puede recorrer M km. sin parar. El participante dispone de un mapa que le indica las distancias entre las gasolineras que hay en la ruta y cree que, parándose a repostar el menor número de veces posible, podrá ganar. Para ayudarle hay que diseñar un algoritmo que le sugiera en qué gasolineras debe hacerlo. Hay que tener en cuenta que hay una única ruta posible. Indique de los esquemas siguientes cuál es el más adecuado: El esquema voraz. El esquema programación dinámica. El esquema de vuelta atrás. El esquema de ramificación y poda.

¿Cuántos componentes fuertemente conexos existen en el grafo de la siguiente figura?. Uno solo, formado por todo el grafo. Dos. Tres. Más de tres.

Dado el grafo no dirigido de la figura, indique cuál sería el orden en que se seleccionarían (pasan a pertenecer al árbol) los nodos al aplicar el algoritmo de Prim comenzando por el nodo A: A, F, E, C, B, D. A, B, C, E, D, F. A, C, D, B, F, E. Ninguno de los anteriores.

Dado el vector v=[5,6,9,3,4,1] y el algoritmo Quicksort, los vectores argumento de la primera invocación recursiva, con pivote v[1] = 5, son: [1,3,4,5] y [6,9]. [5,6,9] y [5,3,4,1]. [5] y [6,9,3,4,1]. [1] y [5,6,9,3,4].

Dado el problema de la mochila donde tenemos una mochila de capacidad M, n objetos con beneficios b1, b2, b3, … bn y pesos p1, p2, p3, … pn. y siendo el objetivo maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M, en el caso de que los objetos sean fraccionables, la resolución del mismo: Debe resolverse mediante un esquema voraz ya que no es eficiente realizarlo mediante ramificación y poda. Debe hacerse mediante ramificación y poda, ya que no es posible resolverlo utilizando un esquema voraz. Sólo puede resolverse mediante un esquema de programación dinámica. Puede hacerse mediante un esquema voraz pero no es posible resolverlo mediante ramificación y poda.

Se quiere realizar en un soporte secuencial (cinta de dos caras) una recopilación de canciones preferidas. Se dispone de una lista de n canciones favoritas, junto con la duración individual de cada una. Lamentablemente, la cinta de T minutos no tiene capacidad para contener todas las canciones, por lo que se les ha asignado una puntuación (cuanto más favorita es, mayor es la puntuación). Se pretende obtener la mejor cinta posible según la puntuación, teniendo en cuenta que las canciones deben caber enteras y no es admisible que una canción se corte al final de una de las caras. Voraz. Ramificación y poda. Divice y vencerás. Programación dinámica. Vuelta atrás.

Considérese el vector [10,7,7,4,3,1] que representa un montículo. ¿Cuál sería la representación resultante de insertar en este montículo el valor 11 usando la función flotar?. [11,7,7,4,3,1,10]. [10,7,11,4,3,1,7]. [10,7,11,4,3,1,7]. Ninguna de las opciones anteriores.

Los residentes de una ciudad no quieren pavimentar todas sus calles (que son de doble sentido), sino sólo aquellas que les permitan ir de una intersección a otra cualquiera de la ciudad con comodidad. Quieren gastarse lo menos posible en la pavimentación, teniendo en cuenta que el coste es directamente proporcional a la longitud de las calles que hay que pavimentar. El alcalde querría saber qué calles tiene que pavimentar para gastarse lo menos posible. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.

Suponga un algoritmo que dadas dos listas de tamaños n y m: A = a1,. . .an y B = b1,. . . ,bm dé como resultado la lista de aquellos elementos que pertenecen a A pero no a B. Se asume que A y B no contienen elementos duplicados, pero no que éstos estén acotados. Indique cuál de los siguientes costes se ajusta más al del algoritmo que puede resolver el problema con menor coste: O(n log m + m log m). O(n log m + m2). Máx (O (n log n), O(m log m)). O(nm).

Dado un grafo con n vértices y a aristas sobre el que se pueden realizar las siguientes operaciones: esAdyacente, borrarVertice y añadirVertice. ¿Cuál es la complejidad de cada una de las operaciones anteriores según se utilice una matriz de adyacencia (MA) o una lista de adyacencia (LA)?. a. b. c. d.

Indique cuál de las siguientes afirmaciones es cierta: La programación dinámica se puede emplear en muchos de los problemas que se resuelven utilizando el esquema divide y vencerás. La programación dinámica tiene como principal ventaja que supone un decremento tanto en coste computacional como en espacio de almacenamiento. El esquema de programación voraz se aplica a problemas de optimización en los que la solución se puede construir paso a paso comprobando, en cada paso, la secuencia de decisiones tomadas anteriormente. El esquema de ramificación y poda es el más indicado a utilizar en el caso que se deseen encontrar todas las soluciones posibles a un problema dado.

En el recorrido mediante doble hashing, la función h’(x) debe cumplir: Necesariamente debe ser h’(x) ≠ 0. h’(x) debe tener la forma h’(x) = 2h(x) + c, con c constante. Se debe cumplir que h’(x) < h(x) + c, con c constante. Ninguna de las anteriores es cierta.

Teseo se adentra en el laberinto en busca de un minotauro que no sabe dónde está. Se trata de implementar una función ariadna que le ayude a encontrar el minotauro y a salir después del laberinto. El laberinto debe representarse como una matriz de entrada a la función cuyas casillas contienen uno de los siguientes tres valores: 0 para “camino libre”, 1 para “pared” (no se puede ocupar) y 2 para “minotauro”. Teseo sale de la casilla (1,1) y debe encontrar la casilla ocupada por el minotauro. En cada punto, Teseo puede tomar la dirección Norte, Sur, Este u Oeste siempre que no haya una pared. La función ariadna debe devolver la secuencia de casillas que componen el camino de regreso desde la casilla ocupada por el minotauro hasta la casilla (1,1). Voraz. Divide y vencerás. Ramificación y poda. Vuelta atrás. Programación dinámica.

Sea el grafo dirigido de la siguiente figura. ¿Cual de las siguientes afirmaciones es cierta?. Un posible recorrido en anchura visitaria los nodos en orden {D,B,C,E,F,A,G}, si se toma el nodo D como nodo de partida. Un posible recorrido en profundidad visitaria los nodos en orden {D,B,E,A,G,C,F}, si se toma el nodo D como nodo de partida. El nodo E es un punto de articulación. Todas las afirmaciones son ciertas.

Indique cual de las siguientes afirmaciones es cierta. El coste del algoritmo para fusionar dos subvectores ordenados que se utiliza en la ordenación por fusión es O(n), siendo n la suma de los tamaños de los vectores. El coste del algoritmo que soluciona el problema del coloreado de grafos mediante el esquema de vuelta atrás es O(N^M) siendo m el número de colores y n el número de nodos. El coste del algoritmo de Kruskal es O(N^2) siendo n el número de nodos del grafo. El coste del algoritmo de ordenación rápida en el caso mejor es O(n^2) siendo n el número de elementos de larray.

Considéres el vector v[1..n] = [2,3,5,3,4,5,7,5,6]. Indica cuál de las siguientes opciones es cierta: Es un montículo de mínimos. No es un montículo de mínimos porque v[5] = 4 debe ser flotado. No es un montículo de mínimos porque v[5] = 4 debe ser hundido. Ninguna de las anteriores.

Sea el problema de la mochila, en el que tenemos una mochila de capacidad M, n objetos con beneficios b1,b2,b3,...,bn y pesos p1,p2,p3,...,pn. El objetivo es maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M. Indica, de los esquemas siguientes, cuál es el más adecuado y eficiente en el caso de que cada objeto pueda meterse en la mochila entero o fraccionado. El esquema voraz utilizando como criterio de selección escoger el objeto de más valor de los que quedan. El esquema voraz utilizando como criterio de selección el objeto cuyo valor por unidad de peso sea el mayor de las que quedan. El esquema de vuelta atrás calculando todas las soluciones posibles y escogiendo la mejor. El esquema de ramificación y poda.

Para resolver un determinado problema hemos diseñado un algoritmo de tipo divice y vencerás. ¿Cuál de las siguientes afirmaciones es falsa?. La resolución debe alcanzar un caso trivial que se pueda resolver sin realizar nuevas descomposiciones. El problema se resuelve por divisiones sucesivas en subproblemas, que pueden ser demayor o de menor tamaño que el de partida. Los algoritmos basados en este esquema pueden requerir un paso de combinación de las soluciones parciales. El algoritmo de la búsqueda binaria aplica la estrategia divide y vencerás.

Sea un procesador que ha de atender n procesos. Se conoce de antemano el tiempo que necesita cad aproceso. Se desea determinar en qué orden se han de atender los procesos par aminimizar la suma del tiempo que los procesos permanecen en el sistema. En relación a este problema, ¿cuál de las siguientes afirmaciones es cierta?. El coste del algoritmo voraz que resuelve el problema es, en el mejor de los casos, O(N^2). Suponiendo tres clientes con tiempos de servicio t1=5, t2=10 y t3=3, el tiempo mínimo de estancia posible es de 26 segundos. Suponiendo tres clientes con tiempos de servicio t1=5, t2=10 y t3=3, el tiempo mínimo de estancia posible es de 31 segundos. Todas las afirmaciones anteriores son falsas.

Dado el conjunto de carácteres alfabéticos, se quieren generar todas las palabras de cuatro letras que cumplan las siguientes condiciones: La primera letra debe de ser vocal, Solo pueden aparecer dos vocales seguidas si son diferentes, No puede haber ni tres vocales ni tres consonantes seguidas, Existe un conjunto C de parejas de consonantes que no pueden aparecer seguidas. Desarrolla un algoritmo que permita solucionar este problema con el menor coste. Voraz. Dinamica. Ramificación y poda. Vuelta atrás. Divide y vencerás.

Se tiene una tabla hash con n= 23 índices ocupados y de tamaño M= 1000. El factor de carga δ será: 0,023, es decir n/M. 0,046, es decir 2n/M. -3,7723, es decir Ln (n/M). Ninguna de las anteriores.

Dado el siguiente grafo dirigido indique cuál sería el valor del vector especial[] en el primer y penúltimo paso del algoritmo de Dijkstra: [50,30,100,10] y [35,30,20,10]. [50,30,100,10] y [40,30,20,10]. [50,30,100,10] y [35,30,100,10]. Ninguna de las anteriores.

Considere dos vectores f y g de n elementos que representan los valores que toman dos funciones en el intervalo [0..n-1]. Los dos vectores están ordenados, pero el primero f es un vector estrictamente creciente (f[0] < f[1] < … < f[n-1]), mientras g es un vector estrictamente decreciente (g[0] > g[1]>…> g[n-1]). Las curvas que representan dichos vectores se cruzan en un punto concreto, y lo que se desea saber es si dicho punto está contenido entre las componentes de ambos vectores, es decir, si existe un valor i tal que f[i] = g[i] para 0 ≤ i ≤ n 1. La figura muestra un ejemplo en el que las gráficas se cruzan en i=8 que se corresponde con el valor 25 en ambas curvas. Se busca un algoritmo que compruebe si el punto de cruce está contenido en las componentes de ambos vectores. ¿Cuál de las siguientes opciones es cierta?. Se puede encontrar un algoritmo recursivo de coste logarítmico. El algoritmo más eficiente que se puede encontrar es O(n). El algoritmo más eficiente que se puede encontrar es O(n2). Ninguna de las anteriores.

¿Cuál de las siguientes afirmaciones es falsa?. El algoritmo de ordenación por fusión (mergesort) es O(n log n). La eficiencia del algoritmo de ordenación rápida (quicksort) es independiente de que el pivote sea el elemento de menor valor del vector. El algoritmo de ordenación rápida en el caso peor es O(n2). El algoritmo de ordenación basada en montículos (heapsort) es O(n log n).

¿Cuál de las siguientes afirmaciones es falsa?. El grado de un vértice de un grafo no dirigido es el número de aristas que salen o entran en él. Un camino en un grafo dirigido es una secuencia finita de arcos entre dos vértices, tal que el vértice del extremo final de cada arco coincide con el del extremo inicial del arco siguiente. Un grafo nulo es un grafo sin vértices. La longitud de un camino es el número de aristas y nodos que contiene.

Dado el siguiente montículo indique cual de las siguientes afirmaciones es falsa. El montículo propuesto es un montículo de máximos. El vector que lo representa de forma correcta es [15,13,12,8,9,5,8,7,5,3,4,2]. El orden de complejidad de la operación de inserción de un nuevo elemento en el montículo es O(n). Los montículos son estructuras de datos de gran utilidad a la hora de implementar colas de prioridad.

Se tienen 3 palos verticales y n discos agujereados por el centro. Los discos son todos de diferente tamaño y en la posición inicial están insertados en el primer palo ordenados en tamaños en sucesión decreciente desde la base hasta la altura. El problema consiste en pasar los discos del 1er al 3er palo, utilizando el segundo como auxiliar, observando las siguientes reglas: a) Se mueven los discos de 1 en 1. b) Nunca un disco puede colocarse encima de uno menor que éste. Voraz. Ramificación y poda. Divide y vencerás. Programación dinámica. Vuelta atrás.

¿Cuál de las siguientes afirmaciones es cierta con respecto al coste de algunos algoritmos y su eficiencia?. El algoritmo de Kruskal tiene un coste que está en O(n log n). El algoritmo de Prim cuando se combina el uso de la lista de adyacencia con el uso de un montículo es más eficiente cuando el grafo es denso porque de esta manera el coste está en O(n2 log n). El coste del algoritmo Quicksort en el caso peor es de orden O(n log n). La función que crea un montículo a partir de una colección de valores, si se utiliza el procedimiento Hundir puede llegar a tener un coste lineal.

Sea un grafo no dirigido representado con la siguiente matriz de adyacencia: Si se utiliza el algoritmo de Kruskal para calcular un árbol de recubrimiento mínimo, indica cuál de las siguientes secuencias de aristas (que incluye las rechazadas) representa el orden en el que las evalúa el algoritmo: {5,7},{2,4},{4,6},{3,4},{2,3},{1,5},{6,7}. {5,7},{2,4},{4,6},{3,4},{1,5},{6,7},{5,6}. {5,7},{1,5},{6,7},{4,6},{2,4},{4,3}. {1,5},{5,7},{6,7},{4,6},{2,4},{4,3}.

Con respecto a la resolución de colisiones en las funciones Hash, indicar cuál de las siguientes afirmaciones es cierta: El recorrido lineal permite mayor dispersión de las colisiones que el cuadrático. Si el factor de carga es 1 se puede resolver mediante hashing cerrado. El hashing abierto contempla un método de resolución conocido como “recorrido mediante doble hashing”. Ninguna de las anteriores es correcta.

Durante la ejecución de un algoritmo de Ramificación y Poda se halla una solución que es mejor que la mejor solución existente en ese momento y que mejora la estimación optimista de la cima del montículo. Esto implica que: Definitivamente el algoritmo ha encontrado la solución. Se actualiza la cota y se sigue con la exploración porque no hemos terminado. Se actualiza la cima del montículo y se sigue con la exploración porque no hemos terminado. Ninguna de las anteriores es correcta.

Dado el siguiente grafo, indique cuál sería el orden en que se seleccionarían los nodos (pasan a estar explorados) al aplicar el algoritmo de Dijkstra para encontrar todos los caminos de menor coste desde el nodo 1: {1, 2, 4, 3, 5}. {1, 4, 3, 5, 2}. {1, 2, 3, 4, 5}. Ninguna de las anteriores.

Considérese el vector [10,6,3,5,2,3,2] que representa un montículo. ¿Cuál sería la representación resultante de insertar (función Insertar del texto base) en este montículo el valor 6 usando la función flotar?. [10,6,6,3,3,2,5,2]. [10,6,5,3,6,2,2,3]. [10,6,3,6,2,3,2,5]. Ninguna de las opciones anteriores.

Una pareja decide divorciarse tras 10 años de matrimonio. Deciden repartir su patrimonio a partes iguales. Cada uno de los n activos (indivisibles) que hay que repartir tiene un valor entero positivo. Los cónyuges quieren repartir dichos activos a medias y, para ello, primero quieren comprobar si el conjunto de activos se puede dividir en dos subconjuntos disjuntos, de forma que cada uno de ellos tenga el mismo valor. Voraz. Divide y vencerás. Ramificación y poda. Programación dinámica. Vuelta atrás.

Indique cuál de las siguientes afirmaciones es cierta: El esquema de divide y vencerás obtiene siempre soluciones eficientes de coste O(log n) o O(n·log n). La búsqueda en profundidad recursiva obtiene siempre una eficiencia logarítmica. La ordenación por Quicksort tiene coste O(n2) en el caso peor. Ninguna de las anteriores es cierta.

¿Cuántos componentes fuertemente conexos existen en el grafo de la siguiente figura?. Uno solo, formado por todo el grafo. Dos. Tres. Más de tres.

El enemigo ha desembarcado en nuestras costas invadiendo n ciudades. Los servicios de inteligencia han detectado del número de efectivos enemigos en cada ciudad, ei. Para contraatacar, se dispone de n equipos listos para intervenir y hay que distribuirlos entre las n ciudades. Cada uno de estos equipos consta de dj efectivos entrenados y equipados. Para garantizar el éxito de la intervención en una ciudad es necesario que contemos al menos con tantos efectivos de defensa como el enemigo. Se busca un algoritmo que indique qué equipo debe intervenir en cada ciudad, de forma que se maximice el número de éxitos garantizados. Indica cuál de las siguientes afirmaciones es cierta: El esquema de ramificación y poda es el único que puede resolver de forma óptima el problema. Se puede encontrar una estrategia voraz que permita resolver el problema. El esquema de programación dinámica es el único que puede resolver de forma óptima el problema. El esquema de vuelta atrás es el más apropiado para resolver este problema.

Indica de entre los siguientes, cuál sería el coste mínimo de un algoritmo que dado un vector C[1..n] de números enteros distintos no ordenado, y un entero S, determine si existen o no dos elementos de C tales que su suma sea exactamente S. O(N). O(N^2). O(n log(n)). O(N^2 log(n)).

Dado el siguiente grafo no dirigido: Indique cuál sería el orden en que se seleccionarían las aristas al aplicar el algoritmo de Kruskal: {{A,C},{C,D},{C,B},{B,E},{D,F}}. {{A,C},{B,E},{C,D},{C,B},{A,F}}. {{A,C},{C,D},{A,B},{B,E},{A,F}}. Ninguna de las anteriores.

Indique cuál de las siguientes afirmaciones es cierta: El enfoque de vuelta atrás realiza un recorrido en anchura del árbol implícito que representa el espacio de posibles soluciones del problema. Si se utiliza el enfoque de programación dinámica para calcular el camino de coste mínimo entre cada par de nodos de un grafo, la complejidad temporal es de O(n2). Cuando ambos son aplicables, el enfoque de ramificación y poda se comporta de manera más eficiente que el enfoque voraz en la resolución de problemas de optimización. El hecho de utilizar un algoritmo voraz para obtener la solución de un problema no garantiza que la solución obtenida sea la óptima.

Se considera un tablero n x n y un conjunto de n colores. Cuando a cada casilla se le asigna un color de los n disponibles de tal manera que no se repiten colores en ninguna fila ni en ninguna columna, el tablero se conoce como cuadrado latino. La siguiente figura muestra un ejemplo para n = 5: Se pide diseñar un algoritmo que dados n colores presente todos los cuadrados latinos para un tablero nxn. Voraz. Ramificación y poda. Programación dinámica. Divice y vencerás. Vuelta atrás.

Considérese el vector v=[2,6,8,12,7,5,4]. ¿Cuál de las siguientes opciones es cierta?. El vector v es un montículo de mínimos. v sería un montículo de mínimos si se flotara el elemento de valor 5. v sería un montículo de mínimos si se hundiera el elemento de valor 8. Ninguna de las opciones anteriores.

En el problema de colorear un grafo con n nodos utilizando m colores, de manera que no haya dos vértices adyacentes que tengan el mismo color, una cota superior ajustada del coste de encontrar una solución utilizando un esquema adecuado es del orden de: O(n^2). O(m^n). O(m log n). O(n^m).

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado mediante programación dinámica. Suponga que se dispone de 5 objetos con volúmenes {1,2,5,6,7} y que aportan unos beneficios de {1,6,18,22,28}, respectivamente. Suponga también que dispone de una mochila con una capacidad máxima de 11. Indique cuál sería el contenido de la tabla de resultados parciales en la fila correspondiente al objeto de peso 7, si dichos objetos se consideran en orden creciente de pesos. 0 1 6 7 7 18 19 24 25 25 28 29. 0 1 6 7 7 18 22 24 28 29 29 40. 0 1 6 7 7 18 22 28 29 34 35 40. Ninguna de las anteriores.

Dado el siguiente grafo dirigido: Indique el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=4, tomando como nodo origen el nodo 1: [∞, 30,40, ∞]. [50, 30,40, ∞]. [55, 30,40, 80]. Ninguna de las anteriores.

Indica cuál de las siguientes afirmaciones es cierta con respecto a la resolución de colisiones: El método de hashing abierto es siempre más eficiente que el hashing cerrado para la resolución de colisiones. En el método de hashing cerrado con recorrido lineal existe una probabilidad muy baja de colisiones independientemente de los patrones de las claves. En el método de hashing cerrado con recorrido cuadrático es posible garantizar que se van a recorrer todos los elementos de la tabla cuando el número de elementos de la tabla, m, cumple determinadas condiciones. En el método de hashing cerrado con recorrido mediante doble hashing la función h y h’ que se aplican pueden ser iguales cuando el número de elementos de la tabla, m, cumple determinadas condiciones.

Se dispone de cuatro tipos de monedas de valores 1, 2, 4 y 8. Se desea resolver el problema de pagar una cantidad C > 0 utilizando un número mínimo de monedas y suponiendo que la disponibilidad de cada tipo de moneda es ilimitada. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.

La agencia matrimonial Celestina & Co. quiere informatizar parte de la asignación de parejas entre sus clientes. Cuando un cliente llega a la agencia se describe a sí mismo y cómo le gustaría que fuera su pareja. Con la información de los clientes la agencia construye dos matrices M y H que contienen las preferencias de los unos por los otros, tales que la fila M[i, .] es una ordenación de mayor a menor de las mujeres cliente según las preferencias del i-ésimo hombre, y la fila H[i, .] es una ordenación de mayor a menor de los hombres cliente según las preferencias de la i-ésima mujer. Por ejemplo, M[i,1] almacenaría a la mujer preferida por el hombre i y M[i,2] a su segunda mujer preferida. Dado el alto índice de divorcios, la empresa se ha planteado como objetivo que los emparejamientos sean estables. Se considera que una pareja (h , m) es estable si no se dan las siguientes situaciones: 1. Que exista una pareja (h’, m’) con una mujer m’ tal que el hombre h la prefiere sobre la mujer m y además la mujer m’ también prefiere a h sobre h’. 2. Que exista una pareja (h’’, m’’) con un hombre h’’ tal que la mujer m lo prefiere sobre el hombre h y además el hombre h’’ también prefiere a m sobre m’’. La agencia quiere que dadas las matrices de preferencia, un programa establezca parejas evitando las dos situaciones descritas anteriormente. Se pide: Voraz. Ramificación y poda. Programación dinámica. Divide y vencerás. Vuelta atrás.

Dos socios que conforman una sociedad comercial deciden disolverla. Cada uno de los n activos que hay que repartir tiene un valor entero positivo. Los socios quieren repartir dichos activos a medias y, para ello, primero quieren comprobar si el conjunto de activos se puede dividir en dos subconjuntos disjuntos, de forma que cada uno de ellos tenga el mismo valor. ¿Cuál de los siguientes esquemas de los que puedan resolver el problema correctamente es más eficiente?. Esquema voraz. Esquema de divide y vencerás. Esquema de vuelta atrás. Esquema de ramificación y poda.

Dadas las matrices: A1 (2x2), A2 (2x5) y A3 (5x3) y A4 (3x1) siendo E(i,j) el número de operaciones mínimo para resolver la operación Ai x Ai+1 x … x Aj mediante programación dinámica, se pide indicar cuál de las siguientes opciones es cierta. E(2,4) = 25. E(3,4) = 10. E(1,2) = 40. E(2,2) = 10.

Aplicando el algoritmo de Dijkstra al grafo con conjunto de vértices {1,2,…8} y aristas con pesos (entre paréntesis) representadas por la lista de adyacencia adjunta, ¿Cuál de las siguientes NO es un valor correcto para el vector “Especial” D[i] generado por el algoritmo de Dijkstra a lo largo de las iteraciones, representando en cada iteración la distancia mínima hasta el momento entre los vértices 1 e i:?. D = [4,10,2, ∞,8, ∞,∞]. D = [4,10,2, 4,3, 7,∞]. D = [4,9,2, 4,3, 7,∞]. D = [4,10,2, 4,3, 7,19].

Dado el vector M= [5, 6, 12, 1, 7, 9, 3, 7, 1, 11, 3, 2, 8, 6, 5, 9] al que aplicamos el algoritmo de ordenación Quicksort tomando como pivotes los valores M[0] y para una ordenación de menor a mayor. Se pide contestar la opción verdadera: La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [3 5 2 1 3 1 ] y [7 9 11 7 12 8 6 6 9 ] con pivote M[0] = 5. La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [6 12 1 7 9 3 7] y [1 11 3 2 8 6 5 9] con pivote M[0] = 5. La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [1 1 2 3 3 5] y [6 6 7 7 8 9 9 11 12] con pivote M[0] = 5. La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [1 3 6 7 7 9 12] y [1 2 3 5 6 8 9 11] con pivote M[0] = 5.

El problema de la liga de equipos consiste en que dados n equipos con n= 2k, se desea realizar una liga de forma que cada equipo puede jugar un partido al día y la liga debe celebrarse en n-1 días, suponiendo que existen suficientes campos de juego. El objetivo sería realizar un calendario que indique el día que deben jugar cada par de equipos. Si este problema se resuelve con un esquema divide y vencerás, considerando que el caso trivial se da cuando la liga consta de 2 equipos, la descomposición se realiza dividiendo el problema en dos partes similares, y la combinación se produce dando los subproblemas por resueltos y aplicando el principio de inducción. Indica de entre los siguientes, cuál sería el coste mínimo de dicho algoritmo. O(N). O(N^2). O(N*logn). O(N^2logn).

Sea un grafo denso no dirigido representado con la siguiente matriz de adyacencia, en la que puede haber pesos de valor 0: Si se utiliza el algoritmo de Prim para calcular un árbol de recubrimiento mínimo tomando como raíz del árbol el nodo 1, indica cuál de las siguientes secuencias de aristas representa el orden en el que las selecciona el algoritmo de Prim como integrantes del árbol de recubrimiento mínimo: {1,6},{1,7},{6,2},{6,3},{4,6},{6,5},{6,8}. {1,6},{6,2},{2,3},{3,8},{4,6},{6,5},{6,7}. {1,7},{1,6},{6,3},{6,2},{4,6},{6,5},{6,8}. {1,6},{1,2},{2,3},{4,6},{6,5},{6,8},{6,7}.

Se tiene una colección de n objetos “moldeables”, cada uno con un volumen vi, para i entre 1 y n, que hay que empaquetar utilizando envases de capacidad E. Se busca un algoritmo que calcule el empaquetamiento óptimo, es decir, que minimice la cantidad de envases utilizados, teniendo en cuenta que los objetos no se pueden fraccionar. Se pide. Voraz. Ramificación y poda. Programación dinámica. Divide y vencerás. Vuelta atrás.

Una filmoteca ha organizado un maratón de cortometrajes. Durante 24 horas se proyectarán cortos de cine (todos diferentes) en las n salas disponibles. Un cinéfilo ha conseguido la programación completa donde aparecen todas las películas que se van a proyectar durante el maratón, incluyendo el título, duración del corto, sala en la que se proyecta y hora de comienzo. Si se quiere planificar el maratón del cinéfilo de forma que pueda ver el máximo número posible de Cortos, ¿Cuál es el esquema más apropiado para hacer la planificación eficientemente?. Esquema voraz. Divide y vencerás. Esquema de vuelta atrás. Esquema de ramificación y poda.

Considérese el vector v1.n) = 8,6,5,5,4,3,2,2). Indique cuál de las siguientes opciones es Cierta: El vector v es un montículo de máximos. El vector v no es un montículo de máximos porque el elemento v5) = 4 debe ser flotado. El vector v no es un montículo de máximos porque el elemento v4) = 5 debe ser hundido. Ninguna de las anteriores.

Sea el problema de la mochila, en el que tenemos una mochila de capacidad M, n objetos con beneficios b1, b2, b3, ... bn y pesos p, p2 p3. p. El objetivo es maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M. Indica de los esquemas siguientes cuál es el más adecuado en el caso de que cada objeto puede meterse en la mochila, no meterse, o meter la mitad del objeto obteniendo la mitad del beneficio. El esquema voraz. El esquema divide y vencerás. El esquema de vuelta atrás. El esquema de ramificación y poda.

Sea el grafo de la figuraIndique cuál sería el orden en que se seleccionan los nodos del conjunto de candidatos al aplicar el algoritmo de Dijkstra comenzando por el nodo A: A C B D E F. A B C D E F. A B D C F E. Ninguna de las anteriores.

En relación a la representación de grafos mediante listas de adyacencia, indique cuál de las siguientes afirmaciones es falsa. Sean el número de nodos del grafo, necesitaremos n listas para representarlo. Si el grafo presenta pocas aristas, es más eficiente en espacio representarlo mediante listas de adyacencia que representarlo mediante una matriz de adyacencia. El coste asociado a la operación Borrar Arista es O(n+a), siendo n el número de nodos del grafo y siendo a el número de aristas. El coste asociado a la operación Añadir Vértice es O(1).

Indica cuál de las siguientes afirmaciones es cierta: Un árbol libre es un grafo acíclico, conexo y dirigido. Un ciclo es un camino simple que empieza y termina en el mismo vértice. Si un grafo tiene pocas aristas las listas de adyacencia resultan una estructura más costosa en espacio que la matriz de adyacencia. Ninguna de las definiciones anteriores es completa y cierta.

Desarrollar un programa que compruebe si es posible que un caballo de ajedrez, mediante una secuencia de sus movimientos permitidos, recorra todas las casillas de un tablero NxN a partir de una determinada casilla dada como entrada y sin repetir ninguna casilla. Vuelta atrás. Ramificación y poda. Voraz. Programación dinámica. Divide y vencerás.

Considérese el vector v=[2,6,8,12,7,5,4]. ¿Cuál de las siguientes opciones es cierta?. El vector v es un montículo de mínimos. v sería un montículo de mínimos si se flotara el elemento de valor 5. v sería un montículo de mínimos si se hundiera el elemento de valor 8. Ninguna de las opciones anteriores.

En el problema de colorear un grafo con n nodos utilizando m colores, de manera que no haya dos vértices adyacentes que tengan el mismo color, una cota superior ajustada del coste de encontrar una solución utilizando un esquema adecuado es del orden de: O(n^2). O(m^n). O(m log n). O(n^m).

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado mediante programación dinámica. Suponga que se dispone de 5 objetos con volúmenes {1,2,5,6,7} y que aportan unos beneficios de {1,6,18,22,28}, respectivamente. Suponga también que dispone de una mochila con una capacidad máxima de 11. Indique cuál sería el contenido de la tabla de resultados parciales en la fila correspondiente al objeto de peso 7, si dichos objetos se consideran en orden creciente de pesos. 0 1 6 7 7 18 19 24 25 25 28 29. 0 1 6 7 7 18 22 24 28 29 29 40. 0 1 6 7 7 18 22 28 29 34 35 40. Ninguna de las anteriores.

Dado el siguiente grafo dirigido: Indique el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=4, tomando como nodo origen el nodo 1: [∞, 30,40, ∞]. [50, 30,40, ∞]. [55, 30,40, 80]. Ninguna de las anteriores.

Indica cuál de las siguientes afirmaciones es cierta con respecto a la resolución de colisiones: El método de hashing abierto es siempre más eficiente que el hashing cerrado para la resolución de colisiones. En el método de hashing cerrado con recorrido lineal existe una probabilidad muy baja de colisiones independientemente de los patrones de las claves. En el método de hashing cerrado con recorrido cuadrático es posible garantizar que se van a recorrer todos los elementos de la tabla cuando el número de elementos de la tabla, m, cumple determinadas condiciones. En el método de hashing cerrado con recorrido mediante doble hashing la función h y h’ que se aplican pueden ser iguales cuando el número de elementos de la tabla, m, cumple determinadas condiciones.

Se dispone de cuatro tipos de monedas de valores 1, 2, 4 y 8. Se desea resolver el problema de pagar una cantidad C > 0 utilizando un número mínimo de monedas y suponiendo que la disponibilidad de cada tipo de moneda es ilimitada. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.