GATE 2025 CS (Computer Science) Session 2 question paper with solutions

The blank needs a noun meaning firm determination that "never wavered" despite initial hesitation. Ambivalence means mixed feelings, the opposite of what is described. Satisfaction does not fit "to contribute". Revolve is a verb meaning to rotate. Resolve (noun) means firm determination. Answer: (C) resolve.

Concept: Vocabulary in context: the contrast word "Despite" and the phrase "never wavered" point to determination. The trap is the look-alike word revolve, or ambivalence, which echoes the hesitation rather than contrasting with it.

A nest is the home a bird builds. The home of a bee is a hive. A kennel houses a dog, a lair is a wild animal's den and a hammock is a hanging bed. Answer: (C) Hive.

Concept: Animal-to-dwelling analogy. The trap is lair, which is also an animal home but for wild beasts, not bees.

Multiply both sides by e^x: P e^(2x) = Q for every real x. The left side changes with x unless P = 0, and the right side is a constant. So P = 0, and then Q = P e^(2x) = 0. Check: P = Q = 1 gives e^x = e^(-x), true only at x = 0. P/Q = 0 needs Q nonzero, but Q must be 0, so P/Q is undefined. Answer: (A) P = Q = 0.

Concept: An identity holding for all x forces coefficients of independent functions to match; e^x and e^(-x) are linearly independent. The trap is checking a single value like x = 0, which makes option (B) look right.

(A) fails: 2 + 3 = 5 is prime. (B) p1p2 has divisors 1, p1, p2 and p1p2 with p1, p2 at least 2, so it is never prime: true. (C) fails: 3 + 5 + 1 = 9. (D) fails: 3 x 5 + 1 = 16. Answer: (B) p1p2 is not a prime number.

Concept: "For all values" statements are killed by one counterexample, and the prime 2 is the usual counterexample. A product of two primes always has a nontrivial factor.

"Even if I had known" is a counterfactual conditional: it describes a situation contrary to fact. So Ramya did not know that Josephine was in the hospital. Nothing is said about past friendship or the cause of the hospital stay, so (C) and (D) are not supported, and (A) contradicts the counterfactual. Answer: (B).

Concept: Past-perfect "had known" signals an unreal past condition. The trap is reading emotional content (a broken friendship) that the sentence does not state.

IMAGE reversed is EGAMI; shifting each letter forward by one gives FHBNJ. FIELD reversed is DLEIF; shifted by one gives EMFJG, confirming the rule. BEACH reversed is HCAEB; shifted by one gives IDBFC. Answer: (B) IDBFC.

Concept: Coding-decoding: test reversal and letter shifts together, and verify the rule on the second example before applying it.

X: 20 + (-4) = 16, 16 + 10 = 26, 26 + 15 = 41, so X(i) = X(i-1) + I(i). Y: 20 x (-4) = -80, -80 x 10 = -800, -800 x 15 = -12000, so Y(i) = Y(i-1)I(i). Option (D) would give Y(1) = 20 x 20 = 400. Answer: (A).

Concept: Fit a recurrence by testing each candidate on the first step, then confirm on the rest. The trap in (D) is the off-by-one index I(i-1).

Triangle PLS has base PL and its third vertex S lies on MN, the side opposite PL. So its height over PL equals the rectangle's width, and area(PLS) = half of area(PLMN). Viewed inside the square, triangle PLS has base PS = 2 and L on QR, which is parallel to PS at distance 2, so area(PLS) = (1/2)(2)(2) = 2. Hence area(PLMN) = 2 x 2 = 4 cm². Answer: (D) 4.

Concept: A triangle on one side of a parallelogram with its apex on the opposite side has half its area. The same triangle is half the square, so rectangle and square are equal. Trying to find the rectangle's sides directly is the slow trap.

Treat zones as vertices and bridges as edges. Connecting 5 zones needs at least 4 bridges forming a spanning tree, so (A) with 3 bridges is impossible and (D) with 5 is not least. (B) P, Q, S, T joins Z1-Z2, Z1-Z3, Z1-Z5, Z3-Z5: Z4 is never reached. (C) Q, R, T, V joins Z1-Z3, Z2-Z3, Z3-Z5, Z3-Z4: all five zones connected with 4 bridges. Answer: (C).

Concept: Minimum connections for n regions is n - 1, a spanning tree. The trap is counting bridges without checking that every zone, here Z4, is actually reached.

