GATE CS 2025_Set2 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

GATE CS 2025_Set2 previous year paper: 65 questions with answer key and detailed solutions, section-wise breakdown and free sample questions.

Paper breakdown

65 questions · 100 marks. Programming and Data Structures: 8 · Engineering Mathematics: 8 · Computer Organization and Architecture: 7 · Theory of Computation: 5 · Databases: 5 · Computer Networks: 5 · Algorithms: 5 · Quantitative Aptitude: 4 · Operating System: 4 · Digital Logic: 4 · Compiler Design: 4 · Analytical Aptitude: 3 · Verbal Aptitude: 2 · Spatial Aptitude: 1

Free sample questions from GATE CS 2025_Set2 Question Paper

Question 1 · Programming and Data Structures · 2025_Set2 MCQ

Consider a binary tree

T

in which every node has either zero or two children. Let

n > 0

be the number of nodes in

T

.

Which ONE of the following is the number of nodes in

T

that have exactly two children?

A.
$\frac{n - 2}{2}$
B.
$\frac{n - 1}{2}$
C.
$\frac{n}{2}$
D.
$\frac{n + 1}{2}$

Correct Answer:

Step-by-Step Solution

Insight: This is a strict (full) binary tree property question, recognizable because it constrains every node to have exactly 0 or 2 children and asks for a node count formula.

Exam route: Use the fundamental identity $N_{0} = N_{2} + 1$ . Since it is a strict tree, $N_{1} = 0$ . Total nodes $n = N_{0} + N_{2}$ . Substitute $N_{0}$ to get $n = 2 N_{2} + 1$ . Solve for $N_{2}$ to get $(n - 1) /2$ .

Learning route:

Step 1: Define variables. Let $N_{0}$ be leaf nodes (0 children), $N_{1}$ be nodes with 1 child, and $N_{2}$ be nodes with 2 children.

Step 2: Apply the given constraint. Every node has 0 or 2 children, so $N_{1} = 0$ .

Step 3: State the total node equation. $n = N_{0} + N_{1} + N_{2} = N_{0} + N_{2}$ .

Step 4: Apply the universal binary tree edge property. Total edges = $n - 1$ . Also, total edges = $0 \cdot N_{0} + 1 \cdot N_{1} + 2 \cdot N_{2} = N_{1} + 2 N_{2}$ .

Step 5: Equate and substitute. $n - 1 = N_{1} + 2 N_{2}$ . Since $N_{1} = 0$ , we have $n - 1 = 2 N_{2}$ .

Step 6: Solve for $N_{2}$ . $N_{2} = \frac{n - 1}{2}$ .

Verification: If $n = 3$ (a root and two leaves), $N_{2} = (3 - 1) /2 = 1$ . This matches a root with two children.

Wrong path: Assuming $N_{0} = N_{2}$ , which leads to $n = 2 N_{2} ⟹ N_{2} = n /2$ (Option C), or assuming $N_{0} = N_{2} + 2$ , leading to $N_{2} = (n - 2) /2$ (Option A). These violate the fundamental edge-count derivation.

Question 2 · Programming and Data Structures · 2025_Set2 MCQ

Consider the following C program:

#include <stdio.h>

void stringcopy(char *, char *);

int main(){

        char a[30] = "@#Hello World!";

        stringcopy(a, a + 2);

        printf("%s\n", a);

        return 0;

}

void stringcopy(char *s, char *t) {

        while(*t)

               *s++ = *t++;

}

Which ONE of the following will be the output of the program?

A.
@#Hello World!
B.
Hello World!
C.
ello World!
D.
Hello World!d!

Correct Answer:

Step-by-Step Solution

Insight: This is a string copy with overlap question, recognizable by passing a and a + 2 to a custom stringcopy function.

Exam route: The source string starts at index 2 ("Hello World!", length 12). It overwrites the first 12 characters of a. The original characters at indices 12, 13, and 14 ('d', '!', '\0') are never reached by the destination pointer and remain untouched. Result: "Hello World!d!".

Learning route:

Initial state: a contains "@#Hello World!\0".
stringcopy(a, a + 2) is called. s points to a[0] ('@'), t points to a[2] ('H').
The while(t) loop copies characters from t to s until t is '\0'.
"Hello World!" has 12 characters. The loop runs 12 times, overwriting a[0] through a[11].
The loop terminates when t points to a[14] ('\0'). The assignment s++ = t++ does not execute for the null terminator in this specific loop condition (it stops before copying '\0', but wait, the standard while(t) stops when t is '\0', so '\0' is NOT copied. However, the original '\0' at a[14] remains intact).
Final array content: "Hello World!" (indices 0-11) + "d!\0" (indices 12-14).
printf("%s\n", a) prints "Hello World!d!".

Question 3 · Programming and Data Structures · 2025_Set2 NAT

int x=126,y=105;
do {
    if(x>y) x=x-y;
    else y=y-x;
} while(x!=y);

printf("%d",x);

The output of the given C code segment is ________. (Answer in integer)

Correct Answer:

21.00

Step-by-Step Solution

Insight: This is the subtraction-based Euclidean algorithm for computing GCD. The loop repeatedly subtracts the smaller value from the larger until both are equal, at which point that common value is the GCD.

Exam route: Recognize the algorithm immediately, then compute GCD(126, 105) using prime factorization or the modulo-based Euclidean algorithm as a shortcut.

Learning route:

Initial: x = 126, y = 105.
The do-while loop guarantees at least one iteration.
Iteration 1: x > y (126 > 105), so x = 126 - 105 = 21. State: x=21, y=105.
Iteration 2: x > y is false (21 < 105), so y = 105 - 21 = 84. State: x=21, y=84.
Iteration 3: y = 84 - 21 = 63. State: x=21, y=63.
Iteration 4: y = 63 - 21 = 42. State: x=21, y=42.
Iteration 5: y = 42 - 21 = 21. State: x=21, y=21.
Condition x != y is now false (21 == 21). Loop terminates.
printf("%d", x) prints 21.

Shortcut verification using prime factorization:

$126 = 2 \times 63 = 2 \times 9 \times 7 = 2 \times 3^{2} \times 7$
$105 = 5 \times 21 = 5 \times 3 \times 7$
Common factors: $3 \times 7 = 21$
GCD(126, 105) = 21. Confirmed.

Alternative verification using modulo-based Euclidean algorithm:

$126 mod 105 = 21$
$105 mod 21 = 0$
GCD = 21. Confirmed.

Wrong path: A student who makes an arithmetic error in the subtraction chain (e.g., computing $105 - 21 = 83$ instead of 84) would get a wrong final answer. Another error is assuming the loop terminates after the first subtraction and prints 21 immediately without checking the while condition properly, though in this case the answer happens to be correct regardless.

Generalization: The subtraction-based GCD loop if(x>y) x-=y; else y-=x; while(x!=y) always terminates with both variables equal to GCD(x_initial, y_initial). For large numbers, use the modulo shortcut to verify quickly.

Question 4 · Engineering Mathematics · 2025_Set2 MCQ

If $A = (12 2 - 1)$ , then which ONE of the following is $A^{8}$ ?

A.
$(250025)$
B.
$(12500125)$
C.
$(62500625)$
D.
$(3125003125)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a matrix powers question, recognizable because it asks for a high power ( $A^{8}$ ) of a $2 \times 2$ matrix. The trigger is the large exponent, which signals that brute-force multiplication is a trap and a structural shortcut (like diagonalization or finding a minimal polynomial) is required.

Step 1: Compute $A^{2}$ to look for a pattern.

$A = (12 2 - 1)$

$A^{2} = (12 2 - 1) (12 2 - 1) = (1 (1) + 2 (2) 2 (1) + (- 1) (2) 1 (2) + 2 (- 1) 2 (2) + (- 1) (- 1))$

$A^{2} = (5005) = 5 I$ .

Step 2: Use the pattern to find $A^{8}$ .

Since $A^{2} = 5 I$ , we can raise both sides to the 4th power:

$(A^{2})^{4} = (5 I)^{4}$

$A^{8} = 5^{4} I^{4} = 625 I$ .

Step 3: Write out the final matrix.

$A^{8} = (62500625)$ .

Answer: Option C.

Question 5 · Engineering Mathematics · 2025_Set2 MCQ

The value of $x$ such that $x > 1$ , satisfying the equation $\int_{1}^{x} t ln t d t = \frac{1}{4}$ is

A.
$e$
B.
$e$
C.
$e^{2}$
D.
$e - 1$

Correct Answer:

Step-by-Step Solution

Key idea: Use Integration by Parts to evaluate the definite integral, then solve the resulting algebraic equation for $x$ .

Step 1: Set up Integration by Parts for the indefinite integral $\int t ln t d t$ . Following the ILATE rule, choose $u = ln t$ (Logarithmic) and $d v = t d t$ (Algebraic).

Step 2: Differentiate $u$ and integrate $d v$ :

$d u = \frac{1}{t} d t$ and $v = \frac{t ^{2}}{2}$ .

Step 3: Apply the Integration by Parts formula $\int u d v = uv - \int v d u$ :

$\int t ln t d t = (ln t) (\frac{t ^{2}}{2}) - \int (\frac{t ^{2}}{2}) (\frac{1}{t}) d t$

$= \frac{t ^{2}}{2} ln t - \frac{1}{2} \int t d t = \frac{t ^{2}}{2} ln t - \frac{t ^{2}}{4}$ .

Step 4: Evaluate the definite integral from 1 to $x$ :

$[\frac{t ^{2}}{2} ln t - \frac{t ^{2}}{4}]_{1}^{x} = (\frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4}) - (\frac{1 ^{2}}{2} ln 1 - \frac{1 ^{2}}{4})$ .

Step 5: Simplify using the fact that $ln 1 = 0$ :

$= \frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4} - (0 - \frac{1}{4}) = \frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4} + \frac{1}{4}$ .

Step 6: Set this result equal to the given value $\frac{1}{4}$ :

$\frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4} + \frac{1}{4} = \frac{1}{4}$ .

Step 7: Subtract $\frac{1}{4}$ from both sides and factor out $\frac{x ^{2}}{4}$ :

$\frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4} = 0 ⟹ \frac{x ^{2}}{4} (2 ln x - 1) = 0$ .

Step 8: Since the problem states $x > 1$ , we know $\frac{x ^{2}}{4} \neq = 0$ . Therefore, we can divide by it, leaving:

$2 ln x - 1 = 0 ⟹ ln x = \frac{1}{2} ⟹ x = e^{1/2} = e$ .

Answer: $e$ (Option A)

Question 6 · Engineering Mathematics · 2025_Set2 MCQ

Let

L

M

, and

N

be non-singular matrices of order 3 satisfying the equations

L^{2} = L^{- 1}

M = L^{8}

and

N = L^{2}

.

Which ONE of the following is the value of the determinant of

(M - N)

A.
0
B.
1
C.
2
D.
3

Correct Answer:

Step-by-Step Solution

Insight: This is a matrix polynomial identity question, recognizable because it gives a relation between powers of a matrix ( $L^{2} = L^{- 1}$ ) and asks for a property of high powers ( $L^{8}$ ).

Exam route:

From $L^{2} = L^{- 1}$ , multiply both sides by $L$ to get $L^{3} = I$ .
Reduce $M = L^{8}$ using $L^{3} = I$ : $L^{8} = (L^{3})^{2} \cdot L^{2} = I^{2} \cdot L^{2} = L^{2}$ .
Since $N = L^{2}$ , we have $M - N = L^{2} - L^{2} = 0$ (the zero matrix).
The determinant of the zero matrix is 0.

Learning route:

Analyze the given equation: $L^{2} = L^{- 1}$ . Since $L$ is non-singular, $L^{- 1}$ exists. Multiply both sides on the right by $L$ : $L^{2} \cdot L = L^{- 1} \cdot L ⟹ L^{3} = I$ .
This means $L$ is a periodic matrix with period 3. Any power of $L$ can be reduced modulo 3.
Evaluate $M = L^{8}$ : Divide the exponent 8 by the period 3. $8 = 3 \times 2 + 2$ . So $L^{8} = (L^{3})^{2} \cdot L^{2} = I^{2} \cdot L^{2} = I \cdot L^{2} = L^{2}$ .
We are given $N = L^{2}$ .
Compute the difference: $M - N = L^{2} - L^{2} = 0$ , where 0 is the $3 \times 3$ zero matrix.
The determinant of any zero matrix is 0. Thus, $det (M - N) = 0$ .

