GATE 2022 CS (Computer Science) question paper with solutions

The first blank needs a noun meaning the price of travel: 'fare'. The second blank needs an adjective meaning reasonable or just: 'fair'. The sentence reads 'The fare is too high for it to be considered fair.' Answer: (D) fare / fair.

Concept: Homophone pair fare (price of a ticket) and fair (just, reasonable). The trap is choosing by sound alone; read each blank for the part of speech it needs.

The curve is a step function, so the area is a sum of rectangles. First piece: width 1/3, height 2, area 2/3. Second piece: width 3/4 - 1/3 = 5/12, height 3, area 5/4. Third piece: width 1/4, height 1, area 1/4. Total = 2/3 + 5/4 + 1/4 = 2/3 + 3/2 = 4/6 + 9/6 = 13/6. Answer: (C) 13/6.

Concept: Area under a piecewise constant function is the sum of width times height for each piece. The usual slip is mis-computing the middle width 3/4 - 1/3 = 5/12.

From the equation, r² + 2r = −6, i.e. r² = −2r − 6. Pair the factors: (r + 2)(r + 3) = r² + 5r + 6 = (−2r − 6) + 5r + 6 = 3r. (r + 4)(r + 5) = r² + 9r + 20 = 7r + 14. Product = 3r(7r + 14) = 21r² + 42r = 21(r² + 2r) = 21 × (−6) = −126. Answer: (D) −126.

Concept: Reduce every r² using the equation instead of solving for the complex roots. The trap is pairing (r+2)(r+5) and (r+3)(r+4), which does not collapse as neatly, or a sign slip giving 126.

With at least one student, 'All students are inquisitive' and 'No student is inquisitive' are contraries: they cannot both be true. Statements 1 and 2 can both be true (all implies some). Statements 2 and 4 can both be true (some are, some are not). Statements 3 and 4 can both be true (if none is, then some are not). Answer: (A) Statement 1 and Statement 3.

Concept: Square of opposition: A (all) and E (none) are contraries, A and O / E and I are contradictories. The existence assumption is what makes 'some' follow from 'all'.

Rotate every plate upright and list the five letters. (A) A, D, D, D, J: J appears once and A appears once, so two letters have odd counts - no palindrome. (B) A, D, R, A, R: counts A2, R2, D1 - one odd letter, so a palindrome exists: RADAR. (C) A, D, Z, E, D: A, Z, E each once - no. (D) A, D, I, L, Y: all single - no. Answer: (B).

Concept: A five-letter palindrome needs every letter to appear an even number of times except one (the middle). Rotating a plate in its plane does not change which letter it is; mirroring would, but is not allowed.

The passage states that in organizations with good work culture, metrics help improve outcomes, while in poor work culture they are counterproductive. (A) contradicts the passage, (C) and (D) contradict it for good work culture. (B) restates the passage. Answer: (B) Metrics are useful in organizations with good work culture.

Concept: An inference must follow from the passage without adding claims. Watch for absolute words like 'always' and 'never', which the passage does not support.

Girls are 60% of the qualified candidates, so boys are 40% of the qualified. Therefore fewer boys qualified than girls. (A) is wrong (60 vs 40), (B) is wrong (65% vs 35% appeared), (C) is wrong (more boys appeared). Answer: (D) The number of boys who qualified the test is less than the number of girls who qualified.

Concept: Keep the two bases separate: 65% is of those who appeared, 60% is of those who qualified. The trap is mixing the percentages across bases.

Condition on the first draw. Green first (probability 3/5): box becomes 2 green, 2 orange, so P(orange next) = 2/4 = 1/2. Orange first (probability 2/5): it is replaced, box stays 3 green, 2 orange, so P(orange next) = 2/5. Total = (3/5)(1/2) + (2/5)(2/5) = 3/10 + 4/25 = 15/50 + 8/50 = 23/50. Answer: (D) 23/50.

Concept: Total probability over the outcome of the first draw. The trap is assuming the box is unchanged, giving 2/5, or forgetting that only green balls are removed.

Among the six points, two joins are parallel only when one is a midline (two midpoints) and the other lies along the third side. Suppose S were a corner. S lies on two sides, so U (not sharing a side with S) must be the midpoint of the side opposite S. QS through corner S cannot be a midline, so PR must be the midline parallel to a side through S; that midline joins the midpoint opposite S (which is U) to another midpoint, so P or R would be U - impossible. Hence S cannot be a corner. Arrangements exist with P at a corner, U at a midpoint and R at a corner, so (A), (C), (D) are not forced. Answer: (B) S cannot be placed at a corner.

Concept: Midpoint theorem: the segment joining two midpoints is parallel to the third side. Test each option by assuming it false and checking for a contradiction.

Polynomial f(n) = a·nᵏ + lower terms: f(n²) ~ a·n²ᵏ and f(n)² ~ a²·n²ᵏ, same order, so (A) holds. Exponential f(n) = 2ⁿ: f(n²) = 2^(n²) while f(n)² = 2^(2n), so f(n²) is not O(f(n)²) - (C) fails, and this also kills (B). For f(n) = log n: f(n²) = 2 log n while f(n)² = log²n, so f(n²) is not Ω(f(n)²) - (D) fails. Answer: (A).

Concept: Test each claim with a polynomial, an exponential and a slow function like log n. The trap is (D): squaring the input grows polynomials and exponentials faster, but not logarithms.

Paths that leave q0 and return to it are a b* b (via q1) or b a* a (via q2), so the loops at q0 are (ab*b + ba*a)*. To finish, the string must end in an accepting state: go to q1 and stay (a b*) or go to q2 and stay (b a*). Language = (ab*b + ba*a)*(ab* + ba*), which is option (D) (the union inside the star is commutative). (C) accepts ε and strings ending at q0; (A) and (B) miss mixed loops. Answer: (D).

Concept: State elimination: collect all q0-to-q0 cycles, star them, then append every path to an accepting state. A common trap is allowing the empty suffix, which wrongly accepts strings ending at the non-accepting start.

(A) False: merging LR(1) states with the same core to form LALR(1) can create reduce-reduce conflicts that LR(1) did not have. (B) False: the symbol table is used by later phases too (semantic analysis, code generation). (C) False: data flow analysis is a compile-time optimization tool, not needed for run-time memory management. (D) True: every deterministic context-free language has an LR(1) grammar, so LR(1) parsing suffices. Answer: (D).

Concept: LR(1) grammars generate exactly the DCFLs. Remember LALR merging can introduce reduce-reduce (never shift-reduce) conflicts.

(A) True: with attributes {A, B}, any non-trivial FD is A→B or B→A, and its left side is then a key; with none, the key is AB. Either way every determinant is a superkey, so BCNF. (B) False: all-prime relations are in 3NF but can violate BCNF (e.g. R(A,B,C), AB→C, C→B). (C) False: a relation whose only key is all attributes has no non-prime attribute. (D) False: BCNF decomposition may lose dependencies. Answer: (A).

Concept: Two-attribute relations are always BCNF. The trap is (B), which guarantees only 3NF.

Walk the list once with three pointers prev, curr, next: save next = curr->next, set curr->next = prev, advance prev = curr, curr = next. At the end set head = prev. Each node is touched once and only three pointers are used, so time θ(n) and space O(1). Every node's link must change, so Ω(n) is also needed. Answer: (A).

Concept: In-place iterative pointer reversal. The trap is thinking O(1) space forces repeated scans (θ(n²)) or that recursion is required.

Each key, whether hashed by h₁ or h₂, lands in any particular slot with probability 1/m because both functions are simple uniform. By linearity of expectation, the expected number of keys in a slot is n × (1/m) = n/m. Splitting keys between two uniform functions changes nothing. Answer: (B) n/m.

Concept: Load factor α = n/m under simple uniform hashing. The trap is thinking two functions halve or double the load.

In programmed (polling) I/O the CPU moves every word and busy-waits; interrupt-driven I/O still has the CPU move each word, with interrupt overhead per transfer. DMA lets the controller move a whole block directly between the device and memory, interrupting the CPU once at the end, so it gives the highest throughput for bulk transfers. Answer: (A) DMA based I/O transfer.

Concept: DMA is designed for block transfers. Interrupt-driven I/O helps CPU utilisation for slow devices but does not beat DMA for bulk data.

4-bit 2's complement range is −8 to 7. (A) 1011 = −5, 1110 = −2, sum −7: fine. (B) 1100 = −4, 1010 = −6, sum −10: below −8, overflow (bit-wise 1100 + 1010 = 0110, a positive result from two negatives). (C) 3 + 4 = 7: fine. (D) 1001 = −7, 1111 = −1, sum −8: representable. Answer: (B) R1 = 1100 and R2 = 1010.

Concept: Overflow happens only when both operands have the same sign and the result's sign differs. The trap is (D): −8 is still representable in 4 bits.

