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

Articles follow the sound, not the spelling. "younger" starts with a consonant sound, so "a younger brother" (first mention, not a specific one). "university" starts with the sound "yoo", a consonant sound, so "a university". "honorable" has a silent h and starts with a vowel sound, so "an honorable man". Sequence: a; a; an. Answer: (A).

Concept: Tests choice of a/an by initial sound. The trap is choosing "an university" because u is a vowel letter, or "a honorable" because h is a consonant letter. Pronunciation decides.

"Myopic" literally means near-sighted and figuratively means lacking foresight. The sentence confirms this: the decision gave up long-term stability for short-term gains. Visionary, progressive and innovative are all positive and mean nearly the opposite. The only synonym is shortsighted. Answer: (B).

Concept: Vocabulary in context. The context clue "sacrificed long-term stability" points to lack of foresight; the distractors are positive words that contradict the sentence's critical tone.

Let n be the number of students. Correcting the entry raises the total by 42 - 24 = 18. The average rises by 31.4 - 30.8 = 0.6. So 0.6 n = 18, giving n = 30. Answer: (C).

Concept: Change in total = change in average x count. The trap is using 24 + 42 or one of the averages directly instead of the difference of the corrected and wrong marks.

R is Q's mother and S is Q's daughter, so R is S's grandmother: (1) true. P is Q's brother and S, T are Q's daughters (T is S's sister), so P is their uncle: (2) true. R's children include P (a son) and Q, whose gender is not given, so "only one son" cannot be concluded: (3) not established. Q has at least two daughters, S and T: (4) false. Answer: (A).

Concept: Blood-relation deduction. The trap is assuming Q's gender (to accept or reject statement 3) - only statements that follow necessarily count as true.

Library and Canteen are in the same top row, Library on the west side, so the library is due west of the canteen, not northwest: (A) wrong. The hospital is north of the chemistry lab (same east side, across the cross road): (B) wrong. Physics Lab is in the north-west block and Chemistry Lab in the south-east block, so the chemistry lab is south-east of the physics lab: (C) correct. Classrooms (south-west, bottom) and Canteen (north-east, top) are diagonally opposite: (D) wrong. Answer: (C).

Concept: Reading directions from a map. The usual trap is calling a same-row neighbour "northwest" because it sits in the upper-left quadrant of the map.

(A) "reflected" means thought about; no mirror is mentioned. (B) He planned a book of poems about the things in his pocket, not a poem on epics. (C) The passage says the pocket-knife is "the type of all human tools, the infant of the sword" - stated directly. (D) He says the book would be too long and the age of epics is past, not that epics are inconvenient to write. Answer: (C).

Concept: Literal comprehension. Distractors exploit a pun (reflect / mirror) and twist nearby phrases (epics, too long). Only a statement directly supported by the text is correct.

Let the height of P above QR be h. The distance between ST and QR is h/2, so P is h/2 above ST. Triangle PST is similar to triangle PQR with ratio (h/2)/h = 1/2, so its area is (1/2)² = 1/4 of triangle PQR. The trapezium SQRT is the rest: 3/4 of PQR. Ratio = (1/4)/(3/4) = 1/3. Answer: (A).

Concept: Similar triangles: areas scale with the square of the linear ratio. The trap is answering 1/4 (PST to the whole triangle) or 1/2 (the linear ratio) instead of PST to the trapezium.

Binomial with n = 3, p = 1/6. P(exactly one 6) = C(3,1) x (1/6) x (5/6)² = 3 x 25/216 = 75/216. Answer: (A).

Concept: Binomial probability. The trap is 25/216, which is the probability for one specific position of the 6 - forgetting the factor 3 for which roll shows it.

We choose 3 scoops from 4 flavours with repetition allowed and order ignored: combinations with repetition, C(n + r - 1, r) = C(4 + 3 - 1, 3) = C(6,3) = 20. Check by cases: all three same flavour 4, two of one and one of another 4 x 3 = 12, all different C(4,3) = 4; total 20. Answer: (B).

Concept: Stars and bars (multisets). Traps: 4³ = 64 or 4 x 3 x 2 = 24 count ordered selections; C(4,3) = 4 forbids repetition.

Interrupts are recognised only at instruction boundaries, so the current instruction completes first (iii). Then the return address in the PC must be saved (i), otherwise it would be lost. Only then is the PC loaded with the ISR start address (ii). Sequence: (iii), (i), (ii). Answer: (A).

Concept: Interrupt handling order. Loading the PC before saving it destroys the return address, and saving before finishing the instruction would save a mid-instruction state.

The symbol table records identifiers with their scope, type and storage information (A true). It can be a hash table, list or BST (B true). Entries are created as the lexer meets identifiers (D true). After parsing, semantic analysis (type checking), intermediate code generation and code generation (storage offsets) all still consult it, so it is needed beyond parsing. Statement (C) is false. Answer: (C).

Concept: The symbol table persists through all compiler phases. The trap is thinking it is a front-end-only structure.

Live variable analysis finds, at each point, the variables whose current values may still be used later. Register allocation uses this: two variables whose live ranges do not overlap can share a register, and a dead variable's register can be freed. Strength reduction and constant folding work on expressions and values, not liveness; call management is a runtime concern. Answer: (B).

Concept: Liveness drives register allocation (interference graphs) and dead-code elimination. Constant folding needs constant propagation, not liveness - a common mix-up.

Page size 2048 = 2¹¹ bytes, so the offset is 11 bits. A single-level page table has one entry per logical page: 2³² / 2¹¹ = 2²¹ entries. The 20-bit physical address only affects the frame-number width (20 - 11 = 9 bits per entry), not the entry count. Answer: 2²¹ (A).

Concept: Page table entries = number of virtual pages. The trap is dividing the physical address space instead (2⁹ frames), which sizes each entry, not the table.

T1 writes Y. Then T2 reads Y and T3 reads Y, both before T1 finishes - dirty reads of T1's uncommitted value. When T1 aborts, the value both read never existed, so both must be rolled back (cascading rollback). R2(X) reads X, which T1 only read, so it is harmless. Answer: Both T2 and T3 (C).

Concept: Cascading aborts come from reading uncommitted writes. The trap is focusing on X (read by T1 and T2) - read-read sharing causes no dependency.

Network layer routes packets across networks: (a)-(I). Transport layer provides end-to-end (host to host / process to process) communication: (b)-(III). Data link layer does framing and error detection on a link: (c)-(II). Answer: (B).

Concept: Layer responsibilities. "Host to host" is the transport layer's end-to-end role; error handling also exists at transport, but framing pins (II) to the data link layer.

Counterexample for onto: A = {1}, B = {1, 2}, C = {c}, g(1) = 1, f(1) = f(2) = c. f and f∘g are onto, but g misses 2. Counterexample for one-to-one: A = {1, 2}, B = {1}, C = {c}, g(1) = g(2) = 1, f(1) = c. f and f∘g are onto, but g is not injective. So g need be neither. Answer: (D).

Concept: If f∘g is onto then f must be onto; nothing follows about g. The trap is reversing the rule (that holds for injectivity: f∘g injective implies g injective).

T is a subgraph of G, so the unique u-v path in T is also a path in G. The shortest u-v distance in G is at most the length of that path: d1 ≤ d2. Equality need not hold: in a triangle with weights 2, 2, 3, the MST drops the 3-edge, and its endpoints are 3 apart in G but 4 apart in T. Equality can also hold (u, v adjacent by an MST edge), so (D) fails. Answer: (B).

Concept: An MST minimises total weight, not pairwise distances; it is not a shortest-path tree. Removing edges can only lengthen shortest paths.