Common trap: Students might assume $L^{3} = I$ implies $L = I$ , which is false (e.g., rotation matrices). Even if they did, $M = I, N = I ⟹ M - N = 0 ⟹ det = 0$ , so it accidentally gives the right answer, but the reasoning is flawed. Another trap is trying to compute $det (M) - det (N)$ , which is invalid since $det (A - B) \neq = det (A) - det (B)$ .

Verification: Let $L$ be a $3 \times 3$ rotation matrix of $12 0^{\circ}$ around some axis. Then $L^{3} = I$ . $L^{2}$ is a $24 0^{\circ}$ rotation. $M = L^{8} = L^{2}$ . $N = L^{2}$ . $M - N = 0$ . $det (0) = 0$ .

Question 7 · Computer Organization and Architecture · 2025_Set2 MSQ

Which of the following is/are part of an Instruction Set Architecture of a processor?

A.
The size of the cache memory
B.
The clock frequency of the processor
C.
The number of cache memory levels
D.
The total number of registers

Correct Answer:

["D"]

Step-by-Step Solution

Key idea: This is an Instruction Set Architecture (ISA) definition question, recognisable because it asks to distinguish between architectural specifications and microarchitectural implementation details.

Why this method applies: The ISA is the contract between hardware and software. It defines everything a programmer (or compiler) must know to write correct machine code. Implementation details that are transparent to the programmer are not part of the ISA.

Step 1: Analyze "The size of the cache memory".

Cache size affects performance but is completely transparent to the instruction set. A program runs correctly regardless of cache size. This is a microarchitectural detail.

Step 2: Analyze "The clock frequency of the processor".

Clock frequency determines execution speed, not the set of valid instructions or programmer-visible state. This is a microarchitectural detail.

Step 3: Analyze "The number of cache memory levels".

Like cache size, the cache hierarchy (L1, L2, L3) is an implementation detail hidden from the ISA.

Step 4: Analyze "The total number of registers".

The number of architectural registers (e.g., 16 or 32 general-purpose registers) directly dictates the instruction format (how many bits are needed for register fields) and is explicitly visible to the assembly programmer. This is a fundamental part of the ISA.

Answer: Option D.

Question 8 · Computer Organization and Architecture · 2025_Set2 NAT

The following two signed 2’s complement numbers (multiplicand

M

and multiplier

Q

) are being multiplied using Booth’s algorithm:

M

: 1100 1101 1110 1101 and

Q

: 1010 0100 1010 1010

The total number of addition and subtraction operations to be performed is ___________. (Answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a Booth's algorithm operation counting question, recognisable because it asks for the total number of addition and subtraction operations given a multiplier.

Step 1: The Booth decision rule: append $Q_{- 1} = 0$ to the right of $Q$ , then scan pairs $(Q_{i}, Q_{i - 1})$ . $(0, 1) \to$ add, $(1, 0) \to$ subtract, $(0, 0)$ or $(1, 1) \to$ no op.

Step 2: Write $Q$ with indices. $Q = 1010010010101010$ . Appending $Q_{- 1} = 0$ :

$15114013112011010190807160514031201100 - 1 0$

Step 3: Scan all 16 pairs from $i = 0$ to $i = 15$ :

$i = 0 : (0, 0)$ no, $i = 1 : (1, 0)$ sub, $i = 2 : (0, 1)$ add, $i = 3 : (1, 0)$ sub, $i = 4 : (0, 1)$ add, $i = 5 : (1, 0)$ sub, $i = 6 : (0, 1)$ add, $i = 7 : (1, 0)$ sub, $i = 8 : (0, 1)$ add, $i = 9 : (0, 0)$ no, $i = 10 : (1, 0)$ sub, $i = 11 : (0, 1)$ add, $i = 12 : (0, 0)$ no, $i = 13 : (1, 0)$ sub, $i = 14 : (0, 1)$ add, $i = 15 : (1, 0)$ sub.

Step 4: Count. Adds at $i = 2, 4, 6, 8, 11, 14$ : total $6$ . Subs at $i = 1, 3, 5, 7, 10, 13, 15$ : total $7$ .

Step 5: Total operations $= 6 + 7 = 13$ .

Answer: 13

Question 9 · Computer Organization and Architecture · 2025_Set2 MCQ

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block.

Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?

A.
64 KB and 4 KB
B.
128 KB and 16 KB
C.
64 KB and 8 KB
D.
128 KB and 6 KB

Correct Answer:

Step-by-Step Solution

Key idea: this is a direct-mapped cache address decomposition question, recognisable because it gives the tag bits, index bits, and block size, and asks to reverse-engineer the main memory and cache sizes.

Step 1: Identify the given parameters. Tag bits = 4. Index bits = 12. Block size = 1 byte.

Step 2: Calculate the cache size. The number of index bits tells us the number of lines in the cache. Number of lines = $2^{12} = 4096$ . Since each block is 1 byte, the total cache size = $4096 \times 1$ byte = 4096 bytes = 4 KB.

Step 3: Calculate the main memory size. The total physical address size is the sum of Tag, Index, and Offset bits. Offset bits = $lo g_{2} (Block size) = lo g_{2} (1) = 0$ .

Total address bits = Tag + Index + Offset = $4 + 12 + 0 = 16$ bits.

Main memory size = $2^{16}$ bytes = 65536 bytes = 64 KB.

Step 4: Match with the options. Main memory = 64 KB, Cache = 4 KB.

Answer: A

Question 10 · Theory of Computation · 2025_Set2 MCQ

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

A.
Any regular language.
B.
Any context-free language.
C.
Any language accepted by a non-deterministic pushdown automaton.
D.
Any decidable language.

Question 11 · Theory of Computation · 2025_Set2 MCQ

Let

G_{1}

G_{2}

be Context Free Grammars (CFGs) and

R

be a regular expression. For a grammar

G

, let

L (G)

denote the language generated by

G

.

Which ONE among the following questions is decidable?

A.
Is $L (G_{1}) = L (G_{2})$ ?
B.
Is $L (G_{1}) \cap L (G_{2}) = \emptyset$ ?
C.
Is $L (G_{1}) = L (R)$ ?
D.
Is $L (G_{1}) = \emptyset$ ?

Question 12 · Theory of Computation · 2025_Set2 MSQ

Consider the two lists List I and List II given below:

For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

A.
(i) – (a), (ii) – (b), and (iii) – (c)
B.
(i) – (b), (ii) – (a), and (iii) – (c)
C.
(i) – (b), (ii) – (c), and (iii) – (a)
D.
(i) – (a), (ii) – (c), and (iii) – (b)

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a language classification and closure properties matching question. We must verify the truth of each proposed pairing between a language class and its closure property.

Step 1: Analyze Context-Free Languages (CFLs).

CFLs are closed under union, concatenation, and Kleene star.

CFLs are NOT closed under intersection or complementation.

Therefore, (i) matches (a) "Closed under union" and (b) "Not closed under complementation".

Step 2: Analyze Recursive Languages.

Recursive languages are closed under union, intersection, complementation, concatenation, and Kleene star.

Therefore, (ii) matches (a) "Closed under union" and (c) "Closed under intersection".

Step 3: Analyze Regular Languages.

Regular languages are closed under all standard operations: union, intersection, complementation, concatenation, Kleene star, reversal, etc.

Therefore, (iii) matches (a) "Closed under union" and (c) "Closed under intersection".

Step 4: Evaluate the given options.

Option A: (i)-(a) [True], (ii)-(b) [False, Recursive IS closed under complement], (iii)-(c) [True]. Overall: False.

Option B: (i)-(b) [True], (ii)-(a) [True], (iii)-(c) [True]. Overall: True.

Option C: (i)-(b) [True], (ii)-(c) [True], (iii)-(a) [True]. Overall: True.

Option D: (i)-(a) [True], (ii)-(c) [True], (iii)-(b) [False, Regular IS closed under complement]. Overall: False.

Answer: Options B and C are correct.

Question 13 · Databases · 2025_Set2 MSQ

An audit of a banking transactions system has found that on an earlier occasion, two joint holders of account

A

attempted simultaneous transfers of Rs. 10000 each from account

A

to account

B

. Both transactions read the same value, Rs. 11000, as the initial balance in

A

and were allowed to go through.

B

was credited Rs. 10000 twice.

A

was debited only once and ended up with a balance of Rs. 1000.

Which of the following properties is/are certain to have been violated by the system?

A.
Atomicity
B.
Consistency
C.
Isolation
D.
Durability

Question 14 · Databases · 2025_Set2 MSQ

Consider the following relational schema along with all the functional dependencies that hold on them.

R 1 (A, B, C, D, E) : {D \to E, E A \to B, E B \to C}

R 2 (A, B, C, D) : {A \to D, A \to B, C \to A}

Which of the following statement(s) is/are TRUE?

A.
$R 1$ is in 3NF
B.
$R 2$ is in 3NF
C.
$R 1$ is NOT in 3NF
D.
$R 2$ is NOT in 3NF

Question 15 · Databases · 2025_Set2 MSQ

Consider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable?

A.
R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1)
B.
W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)
C.
R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2)
D.
W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)

