Grafos y Hash

Pregunta 1 de 45

1

¿Cuál de las siguientes afirmaciones es falsa?

Selecciona una de las siguientes respuestas posibles:

La implementación basada en listas de adyacencia ocupa un espacio O(m+n) donde (n=nodos, m=lados) .
No contestar

Explicación

Pregunta 2 de 45

1

¿Cuál es el número de lados en un grafo dirigido de densidad máxima?

Selecciona una de las siguientes respuestas posibles:

N*n
N*(n-1)
N*(n+1)
No contestar

Explicación

Pregunta 3 de 45

1

En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen el nodo 2, cual de las siguientes afirmaciones es cierta.

Selecciona una de las siguientes respuestas posibles:

No contestar.
El predecesor del 4 será el 5.
El predecesor del 2 será el 5.
Ninguna de las otras es cierta.
El predecesor del 1 será el 5.

Explicación

Pregunta 4 de 45

1

Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 4, ¿cual es la afirmación correcta?

Selecciona una de las siguientes respuestas posibles:

El último lado seleccionado sería el (3,5)
El segundo lado seleccionado sería el (1,4)
Después de seleccionar todos los lados, el valor vector cercano[] para todos nodos será el 4.
No contestar.
El primer lado seleccionado sería el (1,4)

Explicación

Pregunta 5 de 45

1

En el algoritmo de Dijkstra, cuando un nodo x pasa a formar parte del conjunto S, ¿Cómo se evalúa si ese nodo acorta la distancia a un nodo z no perteneciente a S?

Selecciona una de las siguientes respuestas posibles:

Comprobando si la distancia al nodo x más el peso del CAMINO (x,z) es inferior a la distancia que
existía al nodo z. El camino de x a z no es conocido aún, por lo tanto es falsa.
Comprobando si la distancia al nodo x más el peso del LADO (x,z) es inferior a la distancia que existía al nodo z.
No hay que comprobar, ya que no puede acortar la distancia
Comprobando si el el peso del lado (origen, x) más el peso del lado (x,z) es inferior a la distancia que existía al nodo z.

Explicación

Pregunta 6 de 45

1

¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Dijkstra?

Selecciona una de las siguientes respuestas posibles:

No contestar.
Es de orden O(N)
Es de orden O(N^2)
Es de orden O(N^3)
Es de orden O(N log (N))

Explicación

Pregunta 7 de 45

1

Si en el grafo de la figura se realiza un recorrido en profundidad partiendo del nodo 2, (en caso de tener más de una opción al seleccionar un nodo, se elige el de menor numeración), indicar qué afirmación es cierta.

Selecciona una de las siguientes respuestas posibles:

No contestar.
Se crea un bosque con un árbol
Se crea un bosque con tres árboles
Se crea un bosque con cuatro árboles
Se crea un bosque con dos árboles

Explicación

Pregunta 8 de 45

1

Indica cual de las siguientes afirmaciones es falsa cuando se obtiene el árbol abarcador de coste mínimo.

Selecciona una de las siguientes respuestas posibles:

No se puede obtener otra solución con un coste inferior al obtenido
La solución no tiene por qué ser única
Cualquier camino que incluya a lados del árbol es mínimo
Se puede acceder de un nodo a cualquier otro usando los lados del árbol
No contestar.

Explicación

Pregunta 9 de 45

1

En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen el nodo 5, cual de las siguientes afirmaciones es cierta.

Selecciona una de las siguientes respuestas posibles:

El segundo nodo del que se obtiene la distancia
mínima es el 3
No contestar
El segundo nodo del que se obtiene la distancia
mínima es el 1
El segundo nodo del que se obtiene la distancia
mínima es el 4
El segundo nodo del que se obtiene la distancia
mínima es el 2

Explicación

Pregunta 10 de 45

1

¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo de
Kruskal?(N = número de nodos, L = número de lados).

Selecciona una de las siguientes respuestas posibles:

No contestar
Ordena los lados de menor a mayor y selecciona
los N1 más pequeños que no formen ciclos.
Ordena los lados de menor a mayor y selecciona
los N1 más pequeños
Ordena los lados de menor a mayor y selecciona
los L1 más pequeños
Ordena los lados de menor a mayor y selecciona
los L1 más pequeños que no formen ciclos.

Explicación

Pregunta 11 de 45

1

¿Cuál de las siguientes afirmaciones es cierta sobre el problema del
árbol abarcador de coste mínimo?