A generates a⁺ = {aⁿ | n ≥ 1} and B generates b⁺ = {bⁿ | n ≥ 1}. So S → aaB gives a²bⁿ (n ≥ 1) and S → Abb gives aⁿb² (n ≥ 1). L(G) = {a²bⁿ | n ≥ 1} ∪ {aⁿb² | n ≥ 1}. Answer: (A).

Concept: Read what each non-terminal derives, then combine. The trap is assuming counts are linked (aⁿbⁿ-style) when A and B grow independently.

Divide by 2ⁿ: let U(n) = T(n)/2ⁿ. Then U(n) = U(n - 1) + n with U(0) = 1. So U(n) = 1 + (1 + 2 + ... + n) = 1 + n(n + 1)/2 = Θ(n²). Hence T(n) = 2ⁿ U(n) = Θ(n²2ⁿ). Answer: (A).

Concept: Normalising by the homogeneous solution 2ⁿ turns it into a sum. The trap is Θ(n2ⁿ), ignoring that the n·2ⁿ term accumulates over n levels.

23 > 19, so it goes to the rightmost leaf [20, 21, 22], which is already full (3 keys). The leaf splits, e.g. into [20, 21] and [22, 23], and a separator (22) must be pushed into the root. The root [6, 12, 19] is also full, so it splits too, and a new root is created above the two halves. Nodes go from 5 to 8 and the height grows by one level. So (A) and (C) are false; (B) and (D) are true. Answer: (B), (D).

Concept: B⁺ tree insertion: a full leaf splits and pushes a key up; a full parent splits recursively, and a root split is the only way height increases. Every node on the path here is full.

P1 (client to server): SYN = 1, ACK = 0. P2 (server to client): SYN = 1, ACK = 1 (SYN-ACK). P3 (client to server): SYN = 0, ACK = 1. So (B) and (D) are true; (A) wrongly sets SYN in P3 and (C) wrongly clears SYN in P2. Answer: (B), (D).

Concept: Handshake flags: SYN, SYN+ACK, ACK. SYN consumes a sequence number and appears only in the first two segments.

Determinant = 1 - k². If k ≠ ±1 there is a unique solution, so infinitely many k give exactly one solution: (C) false. k = 1: x + y = 1 and x + y = -1 are inconsistent: no solution. k = -1: x - y = 1 and -x + y = -1 are the same line: infinitely many solutions. So exactly one k (k = 1) gives no solution: (A) true, (B) false; exactly one k (k = -1) gives infinitely many: (D) true. Answer: (A), (D).

Concept: Singular coefficient matrix means no solution or infinitely many, decided by consistency of the right-hand side. Check each singular k separately rather than assuming both behave alike.

X is the majority function; X(p, q, p) = p. (A) a = b = 1, c = d = e = 0: LHS = X(1, 1, 0) = 1, RHS = X(1, 0, 0) = 0. False. (B) If a = b the result is a, which equals X(a, b, c); if a ≠ b the third argument decides, giving X(a, b, c). True. (C) RHS = a AND c. With a = b = 1, c = d = 0: LHS = X(1, 1, 0) = 1, RHS = 0. False. (D) X(a, c, c) = c; let m = X(a, b, c). X(a, m, c): if a = c the result is a = c = m; if a ≠ c the result is m. Always m. True. Answer: (B), (D).

Concept: Majority-function identities; use X(p, q, p) = p and case-split on equal arguments. The trap is assuming majority is associative like AND/OR - it is not.

Widening a 2's complement number uses sign extension: copy the sign bit (1) into all new high bits. 1010 becomes 1111 1010 in 8 bits and 1111 1111 1111 1010 in 16 bits. Check: 1111 1010 = -128 + 122 = -6. 1000 1010 = -128 + 10 = -118, not -6. Answer: (B), (D).

Concept: Sign extension. The trap is padding with zeros after the sign bit, which works for sign-magnitude, not 2's complement.