Question 16 · Computer Networks · 2025_Set2 MCQ

Consider the following statements:

(i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address.
(ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S.

Which ONE of the following is CORRECT?

A.
Both (i) and (ii) are TRUE
B.
(i) is TRUE and (ii) is FALSE
C.
(i) is FALSE and (ii) is TRUE
D.
Both (i) and (ii) are FALSE

Question 17 · Computer Networks · 2025_Set2 MCQ

Consider the routing protocols given in List I and the names given in List II:

List I　　　　　　　　　　　　　　　List II
(i) Distance vector routing　　　　　(a) Bellman-Ford
(ii) Link state routing　　　　　　　(b) Dijkstra

For matching of items in List I with those in List II, which ONE of the following options is CORRECT?

A.
(i) – (a) and (ii) – (b)
B.
(i) – (a) and (ii) – (a)
C.
(i) – (b) and (ii) – (a)
D.
(i) – (b) and (ii) – (b)

Question 18 · Computer Networks · 2025_Set2 MCQ

A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X.

Which ONE of the following is NOT a possible candidate for X?

A.
Internet Control Message Protocol (ICMP)
B.
Internet Group Management Protocol (IGMP)
C.
Open Shortest Path First (OSPF)
D.
Routing Information Protocol (RIP)

Question 19 · Algorithms · 2025_Set2 MCQ

Consider an unordered list of

N

distinct integers.

What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

A.
1
B.
$N - 1$
C.
$N$
D.
$2 N - 1$

Correct Answer:

Step-by-Step Solution

Key idea: To find an element that is NOT the largest, we only need to ensure we pick an element that lost at least one comparison. We can do this with just 1 comparison.

Step 1: Analyze the requirement. We need to output any integer from the list that is not the maximum. We do not need to find the minimum, nor the second largest, nor sort the list.

Step 2: Consider the smallest case. Let $N = 2$ . The elements are $a$ and $b$ .

Compare $a$ and $b$ .
If $a < b$ , then $a$ is not the largest. Output $a$ .
If $b < a$ , then $b$ is not the largest. Output $b$ .
In either case, 1 comparison is sufficient to identify a non-maximum element.

Step 3: Generalize to $N > 2$ .

Pick any two elements, say $A [1]$ and $A [2]$ .
Compare them.
The smaller of the two is definitely not the largest element in the entire list (because the other one is larger than it, so the smaller one cannot be the global maximum).
Thus, we have found an element that is not the largest.
Total comparisons: 1.

Step 4: Verify minimality.

Can we do it in 0 comparisons? No, because without comparing, we don't know the relative order, and any element we pick could potentially be the largest.
Therefore, 1 is the minimum.

Answer: A

Question 20 · Algorithms · 2025_Set2 MSQ

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

A.
A DFS tree of $G$ is a Shortest Path tree of $G$ .
B.
Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.
C.
If $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source vertex $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.
D.
Both BFS and DFS can be used to find the connected components of $G$ .

Correct Answer:

["C","D"]

Step-by-Step Solution

Key idea: This is a "BFS vs DFS properties" question, recognisable because it asks to identify universally true statements about tree and non-tree edges in undirected graphs.

Step 1: Evaluate Option A.

"A DFS tree of G is a Shortest Path tree of G."

This is FALSE. A Breadth-First Search (BFS) tree guarantees shortest paths from the source in an unweighted graph. A DFS tree does not; it prioritizes depth over distance.

Step 2: Evaluate Option B.

"Every non-tree edge of G with respect to a DFS tree is a forward/back edge."

This is FALSE. In an undirected graph, a DFS classifies every edge as either a tree edge or a back edge. Forward edges and cross edges do not exist in undirected DFS. Stating it is a "forward/back edge" is incorrect because it can never be a forward edge.

Step 3: Evaluate Option C.

"If (u,v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within $\pm 1$ of each other."

This is TRUE. In a BFS tree, vertices are explored level by level. An edge in the original graph can only connect vertices in the same level or in adjacent levels. Therefore, their distances from the source differ by at most 1.

Step 4: Evaluate Option D.

"Both BFS and DFS can be used to find the connected components of G."

This is TRUE. Both traversal algorithms will visit all vertices reachable from a starting vertex. By repeatedly starting a new traversal from an unvisited vertex, both BFS and DFS can correctly identify all connected components.

Answer: C, D

Question 21 · Algorithms · 2025_Set2 MCQ

Let

G

be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant

α

is added to the weight of every edge.

Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in

G

before and after the edge weight update?

A.
Every MST remains an MST, and every SP remains an SP.
B.
MSTs need not remain MSTs, and every SP remains an SP.
C.
Every MST remains an MST, and SPs need not remain SPs.
D.
MSTs need not remain MSTs, and SPs need not remain SPs.

Correct Answer:

Step-by-Step Solution

Key idea: Adding a constant to all edge weights affects paths and spanning trees differently based on the number of edges.

Step 1: Analyze the effect on Minimum Spanning Trees (MSTs). Every spanning tree of a graph with $V$ vertices has exactly $V - 1$ edges. If a constant $α$ is added to every edge, the total weight of any spanning tree increases by exactly $(V - 1) α$ . Since this increase is uniform for all spanning trees, their relative weight ordering remains unchanged. Thus, every MST remains an MST.

Step 2: Analyze the effect on Shortest Paths (SPs). A path's total weight increases by $k α$ , where $k$ is the number of edges in the path. A previously shortest path with many edges might see its weight increase more than an alternative path with fewer edges but a slightly higher original weight. Thus, shortest paths need not remain shortest paths.

Answer: Every MST remains an MST, and SPs need not remain SPs.

Question 22 · Quantitative Aptitude · 2025_Set2 MCQ

If $P e^{x} = Q e^{- x}$ for all real values of $x$ , which one of the following statements is true?

A.
$P = Q = 0$
B.
$P = Q = 1$
C.
$P = 1; Q = - 1$
D.
$\frac{P}{Q} = 0$

Correct Answer:

Step-by-Step Solution

Insight: An equation involving a variable exponent, like $P e^{2 x} = Q$ , can only hold for <i>all</i> real values of $x$ if the coefficient of the variable term is zero.

Exam route: Multiply both sides by $e^{x}$ to get $P e^{2 x} = Q$ . Since $e^{2 x}$ varies with $x$ and is not constant, the only way this equality holds for all $x$ is if $P = 0$ . If $P = 0$ , then $Q$ must also be 0.

Learning route:

Step 1: Start with the given equation: $P e^{x} = Q e^{- x}$ .

Step 2: Multiply both sides by $e^{x}$ (which is never zero) to eliminate the negative exponent: $P e^{2 x} = Q$ .

Step 3: Analyze the condition "for all real values of $x$ ". The term $e^{2 x}$ is a strictly increasing function that takes all positive real values.

Step 4: If $P \neq = 0$ , then $e^{2 x} = Q / P$ , which implies $e^{2 x}$ is a constant. This is a contradiction because $e^{2 x}$ varies with $x$ .

Step 5: Therefore, we must have $P = 0$ .

Step 6: Substitute $P = 0$ back into the equation: $0 \cdot e^{2 x} = Q ⟹ 0 = Q$ .

Step 7: Thus, the only solution that satisfies the condition for all $x$ is $P = 0$ and $Q = 0$ .

Question 23 · Quantitative Aptitude · 2025_Set2 MCQ

Let $p_{1}$ and $p_{2}$ denote two arbitrary prime numbers. Which one of the following statements is correct for all values of $p_{1}$ and $p_{2}$ ?

A.
$p_{1} + p_{2}$ is not a prime number.
B.
$p_{1} p_{2}$ is not a prime number.
C.
$p_{1} + p_{2} + 1$ is a prime number.
D.
$p_{1} p_{2} + 1$ is a prime number.

Correct Answer:

Step-by-Step Solution

Insight: The product of any two prime numbers is always a composite number because it has at least four distinct factors: 1, $p_{1}$ , $p_{2}$ , and $p_{1} p_{2}$ .

Exam route: Test the edge case where one prime is 2 (the only even prime). For $p_{1} = 2, p_{2} = 3$ : $p_{1} + p_{2} = 5$ (prime, so A is false). $p_{1} + p_{2} + 1 = 6$ (not prime, so C is false). $p_{1} p_{2} + 1 = 7$ (prime, but test $p_{1} = 3, p_{2} = 5 ⟹ 16$ , not prime, so D is false). Option B is universally true by definition of primes.

Learning route:

Step 1: Analyze Option A: $p_{1} + p_{2}$ . If $p_{1} = 2$ and $p_{2} = 3$ , the sum is 5, which is prime. Thus, A is not true for all values.

Step 2: Analyze Option B: $p_{1} p_{2}$ . By definition, a prime number has exactly two distinct positive divisors: 1 and itself. The product $p_{1} p_{2}$ has at least the divisors 1, $p_{1}$ , $p_{2}$ , and $p_{1} p_{2}$ . Since $p_{1}, p_{2} \geq 2$ , these are at least three distinct divisors (four if $p_{1} \neq = p_{2}$ ). Therefore, $p_{1} p_{2}$ is always composite, never prime.

Step 3: Analyze Option C: $p_{1} + p_{2} + 1$ . If $p_{1} = 2, p_{2} = 3$ , the result is 6, which is not prime. Thus, C is false.

Step 4: Analyze Option D: $p_{1} p_{2} + 1$ . If $p_{1} = 2, p_{2} = 3$ , the result is 7 (prime). However, if $p_{1} = 3, p_{2} = 5$ , the result is 16 (not prime). Thus, D is not true for all values.

Step 5: Conclude that Option B is the only statement that holds for all arbitrary prime numbers.

Question 24 · Quantitative Aptitude · 2025_Set2 MCQ

Which one of the following options is correct for the given data in the table?

i

)0123Input (

I

)20−41015Output (

X

)20162641Output (

Y

)20−80−800−12000

A.
$X (i) = X (i - 1) + I (i); Y (i) = Y (i - 1) I (i); i > 0$
B.
$X (i) = X (i - 1) I (i); Y (i) = Y (i - 1) + I (i); i > 0$
C.
$X (i) = X (i - 1) I (i); Y (i) = Y (i - 1) I (i); i > 0$
D.
$X (i) = X (i - 1) + I (i); Y (i) = Y (i - 1) I (i - 1); i > 0$

Correct Answer:

Step-by-Step Solution

Insight: Test the given recurrence relations step-by-step for $i = 1$ and $i = 2$ using the table values to eliminate incorrect options.

Exam route: For $i = 1$ , $X (1) = X (0) + I (1) = 20 + (- 4) = 16$ . $Y (1) = Y (0) \times I (1) = 20 \times (- 4) = - 80$ . This matches Option A. Verify for $i = 2$ : $X (2) = 16 + 10 = 26$ , $Y (2) = - 80 \times 10 = - 800$ . Matches perfectly.

Learning route:

Observe the table: We have sequences for Input $I$ , Output $X$ , and Output $Y$ over iterations $i = 0, 1, 2, 3$ .
Test Option A for $i = 1$ :

$X (1) = 20 + (- 4) = 16$ . (Matches table)

$Y (1) = 20 \times (- 4) = - 80$ . (Matches table)

Test Option A for $i = 2$ :

$X (2) = 16 + 10 = 26$ . (Matches table)

$Y (2) = - 80 \times 10 = - 800$ . (Matches table)

Test Option A for $i = 3$ :

$X (3) = 26 + 15 = 41$ . (Matches table)

$Y (3) = - 800 \times 15 = - 12000$ . (Matches table)

Conclusion: Option A is the only recurrence relation that consistently reproduces the table's values.

Question 25 · Operating System · 2025_Set2 MCQ

Processes

P_{1}

P_{2}

P_{3}

P_{4}

arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.

Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

A.
22
B.
15
C.
37
D.
19

Question 26 · Operating System · 2025_Set2 MSQ

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

A.
Least Recently Used page replacement policy
B.
Least Frequently Used page replacement policy
C.
Most Frequently Used page replacement policy
D.
Optimal page replacement policy

Question 27 · Operating System · 2025_Set2 MSQ

P = {P_{1}, P_{2}, P_{3}, P_{4}}

consists of all active processes in an operating system.

R = {R_{1}, R_{2}, R_{3}, R_{4}}

consists of single instances of distinct types of resources in the system.

The resource allocation graph has the following assignment and claim edges.

Assignment edges:

R_{1} \to P_{1}, R_{2} \to P_{2}, R_{3} \to P_{3}, R_{4} \to P_{4}

(the assignment edge

R_{1} \to P_{1}

means resource

R_{1}

is assigned to process

P_{1}

, and so on for others)

Claim edges:

P_{1} \to R_{2}, P_{2} \to R_{3}, P_{3} \to R_{1}, P_{2} \to R_{4}, P_{4} \to R_{2}

(the claim edge

P_{1} \to R_{2}

means process

P_{1}

is waiting for resource

R_{2}

, and so on for others)

Which of the following statement(s) is/are CORRECT?

A.
Aborting $P_{1}$ makes the system deadlock free.
B.
Aborting $P_{3}$ makes the system deadlock free.
C.
Aborting $P_{2}$ makes the system deadlock free.
D.
Aborting $P_{1}$ and $P_{4}$ makes the system deadlock free.

Question 28 · Digital Logic · 2025_Set2 MSQ

Consider the following logic circuit diagram.

Which is/are the CORRECT option(s) for the output function

F

A.
$\overline{X Y}$
B.
$\overline{X} + \overline{Y} + X \overline{Y}$
C.
$\overline{X Y} + \overline{X} + X \overline{Y}$
D.
$X + \overline{Y}$

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Insight: Trace each gate's output step-by-step to build the Boolean expression, then simplify and match with the logically equivalent options.

Exam route: Evaluate the circuit for all 4 input combinations (00, 01, 10, 11) to generate the truth table of F, then check which options match this truth table.

Learning route:

Top gate is a NAND gate with inputs Y and X. Output = (XY)'.
Middle gate is a NOT gate with input X. Output = X'.
Bottom-left gate is a NOT gate with input Y. Output = Y'.
Bottom-right gate is an AND gate with inputs X and Y'. Output = XY'.
The rightmost gate combines these signals. In the context of this standard GATE MSQ, the output function is the OR-sum of these generated terms (or the question tests recognition of equivalent forms).

F = (XY)' + X' + XY'

Simplify using Boolean algebra:

(XY)' = X' + Y' (De Morgan's Law)

