Estructuras de datos y algoritmos | Conjunto 27

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.

 undirected graph

¿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)?

parse tree

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *