GATE 2024 CS (Computer Science) Session 1 question paper with solutions

Dry, arid and parched describe the same idea (lack of water) with rising intensity. Diet means eating less, fast means not eating for a period, and the next, more intense step is to go without food to the point of suffering: starve. Reject, feast and deny do not continue the intensity scale (feast is the opposite). Answer: (A) starve.

Concept: Intensity analogy: the third word must be the strongest form of the same idea. The trap is picking feast because it is food-related, though it reverses the direction.

Proportionality gives x + y = k(x − y) for a fixed constant k. Then x + y = kx − ky, so y(1 + k) = x(k − 1), hence x/y = (k + 1)/(k − 1). This depends only on the constant k, not on x or y individually. Answer: (D) is a constant.

Concept: Proportionality means a fixed ratio, so solving for x/y removes both variables. The trap is assuming the ratio still varies with x or y.

Sort: 9, 10, 11, 11, 13, 14, 15, 17, 18, 69. There are 10 values, so the median is the mean of the 5th and 6th values: (13 + 14)/2 = 13.5. Answer: (A) 13.5.

Concept: Median of an even-sized sample is the average of the two middle values after sorting. Traps: not sorting first, or computing the mean (18.7), which the outlier 69 inflates.

Take 5k, 3k and 13k coins. Value: ₹1 coins = 5k, ₹5 coins = 15k, ₹10 coins = 130k. Total = 150k. Share of ₹5 coins = 15k/150k = 10%. Answer: (C) 10%.

Concept: Convert the count ratio to a value ratio before taking percentages. The trap is using the count share 3/21 = 14 2/7%.

The right side is log(9pq), so p² + q² = 9pq. Square: p⁴ + 2p²q² + q⁴ = 81p²q², so p⁴ + q⁴ = 79p²q². Therefore (p⁴ + q⁴)/(p²q²) = 79. Answer: (A) 79.

Concept: Combine logs into one, drop the log, then use (a + b)² = a² + 2ab + b². The trap is answering 81 by forgetting to subtract 2p²q².

Keep one's head down = stay focused and avoid trouble. A batter heads out to bat. Having a head for something = a natural aptitude for it, so a head for batting. A cool head on one's shoulders = calm and sensible. So (i) down, (ii) out, (iii) for, (iv) on. Answer: (C).

Concept: Tests fixed idioms with prepositions: head down, head out, a head for, a head on one's shoulders. The trap is choosing by sound rather than the fixed phrase.

Joining the two 54 cm edges makes a tube of length 54 cm whose circumference is 4 cm, so r = 2/π. Volume = πr²h = π(4/π²)(54) = 216/π. Sheet area = 216 cm², so cube surface 6a² = 216 gives a = 6 and volume 216. Ratio = (216/π)/216 = 1/π. Answer: (A) 1/π.

Concept: When the longer edges are joined, the shorter side becomes the circumference. The trap is using 54 cm as the circumference, which gives a very different radius.

Fat share = 20% + 20% + 5% = 45% of 2,000 kcal = 900 kcal. All fats give 9 kcal/g, so mass = 900/9 = 100 g. Answer: (C) 100.

Concept: Convert the energy share to kcal, then divide by energy density to get grams. Traps: using 4 kcal/g, or forgetting trans fat.

Each fold halves the current long edge. Fold 1: 20 × 8 becomes 10 × 8. Fold 2: long edge 10 becomes 5, giving 5 × 8. Now the long edge is 8, so fold 3 gives 5 × 4. Perimeter = 2(5 + 4) = 18 cm. Answer: (A) 18.

Concept: 'Its long edge' refers to the sheet as it is at each fold, so the folding direction switches once 8 becomes the longer side. The trap is halving 20 three times (2.5 × 8, perimeter 21).

x³ − x = x(x − 1)(x + 1), so x³ ≥ x on [−1, 0] and [1, ∞), and x ≥ x³ elsewhere. The pieces meet at x = −1, 0, 1. Slopes: at −1, x³ has slope 3 and x has slope 1; at 0, slope 0 vs 1; at 1, slope 1 vs 3. The slopes differ at every crossing, so f has a corner at each. Answer: (D) {−1, 0, 1}.

