Kopieren und bearbeiten

Grafos y Hash

Beschreibung

Teoría Test 17/18 Estructura de Datos Quiz am Grafos y Hash, erstellt von Tomás de la Yglesia am 27/05/2018.
Tomás de la Yglesia
Quiz von Tomás de la Yglesia, aktualisiert more than 1 year ago
Tomás de la Yglesia
Erstellt von Tomás de la Yglesia vor mehr als 8 Jahre
58
1
0

Zusammenfassung der Ressource

Frage 1

Frage
¿Cuál de las siguientes afirmaciones es falsa?
Antworten
  • La implementación basada en listas de adyacencia ocupa un espacio O(m+n) donde (n=nodos, m=lados) .
  • No contestar

Frage 2

Frage
¿Cuál es el número de lados en un grafo dirigido de densidad máxima?
Antworten
  • N*n
  • N*(n-1)
  • N*(n+1)
  • No contestar

Frage 3

Frage
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.
Image:
1 (binary/octet-stream)
Antworten
  • 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.

Frage 4

Frage
Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 4, ¿cual es la afirmación correcta?
Image:
2 (binary/octet-stream)
Antworten
  • 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)

Frage 5

Frage
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?
Antworten
  • 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.

Frage 6

Frage
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Dijkstra?
Antworten
  • 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))

Frage 7

Frage
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.
Image:
3 (binary/octet-stream)
Antworten
  • 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

Frage 8

Frage
Indica cual de las siguientes afirmaciones es falsa cuando se obtiene el árbol abarcador de coste mínimo.
Antworten
  • 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.

Frage 9

Frage
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.
Image:
4 (binary/octet-stream)
Antworten
  • 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

Frage 10

Frage
¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?(N = número de nodos, L = número de lados).
Antworten
  • No contestar
  • Ordena los lados de menor a mayor y selecciona los N­1 más pequeños que no formen ciclos.
  • Ordena los lados de menor a mayor y selecciona los N­1 más pequeños
  • Ordena los lados de menor a mayor y selecciona los L­1 más pequeños
  • Ordena los lados de menor a mayor y selecciona los L­1 más pequeños que no formen ciclos.

Frage 11

Frage
¿Cuál de las siguientes afirmaciones es cierta sobre el problema del árbol abarcador de coste mínimo?
Antworten
  • 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..

Frage 12

Frage
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á:
Antworten
  • 2,4,1,3,5
  • 1,3,5,2,4
  • No contestar
  • 1,2,4,3,5
  • 1,2,3,4,5

Frage 13

Frage
¿Cuál de las siguientes afirmaciones es cierta sobre la clasificación topológica?
Antworten
  • 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.

Frage 14

Frage
¿Cual de las siguientes afirmaciones es cierta en el algoritmo de Warshall?
Antworten
  • 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)

Frage 15

Frage
Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz de adyacencia, indica cual de las siguientes opciones es falsa
Antworten
  • 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

Frage 16

Frage
¿Cual de las siguientes afirmaciones es falsa?
Antworten
  • 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)

Frage 17

Frage
¿Cual de las siguientes afirmaciones es falsa en la implementación de un grafo?
Antworten
  • 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

Frage 18

Frage
Al terminar la iteración késima en el algoritmo de Floyd. ¿Cual de las siguientes afirmaciones es cierta?
Antworten
  • 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.

Frage 19

Frage
En una iteración del algoritmo de Prim o del algoritmo de Kruskal se selecciona un lado que enlaza dos conjuntos distintos. ¿Porqué?
Antworten
  • 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.

Frage 20

Frage
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):
Image:
6 (binary/octet-stream)
Antworten
  • 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

Frage 21

Frage
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?
Antworten
  • 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.

Frage 22

Frage
Indica cual de las siguientes afirmaciones es cierta en el algoritmo de Dijkstra
Antworten
  • 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.

Frage 23

Frage
Al aplicar el algoritmo de Floyd, ¿cuál de las siguientes afirmaciones es cierta?
Antworten
  • 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

Frage 24

Frage
Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz de adyacencia, indica cual de las siguientes opciones es cierta.
Antworten
  • 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.

Frage 25

Frage
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).
Image:
7 (binary/octet-stream)
Antworten
  • 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

Frage 26

Frage
Cual de las siguientes afirmaciones es cierta en el recorrido en profundidad de un grafo no dirigido.
Antworten
  • 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.

Frage 27

Frage
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)
Image:
8 (binary/octet-stream)
Antworten
  • 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

Frage 28

Frage
¿Cual es el principal inconveniente de la implementación de un grafo basada en listas de adyacencia?
Antworten
  • 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.

Frage 29

Frage
¿Cuál de las siguientes afirmaciones es falsa?
Antworten
  • 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

Frage 30

Frage
Indica cual de las siguientes afirmaciones se cumple después de la iteración k-ésima del algoritmo de Floy
Antworten
  • 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

Frage 31

Frage
Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 5, ¿cual es la afirmación correcta?.
Image:
9 (binary/octet-stream)
Antworten
  • 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.

Frage 32

Frage
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.
Image:
10 (binary/octet-stream)
Antworten
  • (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)

Frage 33

Frage
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?
Antworten
  • 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.

Frage 34

Frage
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?
Antworten
  • Cercano[k] < Cercano[x]
  • PesoLAdo(x, k) > coste(k)
  • No contestar
  • Cercano[x] < Cercano[k]
  • PesoLado(x,k) < coste(k)

Frage 35

Frage
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
Image:
11 (binary/octet-stream)
Antworten
  • 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

Frage 36

Frage
¿Cuál de las siguientes afirmaciones es cierta en el algoritmo de Warshall?
Antworten
  • Si se aplica a un grafo conexo no dirigido, todos los elementos de la matriz resultado son 1.
  • No contestar

Frage 37

Frage
¿Cual es el principal inconveniente de la implementación de un grafo basada en la matriz de adyacencia?
Antworten
  • El desperdicio de memoria en grafos poco densos.
  • No contestar

Frage 38

Frage
¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Floyd?
Antworten
  • Es de orden O(N^3)
  • Es de orden O(N^2)
  • Es de orden O(N)
  • No contestar

Frage 39

Frage
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.
Image:
12 (binary/octet-stream)
Antworten
  • 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

Frage 40

Frage
¿Cuál de las siguientes afirmaciones es CIERTA en la organización hashing?
Antworten
  • 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.

Frage 41

Frage
¿Cuál de las siguientes funciones elegirías para la función hash?
Antworten
  • 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.

Frage 42

Frage
¿Cuál de las siguientes funciones elegirías para la función hash?
Antworten
  • 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.

Frage 43

Frage
Asumiendo que no hay colisiones, ¿cuál de las siguientes afirmaciones es CIERTA en la organización hashing?
Antworten
  • La consulta es de orden O(1)
  • La consulta es de orden O(2)
  • La consulta es de orden O(3)
  • No contestar

Frage 44

Frage
¿Cuál de las siguientes funciones elegirías para la función hash?
Antworten
  • 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

Frage 45

Frage
¿Cuál de las siguientes afirmaciones es CIERTA en la organización hashing?
Antworten
  • Se puede usar también en memoria interna
  • Se puede usar también en memoria externa.
  • No contestar
Zusammenfassung anzeigen Zusammenfassung ausblenden

Möchten Sie mit GoConqr kostenlos Ihre eigenen Quiz erstellen? eigenen Mehr erfahren.

ähnlicher Inhalt

Tipos de Estructuras de Datos
Tania Cedeño Párraga
ESTRUCTURA DE DATOS I - Introduccion
Xibia Cecilia Hurtado
Tipos de Estructura de Datos
yadifg95
MODELOS EDUCATIVOS.
Soco Méndez
Pilas y colas
jmezacogollo
Conceptos Basicos de Arboles Binarios
Uriel Samano
Contenido Lógica y Representación II
Luis Carlos Puerta Arroyave
Estructura de Datos
Yarinelis Bernal
Métodos de Ordenamiento
IRENE AGUILAR JUAREZ
ESTRUCTURA DE DATOS
Lorena Modesto
Examen unidad 1 estructura de datos
Doris Rodriguez
Bibliothek durchsuchen