B must come first, so only T2 may proceed initially: S1 = 1 and S2 = S3 = 0. Then T2 prints B and signals S3, enabling only T1, which prints C and signals S2, enabling only T3, which prints A and signals S1, enabling T2 again. The cycle BCA repeats with exactly one semaphore at 1 at any time. Any initialization with two semaphores at 1 lets another thread print first or interleave. Answer: (C) S1 = 1; S2 = 0; S3 = 0.

Concept: A token-passing ring of semaphores enforces a strict order only if exactly one token exists. The trap is (B), where T3 could print A before B.

tr(AB) = Σᵢ Σⱼ aᵢⱼ bⱼᵢ (AB is m×m) and tr(BA) = Σⱼ Σᵢ bⱼᵢ aᵢⱼ (BA is n×n). Both are the same double sum, so tr(AB) = tr(BA) even though AB and BA have different sizes. Statement 2 is the special case m = n. Answer: (C) Both Statement 1 and Statement 2 are correct.

Concept: The cyclic property of trace holds whenever both products are defined. The trap is thinking different sizes of AB and BA break the identity.

p = &x and *p = 10 set x = 10. p is then pointed at z[1] but not used for writing. &z[0] + 1 is the address of z[1], so *(&z[0] + 1) += 3 makes z[1] = 11 + 3 = 14. z[0] stays 10. Output: 10, 10, 14. Answer: (D).

Concept: Pointer arithmetic: &z[0] + 1 equals &z[1]. The trap is thinking the write goes to z[0] or that x is unchanged.

Every router or firewall interface bounds a subnet, so count the distinct links inside the enterprise: firewall-Router 1, firewall-Router 2, Router 2-web server, Router 2-Router 3, Router 1-Ethernet segment 1, Router 3-Ethernet segment 2. That is 6 subnets (the Internet side of the firewall is outside the enterprise). Answer: (C) 6.

Concept: Routers separate subnets: each point-to-point router link and each LAN behind a router is its own subnet. The trap is counting only the two Ethernet LANs or including the Internet link.

(A) False: Σ* is recursive, yet its subset HALT is not recursive. (B) True: run recognisers for L and L̄ in parallel; one must accept, so membership is decided. (C) True: every CFL is recursive, and recursive languages are closed under complement. (D) True: regular languages are closed under intersection, and every regular language is deterministic context-free. Answer: (B), (C), (D).

Concept: Closure facts: recursive languages are closed under complement; L and L̄ both RE implies recursive. Subsets inherit nothing - any language is a subset of Σ*.

(A) False: only a write-back cache needs a dirty bit; write-through keeps memory current. (B) False: a write hit in WB updates only the cache and sets the dirty bit; memory is written on eviction. (C) True: WT memory is always up to date, so eviction just discards the block. (D) False: a read miss in WB may choose a dirty LRU victim, which must be written back. The FALSE statements are (A), (B), (D). Answer: (A), (B), (D).

Concept: Write-back defers memory updates using a dirty bit; write-through writes every store to memory. Note the question asks for FALSE statements.

(A) Division of Own by all brand ids is exactly 'owns every brand'. (B) Π_eId(Own) × Π_bId(Brand) lists every (owner, brand) pair that should exist; subtracting Own leaves the missing pairs; their eIds are owners missing some brand; removing them leaves owners of all brands - the expansion of division. (C) Divides by brands that someone owns, so an unowned brand is ignored - wrong. (D) The cross product pairs every owner with every owned brand regardless of actual ownership - wrong. Answer: (A), (B).

Concept: R ÷ S = Π_X(R) − Π_X((Π_X(R) × S) − R). The trap is dividing by Π_bId(Own) instead of Brand.

(A) True: circular wait is one of the four Coffman necessary conditions. (B) False: with multiple instances per resource, a cycle is necessary but not sufficient for deadlock. (C) False: an unsafe state may lead to deadlock, but processes may release resources early, so deadlock is not certain. (D) True: if every edge is an assignment edge, no process is waiting for anything, so no deadlock. Answer: (A), (D).

Concept: Cycle implies deadlock only for single-instance resources; unsafe does not mean deadlocked. Deadlock needs some process waiting.

(A) xyxy = xxyy; cancel x on the left and y on the right: yx = xy. True. (B) Every element is its own inverse, so xy = (xy)⁻¹ = y⁻¹x⁻¹ = yx. True. (C) A group of order 2 is cyclic, hence abelian. True. (D) False: elements of a subgroup are elements of G, so they commute. Answer: (A), (B), (C).

Concept: Standard abelian criteria via cancellation laws. Every subgroup of an abelian group is abelian, and every group of prime order is cyclic.

