Se han hecho las siguientes preguntas en el examen GATE CS 2011.
1) Un grafo no dirigido G(V, E) contiene n ( n > 2 ) Nodes llamados v1 , v2 ,….vn. Dos Nodes vi, vj están conectados si y solo si 0 < |i – j| <= 2. A cada arista (vi, vj) se le asigna un peso i + j. A continuación se muestra un gráfico de muestra con n = 4.
¿Cuál será el costo del árbol de expansión mínimo (MST) de tal gráfico con n Nodes?
(A) 1/12(11n^2 – 5n)
(B) n^2 – n + 1
(C) 6n – 11
(D) 2n + 1
Respuesta: (B)
El árbol de expansión mínimo para 2 Nodes sería
(v1) _ (v2)
Peso total 3
El árbol de expansión mínimo para 3 Nodes sería
(v1) _ (v2)
|
(v3)
Peso total= 3 + 4 = 7
El árbol de expansión mínimo para 4 Nodes sería
(v1) _ (v2) _ (v4)
|
(v3)
Peso total= 3 + 4 + 6 = 13
El árbol de expansión mínimo para 5 Nodes sería
(v1) _ (v2) _ (v4)
|
(v3)
|
(v5)
Peso total= 3 + 4 + 6 + 8 = 21
El árbol de expansión mínimo para 6 Nodes sería
(v1) _ (v2) _ (v4) _ (v6)
|
(v3)
|
(v5)
Peso total= 3 + 4 + 6 + 8 + 10 = 31
Podemos observar en los ejemplos anteriores que cuando agregamos el k-ésimo Node, el peso del árbol de expansión aumenta en 2k-2. Sea T(n) el peso del árbol de expansión mínimo. T(n) se puede escribir como
T(n) = T(n-1) + (2n-2) para n > 2
T(1) = 0, T(2) = 0 y T(2) = 3
La recurrencia se puede escribir como suma de series (2n – 2) + (2n-4) + (2n-6) + (2n-8) + …. 3 y la solución de esta recurrencia es n^2 – n + 1.
2) La longitud del camino de v5 a v6 en el MST de la pregunta anterior con n = 10 es
(A) 11
(B) 25
(C) 31
(D) 41
Respuesta: (C)
Cualquier MST que tenga más de 5 Nodes tendrá la misma distancia entre v5 y v6 que la estructura básica de todos los MST (con más de 5 Nodes) sería la siguiente.
(v1) _ (v2) _ (v4) _ (v6) _ . . (more even numbered nodes)
|
(v3)
|
(v5)
|
.
.
(more odd numbered nodes)
Distancia entre v5 y v6 = 3 + 4 + 6 + 8 + 10 = 31
3) Considere dos operadores binarios ‘↑ ‘ y ‘↓’ con la precedencia del operador ↓ menor que la del operador ↑. El operador ↑ es asociativo por la derecha mientras que el operador ↓ es asociativo por la izquierda. ¿Cuál de los siguientes representa el árbol de análisis sintáctico para la expresión (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?
Respuesta: (B)
Consideremos la expresión dada (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2).
Dado que la precedencia de ↑ es mayor, la subexpresión ([3 ↑ 4 ↑ 3) se evaluará primero. En esta subexpresión, 4 ↑ 3 se evaluaría primero porque ↑ es asociativo de derecha a izquierda. Entonces la expresión se evalúa como ((7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2). Además, tenga en cuenta que entre los dos operadores ↓, el primero se evalúa antes que el segundo porque la asociatividad de ↓ es de izquierda a derecha.
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