PREDA - 22, 23, 24

Si realizáramos un recorrido en anchura partiendo del nodo 2, indica cuál de las siguientes afirmaciones sería cierta con respecto al contenido de la estructura de datos cola que dirige el recorrido, si los adyacentes a un nodo se almacenan en orden no decreciente: En un determinado paso, el contenido de la cola sería (4,5,6). En un determinado paso, el contenido de la cola sería (4,5,7). En un determinado paso, el contenido de la cola sería (4,7). Ninguna de las anteriores.

Indique cuál de las siguientes afirmaciones es cierta: El problema de calcular el camino de coste mínimo entre cada par de nodos de un grafo (es decir, desde todos los nodos hasta todos los restantes nodos) se resuelve utilizando el algoritmo de Dijkstra con una complejidad total de O(N^2). La programación dinámica es aplicable a muchos problemas de optimización siempre que no se cumpla el Principio de Optimalidad de Bellman. La programación dinámica no es apropiada para resolver problemas que pueden descomponerse en subproblemas más sencillos en los que haya llamadas repetidas en la secuencia de llamadas recursivas. En un algoritmo de vuelta atrás es posible retroceder para deshacer una decisión ya tomada, ya que las soluciones se construyen de forma incremental y es posible retroceder cuando se llega a un nodo de f.

Dado el grafo de la figura, al aplicar el algoritmo de Kruskal: La arista (1,2) será rechazada. La arista (1,3) será rechazada. La arista (4,6) será seleccionada. Ninguna de las anteriores es cierta.

Sea una tabla hash de tamaño m=13. Se quieren resolver las colisiones mediante hashing cerrado con doble hashing siendo h1(k)=k mod m y h2(k) = (k mod(m-3)) y con función de paso h(k,i)= (h1(k) + 2ih2(k)) mod m. Al insertar la secuencia [12,13,21,54,7,3] obtenemos. [13,-,54,3,-,-,-,7,21,-,-,-,12]. [-,54,3,-,-,-,-,7,-,21,12,13,-]. [-,12,-,-,-,54,13,-,7,3,21,-,-]. Ninguna de las anteriores.

Dado el vector v= [17,13,10,8,7,11,9], es posible afirmar que: El vector v es un montículo de máximos. El vector v sería un montículo de máximos si se flotara el elemento de valor 9. El vector sería un montículo de máximos si se flotara el elemento de valor 11. Ninguna de las opciones anteriores es cierta.

Sea el grafo no dirigido representado por la siguiente matriz de adyacencia. Indique cuál de las siguientes afirmaciones es falsa: El árbol de recubrimiento mínimo calculado por el algoritmo de Prim es {{A,B}, {A,C},{B,D},{D,G},{G,F},{G,E}}. ) Si se elimina el vértice F y todas las aristas que se inician o terminan en él, el nuevo árbol de recubrimiento es es {{A,B}, {A,C},{B,D},{D,G},{G, E}}. El borrado del vértice F tiene un coste lineal. Ninguna de las anteriores es cierta.

Dado el grafo siguiente y considerando el algoritmo de Kruskal para calcular el árbol de recubrimiento mínimo asociado y la tabla que registra el seguimiento de dicho algoritmo de la forma: (imagen de abajo) Indica cuál de las siguientes afirmaciones es cierta: En el paso 3 se añade al árbol de recubrimiento AR la arista {1,5}. En el paso 4 las componentes conexas son: {1,4,7}{3,2,5}{6}. En el desarrollo del algoritmo, las aristas {5,4} y {3,6} se podrían seleccionar al tener el mismo coste pero la que finalmente se añade al árbol de recubrimiento AR es la arista {3,6}. Ninguna de las anteriores es cierta.

Para el siguiente grafo, al que queremos aplicar el algoritmo de cálculo de puntos de articulación, y suponiendo que el inicial es el 1 y que, a igual prioridad, se elige el nodo menor, el valor de numOrden[] es: [1,2,3,4,5,7,8,6]. [1,2,3,4,5,6,7,8]. [1,2,3,4,6,5,7,8]. Ninguna de las anteriores.

Con relación a las tablas hash, indique cuál de las siguientes afirmaciones es falsa: En la función hash de tipo multiplicación, se requiere la normalización de los valores de entrada. El encadenamiento directo es una de las formas de resolver que utiliza estructuras de almacenamiento externas. En el recorrido cuadrático se utiliza una segunda función hash denominada función de paso. El factor de carga es un valor crítico a la hora de diseñar una tabla hash y debe mantenerse por debajo del 50%.

Sea el vector v[1..n] =[14,23,14,24,23,14,23,24]. ¿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 v[7]. v sería un montículo de máximos si se hundiera el elemento v[7]. Ninguna de las opciones anteriores.

Dado el siguiente grafo dirigido, se pide el orden de selección de los nodos de acuerdo con el algoritmo de Dijkstra suponiendo que el origen es el nodo 1. 1,4,2,3,5,6,7. 1,4,2,5,3,6,7. 1,4,2,3,7,5,6. Ninguna de las anteriores.

Indica de entre los costes 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. Θ(n). Θ(n log n). Θ(n^2). Θ(n^2 log n).

Considerando el algoritmo de ordenación por fusión y el siguiente vector para ordenar [83, 7, 13, 2, -5, 30, -7, 1 00], indica cuál de las siguientes afirmaciones es cierta, teniendo en cuenta que no se utiliza otro algoritmo para tamaños pequeños de los vectores: Una de las fusiones se produce con los vectores [2,-7,13,83] y [-5, 7,30, 1 00]. Una de las fusiones se produce con los vectores [7,83] y [2, 13]. Una de las fusiones se produce con los vectores [7,83] y [-5,30]. Ninguna de las anteriores es cierta.

Sea el grafo de la siguiente figura: Indique cuál de las siguientes afirmaciones es cierta: El grafo es fuertemente conexo. Es un grafo simple y acíclico. Es un grafo débilmente conexo con tres componentes conexas. Ninguna de las opciones anteriores es cierta.

¿Cuál de las siguientes afirmaciones es falsa?. El coste del algoritmo de ordenación por fusión (Mergesort) es O(n log n). En una tabla hash se recomienda que el factor de carga o esté por debajo del 50%. Determinar si dos nodos son adyacentes se calcula de forma más eficiente si se utiliza para representar el grafo una matriz de adyacencia que si se utiliza una lista de adyacencia. En el problema del cálculo de caminos de coste mínimo entre los nodos de un grafo dirigido, el algoritmo de Floyd es preferible para grafos dispersos, mientras que el de Dijkstra es preferible para grafos densos.

En el problema de la mochila con objetos fraccionables, el esquema más apropiado para resolverlo es: Voraz. Programación dinámica. Ramificación y Poda. Vuelta Atrás.

Se quiere conectar entre sí mediante carreteras todos los pueblos de una región. Se dispone de un estudio que recoge todas las posibles carreteras que podrían construirse junto con el coste de construir cada una de ellas. Se desea diseñar un algoritmo que permita seleccionar, de entre todas las carreteras posibles, un subconjunto que conecte todos los pueblos con el coste global mínimo. Indique cuál de las siguientes afirmaciones es cierta: Se trata de un problema de optimización, por lo que un algoritmo voraz puede ofrecer una solución eficiente al problema. Es posible resolver el problema utilizando el algoritmo de Prim. Es posible resolver el problema utilizando el algoritmo de Kruskal. Todas las respuestas anteriores son ciertas.

Sea un vector de N números naturales, algunos de ellos repetidos. Se desea diseñar un algoritmo que elimine los elementos duplicados. Indique cuál de las siguientes afirmaciones es cierta: La resolución del problema requiere ordenar previamente el vector. Es posible encontrar un algoritmo divide y vencerás que resuelva el problema con coste O(n log n). Al tratarse de un problema de optimización, el esquema voraz también es aplicable. Todas las opciones anteriores son ciertas.

Dado el siguiente grafo, ¿Qué opción es cierta sobre la aplicación del algoritmo de Dijkstra tomando como origen el nodo 1 y seleccionándolos en caso de igual coste en orden no decreciente del valor del nodo?. El vector especial[] actualiza un valor tras la selección del nodo 3. El vector especial[] actualiza un valor tras la selección del nodo 2. El vector especial[] actualiza un valor tras la selección del nodo 6. Ninguna de las anteriores.