Complete tree with 1000 nodes in array form: node i has children 2i+1 and 2i+2. Largest element = rightmost node: 0 → 2 → 6 → 14 → 30 → 62 → 126 → 254 → 510; its right child 1022 does not exist, so the maximum is at 510. 510 has no left child (1021 > 999), so the 2nd largest is its parent 254. The 3rd largest is the maximum of 254's left subtree, rooted at 509; 509's children (1019, 1020) do not exist, so it is 509. Answer: 509.

Concept: In-order predecessor in a BST: max of left subtree, else nearest ancestor from which you came right. Heap-style indexing locates the nodes. The trap is assuming the largest is at the last index 999.

closure(I₀) = I₀ (the dots are at the end or before the terminal +). goto on + gives S → S + .R. Its closure adds R → .R * P, R → .P, and then for P: P → .(S), P → .id. Total = 5 items. Answer: 5.

Concept: goto moves the dot over the symbol, then closure adds productions for every non-terminal right after a dot, repeatedly. The trap is forgetting the P items reached through R → .P.

A disconnected graph splits into at least two components. With parts of size k and 10 − k the edge maximum is C(k,2) + C(10−k,2), largest when one part is a single vertex: K₉ plus an isolated vertex gives C(9,2) = 36 edges. Answer: 36.

Concept: Maximum edges in a disconnected simple graph on n vertices is C(n−1, 2). The trap is splitting the vertices evenly, which minimises the count.

A and B never appear on a right-hand side, so every key must contain both. AB⁺: AB → C, then BC → D, C → E, so AB⁺ = ABCDE and AB is the only candidate key. A superkey is any superset of AB: the remaining attributes C, D, E can each be in or out, giving 2³ = 8 superkeys. Answer: 8.

Concept: Attributes absent from every right side belong to every key. With a single candidate key of size k in n attributes, there are 2ⁿ⁻ᵏ superkeys.

Identical balls and identical bins means we count partitions of 6 into at most 3 parts (empty bins allowed): 6; 5+1; 4+2; 3+3; 4+1+1; 3+2+1; 2+2+2. That is 7 arrangements. Answer: 7.

Concept: Identical objects into identical boxes is a partition count, not stars and bars. The trap is using C(8,2) = 28, which assumes distinct bins.

AMAT = hit time + miss rate × miss penalty. Before: 10 + 0.2 × 100 = 30 ns. After: 15 + (1 − h) × 100 must be ≤ 30, so (1 − h) × 100 ≤ 15, giving 1 − h ≤ 0.15 and h ≥ 0.85. Answer: 0.85.

Concept: Trade-off between hit time and miss rate in the AMAT formula. Use the same AMAT model before and after; mixing models changes the result.

At x = 0 both numerator and denominator are 0, so apply L'Hôpital's rule: derivative of x is 1; derivative of 1 − e²ˣ is −2e²ˣ. The limit is 1 / (−2e⁰) = −1/2. Equivalently e²ˣ ≈ 1 + 2x, so the ratio ≈ x / (−2x). Answer: −0.5.

Concept: 0/0 form handled by L'Hôpital or the series e^u ≈ 1 + u. The usual slip is dropping the minus sign.

With nothing cached and iterative resolution, the resolver walks the hierarchy one level at a time: (1) root server, referred to the .in TLD server; (2) .in server, referred to the org.in server; (3) org.in server, referred to the gate.org.in server; (4) gate.org.in authoritative server returns the address of www.gate.org.in. That is 4 query-response pairs. Answer: 4.

Concept: In iterative resolution the resolver contacts each level of the domain hierarchy separately. The trap is counting only root, TLD and authoritative (3) and forgetting the second-level org.in zone.

Write aₙ = 1 + (n if n odd, else 0). Σ xⁿ = 1/(1 − x). For the odd part, let g(x) = Σ over odd n of xⁿ = x/(1 − x²). Then Σ over odd n of n·xⁿ = x·g'(x). g'(x) = [(1 − x²) + 2x²]/(1 − x²)² = (1 + x²)/(1 − x²)², so x·g'(x) = x(1 + x²)/(1 − x²)². Total = x(1 + x²)/(1 − x²)² + 1/(1 − x). Check: coefficient of x is 1 + 1 = 2 = a₁. Answer: (A).

Concept: Split the sequence into simple pieces and use x·d/dx to bring down the factor n. Checking a₁ = 2 and a₃ = 4 quickly eliminates the other options.

(A³)ᵢᵢ counts closed walks of length 3 starting and ending at vertex i. In a simple graph such a walk must trace a triangle. Each triangle {u, v, w} yields 6 closed walks: 3 choices of starting vertex times 2 directions. So the number of triangles = tr(A³)/6. Answer: (D) A³ divided by 6.

