GATE CS 2025 Set 1

A non-pipelined processor checks for interrupts only between instructions, so it first completes the instruction it is executing (iii). Next it saves the program counter (i), which now holds the address of the next instruction, so the interrupted program can continue from there once the ISR returns. Only then is the program counter loaded with the ISR's start address (ii); doing (ii) before (i) would destroy the return address.

Answer: A

The symbol table is used by nearly every phase of the compiler, not only up to parsing. Semantic analysis uses it for type and scope checks, and intermediate code generation and code generation read the type, size and memory offset of each name from it, so statement (C) is false. The other statements are true: the table records the scope of names (A), it can be organised as a list, a binary search tree or a hash table (B), and entries for identifiers are first made while the lexical analyser scans the source (D).

Answer: C

A variable is live at a point if its current value may still be read later, before it is overwritten; live variable analysis works this out for every point of the program. Register allocation needs exactly this: a register can be handed to another variable once its variable is dead, and two variables that are live at the same time cannot share a register. Strength reduction (cheaper operations on loop induction variables), constant folding (evaluating constant expressions at compile time) and run-time call management (activation records and calling sequences) do not depend on liveness.

Answer: B

A page table has one entry for each page of the logical address space. The page size is \(2048 = 2^{11}\) bytes, so the number of pages is \(\frac{2^{32}}{2^{11}} = 2^{21}\). The 20-bit physical address affects only the size of each entry (a frame number of \(20 - 11 = 9\) bits), not the number of entries.

Answer: A

When \(T_1\) aborts, every transaction that read a value written by \(T_1\) (a dirty read) must also be rolled back; this is a cascading rollback. \(T_1\) wrote only \(Y\). Both \(R_2(Y)\) and \(R_3(Y)\) come after \(W_1(Y)\) with no other write to \(Y\) in between, so \(T_2\) and \(T_3\) both read the uncommitted value. \(R_2(X)\) does not matter, because \(T_1\) only read \(X\).

Answer: C

The network layer decides the path a packet takes from network to network, so (a)-(I) Packet routing. The transport layer works end to end, carrying data between the source and destination hosts, so (b)-(III) Host to host communication. The data link layer packs bits into frames and detects and handles errors on each single link, so (c)-(II) Framing and error handling.

Answer: B

For \(f(g(.))\) to be onto, the values produced by \(g\) only have to be enough for \(f\) to reach every element of \(C\). That puts no one-to-one or onto condition on \(g\) itself.

Counterexample: \(A = \{1, 2\}\), \(B = \{p, q\}\), \(C = \{z\}\), with \(g(1) = g(2) = p\) and \(f(p) = f(q) = z\). Both \(f\) and \(f(g(.))\) are onto, yet \(g\) is not one-to-one (1 and 2 both go to \(p\)) and not onto (\(q\) is never reached). So (A), (B) and (C) are false.

Answer: D

\(T\) is a subgraph of \(G\), so every path between \(u\) and \(v\) in \(T\) is also a path in \(G\). Hence the shortest path in \(G\) can never be longer than the one in \(T\): \(d_1(u, v) \le d_2(u, v)\).

Equality is not guaranteed. Take a triangle \(x, y, z\) with \(w(x, y) = w(y, z) = 1\) and \(w(x, z) = 1.5\); the MST keeps the two edges of weight 1. Then \(d_1(x, z) = 1.5\) but \(d_2(x, z) = 2\), which rules out (A) and (C), while \(d_1(x, y) = d_2(x, y) = 1\) rules out (D).

Answer: B

\(A \to a \mid aA\) generates \(a^{n}\) and \(B \to b \mid bB\) generates \(b^{n}\), for \(n \ge 1\).

So \(S \to aaB\) gives the strings \(a^{2}b^{n}\), and \(S \to Abb\) gives the strings \(a^{n}b^{2}\). Together, \(L(G) = \{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).

The other options do not match: for example, \(aabbb \in L(G)\), but it belongs to none of (B), (C) and (D).

Answer: A

Divide both sides by \(2^{n}\) and put \(S(n) = T(n)/2^{n}\). The recurrence becomes \(S(n) = S(n - 1) + n\) with \(S(0) = 1\).

So \(S(n) = 1 + (1 + 2 + \dots + n) = 1 + \frac{n(n+1)}{2}\), and \(T(n) = 2^{n}\left(1 + \frac{n(n+1)}{2}\right) = \Theta(n^{2}2^{n})\).

Answer: A