A² = [[1+4, 2-2], [2-2, 4+1]] = [[5, 0], [0, 5]] = 5I. Then A⁸ = (A²)⁴ = 5⁴ I = 625 I. Answer: (C) [[625, 0], [0, 625]].

Concept: Squaring first exposes A² as a scalar matrix, so high powers are immediate. Equivalently the eigenvalues are ±√5. The trap is stopping at A⁴ = 25I and picking (A).

By parts: ∫ t ln t dt = (t²/2) ln t - t²/4. From 1 to x: (x²/2) ln x - x²/4 + 1/4. Setting this equal to 1/4 gives x²(2 ln x - 1)/4 = 0, so ln x = 1/2 and x = √e. Answer: (A) √e.

Concept: Integration by parts with u = ln t. Forgetting the lower-limit term +1/4 is the usual slip and leads to a wrong equation.

Let I be internal nodes (two children each) and L leaves. Edges = n - 1 = 2I, so I = (n - 1)/2. Check: a single node gives 0; a root with two leaves gives n = 3, I = 1. Answer: (B) (n - 1)/2.

Concept: Full binary tree counting: every non-root node has one parent edge, and every internal node contributes two. Also L = I + 1, so n is always odd.

L² = L⁻¹ gives L³ = I. Then M = L⁸ = L⁶ L² = L², so M = N and M - N is the zero matrix. det(M - N) = 0. Answer: (A) 0.

Concept: Reduce powers using L³ = I. The trap is computing det L instead of noticing M and N are the same matrix.

(A) is the principle of mathematical induction, valid for every predicate. (B) take P(x) true only at 0: the step P(x) ⇒ P(x-1) holds, yet not all P(x). (C) take P(x) true for x ≤ 1000: premises hold but P(1001) is false. (D) take P(x) true for x ≥ 1000: premises hold but P(0) is false. Answer: (A).

Concept: Induction must start at the least element and step upward. Each wrong option covers only a ray of naturals, shown by a predicate true exactly on that ray.

(i) ARP maps an IPv4 address to the MAC (link-layer) address on the local network: true. (ii) TCP supports piggybacking: a data segment from S to R carries the ACK flag and acknowledgement number for data received from R, so (ii) is false. Answer: (B) (i) is TRUE and (ii) is FALSE.

Concept: Tests ARP's direction (IP to MAC, not the reverse, which was RARP) and TCP piggybacking of ACKs on data segments.

Distance vector routing (for example RIP) computes routes with the distributed Bellman-Ford algorithm. Link state routing (for example OSPF) floods the topology and each router runs Dijkstra's algorithm. Answer: (A) (i) - (a) and (ii) - (b).

Concept: Distance vector uses neighbour-only information iteratively (Bellman-Ford); link state needs the full map and a single-source shortest path computation (Dijkstra).

The IPv4 protocol field names the protocol carried directly inside the IP payload. ICMP (1), IGMP (2) and OSPF (89) are carried directly in IP. RIP runs over UDP (port 520), so the protocol field would say UDP (17), never RIP. Answer: (D) RIP.

Concept: Know which protocols sit directly on IP. The trap is assuming all routing protocols are alike: OSPF is directly over IP, RIP over UDP, BGP over TCP.

a holds "@#Hello World!" in a[0..13] with '\0' at a[14]. stringcopy copies from a+2 to a, character by character, while *t is not '\0': the 12 characters "Hello World!" go to a[0..11]. The loop stops at the terminator without copying it. a[12] and a[13] still hold 'd' and '!', and a[14] is '\0'. printf prints "Hello World!d!". Answer: (D).

Concept: The copy loop omits the null terminator, so leftover characters of the old string stay visible. The trap is answering (B), assuming a normal strcpy.

Pick any two elements and compare them once. The smaller one cannot be the largest element of the list, since the other is bigger. Zero comparisons cannot work because no element is known to be non-maximal. Answer: (A) 1.

Concept: Read the question: any non-largest element is enough, not the largest itself. The trap is answering N - 1, the cost of finding the maximum.

Backpatching keeps lists of jumps with unfilled targets (truelist, falselist, nextlist) and fills them in when the target label becomes known. This is exactly what lets a compiler generate code for Boolean expressions with short-circuit jumps and for flow-of-control statements (if, while) in a single pass. Both statements are correct. Answer: (C).

