Parcial Oña 3

Indica cuál de las siguientes afirmaciones es cierta cuando se usa como función hash el método de la división, suponiendo que la clave es 20 y el divisor es 7. Todas las restantes son falsas. La función hash proporciona el valor 3. La función hash proporciona el valor 2. La función hash proporciona el valor 7.

Si aplicamos el algoritmo de Prim al grafo de la figura, sobre del nodo 4, ¿cual es la afirmación correcta?. El tercer lado seleccionado sería el (3,5). Después de seleccionar todos los lados, el valor vector cercano[] para todos nodos será el 4. El tercer lado seleccionado sería el (1, 4). El tercer lado seleccionado sería el (1, 2).

Asumiendo que NO hay colisiones, ¿cúal de las siguientes afirmaciones es CIERTA en la organización hashing?. La consulta es de O(N) si se hace por la clave. La consulta es de O(logN) si se hace por la clave. La consulta no puede ser de O(1) si se hace por un campo que no es la clave. La consulta es de O(N^2) si se hace por la clave. Todas son falsas.

Indica cual de las siguientes afirmaciones es falsa (l = numero de lados). Prim es menos eficiente en grafos poco densos. El algoritmo de Kruskal es mas eficiente en grafos poco densos. El algoritmo de Kruskal es de orden O(Nlog(N)). El algoritmo de Kruskal es de orden O(N^2).

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?. Comprobando si 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. 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. En las comprobaciones se indica que las otras opciones son falsas. 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. Ninguna es correcta.

Si tuvieses que obtener el árbol abarcador de coste mínimo en el grafo que forma la red de carreteras españolas. ¿Cuál de las siguientes afirmaciones sería cierta?. 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 denso. El algoritmo de Prim sería el más eficiente al tratarse de un grafo poco denso.

Al terminar la iteración késima en el algoritmo de FLoyd. ¿Cuál de las siguientes afirmaciones es cierta?. La matriz intermedios tendrá solo un nodo con numeración superior a k. Todas son falsas. La matriz intermedios tendrá solo un nodo con numeración inferior a k. La matriz intermedios solo puede tener al nodo k.

Suponiendo que se utiliza como función hash el método de la división con divisor = 5, que la tabla tiene 5 elementos, y la tabla ya tiene algunos elementos: tabla[0] = vacio tabla[1] = 11 tabla[2] = vacio tabla[3] = 8 tabla[4] = 14 Di cual de las siguientes afirmaciones es cierta utilizando linear probing para resolver colisiones: Si se borrase la clave 14, la clave 24 iría a la posición 4 de la tabla. Todas las afirmaciones son falsas. La clave 5 iría a la posición 2 de la tabla. La clave 21 iría a la posición 0 de la tabla.

En una iteración del algoritmo de Prim o del algoritmo de Kruskal se selecciona un lado que enlaza dos conjuntos distintos. ¿Porqué?. Porque así se garantiza que tres lados no incidan en un nodo. Porque así garantiza que no haya caminos duplicados, es decir, que no se pueda ir de un nodo a otro por 2 caminos distintos. Porque así se garantiza que se obtengan todas las posibles soluciones. Porque así se garantiza que la solución sea única.

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 un valor, se seleccionará el de menor numeración. Todas son falsas. El lado 5,7 es cruzado. El lado 3,4 es de retroceso. El lado 3,4 es cruzado. El lado 5,1 es de retroceso.

El grado de la figura, si aplicamos el algoritmo de Dijkstra tomando como origen el nodo 1, cuál de las siguientes afirmaciones es cierta. El predecesor del nodo 4 será el 5. El predecesor del nodo 5 será el 3. El predecesor del nodo 2 será el 7. Todas son falsas.

Indica cuál de las siguientes afirmaciones se cumple después de la iteración k-ésima del algoritmo de Floyd. Se obtienen las distancias y caminos mínimos entre todos los pares de nodos, pasando únicamente por el nodo k. Se obtienen las distancias y caminos mínimos entre todos los k primeros nodos. Se obtienen las distancias y caminos mínimos utilizando como nodo intermedio 2k-1-2. No se encuentra el número de la frecuencia entre los restantes.

Sabiendo que se usa la función hash del método folding, que la clave es 152398013 y que las particiones son de tres dígitos, el resultado de la función hash es: 465. 365. 564. Todas son falsas.

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. El lado 2,5 es raíz del árbol. El lado 4,3 es de retroceso. El lado 4,3 es cruzado. El lado 5,1 es de retroceso. Todas son falsas.

¿Cual afirmación es cierta en la implementación de un grafo basada en la matriz de adyacencia?. Todas las demás son falsas. Su tamaño depende del número de lados. La comprobación de si dos nodos están conectados es poco eficiente. Siempre ocupa más espacio que si se usan listas de adyacencia.

Indica cual de las siguientes afirmaciones es cierta sobre el reashing. En general no provoca ningún tipo de clustering. Todas las demás son falsas. Puede aumentar el clustering primario pero no el secundario. Puede provocar el clustering primario pero no el secundario. No puede aumentar el clustering primario pero si el secundario.

¿Cuál de las siguientes afirmaciones es cierta sobre la clasificación topológica?. Todas las restantes son falsas. El orden de los nodos no depende del nodo inicial del recorrido. Se puede aplicar a cualquier nodo de grafo dirigido. Clasifica a los nodos teniendo en cuenta los pesos de los lados que inciden en ellos.

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. El tercer nodo del que se obtiene la distancia mínima es el 4. El tercer nodo del que se obtiene la distancia mínima es el 2. El tercer nodo del que se obtiene la distancia mínima es el 3. El tercer nodo del que se obtiene la distancia mínima es el 1.

Si aplicamos el algoritmo de Kruskal al grafo de la figura ¿cual es la afirmación correcta?. El segundo lado seleccionado sería el (1,4). El lado (2,4) forma parte de la solución. El tercer lado seleccionado sería el (1,4). El primer lado seleccionado sería el (1,4). Ninguna es correcta.

Indica cuál de las siguientes afirmaciones es cierta sobre el random probing. Aumenta clustering primario reduce el secundario. Todas las demás son falsas. Provoca algún tipo de clustering. Provoca clustering primario pero no secundario.