GATE CS 2025 Set 2 - W3Colleges

Question 21

MCQ · 1 mark · −0.33

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:

(I) Backpatching can be used to generate code for Boolean expression in one pass.

(II) Backpatching can be used to generate code for flow-of-control statements in one pass.

Which ONE of the following options is CORRECT?

Only (I) is correct. Only (II) is correct. Both (I) and (II) are correct. Neither (I) nor (II) is correct.

Explanation

Answer: (C)

In one-pass code generation, a jump is often emitted before the address it should jump to is known. Backpatching handles this: the jump is emitted with an empty target, its position is added to a list, and every jump on the list is filled in once the target becomes known.

(I) is correct. For Boolean expressions with short-circuit evaluation, the jumps taken when the expression is true or false are collected in truelist and falselist and patched later.
(II) is correct. If, if-else and while statements patch their jumps the same way, using these lists and a nextlist, without a second pass.

Answer: C

Question 22

MCQ · 1 mark · −0.33

Given the following syntax directed translation rules:

Rule 1: \(R \rightarrow AB\ \{B.i = R.i - 1;\ A.i = B.i;\ R.i = A.i + 1;\ \}\)
Rule 2: \(P \rightarrow CD\ \{P.i = C.i + D.i;\ D.i = C.i + 2;\ \}\)
Rule 3: \(Q \rightarrow EF\ \{Q.i = E.i + F.i;\ \}\)

Which ONE is the CORRECT option among the following?

Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

Explanation

Answer: (C)

A definition is S-attributed if it uses only synthesized attributes. It is L-attributed if each inherited attribute of a body symbol depends only on inherited attributes of the head and on attributes of symbols to its left. Every S-attributed definition is also L-attributed.

Rule 1: \(A.i\) and \(B.i\) are inherited, so it is not S-attributed. \(A.i = B.i\) takes its value from \(B\), which lies to the right of \(A\), so it is not L-attributed either. The rules are even circular: \(R.i\) needs \(A.i\), which needs \(B.i\), which needs \(R.i\).
Rule 2: \(D.i = C.i + 2\) is inherited, so it is not S-attributed, but it uses only the left sibling \(C\), so it is L-attributed.
Rule 3: only the synthesized \(Q.i\) is computed, so it is S-attributed and therefore L-attributed.

Answer: C

Question 23

MCQ · 1 mark · −0.33

Consider a network that uses Ethernet and IPv4. Assume that IPv4 headers do not use any options field. Each Ethernet frame can carry a maximum of 1500 bytes in its data field. A UDP segment is transmitted. The payload (data) in the UDP segment is 7488 bytes.

Which ONE of the following choices has the CORRECT total number of fragments transmitted and the size of the last fragment including IPv4 header?

5 fragments, 1488 bytes 6 fragments, 88 bytes 6 fragments, 108 bytes 6 fragments, 116 bytes

Explanation

Answer: (D)

IP fragments the whole UDP segment, header included: \(8 + 7488 = 7496\) bytes of IP data.

A fragment has a 20-byte IPv4 header and must fit in 1500 bytes, so it carries at most 1480 data bytes. Since 1480 is a multiple of 8, as fragment offsets require, every fragment except the last carries exactly 1480 bytes.

Five full fragments carry \(5 \times 1480 = 7400\) bytes.
The remaining \(7496 - 7400 = 96\) bytes form a sixth fragment of \(96 + 20 = 116\) bytes.

Leaving out the UDP header gives 88 data bytes (108 bytes with the IP header), the trap in options B and C.

Answer: D

Question 24

MCQ · 1 mark · −0.33

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Any regular language. Any context-free language. Any language accepted by a non-deterministic pushdown automaton. Any decidable language.

Explanation

Answer: (A)

A DFA is simply a DPDA that never touches its stack, so every regular language is accepted by some DPDA. That makes (A) true.

(B) and (C) describe the same class, because non-deterministic PDAs accept exactly the context-free languages. Both fail because DPDAs are strictly weaker: the even-length palindromes \(\{ww^{R} \mid w \in \{a, b\}^{*}\}\) are context-free, but no DPDA can tell where the middle of the input is.
(D) fails because a decidable language such as \(\{a^{n}b^{n}c^{n} \mid n \ge 0\}\) is not even context-free, so no pushdown automaton of either kind accepts it.

Answer: A

Question 25

MCQ · 1 mark · −0.33

Let \(G_{1}, G_{2}\) be Context Free Grammars (CFGs) and \(R\) be a regular expression. For a grammar \(G\), let \(L(G)\) denote the language generated by \(G\).

Which ONE among the following questions is decidable?

Is \(L(G_{1}) = L(G_{2})\)? Is \(L(G_{1}) \cap L(G_{2}) = \emptyset\)? Is \(L(G_{1}) = L(R)\)? Is \(L(G_{1}) = \emptyset\)?

Explanation

Answer: (D)

Emptiness of a CFG is decidable. Mark every variable that can derive a string of terminals: first those with a production whose body has only terminals (or is \(\varepsilon\)), then, repeatedly, any variable with a body made of terminals and marked variables. \(L(G_{1}) = \emptyset\) exactly when the start symbol is never marked, and the marking stops after at most as many rounds as there are variables. So (D) is decidable.

The other three are undecidable for CFGs:

(A) equivalence of two CFGs;
(B) whether two context-free languages share a string;
(C) with \(R = \Sigma^{*}\), it asks whether \(G_{1}\) generates every string, which is undecidable.