Concept: Backpatching exists to avoid a second pass over generated code; the textbook treatment applies it first to Boolean expressions and then to control flow.

Rule 1: A.i = B.i makes A's attribute depend on its right sibling B, which violates L-attribution; it also has inherited attributes, so it is not S-attributed. Neither. Rule 2: D.i = C.i + 2 is inherited from the left sibling (allowed in L-attributed, not in S-attributed); P.i is synthesized. So L-attributed, not S-attributed. Rule 3: only the head is computed from children: S-attributed and hence also L-attributed. Answer: (C).

Concept: S-attributed means only synthesized attributes. L-attributed allows inherited attributes that depend only on the parent and left siblings. Every S-attributed definition is L-attributed. The trap is missing the right-sibling dependency in Rule 1.

IP payload = UDP header 8 + data 7488 = 7496 bytes. With a 20-byte IP header and MTU 1500, each fragment carries at most 1480 bytes of payload (a multiple of 8, so valid). 7496 = 5 x 1480 + 96, so there are 5 full fragments and a 6th carrying 96 bytes. Last fragment size = 96 + 20 = 116 bytes. Answer: (D) 6 fragments, 116 bytes.

Concept: Fragmentation splits the whole IP payload, which includes the UDP header. Forgetting the 8-byte UDP header gives 88 bytes of payload and the trap answers 88 or 108.

Every regular language is accepted by a DFA, and a DFA is a DPDA that never uses its stack, so (A) holds. DPDAs accept only the deterministic CFLs, a proper subset of CFLs (for example even-length palindromes are not deterministic), so (B) and (C) fail. Decidable languages such as aⁿbⁿcⁿ are not even context-free, so (D) fails. Answer: (A).

Concept: Hierarchy: regular ⊂ DCFL ⊂ CFL ⊂ decidable. Unlike finite automata, nondeterministic PDAs are strictly more powerful than deterministic ones.

Emptiness of a CFG is decidable: mark generating variables bottom-up and check whether the start symbol is generating. Equivalence of two CFGs, emptiness of the intersection of two CFLs and equality of a CFL with a regular language are all undecidable (the last includes L(G) = Σ*, which is undecidable). Answer: (D).

Concept: For CFLs, membership, emptiness and finiteness are decidable; equivalence, universality, intersection-emptiness and ambiguity are not. The trap is (C): comparing with a regular language does not rescue equivalence.

t=0 P1 starts. t=1 P2 (13) arrives; P1 has 9 left, continues. t=2 P3 (6) arrives; P1 has 8 left, so P3 preempts and runs 2-8. t=8 P4 (9) arrives; remaining P1 8, P2 13, P4 9, so P1 runs 8-16. Then P4 16-25, P2 25-38. Turnaround: P1 16, P2 38-1 = 37, P3 8-2 = 6, P4 25-8 = 17. Average = 76/4 = 19 ms. Answer: (D) 19.

Concept: SRTF re-decides at every arrival using remaining time. The trap is using original burst times, or forgetting to subtract arrival times; 37 is P2's turnaround alone.

Both transactions read A = 11000 before either wrote, and one debit overwrote the other: a lost update, so the interleaving was not equivalent to any serial order and Isolation was violated. The database ended with Rs. 20000 credited but only Rs. 10000 debited, so the invariant that transfers preserve total money broke: Consistency was violated (serially, the second transfer would have been refused for insufficient funds). Each transaction did all its own writes and the results persisted, so Atomicity and Durability are not certainly violated. Answer: (B) and (C).

Concept: Lost-update anomaly: a concurrency (isolation) failure that produces an inconsistent state. The trap is choosing atomicity because money went missing; each transaction itself completed fully.

The ISA is the programmer-visible contract: instructions, addressing modes, data types and the architectural registers. The total number of registers is part of it. Cache size, number of cache levels and clock frequency are implementation (microarchitecture) choices invisible to the instruction set and can differ between processors with the same ISA. Answer: (D).

Concept: Separate architecture from organization. The trap is treating performance features like caches or clock speed as part of the ISA.

(A) False: in a triangle s-a-b, DFS may go s-a-b, giving b depth 2 though its distance is 1. (B) True: in an undirected DFS there are no cross edges; every non-tree edge joins an ancestor and a descendant. (C) True: for any edge (u, v), BFS levels satisfy |d(u) - d(v)| ≤ 1, otherwise the farther vertex would have been discovered earlier. (D) True: repeatedly starting either traversal from an unvisited vertex labels components. Answer: (B), (C), (D).