Concept: Powers of the adjacency matrix count walks. The trap is dividing by 3 (forgetting direction) or by 2 (forgetting the starting vertex).

(A) True: a TLB is associative memory, searched in parallel on the page number. (B) True: a TLB hit means the page is mapped to a frame, i.e. resident in main memory, so a cache miss is served from main memory. (C) False: an inverted page table is searched for the (process, page) entry - linearly or via a hash with chains - so lookup time depends on where the entry is found and varies across addresses. (D) True: colliding addresses share a hash chain, so one is found later than the other. Answer: (C).

Concept: Inverted and hashed page tables trade memory for variable lookup time. Note the question asks for the FALSE statement.

Conflicting pairs (same item, different transactions, at least one write), in schedule order: on x - R₄(x) before W₂(x) gives T₄ → T₂; R₃(x) before W₂(x) gives T₃ → T₂. On y - R₁(y)/W₁(y) before W₃(y) gives T₁ → T₃; W₁(y) before R₄(y) gives T₁ → T₄; W₃(y) before R₄(y) gives T₃ → T₄. The precedence graph is acyclic with unique topological order T₁ → T₃ → T₄ → T₂. Answer: (A).

Concept: Build the precedence graph from conflicting operations and topologically sort it. The trap is missing W₃(y) → R₄(y), which forces T₃ before T₄.

S has 1024 = 2¹⁰ words, so its address field is 10 bits and P must turn 10 address bits into one of 1024 word-select lines: a 10:2¹⁰ decoder. R has 32 = 2⁵ words, so Q is a 5:2⁵ decoder. T chooses between two data words (from S or R) under the control of M: a 2:1 multiplexer. Bits check: 1 + 10 + 5 = 16. Answer: (C).

Concept: Address bits select a word through a decoder; choosing one of several data inputs is a multiplexer. The trap is calling T an encoder.

RA = 1100 0001 0100 0...: sign 1, exponent 1000 0010 = 130, so 2³; fraction .1 = 0.5; A = −1.5 × 8 = −12. RB = 0100 0010 0001 0...: exponent 1000 0100 = 132, so 2⁵; fraction .001 = 0.125; B = 1.125 × 32 = 36. RC = 0100 0001 0100 0...: C = +12. Check: A + C = 0 true; A + B = 24 ≠ 12, so C = A + B is false; 3C = 36 = B true; B − C = 24 > 0 true. Answer: (B).

Concept: Decode sign, biased exponent (bias 127) and fraction with the hidden 1. Note the question asks for the FALSE statement.

Simulate RR, quantum 4, queue P, Q, R, S. (A) P4 Q10 R6 S2: P(done) → Q(6 left) → R(2 left) → S(done) → Q(2 left) → R(done) → Q. Switches S→Q 1, R→Q 1, Q→R 2, no S→P: possible. (B) P2 Q9 R5 S1: P → Q(5) → R(1) → S → Q(1) → R → Q: same pattern, possible. (C) P4 Q12 R5 S4: P → Q(8) → R(1) → S → Q(4) → R → Q: possible. (D) P3 Q7 R7 S3: P → Q(3 left) → R(3 left) → S → Q(finishes) → R. There is no R→Q switch, violating 'exactly one R→Q'. Answer: (D) P = 3, Q = 7, R = 7, S = 3.

Concept: Trace the ready queue and record every switch, including switches after termination. The constraints amount to Q needing a third CPU turn after R's second turn.

Each inner brace initialises one a[i] (a 3×3 block) in row-major order: a[0] = 1..9, a[1] = 10..18, a[2] = 19..27. Within a[i], a[i][0][k] is the first row: elements 1-3 of that block. j stays 0 throughout. So the loop prints a[0][0][0..2] = 1 2 3, a[1][0][0..2] = 10 11 12, a[2][0][0..2] = 19 20 21, one line each. Answer: (A).

Concept: Brace elision fills a sub-aggregate in row-major order. The trap is assuming j advances (it is never changed) or that k steps by a row (option B).

'P' = 80 = 0101 0000 and 'x' = 120 = 0111 1000. a & b = 0101 0000 = 80; 80 + 42 = 122 = 'z'. a | b = 0111 1000 = 120; 120 − 45 = 75 = 'K'. a ^ b = 0010 1000 = 40; 40 + 43 = 83 = 'S'. %c prints characters: z K S. Answer: (A).

Concept: Bitwise operators on character codes, then printing with %c. The trap is (B), the same values printed as integers.

Doolittle (unit diagonal L): U row 1 = [1, 1, −2]; L₂₁ = 1, L₃₁ = 2. Row 2: U₂₂ = 3 − 1 = 2, U₂₃ = −1 − (−2) = 1. L₃₂ = (1 − 2·1)/2 = −1/2. U₃₃ = −5 − (2)(−2) − (−1/2)(1) = −5 + 4 + 1/2 = −1/2. Solve: eq2 − eq1 gives 2x₂ + x₃ = 3; eq3 − 2·eq1 gives −x₂ − x₃ = −1. Adding: x₂ = 2, x₃ = −1, then x₁ = 4 − 2 − 2 = 0. Answer: (D) L₃₂ = −1/2, U₃₃ = −1/2, x₁ = 0.

Concept: LU factors are the Gaussian elimination multipliers (L) and the reduced rows (U). The trap is a sign slip in L₃₂, whose multiplier is negative here.

(A) Equivalence of TMs is undecidable (it is not even RE nor co-RE). (B) Regularity of L(M) is a non-trivial semantic property, undecidable by Rice's theorem. (C) L(M) = Σ* is a non-trivial semantic property, undecidable by Rice's theorem. (D) Decidable: in 1073 steps M reads at most the first 1073 symbols, so it suffices to simulate M for 1073 steps on every string of length at most 1073 - a finite check. Answer: (A), (B), (C).

Concept: Rice's theorem covers properties of the language L(M). A bound on running steps is a property of the machine's behaviour on finitely many relevant inputs, so it is decidable.

L₁: take n as small as allowed and absorb the rest of the a's into w; L₁ = a(a+b)*a (or all of {a,b}* if n = 0 is allowed) - regular either way. L₂: shrink w to a single letter and absorb the rest into x; a string is in L₂ iff it has length ≥ 3 and starts and ends with the same letter: a(a+b)⁺a + b(a+b)⁺b - regular. Regular languages are context-free, so (A), (B), (C) hold and (D) fails. Answer: (A), (B), (C).

Concept: When an unrestricted middle string w or x can swallow the matched parts, the matching constraint disappears. The trap is assuming aⁿ...aⁿ or w...wᴿ always needs a stack.

L₁ = {ww} is not context-free. L₂ and L₃ are deterministic CFLs (one stack comparison each). L₂ ∩ L₃ = {aⁿbⁿcⁿ}, not context-free. The complement of {ww} is context-free (a standard result). (A) True. (B) False, since L₂ is context-free. (C) False, since L₂ ∩ L₃ is not context-free. (D) False, since the complement of L₁ is context-free. Answer: (B), (C), (D).

Concept: CFLs are not closed under intersection; {aⁿbⁿcⁿ} is the classic witness. The complement of {ww} is a CFL even though {ww} is not. Note the question asks for FALSE statements.

Think of Kruskal. (A) The two lightest edges can never form a cycle, so both are picked: true. (B) The third edge is rejected only if edges 1, 2, 3 form a triangle. Then the fourth edge would be rejected only if it closed a cycle with edges 1 and 2, i.e. joined the same pair as edge 3, impossible in a simple graph. So at least one of them is picked: true. (C) Cut property: with distinct weights, the lightest edge crossing any cut is in every MST: true. (D) Distinct weights give a unique MST: false. Answer: (A), (B), (C).

Concept: Kruskal's order and the cut property. The trap is (D): multiple MSTs need tied weights.

(B) f(2) = 2·1 − 1 = 1, and if f(2ᵏ) = 1 then f(2ᵏ⁺¹) = 2·1 − 1 = 1: true. (A) f(1) = 1, f(3) = 2f(1) + 1 = 3, f(7) = 7; 2ⁿ⁺¹ − 1 = 2(2ⁿ − 1) + 1 gives f = 2(2ⁿ − 1) + 1 = 2ⁿ⁺¹ − 1: true. (C) f(5) = 2f(2) + 1 = 3 = 2¹ + 1; f(5·2ⁿ⁺¹) = 2f(5·2ⁿ) − 1 = 2(2ⁿ⁺¹ + 1) − 1 = 2ⁿ⁺² + 1: true. (D) f(5) = 2f(2) + 1 = 3, but 2² + 1 = 5: false. Answer: (A), (B), (C).

Concept: Prove each closed form by induction along the recurrence's own step (n to 2n or 2n + 1). One counterexample such as f(5) = 3 kills (D).

(A) (A²)ᵢᵢ = Σⱼ aᵢⱼaⱼᵢ = Σⱼ aᵢⱼ = degree of i: true. (B) False: path 1-2-3 (n = 3). A² + I has entry (1,2) = 0, since there is no walk of length exactly 2 from 1 to 2. (C) Sum of entries = 2|E| ≤ 2(n − 1) means |E| ≤ n − 1, but a triangle plus an isolated vertex (n = 4, 3 edges) has a cycle: false. (D) No isolated vertex does not imply connected (two disjoint edges): false. Answer: (A).

Concept: Aᵏ counts walks of length exactly k, so bipartite parity can leave zeros; (I + A)ⁿ⁻¹ would be the correct test. Few edges does not guarantee a forest unless the graph is connected.

Multiply the matrix by each vector. (A) (−1,1,0,1): rows give 9−6−4 = −1, 8−6−1 = 1, −20+15+5 = 0, −32+21+12 = 1, so Av = v (λ = 1). (B) (1,0,−1,0): first two rows give −9+2 = −7 and −8+3 = −5, not proportional to (1,0,...): not an eigenvector. (C) (−1,0,2,2): 9−4−8 = −3, 8−6−2 = 0, −20+16+10 = 6, −32+14+24 = 6, giving 3v (λ = 3). (D) (0,1,−3,0): −6+6 = 0, −6+9 = 3, 15−24 = −9, 21−21 = 0, giving 3v (λ = 3). Answer: (A), (C), (D).

Concept: Check Av = λv directly; no need for the characteristic polynomial. A zero entry in v must map to zero in Av, which quickly rules out (B).

64 KB space: 16-bit addresses. 2 KB / 64 B = 32 lines, so 6 offset bits, 5 index bits, 5 tag bits. Block number = address / 64: P 0xA248 → block 649, line 649 mod 32 = 9. Q 0xC28A → block 778, line 10. R 0xCA8A → block 810, line 10. S 0xA262 → block 649, line 9 - the same block as P. Round 1: P miss, Q miss, R miss (evicts Q), S hit. Each later round: P hit, Q miss (evicts R), R miss (evicts Q), S hit. So every S access hits (A true), P's block is never evicted (B true), every R access evicts Q (D true). At the end line 9 holds P and S and line 10 holds R, so P is also resident and (C) is false. Answer: (A), (B), (D).

Concept: Split the address into tag, index and offset. The trap is missing that S lies in the same 64-byte block as P.

Third-octet ranges: 12.20.164.0/22 covers 164-167; 12.20.166.0/23 covers 166-167 (inside it); 12.20.168.0/23 covers 168-169; 12.20.170.0/23 covers 170-171. Together: 164-171. 12.20.164.0/22 (164-167) plus 12.20.168.0/22 (168-171) cover exactly this range. A /21 must start at a multiple of 8 (160), so 12.20.164.0/21 is not a valid aligned prefix and would mean 160-167. A /20 (160-175) also grabs addresses that should go to the default route R3. Answer: (B) and (D).

Concept: Aggregation must be exact and aligned: a /k block starts at a multiple of its size. The trap is picking a single larger prefix that over-covers or is misaligned.

The subquery lists D01 courses the student has NOT registered for; NOT EXISTS keeps students for whom that list is empty, i.e. students registered for every D01 course. D01 courses: C11, C12. S01 has C11 and C12: kept. S02 has only C11: dropped. S03 has neither: dropped. S04 has C11 and C12: kept. S05 has C11 and C21 (no C12): dropped. Rows returned = 2. Answer: 2.

Concept: NOT EXISTS (required EXCEPT taken) is SQL's relational division. The student's own department does not matter here, which is the usual trap.

Before the failure, P's distance to R is 2 (via Q). When Q-R fails, Q sets its distance to R to ∞. If Q sends its update first, P learns R is unreachable and no loop forms. If P sends first, it still advertises distance 2 to R, so Q adopts a route via P with cost 3 while P routes via Q: a loop that counts to infinity. With equal rates, each is first with probability 1/2. Answer: 0.5.

Concept: Count-to-infinity arises when a stale route is advertised back to the router that lost the link. Without split horizon, the outcome depends only on who updates first.

Edges go from i to j only when j ≤ i, so every edge points to a smaller (or the same) vertex. In a spanning tree rooted at 5, each other vertex v has exactly one incoming tree edge from a parent u with u > v. Any such choice is automatically acyclic because parents are strictly larger, and every vertex then reaches back to 5. Choices: vertex 4 - parent 5 (1); vertex 3 - 4 or 5 (2); vertex 2 - 3, 4 or 5 (3); vertex 1 - 2, 3, 4 or 5 (4). Total = 1 × 2 × 3 × 4 = 24. Answer: 24.