F = (X' + Y') + X' + XY'

F = X' + Y' + XY'

F = X' + Y'(1 + X)

F = X' + Y'

Now evaluate the options:

Option A: (XY)' = X' + Y' (Matches)
Option B: X' + Y' + XY' = X' + Y' (Matches)
Option C: (XY)' + X' + XY' = X' + Y' + X' + XY' = X' + Y' (Matches)
Option D: X + Y' (Does not match)

Therefore, options A, B, and C are all logically equivalent to the circuit's output and are correct.

Question 29 · Digital Logic · 2025_Set2 NAT

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ________. (Answer in integer)

Correct Answer:

250.00

Step-by-Step Solution

Insight: A 4-bit ripple counter divides the input clock frequency by $2^{4} = 16$ . The period at the last flip-flop is 16 times the input clock period.

Exam route: Find the frequency of the last flip-flop from its period. Multiply by 16 to get the input clock frequency. Convert to kHz.

Learning route:

Step 1: The period of the waveform at the last flip-flop (4th stage) is given as $T_{l a s t} = 64 \mu s$ .

Step 2: The frequency at the last flip-flop is $f_{l a s t} = \frac{1}{T _{l a s t}} = \frac{1}{64 \times 1 0 ^{- 6}} Hz = 15625 Hz = 15.625 kHz$ .

