Las siguientes preguntas se han hecho en el examen GATE 2010.
1 Considere un gráfico no dirigido completo con el conjunto de vértices {0, 1, 2, 3, 4}. La entrada Wij en la array W a continuación es el peso de la arista {i, j}. 
¿Cuál es el peso mínimo posible de un árbol de expansión T en este gráfico tal que el vértice 0 sea un Node hoja en el árbol T?
(A) 7
(B) 8
(C) 9
(D) 10
Respuesta (D)
Para obtener el árbol de expansión mínimo con el vértice 0 como hoja, primero elimine la fila 0 y la columna 0 y luego obtenga el árbol de expansión mínimo (MST) del gráfico restante. Una vez que tengamos el MST del gráfico restante, conecte el MST al vértice 0 con el borde con peso mínimo (tenemos dos opciones ya que hay dos 1 en la fila 0).
2. En el gráfico dado en la pregunta 1, ¿cuál es el peso mínimo posible de un camino P desde el vértice 1 al vértice 2 en este gráfico tal que P contiene como máximo 3 aristas?
(A) 7
(B) 8
(C) 9
(D) 10
Respuesta (B)
Ruta: 1 -> 0 -> 4 -> 2
Peso: 1 + 4 + 3
3. La secuencia de grados de un gráfico simple es la secuencia de los grados de los Nodes en el gráfico en orden decreciente. ¿Cuál de las siguientes secuencias no puede ser la secuencia de grados de ningún gráfico?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I y II
(B) III y IV
(C) IV únicamente
(D) II y IV
Respuesta (D)
En la secuencia IV, tenemos un vértice con grado 8 que no es posible en un gráfico simple (sin bucles automáticos ni aristas múltiples) con un recuento total de vértices de 8. El grado máximo posible en dicho gráfico es 7.
En la secuencia II, cuatro vértices están conectados a otros 6 vértices, pero los 4 vértices restantes tienen grados como 3, 3, 2 y 2 que no son posibles en un gráfico simple (sin bucles propios ni aristas múltiples).
4. Considere un árbol B+ en el que el número máximo de claves en un Node es 5. ¿Cuál es el número mínimo de claves en cualquier Node no raíz?
(A) 1
(B) 2
(C) 3
(D) 4
Respuesta (B)
Dado que la cantidad máxima de claves es 5, la cantidad máxima de elementos secundarios que puede tener un Node es 6. Por definición de B Tree , la cantidad mínima de elementos secundarios que puede tener un Node sería 6/2 = 3. Por lo tanto, la cantidad mínima de claves que un Node puede tener se convierte en 2 (3-1).
Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, programa de estudios, fechas importantes, notas, etc.
Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA