Quiz
Estructura de Datos 3º Parcial : Completo
Fragen in diesem Quiz (46)
1¿Cuál de las siguientes afirmaciones es CIERTA en la organización hashing?
- ALa función hash debe distribuir uniformemente las claves a la hora de determinar el cubo.
- BLas colisiones no dependen de la función hash.
- CNo contestar.
- DLa función hash nunca producirá colisiones.
- ELa función hash no debe distribuir uniformemente las claves a la hora de determinar
el cubo.
2¿Cuál de las siguientes funciones elegirías para la función hash?
- AUna que utilice el resto de dividir el dni por un entero primo.
- BNo contestar.
- CUna que utilice como base la primera letra del primer apellido.
- DUna que utilice como base la primer letra del nombre.
- EUna que utilice como base la primera letra del segundo apellido.
3¿Cuál de las siguientes funciones elegirías para la función hash?
- AUna que use como base las dos últimas cifras del dni.
- BUna que utilice como base las dos primeras letras del segundo apellido.
- CUna que utilice como base las dos primeras letras del nombre.
- DUna que utilice como base las dos primeras letras del segundo
apellido.
4Al aplicar el algoritmo de Floyd, ¿cuál de las siguientes afirmaciones es cierta?
- AEl 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.
- BEl 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. - CNo contestar.
- DEl 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.
- EEl camino mínimo de un nodo i a un j siempre es directo y no pasa por intermedios.
5Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz de adyacencia, indica cual de las siguientes opciones es cierta.
- APodemos saber si existe algún camino que enlaza dos nodos cualesquiera y cuantos caminos enlazan esos dos nodos.
- BSolo podemos saber si existe camino que enlace dos nodos cualesquiera.
- CObtenemos los caminos mínimos entre dos nodos cualesquiera.
- DNo contestar.
- ESolo podemos saber los posibles cuantos caminos enlazan dos nodos cualesquiera.
6En 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.
- A1,2,3,4, 6,5,7
- B1,2,3,4,5,7,6
- C1,3,4,2,6,5,7
- D1,2,3,4,5,6,7
- ENo contestar.
7Cual de las siguientes afirmaciones es CIERTA en el recorrido en profundidad de un grafo no dirigido.
- AEl número de árboles resultante en el bosque no depende del nodo de comienzo.
- BEl bosque resultante no puede tener más de un árbol.
- CNo contestar.
- DNo hay lados de avance.
- EPuede tener lados cruzados.
8¿Cual de las siguientes afirmaciones es cierta sobre el algoritmo de Kruskal?(N = número de nodos, L = número de lados).
- AOrdena los lados de menor a mayor y selecciona los L-1 más pequeños.
- BOrdena los lados de menor a mayor y selecciona los L-1 más pequeños que no formen ciclos.
- COrdena los lados de menor a mayor y selecciona los N-1 más pequeños que no formen ciclos.
- DNo contestar
- EOrdena los lados de menor a mayor y selecciona los N-1 más pequeños.
9¿Cuál de las siguientes afirmaciones es CIERTA sobre el problema del árbol abarcador de coste mínimo?
- ASe pueden obtener varias soluciones, pero todos los árboles solución han de tener el mismo coste.
- BNo contestar.
- CSiempre hay una solución única.
- DNo tiene porqué tener solución.
- ESe pueden obtener varias soluciones y los árboles solución pueden tener distintos costes..
10Indica cual de las siguientes afirmaciones es FALSA cuando se obtiene el árbol abarcador de coste mínimo.
- ACualquier camino que incluya a lados del árbol es mínimo.
- BSe puede acceder de un nodo a cualquier otro usando los lados del árbol.
- CNo se puede obtener otra solución con un coste inferior al obtenido.
- DLa solución no tiene por qué ser única.
- ENo contestar.
11En 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).
- AEl lado 2,3 es de árbol.
- BEl lado 3,4 es cruzado.
- CEl lado 5,1 es de retroceso.
- DEl lado 5,7 es cruzado
- ENo contestar
12En 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?
- AComprobando 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.
- BComprobando 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.
- CNo hay que comprobar, ya que no puede acortar la distancia.
- DNo contestar.
- EComprobando 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.
13¿Cual es el principal inconveniente de la implementación de un grafo basada en listas de adyacencia?
- AEs más complicado determinar si dos nodos son adyacentes.
- BDesperdicia más memoria que la matriz de adyacencia
- CNo contestar.
- DEl recorrido de los lados que inciden en un nodo es menos eficiente que en la matriz de adyacencia.
- ESu tamaño no depende del número de lados.
14¿Cuál de las siguientes afirmaciones es FALSA?
- AEl orden selección de los lados en el algoritmo de Kruskal depende de nodo de inicio de
- BEl algoritmo de Kruskal es de orden O(l log l).
- CNo contestar
- DEl algoritmo de Prim es más eficiente en grafos muy densos.
- EEl algoritmo de Prim es de orden O(n^2)
15Indica cual de las siguientes afirmaciones se cumple después de la iteración k-ésima del algoritmo de Floy.
- ASe obtienen los caminos y distancias mínimas entre todos los pares de nodos usando como posibles intermedios los k primeros nodos.
- BSe obtienen las distancias y caminos mínimos del nodo k al resto de nodos.
- CNo contestar,
- DSe obtienen las distancias y caminos mínimos entre todos los k primeros nodos.
- ESe obtienen las distancias y caminos mínimos entre todos los pares de nodos, pasando únicamente por el nodo k.
16Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 4, ¿cual es la afirmación correcta?.
- AEl último lado seleccionado sería el (3,5).
- BEl primer lado seleccionado sería el (1,4) .
- CNo contestar.
- DEl segundo lado seleccionado sería el (1,4)
- EDespués de seleccionar todos los lados, el valor vector cercano[] para todos nodos será el 4.
17Si calculamos las potencias sucesivas (hasta llegar a A^N) de la matriz de adyacencia, indica cual de las siguientes opciones es FALSA.
- APodemos saber el camino mínimo entre dos nodos.
- BNo contestar.
- CPodemos saber si dos nodos están conectados.
- DPodemos saber si hay caminos de longitud l< N que enlazan dos nodos.
- EPodemos saber si hay ciclos.
18¿Cual de las siguientes afirmaciones es CIERTA en el algoritmo de Warshall?
- AEs de orden O(N^3)
- BEs de orden O(N) .
- CEs de orden O(N^2)
- DEs de orden O(N log N)
- ENo contestar.
19Indica cual de las siguientes afirmaciones es CIERTA en el algoritmo de Dijkstra.
- ASu orden de complejidad es el mismo que si se aplicase para calcular la distancia mínima desde el origen a un nodo destino fijo.
- BNo contestar.
- CSi hay algún nodo al que no se pueda acceder desde el nodo origen, no se puede aplicar.
- DSu orden de complejidad depende del número de lados del grafo.
20En una iteración del algoritmo de Prim o del algoritmo de Kruskal se selecciona un lado que enlaza dos conjuntos distintos. ¿Porqué?
- APorque así se garantiza que se obtengan todas las posibles soluciones.
- BPorque así se garantiza que la solución sea única.
- CPorque así se garantiza que no haya ciclos.
- DPorque así se garantiza que tres lados no incidan en un nodo.
- ENo contestar.
21Si aplicamos el algoritmo de Prim al grafo de la figura, partiendo del nodo 5, ¿cual es la afirmación correcta?
- ALa solución no cambiaría si se comenzase en el nodo 4.
- BLa solución cambiaría si se comenzase en el nodo 3.
- CDespués de seleccionar el segundo lado de la solución, el valor del vector Cercano[3] es el nodo 1.
- DDespués de seleccionar todos los lados, el más cercano a todos será el 1.
- ENo contestar.
22Si 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.
- A(1,5) (5,4)(1,2)(5,3)
- B(1,5)(5,4)(1,4)(1,2)
- C(1,5)(1,4)(1,2)(1,3)
- D(1,5)(5,4)(3,5)(1,2)
- ENo contestar.
23¿Cuál de las siguientes afirmaciones es cierta sobre la clasificación topológica?
- AEl orden resultante depende del nodo de comienzo.
- BClasifica a ls nodos teniendo en cuenta los pesos de los lados que inciden en ellos.
- CSe puede aplicar a cualquier tipo de grafo dirigido.
- DSe puede aplicar a cualquier tipo de grafos acíclicos.
- ENo contestar.
24En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen
el nodo 5, cual de las siguientes afirmaciones es cierta.
- AEl segundo nodo del que se obtiene la distancia mínima es el 4.
- BNo contestar.
- CEl segundo nodo del que se obtiene la distancia mínima es el 1.
- DEl segundo nodo del que se obtiene la distancia mínima es el 3.
- EEl segundo nodo del que se obtiene la distancia mínima es el 2.
25Si 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?
- AEl algoritmo de Kruskal sería el más eficiente al tratarse de un grafo poco denso.
- BNo contestar.
- CEl algoritmo de Prim sería el más eficiente al tratarse de un grafo denso.
- DEl algoritmo de Kruskal sería el más eficiente al tratarse de un grafo denso.
- EEl algoritmo de Prim sería el más eficiente al tratarse de un grafo poco denso.
26En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen
el nodo (2), cúal de las siguientes afirmaciones es cierta.- ANinguna de las otras es cierta.
- BEl predecesor del 4 será el 5.
- CEl predecesor del 1 será el 5.
- DEl predecesor del 2 será el 5.
27En 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á:
- A2,4,1,3,5
- BNo contestar.
- C1,3,5,2,4
- D1,2,3,4,5
- E1,2,4,3,5
28¿Cual es el principal inconveniente de la implementación de un grafo basada en la
matriz de adyacencia?- AEl desperdicio de memoria en grafos poco densos.
- BNo contestar.
- CLa comprobación de si dos nodos están conectados es poco eficiente.
- DSiempre ocupa más espacio que si se usan listas de adyacencia.
- ESu tamaño depende del número de lados.
29Al terminar la iteración késima en el algoritmo de Floyd. ¿Cual de las siguientes afirmaciones es CIERTA?
- ALa matriz de intermedios solo puede tener nodos con numeración menor o igual a k.
- BNo contestar.
- CLa matriz de intermedios solo puede tener al nodo k.
- DLa matriz de intermedios tendrá solo nodos con numeracion superior a k.
- ELa matriz de intermedios puede tener a cualquier nodo.
30Desde 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?- AEl uso de listas de adyacencia sería lo más eficiente.
- BNo contestar.
- CLa matriz de adyacencia apenas supondría desperdicio de memoria.
- DEl uso de la matriz de adyacencia sería lo más eficiente.
- ELa matriz de adyacencia y las listas de adyacencia serían iguales de eficientes.
31¿Cual de las siguientes afirmaciones es falsa en la implementación de un grafo?
- AEl tiempo empleado para saber si dos nodos están conectados es constante si se usan listas de adyacencia
- BNo contestar.
- CEn una matiz de adyacencia puede desperdiciarse memoria.
- DEl tiempo empleado para saber si dos nodos están conectados es constante si se usa una matriz de adyacencia.
- ELas listas de adyacencia optimizan la búsqueda de los lados incidentes en un nodo.
32¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Dijkstra?
- AEs de orden O(N²).
- BNo contestar.
33Si 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.
- ASe crea un bosque con dos árboles.
- BNo contestar.
34¿Cual de las siguientes afirmaciones es FALSA?
- ALa 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)
- BNo contestar.
35Si 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):- A4, 3, 6, 7, 1, 2, 5.
- BNo contestar.
36¿Cuál de las siguientes afirmaciones es cierta sobre el algoritmo de Floyd?
- AEs de orden O(N^3).
- BNo contestar.
37Si aplicamos el algoritmo de Kruskal al grafo de la figura ¿cual es la afirmación
correcta?- AEl último lado seleccionado sería el (3,5)
- BNo contestar.
38Si 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.- AEl lado 4,7 es de árbol.
- BNo contestar.
39En el grafo de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen
el nodo (1), cual de las siguientes afirmaciones es cierta.- AEl predecesor del nodo 5 es el 3.
- BNo contestar.
40Cuando 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?- APesoLado(x,k) < coste(k).
- BNo contestar.
41Asumiendo que no hay colisiones, ¿cuál de las siguientes afirmaciones es CIERTA
en la organización hashing?- ALa consulta es de orden O(1).
- BNo contestar.
- CLa consulta es de O(logN)
- DLa consulta es de O(N)
- ELa consulta es de O(N^2)
42¿Cuál de las siguientes funciones elegirías para la función hash?
- AUna 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.
- BNo contestar.
43¿Cuál de las siguientes afirmaciones es CIERTA en la organización hashing?
- ASe puede usar también en memoria interna.
- BNo contestar.
- CEl acceso es más lento que en la organización indexada.
- DNo se puede usar en memoria interna
- ENo es recomendable para accesos rápidos.
44¿Cuál es el número de lados en un grafo dirigido de densidad máxima?
- AN*(n-1)
- BNo contestar.
45¿Cuál de las siguientes afirmaciones es cierta en el algoritmo de Warshall?
- ASi se aplica a un grafo conexo no dirigido, todos los elementos de la matriz resultado son 1.
- BNo contestar.
46¿Cuál de las siguientes afirmaciones falsa?
- ALa implementación basada en listas de adyacencia ocupa un espacio de O(m+n) (n = nodos, m = lados).
- BNo contestar.
Informationen
- Beschreibung
- Estructura de Datos 3º Parcial : Completo
- Autor
- Team Getppid() Rulz
- Sprache
- Español
- Aufrufe
- 803
- Schlagwörter
- Bewertung
- 2,0 von 5 · 1 Bewertung Bewerte dieses Quiz