Selecciona una de las siguientes respuestas posibles:

Siempre hay una solución única.
No contestar
Se pueden obtener varias soluciones, pero todos
los árboles solución han de tener el mismo coste.
No tiene porqué tener solución.
Se pueden obtener varias soluciones y los árboles
solución pueden tener distintos costes..

Explicación

Pregunta 12 de 45

1

En el grafo dirigido acíclico de la figura. Si realizamos una clasificación
topológica, iniciando el recorrido a partir del nodo 1 (cuando haya más
de una posibilidad se selecciona el nodo de menor numeración) , el
orden resultante será:

Selecciona una de las siguientes respuestas posibles:

2,4,1,3,5
1,3,5,2,4
No contestar
1,2,4,3,5
1,2,3,4,5

Explicación

Pregunta 13 de 45

1

¿Cuál de las siguientes afirmaciones es cierta sobre la clasificación
topológica?

Selecciona una de las siguientes respuestas posibles:

Se puede aplicar a cualquier tipo de grafos
acíclicos.
No contestar
El orden resultante depende del nodo de comienzo
Clasifica a ls nodos teniendo en cuenta los pesos
de los lados que inciden en ellos.
Se puede aplicar a cualquier tipo de grafo dirigido.

Explicación

Pregunta 14 de 45

1

¿Cual de las siguientes afirmaciones es cierta en el algoritmo de
Warshall?

Selecciona una de las siguientes respuestas posibles:

es de orden O(N^2)
es de orden O(N^3)
No contestar
Es de orden O(N log N)
Es de orden O(N)

Explicación

Pregunta 15 de 45

1

Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz
de adyacencia, indica cual de las siguientes opciones es falsa

Selecciona una de las siguientes respuestas posibles:

Podemos saber el camino mínimo entre dos nodos.
Podemos saber si hay ciclos.
No contestar.
Podemos saber si dos nodos están conectados
. Podemos saber si hay caminos de longitud l< N que
enlazan dos nodos

Explicación

Pregunta 16 de 45

1

¿Cual de las siguientes afirmaciones es falsa?

Selecciona una de las siguientes respuestas posibles:

La implementación de un grafo basada en listas de
adyacencia es eficiente cuando un grafo es poco
denso
La implementación de un grafo basada en la lista
de adyacencia es la recomendada cuando el grafo es
muy denso (m similar a n^2)
No contestar.
La implementación de un grafo basada en la matriz
de adyacencia ocupa un espacio de orden O(n^2) (n =
número de nodos)
La implementación basada en listas de adyacencia
ocupa un espacio de O(m+n) (n = nodos, m = lados)

Explicación

Pregunta 17 de 45

1

¿Cual de las siguientes afirmaciones es falsa en la implementación de
un grafo?

Selecciona una de las siguientes respuestas posibles:

No contestar.
En una matiz de adyacencia puede desperdiciarse
memoria
El tiempo empleado para saber si dos nodos están
conectados es constante si se usa una matriz de
adyacencia
Las listas de adyacencia optimizan la búsqueda de
los lados incidentes en un nodo
El tiempo empleado para saber si dos nodos están
conectados es constante si se usan listas de
adyacencia

Explicación

Pregunta 18 de 45

1

Al terminar la iteración késima en el algoritmo de Floyd. ¿Cual de las
siguientes afirmaciones es cierta?

Selecciona una de las siguientes respuestas posibles:

No contestar.
La matriz de intermedios tendrá solo nodos con
numeracion superior a k.
La matriz de intermedios solo puede tener nodos
con numeración menor o igual a k.
La matriz de intermedios solo puede tener al nodo k
La matriz de intermedios puede tener a cualquier
nodo.

Explicación

Pregunta 19 de 45

1

En una iteración del algoritmo de Prim o del algoritmo de Kruskal se
selecciona un lado que enlaza dos conjuntos distintos. ¿Porqué?

Selecciona una de las siguientes respuestas posibles:

Porque así se garantiza que se obtengan todas las
posibles soluciones
Porque así se garantiza que la solución sea única
No contestar
Porque así se garantiza que no haya ciclos
Porque así se garantiza que tres lados no incidan
en un nodo.

Explicación

Pregunta 20 de 45

1

Si en el grafo de la figura se realiza un recorrido en profundidad
partiendo del nodo 4, el orden de los nodos recorridos sería (en caso
de tener más de una opción al seleccionar un nodo, se elige el de menor numeración):

Selecciona una de las siguientes respuestas posibles:

4, 7, 3, 6, 1, 2, 5
No contestar
4, 3, 6, 7, 1, 2, 5
4, 6, 7, 3, 1, 2, 5
4, 7, 6, 3, 1, 2, 5

Explicación

Pregunta 21 de 45

1

Si tuvieses que obtener el árbol abarcador de coste mínimo en el grafo
que forma la red de carreteras españolas. ¿Cual de las siguientes
afirmaciones sería cierta?

Selecciona una de las siguientes respuestas posibles:

No contestar.
El algoritmo de Kruskal sería el más eficiente al
tratarse de un grafo denso.
El algoritmo de Prim sería el más eficiente al
tratarse de un grafo denso.
El algoritmo de Kruskal sería el más eficiente al
tratarse de un grafo poco denso.
El algoritmo de Prim sería el más eficiente al
tratarse de un grafo poco denso.

Explicación

Pregunta 22 de 45

1

Indica cual de las siguientes afirmaciones es cierta en el algoritmo de
Dijkstra

Selecciona una de las siguientes respuestas posibles:

No contestar
Su orden de complejidad depende del número de
lados del grafo.
Si hay algún nodo al que no se pueda acceder
desde el nodo origen, no se puede aplicar.
Su orden de complejidad es el mismo que si se
aplicase para calcular la distancia mínima desde el
origen a un nodo destino fijo
Se puede aplicar en grafos con pesos negativos.

Explicación

Pregunta 23 de 45

1

Al aplicar el algoritmo de Floyd, ¿cuál de las siguientes
afirmaciones es cierta?

Selecciona una de las siguientes respuestas posibles:

El camino mínimo de un nodo i a un j es
camino(i,j) = i+ I(i,j) + camino(i,j), siendo I(i,j) el
intermedio entre i y j.
El camino mínimo de un nodo i a un j es
camino(i,j) = camino(i, I(i,j)) + I(i,j) + camino(I(i,j),j),
siendo I(i,j) el intermedio entre i y j.
El camino mínimo de un nodo i a un j es
camino(i,j) = i+I(i,j)+j siendo I(i,j) el intermedio
entre i y j.
No contestar

Explicación

Pregunta 24 de 45

1

Si calculamos las potencias sucesivas (hasta llegar a A^N) de la
matriz de adyacencia, indica cual de las siguientes opciones es
cierta.

Selecciona una de las siguientes respuestas posibles:

Solo podemos saber si existe camino que
enlace dos nodos cualesquiera
Podemos saber si existe algún camino que
enlaza dos nodos cualesquiera y cuantos caminos
enlazan esos dos nodos.
Obtenemos los caminos mínimos entre dos
nodos cualesquiera.
No contestar.
Solo podemos saber los posibles cuantos
caminos enlazan dos nodos cualesquiera.

Explicación

Pregunta 25 de 45

1

En el grafo dirigido de la figura, si se realiza un recorrido en
amplitud desde el nodo 1, el recorrido será (en caso de poder
seleccionar más de un nodo se seleccionará el de menor numeración).

Selecciona una de las siguientes respuestas posibles:

1,2,3,4,5,7,6
1,2,3,4, 6,5, 7
1,3,4,2,6,5,7
1,2,3,4,5,6,7
No contestar

Explicación

Pregunta 26 de 45

1

Cual de las siguientes afirmaciones es cierta en el recorrido en
profundidad de un grafo no dirigido.

Selecciona una de las siguientes respuestas posibles:

Puede tener lados cruzados. En un grafo no dirigido no puede haber lados cruzados, en uno dirigido si puede haberlos.
No hay lados de avance.
No contestar.
El bosque resultante no puede tener más de un árbol.
El número de árboles resultante en el bosque no depende del nodo de comienzo.

Explicación

Pregunta 27 de 45

1

En el grafo dirigido de la figura, si se realiza un recorrido en
amplitud desde el nodo 1, cual de las siguientes afirmaciones es
falsa (en caso de poder seleccionar más de un nodo se
seleccionará el de menor numeración)

Selecciona una de las siguientes respuestas posibles:

El lado 3,4 es cruzado
El lado 2,3 es de árbol
El lado 5,1 es de retroceso
el lado 5,7 es cruzado
No contestar

Explicación

Pregunta 28 de 45

1

¿Cual es el principal inconveniente de la implementación de un
grafo basada en listas de adyacencia?