Concept: Key edge properties: undirected DFS has only tree and back edges; BFS non-tree edges join the same or adjacent levels. Only BFS gives shortest paths in unweighted graphs.

CFLs: closed under union, not closed under complementation, not closed under intersection. Recursive languages: closed under union, intersection and complementation. Regular languages: closed under all three. (A) fails: recursive languages are closed under complement. (B) holds: CFL-(b), recursive-(a), regular-(c). (C) holds: CFL-(b), recursive-(c), regular-(a). (D) fails: regular languages are closed under complement. Answer: (B) and (C).

Concept: Since several pairings are true, check each pair independently. CFLs fail complement and intersection; recursive and regular classes are closed under all Boolean operations.

F = (XY)' + X' + XY' = X' + Y' + X' + XY'. Since XY' is absorbed by Y', F = X' + Y' = (XY)'. (A) (XY)' = X' + Y': equal. (B) X' + Y' + XY' = X' + Y': equal. (C) is the unsimplified circuit expression: equal. (D) X + Y' is 0 at X=0, Y=1 while F = 1 there: not equal. Answer: (A), (B), (C).

Concept: Read the gate outputs, OR them, then simplify with De Morgan and absorption. Several algebraically different forms can be equal; check each against the simplified function.

Booth's algorithm scans multiplier bit pairs (Qi, Qi-1) from the LSB with Q-1 = 0: 10 means subtract M, 01 means add M, 00 and 11 do nothing. Q = 1010 0100 1010 1010. From the LSB the bits are 0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,1. Pairs for i = 0..15: 00, 10, 01, 10, 01, 10, 01, 10, 01, 00, 10, 01, 00, 10, 01, 10. Non-00/11 pairs: 8 (i = 1 to 8) + 2 (i = 10, 11) + 3 (i = 13, 14, 15) = 13. The multiplicand M does not affect the count. Answer: 13.

Concept: Count bit transitions in the multiplier with an implicit 0 appended at the right. Alternating bit patterns are Booth's worst case. The trap is counting operations on M, or forgetting Q-1.

This is the subtraction form of Euclid's algorithm, ending at gcd(x, y). Trace: (126,105) -> (21,105) -> (21,84) -> (21,63) -> (21,42) -> (21,21), stop. gcd(126, 105) = 21. Answer: 21.

Concept: Recognising repeated subtraction as Euclid's GCD saves tracing. The do-while runs its body at least once, harmless here since x ≠ y initially.

Each flip-flop in a ripple counter divides the frequency by 2, so the 4th flip-flop output has frequency f/16. Its period is 64 µs, so its frequency is 1/64 µs = 15.625 kHz. Clock frequency f = 16 x 15.625 = 250 kHz. Answer: 250.

Concept: An n-bit ripple counter is a divide-by-2ⁿ chain. The trap is reporting the last stage's 15.625 kHz instead of the counter's clock frequency.

10 is the root. -4 goes left of 10, 15 right of 10, 30 right of 15, 20 left of 30, 5 right of -4, 60 right of 30, 19 left of 20. Path from 19 to the root: 19 - 20 - 30 - 15 - 10, which has 4 edges. Answer: 4.

Concept: Insert in order, comparing from the root each time. Count edges, not nodes: 5 nodes on the path means 4 edges.

Transmission time = 3000 / 2000 = 1.5 s. Propagation delay = 0.1 s, so round trip = 0.2 s (ACK transmission negligible). Utilization = 1.5 / (1.5 + 0.2) = 1.5 / 1.7 = 0.88235, i.e. 88.23%. Answer: (A) 88.23.

Concept: Stop-and-wait efficiency = Tt / (Tt + 2Tp). The trap is using one-way delay, which gives 93.75%.

Every spanning tree has exactly n - 1 edges, so each tree's weight rises by (n - 1)α and the ranking of trees is unchanged: every MST stays an MST. A path with k edges rises by kα, so paths with more edges are penalized more. Example: s-t direct weight 3, s-a-t with weights 1 and 1. Before, s-a-t (2) is shortest; after adding 2, direct = 5 and s-a-t = 6. SPs need not remain SPs. Answer: (C).

Concept: MSTs depend only on the relative order of edge weights; shortest paths depend on sums over paths of varying length. Multiplying all weights by a positive constant would preserve both.