(A) A path from the root can visit at most all n nodes, i.e. n - 1 edges, reached by a skewed tree: true as the maximum. (B) Inorder visits left subtree, root, right subtree, which is ascending order by the BST property: true. (C) A skewed BST needs O(n) search, so O(log n) worst case is false. (D) In a BST the left child is smaller than the parent, violating the min-heap property: false. Answer: (A), (B).

Concept: BST height ranges from log n to n - 1; only balanced BSTs guarantee logarithmic search. Inorder-sorted is the defining BST property.

Each ALU input has its own mux with an independent select. RA and RB selected: register-register (A). RA with immediate on Mux_B, or immediate on Mux_A with RB: register-immediate (B). Both muxes on immediates: two immediate values (C). Since all three combinations are possible, the word "only" makes (D) false. Answer: (A), (B), (C).

Concept: Enumerate the mux select combinations: 2 x 2 = 4 input pairings. The trap is (D), which ignores that each mux can still pick its register.

The given NFA need not be minimal, so a smaller NFA or even a smaller DFA may exist: (A) and (B) are true (they only say "may"). The subset construction gives a DFA with at most 2ⁿ states: (C) true. (D) contradicts (C), since a DFA with at most 2ⁿ states always exists: (D) is false. Answer: (D).

Concept: Subset construction bound: an n-state NFA yields a DFA with at most 2ⁿ states. Watch the question asks for FALSE statements.

Each I/O call sends the process to the I/O queue; when the I/O completes it returns to the ready queue. I/O operations: one scanf, plus printf executed 20 times in the loop = 21 I/O operations. Each produces one entry into the ready queue. return 0 terminates the process, no further entry. Answer: 21.

Concept: Process state transitions: running to waiting on I/O, waiting to ready on completion. Traps: forgetting the scanf (20) or counting the initial admission.

Complement count. Total strings of length 5: 3⁵ = 243. Strings with no two equal adjacent symbols: 3 choices for the first, then 2 for each of the next 4 (anything but the previous symbol): 3 x 2⁴ = 48. Strings with at least one equal adjacent pair: 243 - 48 = 195. Answer: 195.

Concept: "At least one" counts are easiest via the complement. Direct counting of aa/bb/cc occurrences double-counts strings with several pairs.

Continuity at x = 1: a + b = 1 + 1 + 1 = 3. Differentiability at x = 1: left derivative a equals right derivative 3x² + 2x at x = 1, which is 5. So a = 5 and b = 3 - 5 = -2. Answer: -2.0.

Concept: Differentiable at a join needs both continuity (values match) and equal one-sided derivatives. Using only one condition leaves b undetermined.

P(fake) = 1/5, P(HH | fake) = 1. P(regular) = 4/5, P(HH | regular) = 0.25. P(HH) = 0.2 x 1 + 0.8 x 0.25 = 0.2 + 0.2 = 0.4. By Bayes, P(fake | HH) = 0.2 / 0.4 = 0.5. Answer: 0.50.

Concept: Bayes' theorem: posterior = likelihood x prior / evidence. The trap is answering the prior 0.2, ignoring that two heads is much likelier with the fake coin.

fun() is bubble sort; each swap removes exactly one inversion. A descending array of n distinct values has every pair inverted: n(n - 1)/2 inversions. For n = 30: 30 x 29 / 2 = 435 swaps. Answer: 435.

Concept: Bubble sort swaps = number of inversions. Reverse-sorted input is the worst case, giving the maximum C(n, 2).

z holds the address of a. foo receives a copy of that address in p and the value 25 in x. *p = x writes 25 into the location p points to, which is a. So a becomes 25 and the program prints 25. Answer: 25.

Concept: Passing a pointer lets a function modify the caller's variable. The trap is thinking call-by-value leaves a at 20 - the pointer is copied, but it still points to a.

