The number of distinct minimum-weight spanning trees of the following graph is ............
\begin{center}
\includegraphics[width=0.5\textwidth]{59.png}
\end{center}
Show Hint
Solution and Explanation
Step 1: Analyze the graph and find the minimum weight. The graph has 7 edges with weights: \(2, 2, 2, 3, 3, 3, 1\). To construct a minimum spanning tree (MST), the sum of edge weights must be minimized.
Step 2: Apply Kruskal's algorithm. Using Kruskal's algorithm: Select the edge with weight \(1\) (unique choice). Choose three edges of weight \(2\). These edges form a cycle, allowing multiple choices. Choose one edge of weight \(3\) to complete the MST.
Step 3: Count the distinct combinations. There are \(\binom{3}{2} = 3\) ways to choose two edges of weight \(2\). For each choice, there are \(3\) ways to select one edge of weight \(3\). The total number of distinct MSTs is: \[ 3 \times 3 = 9. \]
Final Answer: \[ \boxed{9} \]
Top Questions on Syntax Directed Translation
Given the following syntax directed translation rules:
Rule 1: \( R \to AB \) { \( B.i = R.i - 1 \); \( A.i = B.i \); \( R.i = A.i + 1 \); }
Rule 2: \( P \to CD \) { \( P.i = C.i + D.i \); \( D.i = C.i + 2 \); }
Rule 3: \( Q \to EF \) { \( Q.i = E.i + F.i \); }
Which ONE is the CORRECT option among the following?- GATE CS - 2025
- Compiler Design
- Syntax Directed Translation
- Consider the following augmented grammar, which is to be parsed with an SLR parser. The set of terminals is \(\{a, b, c, d, \#, @\}\). \[ S' \rightarrow S \quad S \rightarrow SS \, | \, Aa \, | \, bAc \, | \, BC \, | \, bBa \quad A \rightarrow d\# \quad B \rightarrow @ \] Let \(I_0 = \text{CLOSURE}(\{S' \rightarrow \cdot S\}\). The number of items in the set \(GOTO(I_0, S)\) is ............
- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
- Consider the following expression: \(x[i] = (p + r) * -s[i] + u / w\). The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6). \begin{center} \begin{tabular}{|c|c|c|c|} \hline (0) & \(+\) & \(p\) & \(r\)
\hline (1) & & &
\hline (2) & \texttt{uminus} & \((1)\) &
\hline (3) & & &
\hline (4) & \(/\) & \(u\) & \(w\)
\hline (5) & \(+\) & \((3)\) & \((4)\)
\hline (6) & & &
\hline (7) & \(=\) & \((6)\) & \(x[i]\)
\hline \end{tabular} \end{center} Which one of the following options fills in the missing entries CORRECTLY?- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
- Consider the following context-free grammar where the start symbol is \(S\) and the set of terminals is \(\{a, b, c, d\}\): \[ S \to AaAb \, | \, BbBa \quad \quad A \to cS \, | \, \epsilon \quad \quad B \to dS \, | \, \epsilon \] The following is a partially-filled LL(1) parsing table. \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline & \(a\) & \(b\) & \(c\) & \(d\) & \(\$\)
\hline \(S\) & \(S \to AaAb\) & \(S \to BbBa\) & (1) & (2) &
\hline \(A\) & \(A \to \epsilon\) & (3) & \(A \to cS\) & &
\hline \(B\) & (4) & \(B \to \epsilon\) & & \(B \to dS\) &
\hline \end{tabular} \end{center} Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table? Note: In the options, "blank" denotes that the corresponding cell is empty.}- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
- Let \(A\) be an array containing integer values. The distance of \(A\) is defined as the minimum number of elements in \(A\) that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array \([2, 5, 3, 1, 4, 2, 6]\) is ...........\_\_\_.
- GATE CS - 2024
- Compiler Design
- Syntax Directed Translation
Questions Asked in GATE CS exam
In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and the line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT?
Note: The figure shown is representative
- GATE CS - 2025
- Geometry
Consider the relationships among P, Q, R, S, and T:
• P is the brother of Q.
• S is the daughter of Q.
• T is the sister of S.
• R is the mother of Q.
The following statements are made based on the relationships given above.
(1) R is the grandmother of S.
(2) P is the uncle of S and T.
(3) R has only one son.
(4) Q has only one daughter.
Which one of the following options is correct?- GATE CS - 2025
- Blood Relations
A quadratic polynomial \( (x - \alpha)(x - \beta) \) over complex numbers is said to be square invariant if \[ (x - \alpha)(x - \beta) = (x - \alpha^2)(x - \beta^2). \] Suppose from the set of all square invariant quadratic polynomials we choose one at random. The probability that the roots of the chosen polynomial are equal is ___________. (rounded off to one decimal place)
- GATE CS - 2025
- Probability
A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)
- GATE CS - 2025
- Memory hierarchy
Consider the following hierarchical cache system with the following access times:
\[ \begin{array}{|c|c|c|} \hline \textbf{Cache Level} & \textbf{Hit Rate} & \textbf{Access Time} \\ \hline L1 & 90\% & 1 \text{ ns} \\ L2 & 80\% & 10 \text{ ns} \\ L3 & 100\% & 100 \text{ ns} \\ \hline \end{array} \]Find \( T_{avg} \) for hierarchical or simultaneous access.