P: link the first list's tail to the second list's head and update the tail pointer: Θ(1). Q: concatenate the two arrays and run bottom-up build-heap on 2n elements: Θ(n); any method must at least move n elements. R: in-order traverse both trees to get two sorted lists (Θ(n)), merge them (Θ(n)) and build a BST from the sorted list (Θ(n)); every node must be visited, so Θ(n). Answer: (A).

Concept: Build-heap is linear, not n log n, and sorted sequences let a BST be rebuilt in linear time. The traps are repeated insertion costs (n log n or n²).

Block size is 1 byte, so there are no offset bits. Address = tag 4 + index 12 = 16 bits, so main memory = 2¹⁶ bytes = 64 KB. The cache has 2¹² blocks of 1 byte = 4 KB (tags are not counted as no other information is stored). Answer: (A) 64 KB and 4 KB.

Concept: Direct-mapped address split: tag | index | offset. With one-byte blocks the offset is 0 bits, a detail that is easy to overlook.

FOLLOW(A) = {a, c}. From I0 on d: {S → d.c, A → d.}. SLR reduces A → d on FOLLOW(A), including c, while S → d.c shifts c: shift-reduce conflict, so not SLR(1). In LR(1) this item is A → d. with lookahead a only, so no conflict. After b then d: {S → bd.a, A → d.} with LR(1) lookahead c, while shift is on a: no conflict (SLR would conflict on a). The two d-states have different cores, so LALR merging joins nothing and introduces no conflict. G is LALR(1) but not SLR(1). Answer: (C).

Concept: Classic grammar separating SLR from LALR: FOLLOW sets are too coarse, while LR(1) lookaheads are context-specific. Check that LALR merging only combines states with identical cores.

Find the peak by binary search: compare A[mid] with A[mid+1]; if increasing, the peak is to the right, else at or to the left. This takes O(log n). Then binary search the increasing part and the decreasing part separately, O(log n) each. Total O(log n). A lower bound of Ω(log n) holds because a sorted array is a special bitonic array. Answer: (D) Θ(log n).

Concept: Decompose into peak-finding plus two ordinary binary searches. The trap is (C), assuming nested binary searches.

≼ is the componentwise order on n-bit vectors. Reflexive (f(x) ≤ f(x)), antisymmetric (f ≤ g and g ≤ f pointwise gives f = g) and transitive: a partial order. Meet and join are the pointwise min (AND) and max (OR), which are in ℱ, so it is a lattice (isomorphic to the subset lattice of {1..n}). It is not symmetric: the all-0 function ≼ the all-1 function but not conversely, hence also not an equivalence relation. Answer: (B) and (C).

Concept: Functions to {0,1} are characteristic vectors of subsets, and ≼ is set inclusion, the Boolean lattice. A partial order is symmetric only on a trivial set.

The four corner cells (x = 0, z = 0) are 1: group x'z'. The central 2x2 block (x = 1, z = 1) is 1: group xz. All other cells are 0, so F = x'z' + xz. (A) the four minterms are exactly the corners (x'z') plus xz: equal. (B) contains wx'yz, which has x = 0, z = 1, a 0 cell: wrong. (C) contains wx'y'z, also x = 0, z = 1: wrong. (D) is the minimal form. Answer: (A) and (D).

Concept: K-maps wrap around, so the four corners form one group. A sum is correct only if it covers every 1 and no 0; a single stray minterm on a 0 cell disqualifies it.

(A) LUX = Q: put Y = UX, solve LY = Q by forward substitution, then UX = Y by back substitution: true. det L = 1 and det U = u11 u22 u33, so det P = u11 u22 u33. (B) P invertible gives det U ≠ 0, and L is always invertible: true. (C) P singular gives u11 u22 u33 = 0, so some uii = 0: true. (D) false: triangular matrices with nonzero off-diagonal entries are not symmetric; for symmetric P one gets P = LDLᵀ, not symmetric L and U. Answer: (A), (B), (C).

Concept: The determinant of a triangular matrix is the product of its diagonal, which links P's invertibility to U's pivots. Symmetry of P gives U = DLᵀ, not symmetric factors.