A binary heap is a complete binary tree. Levels 0 to 4 hold 1 + 2 + 4 + 8 + 16 = 31 nodes, so the 32nd key starts level 5. Height = floor(log₂ 32) = 5 edges. Answer: 5.

Concept: Heap height is floor(log₂ n). The trap is ceil(log₂ 32) - 1 = 4, forgetting that 32 nodes overflow a perfect tree of height 4 (31 nodes).

Block offset: 16 = 2⁴ bytes, 4 bits. Number of cache lines: 16K / 16 = 2¹⁰, so 10 index bits. Tag = 20 - 10 - 4 = 6 bits. One tag per line: 6 x 2¹⁰ bits in total. Answer: 6 × 2¹⁰ (A).

Concept: Direct-mapped address split: tag | index | offset. Tag storage = tag bits x number of lines. Trap: using cache bytes instead of lines as the multiplier.

Opcode: 50 instruction types need ceil(log₂ 50) = 6 bits. Register field: 64 registers need 6 bits (R1 is both source and destination, one field). Immediate: 32 - 6 - 6 = 20 bits. Answer: 20 (B).

Concept: Instruction format field widths. The trap is allotting two register fields (giving 14) when the instruction names only one register.

t = 0: both free. M1 takes its top choice P1 (0-20); M2 takes its top choice P2 (0-16). t = 16: M2 free, waiting P3 and P4; by M2's order P3 > P4, so P3 runs 16-41. t = 20: M1 free, only P4 waits, P4 runs 20-30. Waiting times: P1 0, P2 0, P3 16, P4 20. Average = 36 / 4 = 9.00 ms. Answer: 9.00 (A).

Concept: Multiprocessor non-preemptive priority with per-processor priority orders. The key step is applying M2's order at t = 16, not M1's.

p must range over players (it supplies pname), and there must exist a team t with the same tid whose tname is 'MI'. That is exactly (A). (B) and (D) range p over teams, which has no pname. (C) drops the join p.tid = t.tid, so it returns every player whenever an MI team exists. Answer: (A).

Concept: TRC joins need an explicit equality on the linking attribute. Missing the join condition gives all tuples when the existential is satisfiable.

Third octet 109 = 01101101. /16 145.36.0.0: first 16 bits match, so E1 is a candidate. /17 145.36.128.0 needs third-octet top bit 1; 109 has 0: no. /18 145.36.64.0 needs top two bits 01; 109 starts 01: match. /24 145.36.255.0 needs third octet 255: no. Longest prefix match is /18. Answer: E3 (A).

Concept: Longest prefix match. The trap is stopping at the first matching entry (/16, E1) instead of choosing the most specific match.

Characteristic equation of A: (1 - λ)(-1 - λ) - 1 = λ² - 2 = 0, so λ = ±√2. Eigenvalues of A¹³ are λ¹³ = (±√2)¹³ = ±2⁶√2 = ±64√2. (Also A² = 2I, so A¹³ = 2⁶A = 64A.) Answer: 64√2, -64√2 (D).

Concept: Eigenvalues of Aᵏ are λᵏ. The odd power keeps the signs; the trap is dropping the extra √2 factor (answering ±64).