Answer: D

Question 26

MCQ · 1 mark · −0.33

Processes \(P1\), \(P2\), \(P3\), \(P4\) arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.

Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

22 15 37 19

Explanation

Answer: (D)

SRTF always runs the ready process with the least remaining time, re-checking whenever a process arrives.

0–2: \(P1\) runs. At time 1, \(P2\) needs 13 but \(P1\) only 9 more.
2–8: \(P3\) (6) preempts \(P1\) (8 left) and finishes at 8.
8–16: \(P4\) arrives needing 9, but \(P1\) needs only 8, so \(P1\) finishes at 16.
16–25: \(P4\) (9) runs before \(P2\) (13).
25–38: \(P2\) runs.

Turnaround time = completion − arrival: \(P1 = 16\), \(P2 = 37\), \(P3 = 6\), \(P4 = 17\). The average is \((16 + 37 + 6 + 17)/4 = 76/4 = 19\) ms; 37 is only \(P2\)'s turnaround time.

Answer: D

Question 27

MSQ · 1 mark

An audit of a banking transactions system has found that on an earlier occasion, two joint holders of account \(A\) attempted simultaneous transfers of Rs. 10000 each from account \(A\) to account \(B\). Both transactions read the same value, Rs. 11000, as the initial balance in \(A\) and were allowed to go through. \(B\) was credited Rs. 10000 twice. \(A\) was debited only once and ended up with a balance of Rs. 1000.

Which of the following properties is/are certain to have been violated by the system?

Atomicity Consistency Isolation Durability

Explanation

Answer: (B), (C)

Each transaction read \(A = 11000\), wrote \(A = 1000\) and added Rs. 10000 to \(B\). The second write to \(A\) overwrote the first: a lost update.

Isolation is violated. Run one after the other, the second transfer would have seen only Rs. 1000 in \(A\); no serial order gives the observed result.
Consistency is violated. A transfer must keep the total \(A + B\) unchanged, but the total grew by Rs. 10000.
Atomicity is not shown to fail: each transaction carried out all of its steps, and nothing was left half done.
Durability is not shown to fail: the committed writes all survived.

Answer: B, C

Question 28

MSQ · 1 mark

Which of the following is/are part of an Instruction Set Architecture of a processor?

The size of the cache memory The clock frequency of the processor The number of cache memory levels The total number of registers

Explanation

Answer: (D)

The ISA is the contract between hardware and software: what a compiler or assembly programmer must know to write correct machine code. It covers the instructions and their encodings, the addressing modes, the data types and the programmer-visible registers. Instructions name registers by number, so the number of registers is fixed by the ISA (D).

Cache size, the number of cache levels and the clock frequency are implementation (microarchitecture) choices. Processors with the same ISA differ in all three yet run the same programs unchanged, only at different speeds. So (A), (B) and (C) are not part of the ISA.

Answer: D

Question 29

MSQ · 1 mark

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \(G\) is/are TRUE?

A DFS tree of \(G\) is a Shortest Path tree of \(G\). Every non-tree edge of \(G\) with respect to a DFS tree is a forward/back edge. If \((u, v)\) is a non-tree edge of \(G\) with respect to a BFS tree, then the distances from the source vertex \(s\) to \(u\) and \(v\) in the BFS tree are within \(\pm 1\) of each other. Both BFS and DFS can be used to find the connected components of \(G\).

Explanation

Answer: (B), (C), (D)

(A) False. In a triangle on \(s, a, b\), DFS from \(s\) may go \(s \to a \to b\), placing \(b\) at depth 2 although the edge \(sb\) puts it at distance 1.
(B) True. If \(u\) is discovered before its neighbour \(v\), then \(v\) is discovered before \(u\) finishes, so \(v\) becomes a descendant of \(u\). Every non-tree edge therefore joins a vertex to one of its ancestors; undirected DFS has no cross edges.
(C) True. BFS depths are shortest distances from \(s\), and an edge \((u, v)\) gives \(d(v) \le d(u) + 1\) and \(d(u) \le d(v) + 1\).
(D) True. Restarting the search (BFS or DFS) from each unvisited vertex visits exactly one connected component per start.

Answer: B, C, D

Question 30

MSQ · 1 mark

Consider the two lists List I and List II given below:

List I	List II
(i) Context free languages	(a) Closed under union
(ii) Recursive languages	(b) Not closed under complementation
(iii) Regular languages	(c) Closed under intersection

For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

(i) – (a), (ii) – (b), and (iii) – (c) (i) – (b), (ii) – (a), and (iii) – (c) (i) – (b), (ii) – (c), and (iii) – (a) (i) – (a), (ii) – (c), and (iii) – (b)

Explanation

Answer: (B), (C)

Test each class against each property:

Context-free languages are closed under union but not under intersection or complementation. For example, with \(m, n \ge 0\), \(\{a^{n}b^{n}c^{m}\}\) and \(\{a^{m}b^{n}c^{n}\}\) are context-free, but their intersection \(\{a^{n}b^{n}c^{n}\}\) is not. So (i) fits (a) and (b), not (c).
Recursive languages are closed under union, intersection and complementation (swap a decider's accept and reject answers). So (ii) fits (a) and (c), not (b).
Regular languages are closed under all three as well, so (iii) fits (a) and (c), not (b).

Option A fails on (ii) – (b) and option D on (iii) – (b), while every pair in B and C is true.

Answer: B, C

Computer Science and Information Technology