Mediante programación dinámica, se quieren multiplicar 4 matrices A,B,C,D de dimensiones 5x3, 3x7, 7x4, 4x6 respectivamente. La ordenación óptima es: (A((BC)D)). (AB)(CD). (A(B(CD))). (((AB)C)D).

Respecto a las tablas hash y a la resolución de colisiones, ¿Cuál de las siguientes es cierta?. El uso de niveles es lo más apropiado en el caso del hashing cerrado. El recorrido cuadrático reduce la probabilidad de colisión con respecto al recorrido lineal. El factor de carga debe mantenerse mayor que 1. Ninguna de las anteriores es cierta.

¿Cuál de las siguientes afirmaciones es falsa?. El algoritmo de ordenación por fusión (mergesort) tiene coste O(n log n). El algoritmo de ordenación rápida (quicksort) que toma como pivote el primer elemento del vector en el caso peor tiene coste O(n^2). El algoritmo de ordenación rápida, si se utiliza como pivote la mediana del vector tiene un coste O(n log n). El algoritmo de ordenación basada en montículos (heapsort) es O(n^2).

Considérese el vector v=[3,5,7,14,8,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 7. Ninguna de las opciones anteriores.

Con respecto al algoritmo de Kruskal indica cuál de estas afirmaciones es falsa: Cuando en cada paso se selecciona la arista de menor peso que todavía no ha sido evaluada, se determina si une dos nodos pertenecientes a dos componentes conexas distintas. El algoritmo finaliza cuando el árbol de recubrimiento contiene n-1 aristas, siendo n el número de nodos. Comparando los algoritmos de Prim y Kruskal, si el grafo es denso será preferible el algoritmo de Kruskal ya que su coste es O(n2), pero si el grafo es disperso será más adecuado el algoritmo de Prim. La demostración de optimalidad del algoritmo de Kruskal se puede realizar por inducción.

Dado el grafo siguiente; Si realizáramos un recorrido en anchura partiendo del nodo 1, indica cuál de las siguientes afirmaciones sería cierta con respecto al contenido de la estructura de datos cola que dirige el recorrido, si los adyacentes a un nodo se almacenan en orden no decreciente: En un determinado paso, el contenido de la cola sería (3,6). En un determinado paso, el contenido de la cola sería (4,5,6). En un determinado paso, el contenido de la cola sería (5). Ninguna de las anteriores.

Indica cuál de las siguientes afirmaciones es cierta con respecto al algoritmo de ordenación por fusión (Mergesort) de un vector de tamaño n. Se compone de dos invocaciones recursivas con tamaño n/2 que se realizan a partir del valor de un elemento seleccionado como pivote. Su coste en el caso peor es O(n^2). Solo se realiza una única fusión en el desarrollo de todo algoritmo, pero se realizan log n particiones. Ninguna de las anteriores es cierta.

¿Cuál de las siguientes afirmaciones es falsa?. El coste de determinar si dos nodos son adyacentes en una implementación de un grafo mediante una lista de adyacencia es O(n). Un grafo conexo sin puntos de articulación se llama biconexo. Una cota del coste del problema del coloreado de grafos solucionado mediante el esquema de vuelta atrás es O(nm^n), siendo n el número de nodos y m el conjunto de colores. Se dice que un grafo dirigido es fuertemente conexo si contiene un camino desde n a m o desde m a n para cada par de vértices n y m.

Se dispone de una mochila de capacidad máxima de 25kg y de 3 objetos fraccionables con pesos respectivos 20kg, 12kg y 10kg, y con valores respectivos 25€, 30€ y 20€. Se pide dar la disposición de objetos que maximice el valor de la mochila sin superar el peso máximo. ¿Cuál sería dicho beneficio?. 53.75. 46.25. 61. Ninguna de las anteriores.

Dado el grafo de la figura; Indique 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 1: 1 5 3 4 2. 1 5 3 2 4. 1 2 4 3 5. Ninguna de las anteriores.

Sea un procesador que ha de atender n procesos. Se conoce de antemano el tiempo que necesita cada proceso. Se desea determinar en qué orden se han de atender los procesos para minimizar 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?. No existe un algoritmo voraz capaz de resolver el problema en todos los casos. Suponiendo tres clientes con tiempos de servicio t1=8, t2=2 y t3=5, el tiempo mínimo de estancia posible de todos los procesos es de 27 segundos. Suponiendo tres clientes con tiempos de servicio t1=8, t2=2 y t3=5, el tiempo mínimo de estancia posible de todos los procesos es de 24 segundos. Todas las afirmaciones anteriores son falsas.

Para el siguiente grafo, al que queremos aplicar el algoritmo de cálculo de puntos de articulación, y suponiendo que el inicial es el 1 y que, a igual prioridad, se elige el nodo etiquetado con menor valor, el valor de numOrden[], calculado recorriendo el grafo en profundidad, es: [1,2,3,4,5,7,8,6]. [1,2,3,4,5,6,7,8]. [1,2,3,4,6,5,7,8]. Ninguna de las anteriores.

Un barbero quiere atender a n clientes y conoce el tiempo requerido por cada uno de ellos, siendo ti, i= 1 ,2, ... ,n el tiempo requerido por el cliente i. El objetivo es minimizar el tiempo medio de estancia de los clientes en la barbería, y como el número de clientes es fijo, esto equivale a minimizar el tiempo total que están en la barbería todos los clientes. ¿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.

¿Cuál de las siguientes afirmaciones es falsa con respecto al coste de las funciones de manipulación de grafos?. La función AñadirVertice que añade un vértice a un grafo y devuelve el grafo con dicho vértice incluido, tiene un coste lineal cuando el grafo se implementa con una matriz de adyacencia. La función BorrarArista es más costosa cuando el grafo se implementa mediante una matriz de adyacencia. La operación Adyacente?, que comprueba si dos nodos son adyacentes, es más costosa cuando el grafo se implementa con una lista de adyacencia. La función Adyacentes, que devuelve una lista con los vértices adyacentes a uno dado, es más costosa cuando el grafo se implementa con una matriz de adyacencia.

Indica cuál de las siguientes afirmaciones es cierta con respecto al algoritmo Quicksort de un vector de tamaño n. Se compone de dos invocaciones recursivas con tamaño n/2 más un procedimiento que combina los subvectores ordenados resultantes que es de coste lineal. Su coste en el caso peor es O(n^2), pero existe una versión mejorada eligiendo como pivote la mediana del vector, lo que daría que el coste del Quicksort en el caso peor sería O(n log n). En el recorrido del vector por los dos extremos, en particular en el recorrido de izquierda a derecha se detiene al encontrar un elemento menor que el pivote cuando la ordenación es en orden creciente. Ninguna de las anteriores es cierta.

Para abordar el problema de las colisiones se han desarrollado distintas estrategias. ¿De entre ellas cuales son las que más aumentan el efecto de agrupamiento?. El recorrido cuadrático. El recorrido mediante doble hashing. El recorrido lineal. Ninguna de las anteriores.

Dada la siguiente lista de adyacencia en la que los pesos de las aristas aparecen entre paréntesis: Se va a aplicar el algoritmo de Dijkstra sobre el grafo asociado a la lista anterior, elegir cuál de los vectores especiales no corresponde con ninguno de los pasos que se harán para obtener el camino de menor coste empezando en el vértice 9. especial[]= [00 ,15, 00 , oo, oo, oo, oo,20,10]. especial[]= [oo,15, 25, oo, oo, oo, oo,20,10]. especial[] = [oo, 15, 20,25, oo, oo, oo ,20, 1 O]. especial[] = [25,40, 20,25, oo, oo, 25,20,1 O].

Indique cuál de las siguientes afirmaciones es falsa: Un árbol de recubrimiento asociado a un grafo está formado por las aristas usadas en un recorrido en profundidad del grafo, pero no por las de un recorrido en anchura. La raíz de un árbol de recubrimiento es el nodo inicial del recorrido del grafo. Si el grafo no es conexo, el recorrido en profundidad le asocia un bosque de árboles, uno por cada componente conexa del árbol. Las aristas que no forman parte del árbol son las que no se usan en el recorrido del grafo.

Dado el grafo de la figura: Indique 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 1. 1 2 3 4 5. 1 4 2 3 5. 1 4 3 2 5. Ninguna de las anteriores.

Indique cuál de las siguientes afirmaciones es cierta con respecto al coste: 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 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 dos vectores. El coste del algoritmo de Kruskal es O(n^2), siendo n el número de nodos del grafo y utilizando un montículo para almacenar las aristas pendientes. El coste del algoritmo de ordenación rápida en el caso mejor es O(n^2), siendo n el número de elementos del array.

Indique cuál de las siguientes afirmaciones es falsa: En el esquema voraz, no es necesario reconsiderar decisiones ya tomadas. En el esquema de divide y vencerás, no se puede paralelizar la resolución de los distintos problemas. En el esquema de programación dinámica, la memorización de las soluciones parciales reduce el coste de ejecución. En el esquema voraz, el problema de la mochila con objetos fraccionables se puede resolver en tiempo O(n log n).

E(2,3) = 15. E(1,3) = 48. E(2,4) = 30. E(2,2) = 10.

Dado el siguiente montículo de mínimos, indique cuál de las siguientes afirmaciones es cierta: No se trata de un montículo de mínimos, sino de un montículo de máximos. El vector que lo representa es [5,9, 11, 14, 18,33, 17,27,19,21]. El vector que lo representa es [5,9, 11, 14, 18,19,21 ,33, 17,27]. Ninguna de las anteriores es cierta.

Considérese el vector [7,3,5,9,12,2,6,1,8]. Los vectores argumento de la primera invocación recursiva del algoritmo de quicksort, cuando se toma el elemento 7 de la primera posición como pivote, son: [3,5,1,12,2] y [6,9,8]. [3,5,1,6] y [2,12,9,8]. [2,3,5,1,6] y [12,9,8]. Ninguna de las opciones anteriores.

El valor 9 no se puede ubicar para ningún valor de i. t[6] = vacío. El valor 1 no se puede ubicar para ningún valor de i. Ninguna de las anteriores es cierta.

Dado un grafo con n vértices y a aristas sobre el que se pueden realizar las siguientes operaciones: • Adyacente?: comprueba si dos vértices son adyacentes. • borrarVertice: borra el vértice especificado y todas sus aristas. • borrarArista: elimina la arista entre los vértices. ¿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.

Con respecto al esquema de ramificación y poda, indique cuál de las siguientes afirmaciones es cierta: En la fase de poda se eliminan las ramas que no pueden llegar a una solución y las que mejoran el valor de la función objetivo de la mejor solución alcanzada. En el problema de la distancia de edición entre dos cadenas, si se consideran tres operaciones de transformación, siendo n y m la longitud de las cadenas en caracteres, y n menor o igual que m, una cota superior del espacio de búsqueda generado por el algoritmo de ramificación y poda sería m^3. Los nodos en el montículo se mantienen ordenados en orden decreciente si la optimización es minimización o creciente si la optimización es maximización del valor de la función objetivo. El montículo se utiliza en este esquema porque permite establecer una cola de prioridad de los nodos que aún no se han explorado.

Es posible diseñar un algoritmo de tipo divide y vencerás que resuelve el problema en tiempo O(n log n). Es posible encontrar un algoritmo de búsqueda exhaustiva que resuelve el problema en tiempo O(n). Un algoritmo de vuelta atrás proporcionará una solución más eficiente que uno basado en el esquema de divide y venderás. Ninguna de las anteriores es cierta.

Aplicando el algoritmo de Dijkstra al grafo con conjunto de vértices V= {0 .. 6} y aristas con pesos de la figura: Se pide indicar cuál no es un valor correcto para el vector "Especial" D[i] generado por el algoritmo de Dijkstra aplicado desde el vértice inicial 0 a lo largo de las iteraciones, representando en cada iteración la distancia mínima hasta el momento entre los vértices 0 y 6: [ 12,4,INF,1,18,14]. [6,4,10,1,5,14]. [12,4,10,1,5,8]. [12,4,INF,1,5,8].