(x' denotes NOT x.) b1'b0' (b1 = 0, b0 = 0) covers 0, 4, 8, 12. b2'b0' (b2 = 0, b0 = 0) covers 0, 2, 8, 10. Remaining minterm 11 = 1011 pairs with 10 = 1010 to give b3 b2' b1. All three are essential prime implicants and they cover exactly the 7 minterms. Option (B) misses 11; (C) and (D) include non-minterms. Answer: b1'b0' + b2'b0' + b1b2'b3 (A).

Concept: K-map grouping with edge/corner wrap. The trap is (B): the four-corner groups look complete, but the isolated 11 needs its own pair.

A BFS tree from root r has height equal to the eccentricity e(r), the largest d(r, v). Take u, v with d(u, v) = 30. By the triangle inequality 30 ≤ d(u, r) + d(r, v) ≤ 2e(r), so e(r) ≥ 15. Height 15 occurs from a central vertex (e.g. middle of a path) and 30 from an endpoint, so neither "exactly" option holds for every G, and "at least 30" fails for a central root. Answer: (C).

Concept: BFS tree height = eccentricity of the root, which lies between radius and diameter, and radius ≥ diameter / 2. Trap: assuming BFS height always equals the diameter.

L2: push one symbol per a and per b, pop one per c; accept when the stack empties exactly with n, m ≥ 1. Grammar: S → aSc | aXc, X → bXc | bc. So L2 is context-free. L1 = { aᵐbᵐcᵏ | k > m ≥ 1 } needs #a = #b and also #c > #a: two dependent comparisons. Pumping aᵖbᵖcᵖ⁺¹ breaks it: pumping a's and b's up makes them reach the c count, pumping c's down (or only c's) breaks c > a or a = b. Not context-free. Answer: (C).

Concept: One stack can check one linear relation. L2 is a nested match (c count = a's + b's); L1 needs a = b and c > a simultaneously, like aⁿbⁿcⁿ.

Rule for First: if A → ε is a production, ε ∈ First(A): (A) true. Rule for Follow: the end marker $ is placed in Follow(S) for the start symbol: (D) true. $ is never in a First set (it is not derived from any symbol): (B) false. Follow sets contain terminals and $, never ε: (C) false. Answer: (A), (D).

Concept: First may contain ε; Follow may contain $; never the other way round. Swapping the two is the standard trap.

name → city, owner, so name is a key of team. Every FD has a superkey on the left, so team is in BCNF (and hence 3NF): (A) and (D) false. t1 and t2 are two-attribute relations with name as key: both in BCNF, (B) true. The common attribute name is a key of t1 (and t2), so the join is lossless: (C) true. Answer: (B), (C).

Concept: BCNF: every non-trivial FD's determinant is a superkey. Lossless binary decomposition: the shared attributes must be a key of one side. Decomposing an already-BCNF relation is allowed, just unnecessary.

"Exactly one" = existence plus uniqueness: for each x, some y is x's mother and no z different from y is x's mother. (B) states exactly this. (D) is the same with ∀z(p → ¬q) rewritten as ¬∃z(p ∧ q). (A) only says some y is a mother and some z is not, which allows two mothers. (C) is trivially true (take z = y) and asserts neither existence nor uniqueness. Answer: (B), (D).

Concept: Uniqueness pattern ∃y[P(y) ∧ ∀z(z ≠ y → ¬P(z))]. Recognise the equivalent ¬∃ form; reject formulas satisfied by a trivial witness.

Closure: a sum of non-negative integers is a non-negative integer. Associativity and commutativity follow pointwise from + on integers. Identity: the zero function z(n) = 0. Inverses: f(n) = 1 would need g(n) = -1, which is not in A, so not a group. Hence a commutative (Abelian) monoid. Answer: (B).

Concept: Pointwise operations inherit the properties of the underlying operation on the codomain; (N, +) is a commutative monoid without inverses, so the function space is too.

Interpret states as the longest suffix matching a prefix of bab: q0 = none, q1 = b, q2 = ba, q3 = bab. Check transitions: from ba, a gives baa (no useful suffix) → q0; from bab, a gives suffix ba → q2, b gives suffix b → q1. So the DFA accepts exactly strings ending in bab. (B) fails: baba contains bab but ends in q2. (A) fails: bab has two b's yet bb is rejected. (D) fails: abab contains aba yet ends in bab and is accepted. Answer: (C).

Concept: Pattern-matching DFAs track the longest suffix that is a prefix of the pattern. "Contains" needs a trap accepting state; returning out of the final state means "ends with".

Data per block = 65536 - 4 = 65532 bytes. File = 1048576 bytes. 16 blocks hold 16 x 65532 = 1048512 bytes, leaving 64 bytes, so a 17th block is needed. That block uses 64 data bytes out of 65532, wasting 65532 - 64 = 65468 bytes. Answer: 65468.

Concept: Internal fragmentation is the unused data area of the last block. The trap is ignoring the 4-byte pointer (16 blocks would seem to fit exactly, giving 0).

Leaders: the first statement 1001; jump targets 1003, 1002, 1013; statements after jumps 1010, 1012 (1018 does not exist). Sorted leaders: 1001, 1002, 1003, 1010, 1012, 1013. Blocks: [1001], [1002], [1003-1009], [1010-1011], [1012], [1013-1017]. Answer: 6.

Concept: Leader rules: first instruction, every jump target, every instruction following a jump. Commonly missed: 1002 as a target, making 1001 a block by itself.

Each access time already includes the earlier misses, so weight each by the probability that the access is served there. L1: 0.95 x 10 = 9.5. L2: 0.05 x 0.85 x 20 = 0.85. Memory: 0.05 x 0.15 x 200 = 1.5. AMAT = 9.5 + 0.85 + 1.5 = 11.85 ns. Answer: 11.85.

Concept: When given times include miss penalties, do not add L1 and L2 times again. The trap is the hierarchical sum 10 + 0.05(20 + 0.15 x 200), which double counts.

1, 3, 2: 3 faults, frames {1, 3, 2}. Ref 4 (4th): window 4, 2, 3, 1 - all resident pages appear; 1 is used last, replace 1: {4, 3, 2}. 2, 3 hit. Ref 1 (7th): window 1, 2, 4, 3; 3 used last, replace 3: {4, 1, 2}. 2, 4 hit. Ref 3 (10th): window 3, 1, 4 (end of string); 2 does not appear, replace 2: {4, 1, 3}. 1, 4 hit. Faults: 3 + 1 + 1 + 1 = 6. Answer: 6.

Concept: Optimal replacement limited to a lookahead window: evict a page absent from the window, else the one used furthest within it. Here the window never misleads, so the count matches full OPT.

Mark has cid 102. The team with cid 102 is tid 10 (MI). Members of team 10: pids 1 and 3. Their ages: Jasprit 31, Ishan 26. MIN(age) = 26. Answer: 26.

Concept: Nested IN subquery with a three-way join. Trap: matching coach id to the wrong team or taking the minimum over all players (24).

Each bit arrives correctly with probability 0.99, independently. All 5 correct: 0.99⁵ = 0.95099..., which rounds to 0.951. Answer: 0.951.

Concept: Independent events multiply. The trap is 1 - 5 x 0.01 = 0.95, a first-order approximation that is slightly off at three decimals.

Assume a 20-byte IP header; fragment data (except the last) must be a multiple of 8. At MTU 5000: max data 4980, rounded down to 4976. 15000 = 3 x 4976 + 72, giving 4 fragments: 4976, 4976, 4976, 72. At MTU 3000: max data 2980, rounded down to 2976. Each 4976 fragment splits into 2976 + 2000 (2 fragments); the 72-byte one passes unchanged. Total = 3 x 2 + 1 = 7. Answer: 7.

Concept: IPv4 fragmentation: payload per fragment is (MTU - header) rounded down to a multiple of 8, and fragments are never reassembled at routers. Trap: dividing 15000 directly by the smallest MTU (6).

Normalise: ∫ from 1 to 4 of Cx² dx = C(64 - 1)/3 = 21C = 1, so C = 1/21. P(2 ≤ x ≤ 3) = (1/21) ∫ from 2 to 3 of x² dx = (1/21)(27 - 8)/3 = 19/63 ≈ 0.302. Answer: 0.302 (accepted range 0.300 to 0.302).

Concept: Find the constant from total probability 1, then integrate over the interval. Trap: forgetting to normalise.

Partition by outputs: P1 = {A, B, C, E} (00), {D, H} (10), {F} (11), {G} (01). Refine by next-state classes. D: (G, A), H: (G, A): identical, D ≡ H. In P1: A → (F, P1), C → (F, P1), B → (DH, P1), E → (DH, P1): split into {A, C} and {B, E}. B and E both go to (D, C): equivalent. A → (F, B) and C → (F, E) with B ≡ E: equivalent. Final classes {A, C}, {B, E}, {D, H}, {F}, {G}. Answer: 5.

Concept: State minimisation by partition refinement: start from output classes and split until next-state classes agree. Equivalences can depend on each other (A ≡ C needs B ≡ E).

A shift register with the inverted last output fed back is a Johnson (twisted ring) counter. With n = 4 flip-flops it cycles through 2n = 8 states, e.g. 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000 (Q0Q1Q2Q3). The 16 states split into two cycles of 8, so from any initial value the circuit returns after 8 clocks. Answer: 8 (7 also accepted by the official key, if the initial state is not counted).

Concept: Ring counter (Q3 fed back) has n states; Johnson counter (Q3' fed back) has 2n. The official range 7-8 reflects whether the initial state is counted.

foo adds 1 for every adjacent pair that differs, and 1 for the last element, i.e. it counts runs of equal values. Array: 0 | 1 | 2 2 2 | 0 0 | 1 1. Differing adjacent pairs: 0-1, 1-2, 2-0, 0-1 = 4, plus 1 at size 1. Total 5 (the number of runs). Answer: 5.

Concept: Recognise the recursion's meaning (count of maximal runs) instead of tracing nine calls. Trap: forgetting the base case returns 1, not 0.

The loop deletes every node after the head whose value occurs in L2; the head itself (1) is never tested. L2 values: {1, 11, 6, 9, 15, 12, 4}. Walk L1 after the head: 7 keep, 12 delete, 3 keep, 9 delete, 5 keep, 11 delete, 15 delete, 8 keep. Remaining: 1 → 7 → 3 → 5 → 8. Answer: 5.

Concept: Deleting via ptr1->next without advancing ptr1 handles consecutive deletions (11, 15). Trap: deleting the head 1 as well (giving 4), though only next nodes are ever checked.

First loop: t becomes 100000, then t /= 10 gives 10000, the place value of the leading digit. Second loop extracts digits left to right: 1, 4, 3, 6, 2, with turn = 0, 1, 0, 1, 0. Only digits with turn = 1 are appended: 4 then 6, so newnum = 46. Answer: 46.

Concept: The function keeps the 2nd, 4th, ... digits from the left. Trap: starting turn at 1 (giving 132) or reading digits right to left.

Edge BC is in every MST iff it is strictly lighter than the heaviest edge on every other B-C path (cycle property). Other B-C paths and their maximum edge: B-A-C max(7, 3) = 7; B-D-C max(1, 8) = 8; B-D-A-C max(1, 6, 3) = 6; B-A-D-C max(7, 6, 8) = 8. The smallest of these is 6, so we need x < 6. At x = 6, the MST {BD, AC, AD} avoids BC. Largest integer: x = 5. Answer: 5.

Concept: An edge is in every MST iff every alternative path between its endpoints contains an edge strictly heavier than it. Trap: answering 6, where a tie lets another MST exclude BC.

63 mod 11 = 8 → slot 8. 50 mod 11 = 6 → slot 6. 25 mod 11 = 3 → slot 3. 79 mod 11 = 2 → slot 2. 67 mod 11 = 1 → slot 1. 24: h1 = 2 (occupied), h2 = 1 + (24 mod 7) = 1 + 3 = 4. i = 1: (2 + 4) mod 11 = 6 (occupied). i = 2: (2 + 8) mod 11 = 10, free. Key 24 goes to slot 10. Answer: 10.

Concept: Double hashing steps by h2(k) on each collision. Traps: using linear probing (slot 4) or forgetting h2 adds 1 to k mod 7.