Concept: A max of two smooth functions can fail to be differentiable only where they cross with different slopes. The trap is forgetting the crossing at x = −1 or 0.

The product of eigenvalues equals the determinant. Row 3 − Row 2 = Row 2 − Row 1 = (3, 3, 3), so the rows are linearly dependent and the determinant is 0. Answer: (B) 0.

Concept: Product of eigenvalues = determinant; sum = trace. The trap is trying to compute the eigenvalues directly instead of spotting the dependent rows.

5-bit 2's complement range is −16 to 15. A = 10, B = 11010 = −6. A + B = 4 (fine). A − B = 16 (exceeds 15: overflow). B − A = −16 (representable). 2B = −12 (fine). Answer: (B) A − B.

Concept: Decode both operands, compute in decimal and compare with [−2ⁿ⁻¹, 2ⁿ⁻¹ − 1]. The trap is thinking −16 is out of range; the negative side has one extra value.

By symmetry P(X) = P(Y) = 1/2. The relative orders of {1, 2} and {3, 4} are independent: of the 4 equally likely combined orderings, exactly one has 1 before 2 and 3 before 4, so P(X ∩ Y) = 1/4 = P(X)P(Y). Hence independent. They can co-occur (not exclusive), both can fail (2 before 1 and 4 before 3), and they are equally likely. Answer: (B).

Concept: Events about disjoint sets of elements in a random permutation are independent. The trap is confusing independent with mutually exclusive.

(A) is true: cycle stealing moves one word per stolen bus cycle. (B) is true: burst mode holds the bus for the whole block, so it has higher throughput. (C) is false: programmed I/O busy-waits on the device, wasting CPU cycles, so interrupt-driven I/O gives better CPU utilization. (D) is true: a vectored interrupt supplies the ISR address directly, avoiding polling. Answer: (C).

Concept: Programmed I/O keeps the CPU polling; interrupts free it until the device is ready. The trap is reading 'programmed' as more efficient.

The browser first needs the server's IP, so the DNS request (ii) leaves first. Then TCP opens the connection with SYN (iv). Over that connection it requests the index page (i), and only after parsing it does it learn of and request the embedded image (iii). Order: (ii), (iv), (i), (iii). Answer: (C).

Concept: Name resolution precedes connection setup, which precedes HTTP requests; embedded objects are fetched after the base page. The trap is putting SYN before DNS.

In the worst case (the array is sorted, or the violation is at the end) the single pass makes about N − 1 comparisons, each O(1). So worst-case time is Θ(N), which means it is both O(N) and Ω(N). Answer: (A).

Concept: Θ(N) implies both O(N) and Ω(N). The trap is associating Ω only with best-case analysis; here the bound is on the worst case.

Start a = 6. Iteration 1: a = 6/12 + 1 = 0 + 1 = 1 (integer division), then a += 0 keeps 1. Next: a = 1/12 + 1 = 1 again. Since b = 0 never changes, a stays 1, which is always < 10, so the loop never exits and nothing is printed. Answer: (C) The program gets stuck in an infinite loop.

Concept: Integer division truncates, and a loop whose variable reaches a fixed point never terminates. The trap is treating 6/12 as 0.5.

Each call reads one character into its own local a and recurses until it reads the newline. Calls hold '1', '2', '3', '4', then a call reads '\n' and returns without printing. As the stack unwinds, each call prints its own character after the deeper call returns: 4, 3, 2, 1. Output 4321 and the program terminates. Answer: (C).

Concept: Printing after the recursive call reverses the input order, since each frame keeps its own local variable. The trap is expecting 1234.

In a B+ tree every node except the root must be at least half full. The root may hold as few as one key (two children if internal), since it is created and removed as the tree grows and shrinks. Answer: (A) Only the root node.

Concept: The minimum-occupancy rule exempts only the root. The trap is thinking leaves are exempt.

1NF only requires every attribute to be atomic (single-valued, not composite or multivalued). (A) True: a key may consist of several attributes. (B) False: 1NF says nothing about foreign keys. (C) True: a composite attribute is not atomic. (D) False: any number of candidate keys is allowed. Answer: (A), (C).