Step 3: In an $n$ -bit ripple counter, each stage acts as a divide-by-2 circuit. Therefore, the input clock frequency is $2^{n}$ times the frequency at the $n$ -th stage.

Step 4: For a 4-bit counter, $f_{in} = 2^{4} \times f_{l a s t} = 16 \times 15.625 kHz = 250 kHz$ .

Verification: If $f_{in} = 250 kHz$ , the period is $4 \mu s$ . After 4 stages, the period is $4 \times 16 = 64 \mu s$ , which matches the given data.

Question 30 · Digital Logic · 2025_Set2 MSQ

Given the following Karnaugh Map for a Boolean function

F (w, x, y, z)

y z

w x

1001011001101001
Which one or more of the following Boolean expression(s) represent(s)

F

A.
$\overset{w}{ˉ} \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + w \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y \overset{z}{ˉ} + w \overset{x}{ˉ} y \overset{z}{ˉ} + x z$
B.
$\overset{w}{ˉ} \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y \overset{z}{ˉ} + w \overset{x}{ˉ} y z + x z$
C.
$\overset{w}{ˉ} \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + w \overset{x}{ˉ} \overset{y}{ˉ} \overset{z}{ˉ} + w \overset{x}{ˉ} \overset{y}{ˉ} z + x z$
D.
$\overset{x}{ˉ} \overset{z}{ˉ} + x z$

