CS and IT Gate 2026 Set-2 Questions with Answer

The correct answer is Option A — log(n), n^1/3, 2^log(n), log(n!).
To order these functions asymptotically, we first simplify each one into a familiar growth class.
log(n): A standard logarithm, the slowest-growing of all common function classes. It grows slower than any positive power of n.
n^1/3: A sub-linear polynomial (cube root of n). Any positive polynomial power of n, however small, grows strictly faster than log(n) asymptotically.
2^log(n): When log is base 2, 2^log₂(n) = n exactly, placing it in Θ(n). This grows faster than n^1/3 since n dominates n^1/3 for large n.
log(n!): By Stirling''s approximation, log(n!) ≈ n·log(n) − n, so log(n!) is Θ(n log n). This grows faster than Θ(n), making it the largest of the four.
Putting it all together in increasing order of asymptotic growth: log(n) < n^1/3 < 2^log(n) < log(n!), which corresponds to Option A.
Option B puts n^1/3 before log(n) — incorrect, as log grows slower. Option C places log(n!) before 2^log(n) — incorrect ordering at the top. Option D reverses the first two — also incorrect.

The correct answer is Options A, B, and C — Reflexive, Symmetric, and Transitive. R is an equivalence relation.
Key insight: (x, y) ∈ R iff x·y is a perfect square. This happens exactly when x and y have the same square-free part — the product of prime factors appearing an odd number of times. Numbers 1–10 grouped by square-free part: {1,4,9}, {2,8}, {3}, {5}, {6}, {7}, {10}.
Reflexive: For any x, x·x = x² is always a perfect square. So (x,x) ∈ R for all x ∈ {1,...,10}. TRUE.
Symmetric: If x·y is a perfect square, then y·x = x·y is also a perfect square. So (x,y) ∈ R implies (y,x) ∈ R. TRUE.
Transitive: If (x,y) ∈ R and (y,z) ∈ R, then sqf(x) = sqf(y) and sqf(y) = sqf(z), so sqf(x) = sqf(z), meaning x·z is a perfect square → (x,z) ∈ R. TRUE.
Antisymmetric: Requires (x,y) ∈ R and (y,x) ∈ R to imply x = y. But (1,4) ∈ R since 1×4 = 4 = 2², and (4,1) ∈ R, yet 1 ≠ 4. FALSE.
Since R is reflexive, symmetric, and transitive, it is an equivalence relation — it partitions {1,...,10} into classes of numbers sharing the same square-free part.

The correct answers are Option A and Option C.
We evaluate the definite integral directly: I(a) = ∫₋₁¹ (3x² − ax + 1) dx, splitting it term by term over the symmetric interval [−1, 1].
∫₋₁¹ 3x² dx = [x³]₋₁¹ = 1 − (−1) = 2. ∫₋₁¹ 1 dx = [x]₋₁¹ = 1 − (−1) = 2. ∫₋₁¹ −ax dx = −a·[x²/2]₋₁¹ = −a·(½ − ½) = 0, because x is an odd function and the interval is symmetric about 0.
Therefore, I(a) = 2 + 2 + 0 = 4 for every real value of a, without exception.
Option A — I(a) is independent of a: True. The term containing a vanishes upon integration, leaving a constant value of 4 regardless of a.
Option B — I(a) can vary with a: False. As shown, I(a) = 4 for all a ∈ (−∞, +∞). There is no variation.
Option C — There exists a such that I(a) is a positive real number: True. Since I(a) = 4 > 0 for every a, it is certainly positive for some (in fact, all) values of a.
Option D — There exists a such that I(a) is a negative real number: False. I(a) = 4 > 0 always; it can never be negative.
The key insight is recognising that −ax is an odd function

A grammar is called ambiguous if there is at least one string in the language that can be derived in two or more distinct ways, resulting in different parse trees.
Option A — S → aSb | ε — Unambiguous
This generates strings aⁿbⁿ where n ≥ 0. For any such string, there is exactly one derivation — apply S → aSb exactly n times and then S → ε. No string has two different parse trees. A is unambiguous.
Option B — E → E + E | E * E | id — Ambiguous
This is the classic ambiguous arithmetic grammar. The string id + id * id has two different parse trees depending on which operator is evaluated first — treating it as (id + id) * id or id + (id * id). Since the grammar gives no precedence or associativity rules, both derivations are equally valid. B is ambiguous.
Option C — S → aS | Sa | ε — Ambiguous
Consider the string aa. One derivation is S → aS → aaS → aa (applying aS twice). Another is S → aS → aSa → aεa = aa (mixing aS and Sa). These give different parse trees for the same string. C is ambiguous.
Option D — S → aS | ε — Unambiguous
This generates aⁿ for n ≥ 0. The only way to derive aⁿ is to apply S → aS exactly n times followed by S → ε. There is no room for two different derivations. D is unambiguous.
Correct answer: B and C ✓