Concept: 1NF is purely about atomic values. The trap is reading key-related restrictions into 1NF.

(A) False: L1 ∩ L2' = ϕ only says L1 ⊆ L2; for example L1 = ϕ and L2 = Σ*. (B) False: take L1 = Σ*, then L1 ∪ L3 = Σ*, regular. (C) True: if L3' were regular, L3 = (L3')' would be regular by closure under complement. (D) True: regular languages are closed under complement and union. Answer: (C), (D).

Concept: Use closure properties, and look for counterexamples like Σ* that swallow a non-regular language. The trap is believing union with a non-regular language must be non-regular.

(A) False: user-level threads exist. (B) False: the file descriptor table belongs to the process and is shared by its threads. (C) False: each thread has its own stack. (D) True: threads share one address space, so one thread can read or corrupt another's data. Answer: (D).

Concept: Threads share code, data, heap and open files; each has its own registers, PC and stack. The trap is assuming a shared stack or per-thread file table.

Running to Ready happens on preemption. Running to Terminated happens on exit. Waiting (blocked) to Running is impossible: when the event occurs the process goes to Ready and must be dispatched. Ready to Waiting is impossible: a process can block only by doing something while running. Answer: (B), (C).

Concept: Only a running process can block, and an unblocked process always returns to the ready queue first. The trap is allowing a direct wake-up into Running.

Shift-reduce parsers build the parse tree from leaves to root, and LR parsers (SLR, LALR, CLR) are shift-reduce parsers, so both are bottom-up. Predictive and LL(1) parsers are top-down. Answer: (A), (D).

Concept: LL = top-down (leftmost derivation), LR = bottom-up (rightmost derivation in reverse). The trap is mixing up the two L's.

(A) P(A)P(B) = 0.15 ≠ 0.1, so not independent. (B) P(A ∪ B) = 0.3 + 0.5 − 0.1 = 0.7, true. (C) P(A ∩ Bᶜ) = P(A) − P(A ∩ B) = 0.2, true. (D) P(Aᶜ ∩ Bᶜ) = 1 − P(A ∪ B) = 0.3, not 0.4. Answer: (B), (C).

Concept: Inclusion-exclusion and De Morgan's law. The trap in (D) is computing (1 − 0.3)(1 − 0.5) = 0.35 or similar as if independent.

Without delays Y = X · X' = 0 always, so (A) is true and (B) false. With a NOT delay, when X rises 0 → 1 the inverter output is still 1 for a moment, so both AND inputs are 1 and Y glitches to 1: (C) true. When X falls 1 → 0, the direct input is already 0, so Y stays 0; and Y was already 0 before, so there is no transient zero to speak of: (D) false. Answer: (A), (C).

Concept: A static hazard: a signal ANDed with its own delayed complement produces a brief pulse on one edge only. The trap is expecting a glitch on both edges.

The initial sequence number is chosen (pseudo)randomly to avoid confusion with old segments and spoofing, so (A) true and (B) false. A SYN consumes one sequence number, so Q acknowledges with the next expected number N_P + 1: (D) true, (C) false. Answer: (A), (D).

Concept: SYN and FIN each consume one sequence number even without data. The trap is thinking the ISN starts at 0 (tools like Wireshark show relative numbers).

(A) True: that is the definition of forwarding (bypassing). (B) True: the MEM output (e.g., a loaded value or EX/MEM result) can be fed to the EX input of a following instruction. (C) True: a load followed immediately by a use still needs a one-cycle stall. (D) False: forwarding needs extra multiplexers, paths and hazard-detection logic. Answer: (A), (B), (C).

Concept: Forwarding removes most RAW stalls but not the load-use stall, and it costs hardware. The trap is believing it eliminates all stalls.

Outbound through NAT, the private source IP is replaced by the NAT's public IP (and the transport port, but that is not in the IP header). Changing any header field forces recomputation of the IP header checksum. The destination IP and total length are unchanged. Answer: (A), (C).

Concept: NAT rewrites the source address on the way out and the destination on the way in, and every rewrite changes the checksum. The trap is forgetting the checksum.

A bijection A → B gives |A| = |B| = n. A bijection A × A → A ∪ B gives n² = |A ∪ B|, and n ≤ |A ∪ B| ≤ 2n. So n² ≤ 2n, i.e., n ≤ 2. n = 1: take A = B, |A ∪ B| = 1 = 1². n = 2: take A, B disjoint, |A ∪ B| = 4 = 2². Both work, so 2 values. Answer: 2.

Concept: Bijection means equal cardinality; then bound |A ∪ B| between n and 2n. The trap is forgetting that A and B may overlap or be disjoint as needed.

/ binds loosest and is right-associative, so the expression is (3 + 1 + 5 ∗ 2) / ((7 + 2 − 4 − 7 − 6) / 2). Left part: + binds before ∗, so (3 + 1 + 5) ∗ 2 = 18. Middle: + first gives 9 − 4 − 7 − 6, and right-associative − gives 9 − (4 − (7 − 6)) = 9 − 3 = 6. Then 6 / 2 = 3 and 18 / 3 = 6. Answer: 6.

Concept: Split at the lowest-precedence operator first, applying its associativity, then recurse. The trap is evaluating − left to right.

By Cayley's formula the complete graph Kₙ on n labelled vertices has nⁿ⁻² spanning trees. For n = 4: 4² = 16. Answer: 16.

Concept: Cayley's formula nⁿ⁻² counts labelled spanning trees. The trap is counting non-isomorphic trees (only 2) instead of labelled ones.

Join on A: R(10,20) with S(10,90); R(30,40) with S(30,45); R(30,50) with S(30,45). R tuples with A = 20 and 50 have no match. Apply B < C: 20 < 90 yes, 40 < 45 yes, 50 < 45 no. Result has 2 tuples. Answer: 2.

Concept: Do the equi-join first, then filter. The trap is forgetting that A = 30 appears twice in R and produces two joined rows.

There are 10⁶/10³ = 1000 chunks of 8000 bits; each takes 8000/10⁶ = 8 ms per link. P finishes sending the last chunk at 1000 × 8 ms = 8.000 s. Q is store-and-forward and pipelined, so the last chunk then needs one more 8 ms transmission on Q−R. R has everything at 8.000 + 0.008 = 8.008 s. Answer: (B) 8.008.

Concept: Pipelined store-and-forward: total = (number of packets + hops − 1) × per-packet time. The trap is doubling the whole file time (16 s) as if Q waited for the entire file.

Parse MMLK as D = MM, H = L, T = ϵ, U = K. D.val = 5 + 5 + (−5) = 5. H.val = 50 + (−10) = 40. T.val = −5. U.val = 5. S.val = 5 + 40 − 5 + 5 = 45. Answer: (A) 45.

Concept: Evaluate synthesized attributes bottom-up, remembering the ϵ productions contribute their own (negative) values. The trap is ignoring the ϵ values and getting 65.

ϵ ∈ FIRST(T) and c ∉ FIRST(T), so (2) is T → ϵ, ruling out (C) and (D). S → fR would put R at the end of S, so FOLLOW(R) would include FOLLOW(S) = {c, f, $}, not just {f}; with S → Rf, FIRST(S) = {d} ∪ {c, f} and FOLLOW(R) = {f}. With R → cTR: FOLLOW(T) gets FIRST(R) − ϵ = {c} and, since R is nullable, FOLLOW(R) = {f}; with FOLLOW(S) from T → aS this matches {c, f, $}. Answer: (A).

Concept: Work backwards from the given sets: ϵ in FIRST forces an ϵ production, and a small FOLLOW set means the non-terminal is never at the end of a longer right side. The trap is choosing S → fR, which gives the right FIRST(S) but the wrong FOLLOW(R).

Leaders: L1 (first), L3 (target of L14), L4 (target of L12), L11 (target of L9), and the instructions after each jump: L10, L13, L15. Blocks: L1-L2 (2), L3 (1), L4-L9 (6), L10 (1), L11-L12 (2), L13-L14 (2), L15 (1). That is 7 blocks, the largest with 6 instructions. Answer: (D) 7 and 6.

Concept: Leaders are the first instruction, every jump target, and every instruction following a jump. The trap is missing L3 as a separate leader, which merges it into a 7-instruction block.

Each variable is touched once by each thread, so only the relative order on each variable matters. For a: (a+1 then 2a) gives 4, (2a then a+1) gives 3. For b: (2b then b+1) gives 3, (b+1 then 2b) gives 4. Program order forbids 2a before a+1 together with b+1 before 2b (that would need a cycle), so (3, 4) is impossible. Enumerating all 6 interleavings gives (4, 4), (4, 3) four times, and (3, 3). Answer: (A).

Concept: Enumerate interleavings respecting each thread's program order. The trap is including (a = 3, b = 4), which needs T2's second statement before T1's first while T1's second precedes T2's first.

Build a max-heap bottom-up on [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]. i = 5 (111, child 93): no change. i = 4 (11, children 131, 44): swap with 131. i = 3 (90, children 75, 33): no change. i = 2 (101, children 131, 111): swap with 131; 101 then beats 11, 44. i = 1 (82, children 131, 90): swap with 131; 82 sinks below 111, then below 93. Result starts 131, 111, 90. A min-heap would start with 11, which no option matches with correct children. Answer: (D) 131, 111, 90.

Concept: Heapify sifts down from the last internal node to the root. The trap is inserting one element at a time or forgetting to continue the sift-down after a swap.

Divide by n: T(n)/n = T(√n)/√n + 1. Let S(n) = T(n)/n, so S(n) = S(√n) + 1. Taking square roots repeatedly reaches a constant after log log n steps, so S(n) = Θ(log log n) and T(n) = Θ(n log log n). Answer: (A).

Concept: Normalise by n (or substitute n = 2^(2^k)) to turn the square-root recurrence into a simple count. The trap is treating it like T(n) = 2T(n/2) + n and answering n log n.

In a min-heap the maximum has no larger descendant, so it must be a leaf, and any leaf can hold it. With 1-based indexing, nodes 1 to ⌊105/2⌋ = 52 are internal and 53 to 105 are leaves, i.e., 105 − 52 = 53 leaves. Answer: (A) 53.

Concept: Number of leaves in an n-node heap is ⌈n/2⌉. The trap is counting only the last level.

(A) False: a determinant cannot be shrunk; X alone need not determine Z, W. (B) True by decomposition. (C) True by pseudo-transitivity: W → Y gives XW → XY, and XY → Z, so XW → Z. (D) True by transitivity. Answer: (B), (C), (D).

Concept: Armstrong's axioms let you split the right side or augment the left, never drop attributes from the left. The trap is accepting (A).

Forward edges: an edge u → w to a non-child descendant puts w at least two levels below u, but BFS from v would discover w at depth(u) + 1 via that edge, so T could not be a BFS tree. Hence no forward edges: (C) true. Back edges can exist (v → u and u → v). Cross edges can exist: with v → a, v → b, b → a, DFS visits a then b, and b → a is a cross edge, while BFS gives the same tree. So (A), (B), (D) fail. Answer: (C).

Concept: A BFS tree has no edge that skips a level downward. The trap is assuming the tree must contain every edge or that cross edges are impossible.

Conflicts on y: r3(y) before w2(y), w3(y) before r2(y), w3(y) before w2(y), all giving T3 → T2. T1 touches only z, which nobody else uses, and x is used only by T2. The precedence graph has the single edge T3 → T2, so any serial order with T3 before T2 is conflict equivalent: T1T3T2, T3T2T1, T3T1T2. Answer: (B), (C), (D).

Concept: Conflict-equivalent serial orders are the topological orders of the precedence graph. The trap is assuming T1 must come first because it starts first.

The maxterms are the remaining indices 0, 1, 2, 4, so (A) holds. Minterms 3 (011), 5 (101), 6 (110), 7 (111) are the inputs with at least two 1s, the majority function XY + YZ + XZ, so (B) holds. Majority depends on every input (e.g., F(1,0,0) = 0 but F(1,1,0) = 1), so (C) and (D) are false. Answer: (A), (B).

Concept: Σ and Π use complementary index sets. The trap is writing Π with the same indices as Σ.

rank(A) ≤ n, so the null space has dimension m − rank ≥ m − n: (A) true. (B) needs nullity exactly m − n; for A = 0 the nullity is m, so false. (C) fails for n = 1, m = 2, A = [1 1]: solutions (t, −t) have no zero entry when non-zero. (D) fails for A = [[1,0,0],[0,1,0]] (n = 2, m = 3): solutions (0, 0, t) have at most one non-zero entry. Answer: (A).

Concept: Rank-nullity gives a lower bound on the solution space, not an exact size. The trap is (B), which treats the bound as equality.

Each 0 adds 1 and each 1 subtracts 1 from (n₀ − n₁) mod 3: state 1 is 0, states 2 and 5 are 1 (≡ −2), states 3 and 4 are 2 (≡ −1). So L(M) = {w : n₀ − n₁ ≡ 0 mod 3}. States with the same residue are equivalent: 3 ≡ 4 and 2 ≡ 5, so (B) and (C) are false. 2 and 4 differ (input 1 sends 2 to 1, accept, and 4 to 5, reject), so (A) is true. n₀ = n₁ gives residue 0, so (D) is true. Answer: (B), (C).

Concept: Find the invariant each state tracks; equal invariants mean equivalent states. The trap is the question asking for FALSE statements.

(A) False: the 5-cycle has k = 3 but no triangle. (B) True: an optimal colouring splits n vertices into k independent colour classes, so one has at least n/k. (C) True: in an optimal colouring every pair of colour classes must have an edge between them (else merge them), giving at least C(k,2) edges. (D) False: K_k has chromatic number k but maximum degree k − 1. Answer: (B), (C).

Concept: Colour classes are independent sets, and optimality forces an edge between every pair of classes. The trap is (A): high chromatic number does not require a clique.

(A) (a◊b)◊c = a + 2b + 2c but a◊(b◊c) = a + 2b + 4c: not associative. (B) Multiplication is associative: true. (C) a◊(b□c) = a + 2bc, while (a◊b)□(a◊c) = (a + 2b)(a + 2c): false. (D) a□(b◊c) = a(b + 2c) = ab + 2ac = (a□b)◊(a□c), and (b◊c)□a = ba + 2ca = (b□a)◊(c□a): true. Answer: (B), (D).

Concept: Check each law symbolically; one counterexample disproves it. The trap is assuming ◊ is associative because it is built from +.

(A) False: in a write-back cache the LRU victim of a read miss may be dirty and must be written back. (B) True: write-through keeps memory current, so blocks are never dirty and evictions need no write-back. (C) True: a write hit in write-back sets the dirty bit. (D) False: write-through has no dirty victims to write back, and with no-write-allocate a write miss does not even load the block. Answer: (B), (C).

Concept: Write-back defers memory updates using a dirty bit; write-through updates memory on every write. The trap is (A), forgetting that dirty blocks can be chosen as victims on reads.

Capacity per track = 4096 × 1024 B = 2²² B. Per cylinder (32 surfaces) = 2²⁷ B. 512 GB = 2³⁹ B. Cylinders = 2³⁹ / 2²⁷ = 2¹² = 4096. Answer: 4096.

Concept: Cylinders = capacity / (surfaces × sectors per track × bytes per sector). The trap is dividing by tracks per surface or forgetting the surfaces.

Serial part = 10 ns, parallel part = 90 ns. With n cores: time = 10 + 90/n + 10(n − 1). n = 1: 100. n = 2: 10 + 45 + 10 = 65. n = 3: 10 + 30 + 20 = 60. n = 4: 10 + 22.5 + 30 = 62.5. n = 5: 10 + 18 + 40 = 68. Minimum at n = 3. Answer: 3.

Concept: Amdahl's law with a per-core overhead has an optimum where added overhead outweighs the parallel saving. The trap is charging the overhead for every core, including the first.

Memory stall cycles per instruction = instruction fetch misses + data misses = 1 × 0.02 × 100 + 0.25 × 0.08 × 100 = 2 + 2 = 4. Real CPI = 2 + 4 = 6. Perfect cache CPI = 2. Speedup = 6/2 = 3.00. Answer: 3.

Concept: Every instruction is fetched, but only loads/stores access the data cache. The trap is applying the data miss rate to all instructions.

Every process alive at the start of an iteration forks, and both parent and child print and continue the loop. Processes double each iteration: 2 print in iteration 1, 4 in iteration 2, 8 in iteration 3. wait() only affects ordering. Total = 2 + 4 + 8 = 14. Answer: 14.

Concept: With fork inside a loop, each iteration doubles the processes and each of them executes the printf. The trap is counting only the final 8 processes.

Longest prefix match on the last octet. /25 R2 covers 128-255; /26 R3 covers 64-127; /26 R4 covers 192-255. 16: only /24, R1. 72: R3. 132: R2 (not in 192-255). 191: R2. 205: R4 (longer than /25). R2 gets 2 hosts × 20 = 40 packets. Answer: 40.

Concept: Longest prefix match picks the most specific entry. The trap is sending .205 to R2 or .191 to R4.

In CNF, a rule A → BC increases the number of symbols by one and a rule A → a turns one variable into a terminal. A string of length n needs n − 1 rules of the first kind and n of the second: 2n − 1 steps. Here n = 90, so 179. Answer: 179.

Concept: CNF derivations of a length-n string always take 2n − 1 steps; the number of variables is a distractor. The trap is answering 90 or 89.

DFS on an undirected graph gives a spanning forest with one tree per connected component. A forest with V vertices and c trees has V − c edges. So 100 − c = 40 and c = 60. Answer: 60.

Concept: Edges in a spanning forest = vertices − components. The trap is thinking DFS yields a single tree.

Strings of length 0 to 5: 1 + 2 + 4 + 8 + 16 + 32 = 63. r has ϵ plus 0ᵏ and 1ᵏ for k = 1..5: 11 strings. s has 01ᵏ⁻¹ and 10ᵏ⁻¹ for k = 1..5; the length-1 ones (0, 1) are already in r, leaving 2 × 4 = 8 new strings. Union = 19. Neither: 63 − 19 = 44. Answer: 44.

Concept: Count the union with inclusion-exclusion. The trap is double-counting 0 and 1, which are in both r and s.

Page size 2048 B. Virtual address 2500 is in page ⌊2500/2048⌋ = 1 with offset 452. Page 1 is in frame 3, so physical address = 3 × 2048 + 452 = 6596. Answer: 6596.

Concept: Split the address into page number and offset, map the page to its frame, keep the offset. The trap is mapping page 1 to frame 1.

Given the first ball is red, 9 red remain among 24 balls. P(both red | first red) = 9/24 = 0.375. (Equivalently P(both red)/P(first red) = (10/25 × 9/24)/(10/25).) The key accepts 0.37 to 0.38. Answer: 0.375.

Concept: Conditioning on the first draw just changes the second draw's sample space. The trap is giving the unconditional P(both red) = 0.15.

Q1 = 1 whatever A is (both inputs 1). Q2 = 0 whatever B is (both inputs 0). Y = Q1 when C = 0 and Q2 when C = 1, so Y = 1 exactly when C = 0. A and B are free: 2 × 2 = 4 combinations. Answer: 4.

Concept: A mux with equal data inputs ignores its select line. The trap is counting only combinations where A or B take a specific value.

Payload = 1400 B. Link 1 (MTU 542): max payload 522, rounded down to a multiple of 8 = 520, giving 520, 520, 360. Link 2 (MTU 360): max payload 340, rounded to 336. Router refragments each: 520 → 336 + 184; 520 → 336 + 184; 360 → 336 + 24. Fragments are not reassembled at the router, so the receiver gets 6. Answer: 6.

Concept: Fragment payloads (except the last) must be multiples of 8, and only the destination reassembles. The trap is not rounding to 8, or refragmenting the original datagram at the router (giving 5).