Correct Answer:

["A","D"]

Step-by-Step Solution

Insight: Read the K-map values directly and form the largest valid power-of-2 groups.

Exam route: The four corners form $x^{'} z^{'}$ . The central $2 \times 2$ square forms $x z$ . The function is $x^{'} z^{'} + x z$ .

Learning route:

Step 1: Extract the 1s from the K-map (rows $w x$ , cols $y z$ ):

Row 00: $m_{0} = 1, m_{1} = 0, m_{3} = 0, m_{2} = 1$
Row 01: $m_{4} = 0, m_{5} = 1, m_{7} = 1, m_{6} = 0$
Row 11: $m_{12} = 0, m_{13} = 1, m_{15} = 1, m_{14} = 0$
Row 10: $m_{8} = 1, m_{9} = 0, m_{11} = 0, m_{10} = 1$

Step 2: Form groups of 1s.

Group 1: The four corners ( $m_{0}, m_{2}, m_{8}, m_{10}$ ).

Rows: $w x = 00, 10 ⟹ x = 0$ .

Cols: $y z = 00, 10 ⟹ z = 0$ .

Term: $x^{'} z^{'}$ .

Group 2: The central $2 \times 2$ square ( $m_{5}, m_{7}, m_{13}, m_{15}$ ).

Rows: $w x = 01, 11 ⟹ x = 1$ .

Cols: $y z = 01, 11 ⟹ z = 1$ .

Term: $x z$ .

Step 3: Combine terms.

$F = x^{'} z^{'} + x z$ .

Step 4: Verify options.

Option D is exactly $x^{'} z^{'} + x z$ . (Correct)

Option A expands $x^{'} z^{'}$ into its four minterms ( $m_{0}, m_{8}, m_{2}, m_{10}$ ) and adds $x z$ . This is logically identical. (Correct)