Selecciona una de las siguientes respuestas posibles:

Es más complicado determinar si dos nodos
son adyacentes.
Desperdicia más memoria que la matriz de
adyacencia
No contestar
El recorrido de los lados que inciden en un
nodo es menos eficiente que en la matriz de
adyacencia
Su tamaño no depende del número de lados.

Explicación

Pregunta 29 de 45

1

¿Cuál de las siguientes afirmaciones es falsa?

Selecciona una de las siguientes respuestas posibles:

El algoritmo de Kruskal es de orden O(l log l)
No contestar
El algoritmo de Prim es más eficiente en grafos
muy densos.
El algoritmo de Prim es de orden O(n^2).
El orden selección de los lados en el algoritmo
de Kruskal depende de nodo de inicio de

Explicación

Pregunta 30 de 45

1

Indica cual de las siguientes afirmaciones se cumple después de la
iteración k-ésima del algoritmo de Floy

Selecciona una de las siguientes respuestas posibles:

Se obtienen los caminos y distancias mínimas
entre todos los pares de nodos usando como
posibles intermedios los k primeros nodos.
Se obtienen las distancias y caminos mínimos
del nodo k al resto de nodos
No contestar.
Se obtienen las distancias y caminos mínimos
entre todos los k primeros nodos.
Se obtienen las distancias y caminos mínimos
entre todos los pares de nodos, pasando
únicamente por el nodo k

Explicación

Pregunta 31 de 45

1

Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 5, ¿cual es la afirmación correcta?.

Selecciona una de las siguientes respuestas posibles:

La solución cambiaría si se comenzase en el
nodo 3
La solución no cambiaría si se comenzase en el
nodo 4.
Después de seleccionar el segundo lado de la
solución, el valor del vector Cercano[3] es el nodo
1.
Después de seleccionar todos los lados, el más
cercano a todos será el 1.
No contestar.

Explicación

Pregunta 32 de 45

1

Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del
nodo 1, selecciona la respuesta correcta al orden en el que se seleccionan los lados.

Selecciona una de las siguientes respuestas posibles:

(1,5) (5,4)(1,2)(5,3)
No contestar.
(1,5)(5,4)(1,4)(1,2)
(1,5)(1,4)(1,2)(1,3)
(1,5)(5,4)(3,5)(1,2)

Explicación

Pregunta 33 de 45

1

Desde el punto de vista del espacio que ocupa la
implementación¿Cual de las siguientes afirmaciones es cierta en la
implementación de un grafo poco denso?

Selecciona una de las siguientes respuestas posibles:

La matriz de adyacencia apenas supondría
desperdicio de memoria.
El uso de listas de adyacencia sería lo más
eficiente.
El uso de la matriz de adyacencia sería lo más
eficiente.
No contestar.
La matriz de adyacencia y las listas de
adyacencia serían iguales de eficientes.

Explicación

Pregunta 34 de 45

1

Cuando en una iteración del algoritmo de Prim seleccionamos el
nodo x de menor coste del conjunto N-U, y lo añadimos al conjunto
U, luego se comprueba si el vector de costes y el de cercanos para
los nodos k pertenecientes a N-U cambia. Para que el nodo k
cambie su nodo cercano y su coste, ¿cuál de las siguientes
comprobaciones debe ser cierta?

Selecciona una de las siguientes respuestas posibles:

Cercano[k] < Cercano[x]
PesoLAdo(x, k) > coste(k)
No contestar
Cercano[x] < Cercano[k]
PesoLado(x,k) < coste(k)

Explicación

Pregunta 35 de 45

1

Si en el grafo de la figura se realiza un recorrido en profundidad
partiendo del nodo 1, (en caso de tener más de una opción al
seleccionar un nodo, se elige el de menor numeración), indicar qué afirmación es falsa

Selecciona una de las siguientes respuestas posibles:

El lado 4,3 es cruzado
No contestar.
El lado 4,7 es de árbol
El lado 5,1 es de retroceso
El lado 2, 5 es de árbol

Explicación

Pregunta 36 de 45

1

¿Cuál de las siguientes afirmaciones es cierta en el algoritmo de Warshall?

Selecciona una de las siguientes respuestas posibles:

Si se aplica a un grafo conexo no dirigido, todos los elementos de la matriz resultado
son 1.
No contestar

Explicación

Pregunta 37 de 45

1

¿Cual es el principal inconveniente de la implementación de un grafo basada en la
matriz de adyacencia?