The correct answer is 3.
We apply the hash function h(k) = k mod 9 to each of the 9 keys and group them by their hash slot. Collisions are resolved by chaining, so each slot holds a linked list of all keys that map to it.
Computing the hash for each key: 5 mod 9 = 5, 28 mod 9 = 1, 19 mod 9 = 1, 15 mod 9 = 6, 26 mod 9 = 8, 33 mod 9 = 6, 12 mod 9 = 3, 17 mod 9 = 8, 10 mod 9 = 1.
Grouping by slot: Slot 1 → {28, 19, 10} — chain length 3. Slot 6 → {15, 33} — chain length 2. Slot 8 → {26, 17} — chain length 2. Slot 3 → {12} — chain length 1. Slot 5 → {5} — chain length 1. All other slots are empty.
The longest chain is at slot 1, which contains three keys — 28, 19, and 10 — all of which yield a remainder of 1 when divided by 9. The length of the longest chain is therefore 3.

The correct answer is 4094.
Analyse the subnet mask: 255.255.240.0 in binary = 11111111.11111111.11110000.00000000. This is a /20 mask — 20 network bits and 12 host bits.
Total addresses in the subnet: 2¹² = 4096 addresses.
Subtract reserved addresses: Every subnet reserves 2 addresses that cannot be assigned to interfaces -- the network address (all host bits = 0) and the broadcast address (all host bits = 1).
Maximum assignable addresses: 4096 − 2 = 4094.
These 4094 addresses can be assigned to host interfaces such as computers, routers, or servers within this subnet.

The correct answer is −60.25.
Converting the IEEE 754 single precision hex value 0xC2710000 step by step:
Hex to Binary: 0xC2710000 = 1100 0010 0111 0001 0000 0000 0000 0000
Split the 32 bits into IEEE 754 fields:
Sign bit: 1 (negative number)
Exponent bits: 10000100 = 132 in decimal
Mantissa bits: 11100010000000000000000
Actual exponent: E = 132 − 127 (bias) = 5
Mantissa value (with implicit leading 1):
1.11100010... = 1 + 2⁻¹ + 2⁻² + 2⁻³ + 2⁻⁷ = 1 + 0.5 + 0.25 + 0.125 + 0.0078125 = 1.8828125
Final value:
(−1)¹ × 1.8828125 × 2⁵ = −1 × 1.8828125 × 32 = −60.25

The correct answer is 13.
The lexical analyzer applies the maximal munch rule - it always tries to match the longest possible token. The token rules are: id must start with a letter (followed by letters/digits), number is one or more digits, and ws (whitespace) is excluded from the count.
Tokenizing each whitespace-separated segment:
x1 → starts with letter, followed by digit → id (1 token)
23 → digits only → number (1 token)
mm → letters only → id (1 token)
78 → digits only → number (1 token)
y → single letter → id (1 token)
7z → digit first → number: 7; then letter z cannot extend the number and cannot be skipped → id: z (2 tokens)
zz5 → starts with letter → id: zz5 (1 token)
14A → digit first → number: 14; then letter A → id: A (2 tokens)
8H → digit first → number: 8; then letter H → id: H (2 tokens)
AaYcD → starts with letter, all letters → id: AaYcD (1 token)
Total tokens (excluding ws) = 1+1+1+1+1+2+1+2+2+1 = 13.

The correct answer is Option C - 0.
The Jaccard coefficient between two sets A and B is defined as |A ∩ B| / |A ∪ B|. To find the lowest possible value, we need to minimise the number of shared edges between any two spanning trees of K_n.
Key properties: Every spanning tree of K_n has exactly n−1 edges. K_n has n(n−1)/2 total edges.
Can two spanning trees share zero edges? Yes - by the Nash-Williams theorem, a graph G contains k edge-disjoint spanning trees if and only if for every partition of vertices into r parts, the number of edges crossing between parts is at least k(r−1). For K_n with n > 4, ⌊n/2⌋ ≥ 2, guaranteeing the existence of at least two fully edge-disjoint spanning trees.
When T₁ and T₂ are edge-disjoint: |T₁ ∩ T₂| = 0, so Jaccard = 0 / |T₁ ∪ T₂| = 0.
Why the other options are wrong:
Option A (1/n): This would require exactly 1 shared edge and union of size n - not the minimum achievable. Incorrect.
Option B (1/(2n−3)): This would correspond to 1 shared edge out of 2n−3 total - again not the minimum. Incorrect.
Option D (1/(n−1)): This would mean 1 shared edge out of n−1 total - still positive, and not the minimum. Incorrect.
Since two fully edge-disjoint spanning trees always exist in K_n for n > 4, the lowest possible Jaccard coefficient is 0.