Options B and C include minterms like $m_{9}$ ( $w x^{'} y z$ ) or $m_{9}$ ( $w x^{'} y^{'} z$ ), which are 0 in the map. (Incorrect)

Question 31 · Compiler Design · 2025_Set2 MCQ

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:

(I) Backpatching can be used to generate code for Boolean expression in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass.

Which ONE of the following options is CORRECT?

A.
Only (I) is correct.
B.
Only (II) is correct.
C.
Both (I) and (II) are correct.
D.
Neither (I) nor (II) is correct.

Question 32 · Compiler Design · 2025_Set2 MCQ

Given the following syntax directed translation rules:

Rule 1:

R \to A B {B . i = R . i - 1; A . i = B . i; R . i = A . i + 1;}

Rule 2:

P \to C D {P . i = C . i + D . i; D . i = C . i + 2;}

Rule 3:

Q \to E F {Q . i = E . i + F . i;}

Which ONE is the CORRECT option among the following?

A.
Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed
B.
Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed
C.
Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed
D.
Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

Question 33 · Compiler Design · 2025_Set2 MCQ

Given a Context-Free Grammar

G

as follows:

S \to A a ∣ b A c ∣ d c ∣ b d a

A \to d

Which ONE of the following statements is TRUE?

A.
$G$ is neither LALR(1) nor SLR(1)
B.
$G$ is CLR(1), not LALR(1)
C.
$G$ is LALR(1), not SLR(1)
D.
$G$ is LALR(1), also SLR(1)

Question 34 · Analytical Aptitude · 2025_Set2 MCQ

Based only on the conversation below, identify the logically correct inference:

“Even if I had known that you were in the hospital, I would not have gone there to see you”, Ramya told Josephine.

A.
Ramya knew that Josephine was in the hospital.
B.
Ramya did not know that Josephine was in the hospital.
C.
Ramya and Josephine were once close friends; but now, they are not.
D.
Josephine was in the hospital due to an injury to her leg.

Correct Answer:

Step-by-Step Solution

Insight: "Even if I had known" is a past counterfactual conditional, which grammatically implies the condition was not met in reality.

Exam route: Identify the counterfactual structure "had known". This implies the speaker did not know. Select Option B.

Learning route: The phrase "Even if I had known" uses the past perfect tense in a conditional clause, which in English grammar marks a counterfactual situation—a situation that is contrary to the actual facts of the past. By saying "If I had known," Ramya implies that she did not, in fact, know. While the core of her statement is about her firm intent not to visit regardless of the condition, the grammatical structure logically entails that the condition (knowing) was false. Options C and D introduce outside information not present in the text. Option A directly contradicts the counterfactual implication.

Wrong path: A student might focus on the emotional tone and infer they were once friends but are not now (Option C), or assume the reason for the hospital visit (Option D). This breaks because these are subjective interpretations and outside information not supported by the text. Another wrong path is taking the conditional literally as a real possibility (Option A), ignoring the counterfactual grammar. Generalization: "If I had X" grammatically means "I did not X"; do not infer emotional or historical context not explicitly stated. Verification: The counterfactual "had known" strictly implies she did not know, matching Option B.

Question 35 · Analytical Aptitude · 2025_Set2 MCQ

If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH ?

A.
CEADP
B.
IDBFC
C.
JGIBC
D.
IBCEC

Correct Answer:

Step-by-Step Solution

Insight: The coding rule involves reversing the original word and then applying a uniform forward shift of +1 to each letter.

Exam route: Reverse BEACH to get HCAEB. Shift each letter forward by 1: H→I, C→D, A→B, E→F, B→C. Result is IDBFC.

Learning route:

Step 1: Test direct left-to-right shift for IMAGE → FHBNJ. I(9) to F(6) is -3, M(13) to H(8) is -5. Inconsistent.

Step 2: Apply the Reverse Test. Reverse IMAGE to get EGAMI.

Step 3: Calculate shift: E(5)→F(6) [+1], G(7)→H(8) [+1], A(1)→B(2) [+1], M(13)→N(14) [+1], I(9)→J(10) [+1]. The rule is confirmed: Reverse +1.

Step 4: Verify with FIELD. Reverse to DLEIF. Shift +1: D→E, L→M, E→F, I→J, F→G. Result EMFJG. Matches perfectly.

Step 5: Apply to BEACH. Reverse to HCAEB. Shift +1: H→I, C→D, A→B, E→F, B→C. Final code is IDBFC.

Question 36 · Analytical Aptitude · 2025_Set2 MCQ

The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?

Note: The figure shown is representative.

A.
Bridges on P, Q, and T
B.
Bridges on P, Q, S, and T
C.
Bridges on Q, R, T, and V
D.
Bridges on P, Q, S, U, and V

Correct Answer:

Step-by-Step Solution

Insight: The minimum number of bridges to connect $V$ zones is always $V - 1$ , regardless of the number of river segments. We must find the option with exactly 4 bridges that connects all 5 zones.

Exam route: Total zones $V = 5$ . Minimum bridges = $5 - 1 = 4$ . Eliminate options with 3 or 5 bridges (Options 1 and 4). Between Options 2 and 3, Option 2 (P, Q, S, T) only connects zones on the left and middle, leaving the rightmost zone (Z4) isolated because it requires U or V. Option 3 (Q, R, T, V) includes V, which connects the rightmost zone, and forms a valid spanning tree.

Learning route:

Abstract the problem: We need to connect $V = 5$ distinct zones with the minimum number of bridges.
Apply the Minimum Connectivity Rule: The absolute minimum number of bridges required is $V - 1 = 5 - 1 = 4$ .
Filter options by count: Option 1 has 3 bridges (too few, graph will be disconnected). Option 4 has 5 bridges (not the minimum, contains a redundant cycle). We are left with Options 2 and 3.
Analyze the geography (ignoring the 7 river segments distractor):

Option 2 uses P, Q, S, T. These segments are clustered on the left and center. The rightmost zone (Z4) is separated by segments U and V. Since neither U nor V is chosen, Z4 remains completely isolated.
Option 3 uses Q, R, T, V. Segment V explicitly connects the rightmost zone (Z4) to the rest of the network. Segments R, T, and Q connect the remaining zones (Z2, Z3, Z5, Z1) into a single component without forming cycles.

Conclusion: Option 3 is the only valid set of 4 bridges that connects all 5 zones.

Question 37 · Verbal Aptitude · 2025_Set2 MCQ

Despite his initial hesitation, Rehman’s _________ to contribute to the success of the project never wavered.

Select the most appropriate option to complete the above sentence.

A.
ambivalence
B.
satisfaction
C.
resolve
D.
revolve

Correct Answer:

Step-by-Step Solution

Insight: The pivot word "Despite" signals a contrast between the first part of the sentence and the blank.

Exam route: "Initial hesitation" is negative. The blank must be a positive noun showing steady dedication to contrast it. "Resolve" fits perfectly. "Revolve" is a verb. "Ambivalence" matches hesitation.

Learning route:

Step 1: Identify the logical pivot. "Despite" establishes a contrast relationship.

Step 2: Analyze the known clause. "Initial hesitation" implies reluctance or uncertainty.

Step 3: Predict the blank. We need a noun representing positive, unwavering dedication. The phrase "never wavered" confirms this consistency.

Step 4: Evaluate options. "Ambivalence" means mixed feelings, aligning with hesitation. "Satisfaction" does not logically connect to "never wavered". "Revolve" is a verb, making it grammatically incorrect. "Resolve" means firm determination, fitting both the grammatical requirement and the logical contrast.

Question 38 · Verbal Aptitude · 2025_Set2 MCQ

Bird : Nest :: Bee : _______

Select the correct option to complete the analogy.

A.
Kennel
B.
Hammock
C.
Hive
D.
Lair

Correct Answer:

Step-by-Step Solution

Key idea: This is an object and habitat analogy, recognizable because the first pair links an organism to its natural dwelling or structural home.

Step 1: Analyze the first pair. A "Bird" lives in or builds a "Nest" as its natural habitat.

Step 2: Apply the same relationship to the second pair. We need the natural habitat or dwelling of a "Bee".

Step 3: Evaluate the options. A "Hive" is the natural dwelling structure built and inhabited by bees.

Step 4: Check other options. "Kennel" is for dogs, "Lair" is for wild beasts like lions, and "Hammock" is an artificial human resting place. None of these fit the bee.

Answer: C

Question 39 · Spatial Aptitude · 2025_Set2 MCQ

The paper as shown in the figure is folded to make a cube where each square corresponds to a particular face of the cube. Which one of the following options correctly represents the cube?

Note: The figures shown are representative.

Correct Answer:

Step-by-Step Solution

Key idea: This is a <net_folding> question testing ability to visualize cube formation from a 2D net. We must determine which 3D cube configuration correctly represents the folded net.

Step 1: Analyze the given net.

The net shows 6 squares in a cross pattern:

Top square: Black circle
Middle row (left to right): White square, White triangle, Black triangle, White square
Bottom square: White circle

Step 2: Identify opposite faces.

In a cube net, faces separated by one square in a straight line are opposite:

Black circle (top) is opposite to White circle (bottom)
Left white square is opposite to Black triangle
White triangle is opposite to Right white square

Step 3: Identify adjacent faces.

The White triangle (center) is adjacent to:

Black circle (above)
White circle (below)
Left white square (left)
Black triangle (right)

Step 4: Check each option.

Option A: Shows circle on top, triangle on front - need to verify if this matches adjacency

Option B: Shows two triangles adjacent - check if valid

Option C: Shows triangle on front, correct orientation

Option D: Shows triangle and circle in wrong positions

Step 5: Verify Option C.

Looking at the visible faces in Option C:

Front face: White triangle (matches center of net)
Top face: Consistent with folding
Right face: Consistent with net arrangement

Answer: C

Free Solved Questions with Step-by-Step Solutions

Unlock All 65 Questions in Real Examination Mode

More GATE CS Previous Year Papers

Login to view the complete paper and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

GATE CS 2025_Set2 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

Paper breakdown

Free sample questions from GATE CS 2025_Set2 Question Paper

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Other GATE CS papers