(A) On PUSH, store with the new record a pointer to the minimum among the records below it (computed in O(1) from the previous top's own value and pointer). MIN compares the top with its stored pointer: O(1), and POP needs no work. Works. (B) A single global pointer cannot be restored in O(1) after the minimum is popped. Fails. (C) Inserting into a sorted array costs O(n) per PUSH. Fails. (D) Heap insert and delete cost O(log n), raising PUSH/POP above O(1). Fails. Answer: (A).

Concept: The min-stack technique: each stack level remembers the minimum of everything at or below it, so the answer is restored automatically on pop. The trap is (B), which breaks on popping the minimum.

R1: A and D appear on no right side, so both are in every key. AD+ = {A, D, E, B, C}, so AD is the only candidate key and the prime attributes are A, D. D → E: D is not a superkey and E is not prime, so R1 is not in 3NF. R2: C appears on no right side; C+ = {C, A, D, B}, so C is the only key and C is the only prime attribute. A → D: A is not a superkey and D is not prime (a transitive dependency C → A → D), so R2 is not in 3NF. Answer: (C) and (D).

Concept: 3NF requires every nontrivial X → Y to have X a superkey or Y prime. Find keys first using attributes that never appear on a right side; both schemas contain a dependency from a non-key to a non-prime attribute.

At reference 4, frames hold 1, 2, 3 and page 2 is evicted. LRU would evict 1 (least recently used): LRU fails. Optimal: next uses are 1 at position 7, 3 at 12, 2 at 13, so evict 2: matches. At 5, frames 1, 4, 3: next uses 4 at 6, 1 at 7, 3 at 12, evict 3: matches. At 6, frames 1, 4, 5: next uses 4 at 9, 5 at 10, 1 at 11, evict 1: matches. The last three faults find no resident page used again, so any choice is optimal. LFU: at reference 6, page 5 has been used once while 1 and 4 twice, so LFU evicts 5, not 1: fails. MFU: at reference 4 all counts are 1 and the usual FIFO tie-break evicts 1, not 2; with cumulative counts it also evicts 1 at reference 3 instead of 5: fails. Answer: (D).

Concept: Check each policy at the first fault where it would decide differently. Optimal looks forward and evicts the page used farthest in the future. The trap is accepting a policy only through arbitrary tie-breaking.

With single-instance resources, use the wait-for graph: P1 → P2 (R2), P2 → P3 (R3), P3 → P1 (R1), P2 → P4 (R4), P4 → P2 (R2). Cycles: P1-P2-P3-P1 and P2-P4-P2. (A) Aborting P1 leaves the P2-P4 cycle. (B) Aborting P3 leaves the P2-P4 cycle. (C) P2 lies on both cycles; aborting it releases R2, so P1 and P4 can finish, then P3. Deadlock free. (D) Aborting P1 and P4 frees R1 and R4: P3 gets R1 and finishes, releasing R3, then P2 finishes. Deadlock free. Answer: (C) and (D).

Concept: With one instance per resource, a cycle means deadlock. To recover, every cycle must be broken; pick a process common to all cycles or a set covering them.

0xC1100000 = 1 10000010 00100...: sign -, exponent 130 - 127 = 3, mantissa 1.001₂ = 1.125, so X = -9. 0x40C00000 = 0 10000001 100...: exponent 2, mantissa 1.5, so Y = 6. 0x41400000 = 0 10000010 100...: exponent 3, mantissa 1.5, so Z = 12. (A) 4(-3) + 12 = 0: true. (B) 12 - 12 = 0: true. (C) -36 + 36 = 0: true. (D) -9 + 6 + 12 = 9: false. Answer: (A), (B), (C).

Concept: Decode by splitting into sign (1), biased exponent (8, bias 127) and fraction (23) with the hidden leading 1. Forgetting the hidden bit or the bias is the usual error.

(A) LHS minterms (ABC) are 011, 100, 000, 101, 111 = {0, 3, 4, 5, 7}. RHS: BC = {3, 7}, B'C' = {0, 4}, A'B' = {0, 1}, giving {0, 1, 3, 4, 7}: it includes 1 and misses 5. False. (B) Consensus theorem: BC is redundant. True. (C) (A + C)(A' + B) = AA' + AB + A'C + BC = AB + A'C + BC = AB + A'C. True. (D) By De Morgan, the complement of the product is the sum of complements: A'BD + C'D' + AC'D' + A'B'D = A'D(B + B') + C'D'(1 + A) = A'D + C'D'. True. Answer: (B), (C), (D).

Concept: Tests the consensus theorem, product-of-sums expansion and De Morgan over a whole product. Comparing minterm sets is the safest check for (A)-type claims.

Not LL(1): in G1 two S-productions begin with "if"; in G2, S → if E then S and S → M both have "if" in FIRST (M → if ...). So neither is LL(1). G1 is the classic dangling-else grammar: "if b then if b then a else a" has two parse trees. G2 is also ambiguous because the else-part of M is an unrestricted S. M derives "if b then c else if b then c". Then w = "if b then if b then c else if b then c else c" parses as S → if b then S with S = M = if b then c else (if b then c else c), and also as S → M = if b then M' else c with M' = "if b then c else if b then c". Answer: (C) and (D).

Concept: Any ambiguous grammar is not LL(1), and common prefixes also break LL(1). G2 looks like the standard matched/unmatched fix, but allowing an unmatched S after else reintroduces ambiguity.

(A) = a*b*: regular. (B) Intersecting with {a, b}* forbids c, so m - n = 0 and the language is {aⁿbⁿ | n ≥ 0}: not regular (pumping lemma). (C) A product DFA tracking #a mod 7 and #b mod 9 (63 states) accepts it: regular. (D) Requires #a = #b with no bound, an unbounded comparison: intersecting with a*b* gives {aⁿbⁿ | n ≡ 2 mod 7}, not regular, so (D) is not regular. Answer: (A) and (C).

Concept: Modular counting needs finitely many states; equality of two unbounded counts does not. The trap in (B) is that the intersection forces m = n, leaving aⁿbⁿ.

Conflicting pairs: T1's R1(X), R1(X), W1(X) with W2(X); W1(Y) with W2(Y). (A) R1(X) before W2(X): T1→T2; second R1(X) after W2(X): T2→T1. Cycle, not serializable. (B) W2(X) before both R1(X) and W1(X), W2(Y) before W1(Y): all edges T2→T1. Acyclic, equivalent to T2, T1. (C) R1(X) before W2(X): T1→T2; second R1(X) after W2(X): T2→T1. Cycle. (D) W2(X) before R1(X): T2→T1; W1(Y) before W2(Y): T1→T2. Cycle. Answer: (B).

Concept: Build the precedence graph from every conflicting pair (same item, different transactions, at least one write). The repeated R1(X) is the trap: a write by T2 between T1's two reads creates the back edge.

(A) The correlated EXISTS subquery is true exactly when the student has an Enrolled row for 1470: correct. (B) SIZEOF is not an SQL function, so the query is invalid. (C) COUNT(*) of matching Enrolled rows greater than 0: correct. (D) Students and Enrolled share only rollno, so the natural join pairs each student with their enrollments; filtering courseno = 1470 returns the right names: correct. Answer: (A), (C), (D).

Concept: Several SQL forms express "exists a matching row": EXISTS, COUNT > 0, or a join. Check that a natural join uses only the intended common column, and spot non-standard functions.

AMAT = L1 time + L1 miss rate x (L1 miss penalty), where L1 miss penalty = L2 time + L2 miss rate x (L2 miss penalty). L1 miss penalty = 10 + 0.2 x 100 = 30 ns. AMAT = 1 + 0.1 x 30 = 4 ns. Answer: 4.0.

Concept: Nested miss-penalty formula with local hit rates. The trap is multiplying absolute times for every level or treating 80% as a global hit rate.

Clock cycle = max stage delay + latch delay = 250 + 10 = 260 ns. For k = 5 stages and n = 1000 instructions, cycles = k + n - 1 = 1004. Time = 1004 x 260 ns = 261040 ns = 261.04 µs. The accepted range 260.2 to 261.2 covers this; ignoring the pipeline fill (1000 x 260 = 260.00 µs) falls outside it. Answer: 261.04.

Concept: Pipeline cycle time is set by the slowest stage plus latch overhead, and n instructions need k + n - 1 cycles. Forgetting the latch delay or the fill cycles is the trap.

Leaf C is full, so inserting 23 splits {20, 22, 23, 25, 26} into two leaves, and the new leaf's smallest key (23 for a 2|3 split, 25 for a 3|2 split) is copied into B. B = (7, 19, 33, 44) is also full and becomes 5 keys, e.g. (7, 19, 23, 33, 44). An internal split pushes the middle key up to A: left node (7, 19), right node (33, 44), with 23 (or 25) moving to A. The leaf containing 25* covers keys from 23 (or 25) up to 33, so it hangs from the leftmost pointer of the right node (33, 44). Either split choice gives that parent, whose smallest key is 33. Answer: 33.

Concept: Leaf splits copy a key up, but internal splits move the middle key up without keeping it. The trap is assuming the separator stays in the leaf's parent, which would give 23 or 25.

Page offset = log2(4096) = 12 bits. One page of the inner page table holds 4096 / 8 = 512 entries, so the inner index is 9 bits. Outer index b = 32 - 12 - 9 = 11. Answer: 11.

Concept: Each inner page table occupies exactly one page, so its index width is log2(page size / entry size). The trap is assuming 4-byte entries, which gives 10.

Two BFS passes on a tree return its diameter: the first BFS ends at an endpoint of a longest path, the second measures that path. Longest paths here: N-M-K-H-E-F-G and N-M-K-H-E-C-A, each with 6 edges. Check: from E the farthest vertices are N (4 edges) and A, G, D (2 edges), so no path is longer than 4 + 2 = 6. Answer: 6.

Concept: Double BFS computes the diameter of a tree exactly (not of general graphs). Count edges along the longest path, not vertices.

Track prod(x) mod 7. Every symbol is nonzero mod 7 and 7 is prime, so the product is never 0 and the states are the residues 1 to 6. All are reachable: 3 generates the group (3, 2, 6, 4, 5, 1). Accept only residue 2. Any two residues r ≠ s are distinguishable: take y with r·prod(y) ≡ 2; then s·prod(y) ≢ 2. There is no dead state, since every residue can still reach 2. Minimum DFA: 6 states. Answer: 6.

Concept: Myhill-Nerode with a group structure: multiplication by a fixed symbol permutes the residues, so all reachable states stay distinguishable. The trap is counting 7 states, including an unreachable residue 0.

Total cycles = (2 x 2.25 + 5 x 1.20 + 4 x 1.65 + 3 x 1.30) x 10⁸ = (4.5 + 6.0 + 6.6 + 3.9) x 10⁸ = 21 x 10⁸. Clock period = 6.3 s / (2.1 x 10⁹) = 3 x 10⁻⁹ s. Answer: 3.0.

Concept: CPU time = total cycles x cycle time, with total cycles the CPI-weighted instruction counts. The trap is using an unweighted average CPI.

arr = {30, 50, 10, 0, 0}. ptr = &arr[1], so a = 50. (*ptr)++ makes arr[1] = 51. ptr++ points to arr[2] = 10. Output = a + *ptr + arr[1] = 50 + 10 + 51 = 111. Answer: 111.

Concept: Distinguish (*ptr)++ (increments the pointed-to value) from ptr++ (moves the pointer). a was copied before the increment, so it stays 50.

g(f(n)) = (2n + 10) + 10 = 2n + 20. The loop runs for n = 1 and 2: 22 + 24 = 46. Answer: 46.

Concept: Compose the functions symbolically before tracing. The trap is running the loop three times; n < 3 stops after n = 2.

The root multisets must agree: {α, β} = {α², β²}. Case 1: α² = α and β² = β, so α, β ∈ {0, 1}: polynomials x², x(x - 1), (x - 1)². Case 2: α² = β and β² = α, so α⁴ = α, giving α = 0 (β = 0), α = 1 (β = 1), or α a primitive cube root of unity ω with β = ω², giving (x - ω)(x - ω²) = x² + x + 1. Distinct polynomials: x², x² - x, x² - 2x + 1, x² + x + 1. Equal roots in x² and (x - 1)²: probability 2/4 = 0.5. Answer: 0.5.

Concept: Count distinct polynomials, not ordered root pairs. The trap is missing the complex cube-root case or double-counting (ω, ω²) and (ω², ω).

Let the cut be U ~ Uniform(0,1). If U < 0.4, 0.4 lies in (U, 1) of length 1 - U; if U > 0.4, it lies in (0, U) of length U. E = ∫ from 0 to 0.4 of (1 - u) du + ∫ from 0.4 to 1 of u du = (0.4 - 0.08) + (0.5 - 0.08) = 0.32 + 0.42 = 0.74. This lies in the accepted range 0.7 to 0.8. Answer: 0.74.

Concept: Condition on where the cut falls relative to the fixed point. The trap is answering 0.5: the piece containing a given point is size-biased, so it is longer on average.