Concept: An arborescence is fixed by choosing one parent per non-root vertex, provided no cycle forms; here edge direction rules out cycles. Self-loops (i = j) are never used.

Transmission time = 1000 × 8 bits / 10⁸ bps = 8 × 10⁻⁵ s = 0.08 ms. Propagation delay = 2.1 × 10⁶ m / (3 × 10⁸ m/s) = 7 × 10⁻³ s = 7 ms. The last bit arrives after transmission + propagation = 7.08 ms. Answer: 7.08 (accepted range 7.07 to 7.09).

Concept: Time to fully receive a packet = transmission delay + propagation delay. The trap is counting only the propagation delay (7.00) or doubling it as for round-trip.

TCP numbers bytes. In one MSL the link can send 10⁹ bits/s × 60 s = 6 × 10¹⁰ bits = 7.5 × 10⁹ bytes. The sequence space must hold at least that many distinct numbers: 2ⁿ ≥ 7.5 × 10⁹. 2³² ≈ 4.29 × 10⁹ is too small and 2³³ ≈ 8.59 × 10⁹ suffices, so n = 33 bits. Answer: 33.

Concept: Wrap-around time = 2ⁿ / byte rate must exceed MSL. The trap is using bits instead of bytes, which gives 36.

X₁: CPI = 1 + 0.3 × 2 = 1.6. X₂: only the 20% mispredicted branches stall, CPI = 1 + 0.3 × 0.2 × 2 = 1.12. Same clock, so speed up = 1.6 / 1.12 ≈ 1.43. Answer: 1.43 (accepted range 1.42 to 1.45).

Concept: Effective CPI = base CPI + branch fraction × stall fraction × penalty. The trap is applying the 80% to all instructions rather than to branches.

Use Q2 itself, rotating it. Dequeue 1 from Q1, enqueue to Q2: [1]. Dequeue 2, enqueue to Q2: [1, 2]; rotate Q2 once (dequeue 1, enqueue 1): [2, 1]. Dequeue 3, enqueue: [2, 1, 3]; rotate twice: [3, 2, 1]. Dequeue 4, enqueue: [3, 2, 1, 4]; rotate three times: [4, 3, 2, 1]. No element is ever enqueued back into Q1. Answer: 0.

Concept: Rotating a queue (dequeue then enqueue to the same queue) moves the newest element to the front. The question counts only Enqueue operations on Q1, which is the trap.

Contiguous (A): blocks 51-100 must each move one place right: 50 reads + 50 writes, then write the new block in position 51: nA = 101. Linked (B): follow pointers from the start to block 50: 50 reads; write the new block with its pointer set to old block 51: 1 write; rewrite block 50 with its pointer to the new block: 1 write. nB = 52. nA + nB = 153. Answer: 153.

Concept: Contiguous allocation pays for shifting; linked allocation pays for traversal. A trap is forgetting the write-back of block 50's updated pointer.

7 F, 2 F, 7 H, 3 F, 2 H, 5 F (frames 7,2,3,5), 3 H, 4 F evicts 7 (LRU), 6 F evicts 2, 7 F evicts 5, 7 H, 1 F evicts 3, 5 F evicts 4, 6 H, 1 H. Faults = 9 out of 15 references. Rate = 9/15 = 0.6. Answer: 0.6.

Concept: LRU evicts the page whose last use is oldest. Track last-use times carefully after hits; a hit refreshes recency.

% is generated lower in the tree (by T), so it binds tighter than #; both are left-recursive, hence left-associative. # means multiply and % means divide. Group: (20) # (10 % 5) # ((8 % 2) % 2). T values: 20; 10 ÷ 5 = 2; (8 ÷ 2) ÷ 2 = 2. S = (20 × 2) × 2 = 80. Answer: 80.

Concept: Precedence comes from grammar depth, associativity from left or right recursion. The trap is evaluating left to right ignoring precedence, or treating % as modulus.

p = &x; *p = 10; -> x becomes 10 (was 1). p = &z[1]; -> p now points at z[1] (this line alone changes nothing yet - it only repoints p). *(&z[0] + 1) += 3; -> &z[0]+1 is the same address as &z[1] (pointer arithmetic on an int array), so this adds 3 to z[1]: 11 + 3 = 14. Final values: x=10, z[0]=10 (never touched), z[1]=14. printf prints: 10, 10, 14 -> option (d).

Concept: The trap is assuming `p = &z[1];` itself changes z[1] - it only repoints the pointer p, it never dereferences or writes anything. The actual write to z[1] happens on the NEXT line, via `&z[0] + 1`, a completely separate pointer expression that happens to also reach z[1].