Selecciona una de las siguientes respuestas posibles:

El desperdicio de memoria en grafos poco densos.
No contestar

Explicación

Pregunta 38 de 45

1

¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de
Floyd?

Selecciona una de las siguientes respuestas posibles:

Es de orden O(N^3)
Es de orden O(N^2)
Es de orden O(N)
No contestar

Explicación

Pregunta 39 de 45

1

En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen
el nodo 1, cual de las siguientes afirmaciones es cierta.

Selecciona una de las siguientes respuestas posibles:

El predecesor del nodo 5 es el 3
El predecesor del nodo 5 es el 1
El predecesor del nodo 5 es el 4
No contestar

Explicación

Pregunta 40 de 45

1

¿Cuál de las siguientes afirmaciones es CIERTA en la organización
hashing?

Selecciona una de las siguientes respuestas posibles:

La función hash no debe distribuir
uniformemente las claves a la hora de determinar
el cubo
La función hash nunca producirá colisiones.
No contestar.
Las colisiones no dependen de la función hash.
La función hash debe distribuir uniformemente las claves a la hora de determinar el cubo.

Explicación

Pregunta 41 de 45

1

¿Cuál de las siguientes funciones elegirías para la función hash?

Selecciona una de las siguientes respuestas posibles:

Una que utilice como base la primera letra del
segundo apellido.
a. b. Una que utilice como base la primer letra del
nombre.
Una que utilice como base la primera letra del
primer apellido.
No contestar.
Una que utilice el resto de dividir el dni por un
entero primo.

Explicación

Pregunta 42 de 45

1

¿Cuál de las siguientes funciones elegirías para la función hash?

Selecciona una de las siguientes respuestas posibles:

No contestar.
Una que utilice como base la dos primeras letras del primer apellido.
Una que utilice como base las dos primeras letras del nombre.
Una que utilice como base las dos primeras letras del segundo apellido.
Una que use como base las dos últimas cifras del dni.
Aquí hay 100 posibilidades y cada una de ellas tendrá la misma probabilidad, cosa que no ocurre
en el resto de las opciones que se basan en el alfabeto, donde por ejemplo las vocales aparecen
más que las consonantes.

Explicación

Pregunta 43 de 45

1

Asumiendo que no hay colisiones, ¿cuál de las siguientes afirmaciones es CIERTA
en la organización hashing?

Selecciona una de las siguientes respuestas posibles:

La consulta es de orden O(1)
La consulta es de orden O(2)
La consulta es de orden O(3)
No contestar

Explicación

Pregunta 44 de 45

1

¿Cuál de las siguientes funciones elegirías para la función hash?

Selecciona una de las siguientes respuestas posibles:

Una que use Aquí hay 100 posibilidades y cada como base las una de ellas tendrá la
misma probabilidad, cosa que no ocurre en el resto de las opciones que se basan en el
alfabeto, donde por ejemplo las vocales aparecen más que las consonantes.
No contestar

	Creado por Tomás de la Yglesia hace más de 8 años

Teoría Test 17/18 Estructura de Datos Test sobre Grafos y Hash, creado por Tomás de la Yglesia el 27/05/2018.

Grafos y Hash

Pregunta 1 de 45

¿Cuál de las siguientes afirmaciones es falsa?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 2 de 45

¿Cuál es el número de lados en un grafo dirigido de densidad máxima?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 3 de 45

En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen el nodo 2, cual de las siguientes afirmaciones es cierta.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 4 de 45

Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 4, ¿cual es la afirmación correcta?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 5 de 45

En el algoritmo de Dijkstra, cuando un nodo x pasa a formar parte del conjunto S, ¿Cómo se evalúa si ese nodo acorta la distancia a un nodo z no perteneciente a S?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 6 de 45

¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Dijkstra?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 7 de 45

Si en el grafo de la figura se realiza un recorrido en profundidad partiendo del nodo 2, (en caso de tener más de una opción al seleccionar un nodo, se elige el de menor numeración), indicar qué afirmación es cierta.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 8 de 45

Indica cual de las siguientes afirmaciones es falsa cuando se obtiene el árbol abarcador de coste mínimo.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 9 de 45

En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen el nodo 5, cual de las siguientes afirmaciones es cierta.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 10 de 45

¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?(N = número de nodos, L = número de lados).

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 11 de 45

¿Cuál de las siguientes afirmaciones es cierta sobre el problema del árbol abarcador de coste mínimo?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 12 de 45

En el grafo dirigido acíclico de la figura. Si realizamos una clasificación topológica, iniciando el recorrido a partir del nodo 1 (cuando haya más de una posibilidad se selecciona el nodo de menor numeración) , el orden resultante será:

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 13 de 45

¿Cuál de las siguientes afirmaciones es cierta sobre la clasificación topológica?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 14 de 45

¿Cual de las siguientes afirmaciones es cierta en el algoritmo de Warshall?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 15 de 45

Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz de adyacencia, indica cual de las siguientes opciones es falsa

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 16 de 45

¿Cual de las siguientes afirmaciones es falsa?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 17 de 45

¿Cual de las siguientes afirmaciones es falsa en la implementación de un grafo?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 18 de 45

Al terminar la iteración késima en el algoritmo de Floyd. ¿Cual de las siguientes afirmaciones es cierta?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 19 de 45

En una iteración del algoritmo de Prim o del algoritmo de Kruskal se selecciona un lado que enlaza dos conjuntos distintos. ¿Porqué?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 20 de 45

Si en el grafo de la figura se realiza un recorrido en profundidad partiendo del nodo 4, el orden de los nodos recorridos sería (en caso de tener más de una opción al seleccionar un nodo, se elige el de menor numeración):

¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo de
Kruskal?(N = número de nodos, L = número de lados).

¿Cuál de las siguientes afirmaciones es cierta sobre el problema del
árbol abarcador de coste mínimo?

En el grafo dirigido acíclico de la figura. Si realizamos una clasificación
topológica, iniciando el recorrido a partir del nodo 1 (cuando haya más
de una posibilidad se selecciona el nodo de menor numeración) , el
orden resultante será:

¿Cuál de las siguientes afirmaciones es cierta sobre la clasificación
topológica?

¿Cual de las siguientes afirmaciones es cierta en el algoritmo de
Warshall?

Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz
de adyacencia, indica cual de las siguientes opciones es falsa

¿Cual de las siguientes afirmaciones es falsa en la implementación de
un grafo?

Al terminar la iteración késima en el algoritmo de Floyd. ¿Cual de las
siguientes afirmaciones es cierta?

En una iteración del algoritmo de Prim o del algoritmo de Kruskal se
selecciona un lado que enlaza dos conjuntos distintos. ¿Porqué?

Si en el grafo de la figura se realiza un recorrido en profundidad
partiendo del nodo 4, el orden de los nodos recorridos sería (en caso
de tener más de una opción al seleccionar un nodo, se elige el de menor numeración):

Si tuvieses que obtener el árbol abarcador de coste mínimo en el grafo
que forma la red de carreteras españolas. ¿Cual de las siguientes
afirmaciones sería cierta?

Indica cual de las siguientes afirmaciones es cierta en el algoritmo de
Dijkstra

Al aplicar el algoritmo de Floyd, ¿cuál de las siguientes
afirmaciones es cierta?

Si calculamos las potencias sucesivas (hasta llegar a A^N) de la
matriz de adyacencia, indica cual de las siguientes opciones es
cierta.

En el grafo dirigido de la figura, si se realiza un recorrido en
amplitud desde el nodo 1, el recorrido será (en caso de poder
seleccionar más de un nodo se seleccionará el de menor numeración).

Cual de las siguientes afirmaciones es cierta en el recorrido en
profundidad de un grafo no dirigido.

En el grafo dirigido de la figura, si se realiza un recorrido en
amplitud desde el nodo 1, cual de las siguientes afirmaciones es
falsa (en caso de poder seleccionar más de un nodo se
seleccionará el de menor numeración)

¿Cual es el principal inconveniente de la implementación de un
grafo basada en listas de adyacencia?

Indica cual de las siguientes afirmaciones se cumple después de la
iteración k-ésima del algoritmo de Floy

Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del
nodo 1, selecciona la respuesta correcta al orden en el que se seleccionan los lados.

Desde el punto de vista del espacio que ocupa la
implementación¿Cual de las siguientes afirmaciones es cierta en la
implementación de un grafo poco denso?

Si en el grafo de la figura se realiza un recorrido en profundidad
partiendo del nodo 1, (en caso de tener más de una opción al
seleccionar un nodo, se elige el de menor numeración), indicar qué afirmación es falsa

¿Cual es el principal inconveniente de la implementación de un grafo basada en la
matriz de adyacencia?