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

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

Paper breakdown

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

Free sample questions from GATE CS 2026_Set2 Question Paper

Question 1 · Engineering Mathematics · 2026_Set2 MCQ

A day can only be cloudy or sunny. The probability of a day being cloudy is $0.5$ , independent of the condition on other days. What is the probability that in any given four days, there will be three cloudy days and one sunny day?

A.
$\frac{1}{4}$
B.
$\frac{3}{4}$
C.
$\frac{2}{3}$
D.
$\frac{3}{8}$

Correct Answer:

Step-by-Step Solution

Insight: Independent days with two outcomes = binomial with $n = 4, k = 3, p = 0.5$ .

Exam route:

$n = 4$ days, $k = 3$ cloudy, $p = 0.5$ , $q = 0.5$ .

$P (X = 3) = (3 4) (0.5)^{3} (0.5)^{1} = 4 \times (0.5)^{4} = 4 \times \frac{1}{16} = \frac{1}{4}$ .

Learning route:

This is a binomial question: fixed $n$ , binary outcome, independent trials, constant $p$ .

Step 1 — Identify parameters. $n = 4$ , $k = 3$ , $p = 0.5$ .

Step 2 — Apply the binomial PMF.

$P (X = k) = (k n) p^{k} (1 - p)^{n - k}$

Step 3 — Substitute. $(3 4) = 4$ . $(0.5)^{3} \times (0.5)^{1} = (0.5)^{4} = \frac{1}{16}$ .

Step 4 — Multiply. $4 \times \frac{1}{16} = \frac{1}{4}$ .

Wrong path: If you forget the binomial coefficient $(3 4)$ , you get $(0.5)^{4} = \frac{1}{16}$ , which is not among the options — a signal you missed the arrangements.

Verification: The four arrangements are CCCS, CCSC, CSCC, SCCC. Each has probability $(0.5)^{4} = \frac{1}{16}$ . $4 \times \frac{1}{16} = \frac{1}{4}$ .

Question 2 · Engineering Mathematics · 2026_Set2 MCQ

An unbiased six-faced dice whose faces are marked with numbers $1, 2, 3, 4, 5,$ and $6$ is rolled twice in succession and the number on the top face is recorded each time. The probability that the sum of the two recorded numbers is a prime number is ________

A.
$\frac{3}{36}$
B.
$\frac{13}{36}$
C.
$\frac{15}{36}$
D.
$\frac{19}{36}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a Classical Counting Probability problem. We need to count the number of outcomes where the sum of two dice is prime.

Step 1: Determine the Sample Space.

Two dice are rolled. Total outcomes $N = 6 \times 6 = 36$ .

Each outcome is an ordered pair $(d_{1}, d_{2})$ .

Step 2: Identify Possible Sums.

Minimum sum = $1 + 1 = 2$ .

Maximum sum = $6 + 6 = 12$ .

Prime numbers in range $[2, 12]$ are: $2, 3, 5, 7, 11$ .

Step 3: Count Favorable Outcomes for Each Prime Sum.

Sum = 2: $(1, 1)$ $\to$ 1 way.
Sum = 3: $(1, 2), (2, 1)$ $\to$ 2 ways.
Sum = 5: $(1, 4), (2, 3), (3, 2), (4, 1)$ $\to$ 4 ways.
Sum = 7: $(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)$ $\to$ 6 ways.
Sum = 11: $(5, 6), (6, 5)$ $\to$ 2 ways.

Step 4: Sum the Favorable Outcomes.

Total Favorable = $1 + 2 + 4 + 6 + 2 = 15$ .

Step 5: Calculate Probability.

$P (Prime Sum) = \frac{15}{36}$ .

Answer: $\frac{15}{36}$

Question 3 · Engineering Mathematics · 2026_Set2 MCQ

For two different persons

x

and

y

, the predicate

M (x, y)

denotes that x knows y. Consider the following statement.

There is a person who does not know anyone else, but that person is known by everyone else.

Which one of the following expressions represents the above statement?

A.
$(\exists y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
B.
$(\forall y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
C.
$(\exists y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
D.
$(\forall y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$

Correct Answer:

Step-by-Step Solution

Key idea: This is a nested quantifier translation question, recognizable because it describes a specific relational property ("knows") among a domain of people using phrases like "There is a person" and "everyone else".

Step 1: Identify the core components.

"There is a person" $\to \exists y$ . Let this person be $y$ .

"who does not know anyone else" $\to$ For all $x \neq = y$ , $y$ does not know $x$ . This is $\neg M (y, x)$ .

"but that person is known by everyone else" $\to$ For all $x \neq = y$ , $x$ knows $y$ . This is $M (x, y)$ .

Step 2: Combine the conditions for "everyone else".

For any $x$ , if $x \neq = y$ , then both conditions must hold: $M (x, y) \land \neg M (y, x)$ .

This translates to: $\forall x ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$ .

Step 3: Attach the outer quantifier.

"There is a person $y$ " wraps around the above:

$\exists y \forall x ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$ .

Step 4: Match with options.

Option A matches this exactly.

Answer: A

Question 4 · Programming and Data Structures · 2026_Set2 MCQ

The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal.

T	S
I: Inorder	L: left subtree, node, right subtree
II: Preorder	M: node, left subtree, right subtree
III: Postorder	N: left subtree, right subtree, node

Which one of the following is the correct match from T to S ?

A.
I – L, II – M, III – N
B.
I – M, II – L, III – N
C.
I – N, II – M, III – L
D.
I – L, II – N, III – M

Correct Answer:

Step-by-Step Solution

Insight: The names of the traversals (pre, in, post) directly indicate the position of the current node relative to its subtrees.

Exam route: Preorder = Node first (pre). Inorder = Node in the middle (in). Postorder = Node last (post). Match these to the given descriptions: I (Inorder) is L (left, node, right). II (Preorder) is M (node, left, right). III (Postorder) is N (left, right, node). This matches option A.

Learning route:

Depth-first traversals are defined by when the current node is processed relative to its left and right subtrees.
Preorder: The prefix "pre" means the node is visited before its subtrees. Order: Node, Left, Right (M).
Inorder: The prefix "in" means the node is visited in between its left and right subtrees. Order: Left, Node, Right (L).
Postorder: The prefix "post" means the node is visited after both subtrees. Order: Left, Right, Node (N).
Matching these definitions to the given set S yields I-L, II-M, III-N.

Verification: Consider a tree with root A, left B, right C. Preorder visits A, then B, then C (Node, Left, Right). Inorder visits B, then A, then C (Left, Node, Right). Postorder visits B, then C, then A (Left, Right, Node). This perfectly matches M, L, N respectively.

Question 5 · Programming and Data Structures · 2026_Set2 MCQ

In C runtime environment, which one of the following is stored in heap?

A.
A static variable declared inside a function
B.
An array of integers declared inside a function
C.
A dynamically allocated array of integers created using malloc() function call
D.
Return address of a function

Correct Answer:

Step-by-Step Solution

Insight: This is a memory layout classification question, recognizable by asking where specific C constructs reside in the runtime environment.

Exam route: Eliminate options based on standard C memory segments. Static variables go to Data/BSS. Local arrays and return addresses go to Stack. Only malloc targets the Heap.

Learning route:

Static variable inside a function: Stored in the Data segment (or BSS if uninitialized), not the Heap.
Array of integers declared inside a function: This is a local variable, allocated on the Stack.
Dynamically allocated array using malloc(): Explicitly requests memory from the Heap at runtime.
Return address of a function: Pushed onto the Stack as part of the function call frame.

Therefore, only the dynamically allocated array resides in the Heap.

Question 6 · Programming and Data Structures · 2026_Set2 MCQ

Consider the following three ANSI-C programs, P1, P2, and P3.

P1	P2	P3
#include <stdio.h> int a=5; int main(){ int a=7; return(0); }	#include <stdio.h> int main(){ int a=5; int a=7; return(0); }	#include <stdio.h> int main(){ int a=5; float a=7; return(0); }

Which one of the following statements is true?

A.
Only P1 will compile without any error
B.
Only P2 will compile without any error
C.
Only P3 will compile without any error
D.
All three programs P1, P2, and P3 will compile without any error

Correct Answer:

Step-by-Step Solution

Insight: C allows variable shadowing across different scopes but forbids redeclaration within the same scope, regardless of type.

Exam route: Check the scope of each variable declaration. Global vs local is shadowing. Two locals in the same block is redeclaration.

Learning route:

P1: int a=5; is at file scope. int a=7; is inside main (block scope). The local a shadows the global a. This is perfectly valid C and compiles without error.
P2: int a=5; and int a=7; are both declared inside the exact same block scope (main). This is a redeclaration error. The compiler will reject it.
P3: int a=5; and float a=7; are both in the same block scope. Even though the types differ, C does not allow overloading or redeclaration with different types in the same scope. This is a compilation error.
Therefore, only P1 compiles successfully.

Trap: Believing that shadowing causes a compilation error or that different types in the same scope are allowed. Shadowing is strictly cross-scope; redeclaration is strictly intra-scope.

Verification: Compile P1 mentally: global a exists, local a hides it. No conflict. P2: compiler sees two as in main's symbol table -> error. P3: same symbol table, conflicting types -> error.

Question 7 · Computer Organization and Architecture · 2026_Set2 MCQ

Consider the following two statements about interrupt handling mechanisms in a CPU.

S1: In non-vectored interrupt mechanism, it usually takes more time to start the Interrupt Service Routine (ISR) when compared to that in a vectored interrupt mechanism.

S2: In daisy-chain interrupt mechanism, the CPU polls all the input devices individually to determine the source of the interrupt.

Which one of the following options is correct with respect to S1 and S2 ?

A.
Both S1 and S2 are true
B.
Both S1 and S2 are false
C.
S1 is true and S2 is false
D.
S1 is false and S2 is true

Correct Answer:

Step-by-Step Solution

Key idea: This is an interrupt mechanism comparison question, testing the definitions of vectored vs non-vectored interrupts and daisy-chaining.

Step 1: Analyze S1. In a non-vectored interrupt, the hardware does not provide the ISR address. The CPU must execute a software routine (like polling) to identify the interrupt source, which takes more time. In a vectored interrupt, the hardware directly provides the vector address, making it faster. Thus, S1 is True.

Step 2: Analyze S2. In a daisy-chain interrupt mechanism, the interrupt acknowledge signal is passed serially through a chain of devices. The device that requested the interrupt blocks the signal and places its vector address on the bus. The CPU does not individually poll all devices; the hardware chain resolves the priority. Thus, S2 is False.

Step 3: Conclude that S1 is true and S2 is false.

Answer: C

Question 8 · Computer Organization and Architecture · 2026_Set2 MSQ

In a system, numbers are represented using 4-bit two’s complement form. Consider four numbers $N_{1} = 1011$ , $N_{2} = 1101$ , $N_{3} = 1010$ and $N_{4} = 1001$ in the system. Which of the following operations will result in arithmetic overflow?

A.
$N_{1} + N_{2}$
B.
$N_{2} + N_{3}$
C.
$N_{3} - N_{4}$
D.
$N_{1} + N_{4}$

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is a two's complement arithmetic overflow detection problem. Overflow occurs when adding two numbers of the same sign yields a result of the opposite sign, or when the carry into the sign bit differs from the carry out of the sign bit.

Step 1: Decode the 4-bit two's complement values.

Range for 4-bit two's complement is -8 to +7.

N1 = 1011 = -5

N2 = 1101 = -3

N3 = 1010 = -6

N4 = 1001 = -7

Step 2: Evaluate each operation.

N1 + N2 = -5 + (-3) = -8.

Binary: 1011 + 1101 = 11000 -> 1000 (-8).

Result is within range [-8, 7]. No overflow.

N2 + N3 = -3 + (-6) = -9.

Binary: 1101 + 1010 = 10111 -> 0111 (+7).

Result is +7, but true sum is -9. -9 is outside the range. Overflow occurs.

N3 - N4 = -6 - (-7) = +1.

Binary: 1010 + 0111 (2's comp of 1001) = 10001 -> 0001 (+1).

Result is within range. No overflow.

N1 + N4 = -5 + (-7) = -12.

Binary: 1011 + 1001 = 10100 -> 0100 (+4).

Result is +4, but true sum is -12. -12 is outside the range. Overflow occurs.

Answer: N2+N3 and N1+N4

Question 9 · Computer Organization and Architecture · 2026_Set2 NAT

The 32-bit IEEE 754 single precision representation of a number is 0xC2710000. The number in decimal representation is ________. <i>(rounded off to two decimal places)</i>

Correct Answer:

-60.25

Step-by-Step Solution

Key idea: Decode an IEEE 754 single-precision hexadecimal representation into its decimal equivalent by extracting the sign, exponent, and mantissa.

Step 1: Convert the hex value 0xC2710000 to binary.

C = 1100, 2 = 0010, 7 = 0111, 1 = 0001

Binary: 1100 0010 0111 0001 0000 0000 0000 0000

Step 2: Extract the fields.

Sign bit (1 bit): 1 (indicates a negative number).
Exponent field (8 bits): 10000100.
Mantissa field (23 bits): 11100010000000000000000.

Step 3: Decode the exponent.

Biased exponent = 10000100_2 = 132.

Actual exponent = 132 - 127 (bias) = 5.

Step 4: Decode the mantissa.

The implicit leading bit is 1, so the significand is 1.1110001_2.

Step 5: Calculate the decimal value.

Value = -1 × (1.1110001_2) × 2^5

Multiplying by 2^5 shifts the binary point 5 places to the right:

1.1110001_2 × 2^5 = 111100.01_2

Step 6: Convert binary to decimal.

Integer part: 111100_2 = 32 + 16 + 8 + 4 = 60.

Fractional part: .01_2 = 1/4 = 0.25.

Combined value = -60.25.

Question 10 · Computer Networks · 2026_Set2 MCQ

Consider a file of size 4 million bytes being transferred between two hosts connected via a path consisting of three consecutive links of bandwidth 2 Mbps, 500 kbps, and 1 Mbps, respectively. All processing delays and propagation delays are negligible. Assume that there is no other background traffic over the path and no other additional overhead to transfer the file.
Which one of the following is the total time (in seconds) to transfer the file?
Note:

1 M = 1 0^{6}

1 k = 1 0^{3}

A.
731
B.
64
C.
8
D.
16

Question 11 · Computer Networks · 2026_Set2 MCQ

Which one of the following protocols may need to broadcast some of its messages?

A.
SMTP
B.
FTP
C.
DHCP
D.
HTTP

Question 12 · Computer Networks · 2026_Set2 NAT

If an IP network uses a subnet mask of 255.255.240.0, the maximum number of IP addresses that can be assigned to network interfaces is __________. <i>(answer in integer)</i>

Question 13 · Algorithms · 2026_Set2 MCQ

Consider the following functions, where

n

is a positive integer.

n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)}

Which one of the following options lists the functions in increasing order of asymptotic growth rate?

Note: Assume the base of log to be 2.

A.
$lo g (n), n^{1/3}, 2^{l o g (n)}, lo g (n!)$
B.
$n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)}$
C.
$lo g (n), n^{1/3}, lo g (n!), 2^{l o g (n)}$
D.
$2^{l o g (n)}, n^{1/3}, lo g (n), lo g (n!)$

Question 14 · Algorithms · 2026_Set2 MSQ

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $Θ (n)$ ?

A.
$T (n) = T (n - 1) + 1, T (1) = 1$
B.
$T (n) = 2 T (\frac{n}{2}) + 1, T (1) = 1$
C.
$T (n) = 2 T (\frac{n}{2}) + n, T (1) = 1$
D.
$T (n) = T (n - 1) + n, T (1) = 1$

Question 15 · Algorithms · 2026_Set2 NAT

Consider an array

A = [10, 7, 8, 19, 41, 35, 25, 31]

. Suppose the merge sort algorithm is executed on array

A

to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.

A merge operation on sorted left array

L

and sorted right array

R

is said to be void if the output of the merge operation is the elements of array

L

followed by the elements of array

R

.

The number of void merge operations among these 7 merge operations is __________. (answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a merge sort operation counting question, recognisable because it asks for the number of "void" merge operations on a specific array. A void merge occurs when the left subarray's maximum element is less than or equal to the right subarray's minimum element.

Step 1: Trace the merge sort tree for $A = [10, 7, 8, 19, 41, 35, 25, 31]$ .

Step 2: Level 3 (size 1 to 2):

Merge $[10]$ and $[7] \to [7, 10]$ . Not void ( $10 > 7$ ).
Merge $[8]$ and $[19] \to [8, 19]$ . Void ( $8 \leq 19$ ). (Count = 1)
Merge $[41]$ and $[35] \to [35, 41]$ . Not void ( $41 > 35$ ).
Merge $[25]$ and $[31] \to [25, 31]$ . Void ( $25 \leq 31$ ). (Count = 2)

Step 3: Level 2 (size 2 to 4):

Merge $[7, 10]$ and $[8, 19] \to [7, 8, 10, 19]$ . Not void ( $10 > 8$ ).
Merge $[35, 41]$ and $[25, 31] \to [25, 31, 35, 41]$ . Not void ( $41 > 25$ ).

Step 4: Level 1 (size 4 to 8):

Merge $[7, 8, 10, 19]$ and $[25, 31, 35, 41] \to [7, 8, 10, 19, 25, 31, 35, 41]$ . Void ( $19 \leq 25$ ). (Count = 3)

Step 5: Total void merges = 3.

Answer: 3

Question 16 · Operating System · 2026_Set2 MCQ

Which one of the following CPU scheduling algorithms cannot be preemptive?

A.
Shortest Remaining Time First (SRTF) Scheduling
B.
First Come First Serve (FCFS) Scheduling
C.
Round Robin Scheduling
D.
Priority Scheduling

Question 17 · Operating System · 2026_Set2 MSQ

Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0, respectively. X is a shared variable initialized to 0. Each line in the pseudocode is executed atomically.

Pseudocode of P1, P2, and P3

Wait(A);
Print(*);
X = X+1;
If (X == 2)
   {
      Print($);
      Signal(B);
   }
Signal(A);
Wait(B);
Print(#);
Signal(B);

Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order.

Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

A.
**$*###
B.
**$#*##
C.
**$##*#
D.
***$###

Question 18 · Operating System · 2026_Set2 NAT

To keep track of free blocks in a file system, one of the two approaches is generally used – using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single pointer of size 4 bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is ____________. (answer in integer)

Note:

1 K = 2^{10}

and

1 G = 2^{30}

Question 19 · Theory of Computation · 2026_Set2 MCQ

Which one of the following statements is equivalent to the following assertion?

Turing machine M decides the language L \subseteq {0, 1}^{*}

A.
Turing machine $M$ halts on all input strings in ${0, 1}^{*}$
B.
Turing machine $M$ accepts all input strings in $L$
C.
Turing machine $M$ rejects all input strings in ${0, 1}^{*} - L$
D.
Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in ${0, 1}^{*} - L$

Question 20 · Theory of Computation · 2026_Set2 MSQ

Which of the following grammars is/are ambiguous?

A.
$S \to a S b ∣ ϵ$
B.
$E \to E + E ∣ E * E ∣ i d$
C.
$S \to a S ∣ S a ∣ ϵ$
D.
$S \to a S ∣ ϵ$

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a grammar ambiguity identification question. We need to check each grammar to see if any string has multiple distinct derivations.

Step 1: Check Grammar A: S → aSb | ε

This generates {a^n b^n | n ≥ 0}.

For any string a^n b^n, there's only ONE way to derive it:

Must apply S → aSb exactly n times
Then apply S → ε once
Order is forced (always leftmost or always rightmost)

Grammar A is UNAMBIGUOUS.

Step 2: Check Grammar B: E → E+E | E*E | id

This is the classic expression grammar.

For string "id+id*id":

Derivation 1: E ⇒ E+E ⇒ id+E ⇒ id+EE ⇒ id+idE ⇒ id+idid (groups as id + (id id))

Derivation 2: E ⇒ EE ⇒ E+EE ⇒ id+EE ⇒ id+idE ⇒ id+idid (groups as (id + id) id)

Two different parse trees ⇒ Grammar B is AMBIGUOUS.

Step 3: Check Grammar C: S → aS | Sa | ε

For string "aa":

Derivation 1: S ⇒ aS ⇒ aaS ⇒ aa (using S → aS twice, then S → ε)

Derivation 2: S ⇒ Sa ⇒ aSa ⇒ aa (using S → Sa, then S → aS for the first S, then S → ε)

These are two distinct leftmost derivations for "aa".

Grammar C is AMBIGUOUS.

Step 4: Check Grammar D: S → aS | ε

This generates a* (any number of a's).

For string "aaa", there is only one leftmost derivation:

S ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaa

Grammar D is UNAMBIGUOUS.

Answer: Grammars B and C are ambiguous.

Question 21 · Theory of Computation · 2026_Set2 MSQ

Consider the following two finite automata

D_{1}

and

D_{2}

D_{1}

0 1 1 1 1 0 0 1

D_{2}

Which of the following statements is/are true?

A.
$L (D_{1}) = L (D_{2})$
B.
$L (D_{1})$ is a proper subset of $L (D_{2})$
C.
$L (D_{1}) \cap L (D_{2}) = {ϵ}$
D.
$(L (D_{1}) \cup L (D_{2}))^{*}$ consists of all strings in ${0, 1}^{*}$ whose length is divisible by 3

Question 22 · Databases · 2026_Set2 MCQ

In the context of DBMS, consider the two sets T and S given below.

T	S
I: Logical schema	L: Views
II: Physical schema	M: File organization and indexes
III: External schema	N: Relations

Which one of the following is the correct match from T to S ?

A.
I – L, II – M, III – N
B.
I – M, II – L, III – N
C.
I – N, II – M, III – L
D.
I – N, II – L, III – M

Question 23 · Databases · 2026_Set2 MCQ

Consider concurrent execution of two transactions $T_{1}$ and $T_{2}$ in a DBMS, both of which access a data object $A$ . For these two transactions to not conflict on $A$ , which one of the following statements must be true?

A.
Both $T_{1}$ and $T_{2}$ only read $A$
B.
$T_{1}$ reads $A$ and $T_{2}$ writes $A$
C.
$T_{1}$ writes $A$ and $T_{2}$ reads $A$
D.
Both $T_{1}$ and $T_{2}$ write $A$

Question 24 · Databases · 2026_Set2 MCQ

In the context of schema normalization in relational DBMS, consider a set F of functional dependencies. The set of all functional dependencies implied by F is called the closure of F. To compute the closure of F, Armstrong’s Axioms can be applied. Consider

X

Y

, and

Z

as sets of attributes over a relational schema. The three rules of Armstrong’s Axioms are described as follows.

Reflexivity: If

Y \subseteq X

, then

X \to Y

Augmentation: If

X \to Y

, then

X Z \to Y Z

for any Z
Transitivity: If

X \to Y

and

Y \to Z

, then

X \to Z

The additional rule of Union is defined as follows.

Union: If

X \to Y

and

X \to Z

, then

X \to Y Z

It can be proved that the additional rule of Union is also implied by the three rules of Armstrong’s Axioms. Listed below are four combinations of these three rules. Which one of these combinations is both necessary and sufficient for the proof ?

A.
Reflexivity, Augmentation, and Transitivity
B.
Reflexivity and Augmentation
C.
Transitivity
D.
Augmentation and Transitivity

Question 25 · Digital Logic · 2026_Set2 MCQ

Which one of the following options is not a property of Boolean Algebra?

Note:

+

is OR operation,

.

is AND operation, and

^{'}

is NOT operation

A.
$a + b = b + a$
B.
$a . a^{'} = 1$
C.
$a + a^{'} = 1$
D.
$a . b = b . a$

Correct Answer:

Step-by-Step Solution

Insight: Recall the fundamental axioms of Boolean algebra, specifically the complement laws.

Exam route: $a \cdot a^{'} = 0$ , not $1$ . The other options are standard commutative and complement laws.

Learning route:

Let's evaluate each option against the standard axioms of Boolean algebra:

Option A: $a + b = b + a$ . This is the Commutative Law for OR. (Property)

Option B: $a \cdot a^{'} = 1$ . The Complement Law states that a variable ANDed with its complement is always 0, not 1. ( $a \cdot a^{'} = 0$ ). (NOT a property)

Option C: $a + a^{'} = 1$ . This is the correct Complement Law for OR. (Property)

Option D: $a \cdot b = b \cdot a$ . This is the Commutative Law for AND. (Property)

Therefore, Option B is the only one that is not a valid property.

Question 26 · Digital Logic · 2026_Set2 MCQ

Consider the following 4-variable Boolean function

F (A, B, C, D) = Σ m (0, 1, 2, 3, 8, 9, 10, 11)

Consider

A

as MSB,

D

as LSB. Which one of the following options represents the minimal sum of products form for the above function?

Note:

+

is OR operation,

.

is AND operation,

^{'}

is NOT operation

A.
$A^{'} + B^{'} + C^{'} + D^{'}$
B.
$B^{'}$
C.
$A^{'} . B^{'} + A . B$
D.
$A^{'}$

Correct Answer:

Step-by-Step Solution

Insight: The 8 minterms all share $B = 0$ , and the other variables run through all combinations, collapsing the function to a single literal.

Exam route: Scan the binary representations; the constant column gives the minimal SOP.

Learning route:

Minterms: 0(0000), 1(0001), 2(0010), 3(0011), 8(1000), 9(1001), 10(1010), 11(1011).

Column scan:

$A$ : 0 and 1
$B$ : always 0
$C$ : 0 and 1
$D$ : 0 and 1

Since $B$ is always 0 and the other three variables take all $2^{3} = 8$ possible combinations, the function is exactly $\overset{ˉ}{B}$ .

Matches Option B.

Question 27 · Digital Logic · 2026_Set2 NAT

Consider the digital circuit shown below with two input lines A and B, two select lines S0 and S1, and an output line Y. The blocks Q and M represent active high 2:4 decoder and 4-to-1 multiplexer, respectively. Out of 16 possible input combinations, the number of combinations that produce Y=1 is ____________. (answer in integer)

Note: One input combination is an instance of [A B S1 S0].

Correct Answer:

4.00

Step-by-Step Solution

Insight: The decoder generates mutually exclusive minterms of its inputs, and the MUX simply selects one of these minterms based on its own select lines.

Exam route: Write the MUX output equation $Y = \sum S_{i} I_{i}$ . Substitute the decoder outputs $D_{i}$ for $I_{i}$ . Since $D_{i}$ are minterms of A and B, each product term in the sum represents a unique, non-overlapping combination of all 4 variables [A, B, S1, S0]. Count the valid terms.

Learning route:

The 2-to-4 decoder Q has inputs A and B. Its active-high outputs are the minterms of A and B:

$D_{0} = \overline{A} \overline{B}$
$D_{1} = \overline{A} B$
$D_{2} = A \overline{B}$
$D_{3} = A B$

These outputs are connected directly to the data inputs of the 4-to-1 MUX M: $I_{0} = D_{0}, I_{1} = D_{1}, I_{2} = D_{2}, I_{3} = D_{3}$ .
The MUX has select lines $S_{1}$ and $S_{0}$ . Its output equation is:

$Y = \overline{S_{1}} \overline{S_{0}} I_{0} + \overline{S_{1}} S_{0} I_{1} + S_{1} \overline{S_{0}} I_{2} + S_{1} S_{0} I_{3}$

Substitute the decoder outputs into the MUX equation:

$Y = \overline{S_{1}} \overline{S_{0}} \overline{A} \overline{B} + \overline{S_{1}} S_{0} \overline{A} B + S_{1} \overline{S_{0}} A \overline{B} + S_{1} S_{0} A B$

We need to find the number of input combinations [A, B, S1, S0] that make $Y = 1$ .
Analyze each term:

Term 1 is 1 only when $S_{1} = 0, S_{0} = 0, A = 0, B = 0$ . (1 combination: 0000)
Term 2 is 1 only when $S_{1} = 0, S_{0} = 1, A = 0, B = 1$ . (1 combination: 0101)
Term 3 is 1 only when $S_{1} = 1, S_{0} = 0, A = 1, B = 0$ . (1 combination: 1010)
Term 4 is 1 only when $S_{1} = 1, S_{0} = 1, A = 1, B = 1$ . (1 combination: 1111)

Since these four product terms are mutually exclusive (they represent distinct minterms of the 4 variables), there are exactly 4 combinations that produce $Y = 1$ .

Question 28 · Compiler Design · 2026_Set2 NAT

A lexical analyzer uses the following token definitions

•

l e tt er \to [A - Z a - z]

•

d i g i t \to [0 - 9]

•

i d \to l e tt er (l e tt er ∣ d i g i t)^{*}

•

n u mb er \to d i g i t^{+}

•

w s \to (b l ank ∣ t ab ∣ n e w l in e)^{+}

For the string given below,

x 123 mm 78 y 7 z z z 514 A 8 H A aY cD

the number of tokens (excluding

w s

) that will be produced by the lexical analyzer is __________. (answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: Apply the maximal munch rule (longest match) to tokenize the input string based on the given regular expressions.

Step 1: The input string is separated by whitespace. We process each space-separated chunk.

Step 2: x1 starts with a letter and is followed by a digit. Matches id. (1 token)

Step 3: 23mm starts with digits. The longest match for number is 23. The remaining mm matches id. (2 tokens)

Step 4: 78 matches number. (1 token)

Step 5: y matches id. (1 token)

Step 6: 7z starts with a digit. 7 matches number. z matches id. (2 tokens)

Step 7: zz5 starts with a letter, followed by letters/digits. Matches id. (1 token)

Step 8: 14A starts with digits. 14 matches number. A matches id. (2 tokens)

Step 9: 8H starts with a digit. 8 matches number. H matches id. (2 tokens)

Step 10: AaYcD starts with a letter, followed by letters. Matches id. (1 token)

Step 11: Sum the tokens: 1 + 2 + 1 + 1 + 2 + 1 + 2 + 2 + 1 = 13.

Answer: 13

Question 29 · Compiler Design · 2026_Set2 MCQ

Consider the canonical

L R (0)

parsing of the grammar below using terminals

{a, b, c}

and non-terminals

{A, B, C, S}

with

S

as the start symbol.

S \to A C B

A \to a A ∣ ϵ

C \to c C ∣ ϵ

B \to b B ∣ b

Which one of the following options gives the number of shift-reduce conflicts that will occur in the

L R (0)

ACTION table?

A.
2
B.
3
C.
4
D.
5

Question 30 · Compiler Design · 2026_Set2 MCQ

Consider the control flow graph given below.
Which one of the following options is the set of live variables at the exit point of each basic block?

A.
B1:{a, b, c, e, f}, B2:{d, e}, B3:{b, c, e, f}, B4: $\emptyset$
B.
B1: $\emptyset$ , B2:{d, e}, B3:{a, c, f}, B4: $\emptyset$
C.
B1:{a, b, c, e, f}, B2:{d, e}, B3:{c, e, f}, B4: $\emptyset$
D.
B1: $\emptyset$ , B2:{d, e, f}, B3:{a, b, c, e, f}, B4: $\emptyset$

Question 31 · Analytical Aptitude · 2026_Set2 MCQ

‘When it is raining, peacocks dance.’

Based only on this sentence, which one of the following options is necessarily true?

A.
Peacocks dance only when it is raining.
B.
When peacocks dance, it is raining.
C.
When peacocks are not dancing, it is not raining.
D.
When it is not raining, peacocks do not dance.

Correct Answer:

Step-by-Step Solution

Insight: "When P, Q" translates to $P ⟹ Q$ . The contrapositive $\neg Q ⟹ \neg P$ is logically equivalent and must be true.

Exam route: Identify $P$ (raining) and $Q$ (peacocks dance). The contrapositive is "If peacocks are not dancing, it is not raining." Match with Option C.

Learning route:

Translate the statement: "When it is raining ( $P$ ), peacocks dance ( $Q$ )" means $P ⟹ Q$ .
Recall logical equivalences: The contrapositive $\neg Q ⟹ \neg P$ is always true if $P ⟹ Q$ is true.
Form the contrapositive: "When peacocks are not dancing ( $\neg Q$ ), it is not raining ( $\neg P$ )."
Evaluate options:

Option A & B represent the converse ( $Q ⟹ P$ ), which is not necessarily true.
Option D represents the inverse ( $\neg P ⟹ \neg Q$ ), which is not necessarily true.
Option C represents the contrapositive ( $\neg Q ⟹ \neg P$ ), which must be true.

Answer is C.

Question 32 · Analytical Aptitude · 2026_Set2 MCQ

Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways.
A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.

Which one of the following options is then true?

A.
Such a trip is possible for (i), but not for (ii).
B.
Such a trip is possible for (ii), but not for (i).
C.
Such a trip is possible for both (i) and (ii).
D.
Such a trip is possible neither for (i) nor for (ii).

Correct Answer:

Step-by-Step Solution

Insight: A Hamiltonian cycle requires every vertex to have a degree of exactly 2 within the cycle. Graph (ii) has three vertices of degree 2, which forces a contradiction at the central vertex. Graph (i) is a 4x4 grid, which is bipartite with equal partitions, allowing a valid cycle.

Exam route: For (ii), identify vertices with degree 2. Their incident edges must be in the cycle. This forces the central vertex to have degree 3 in the cycle, which is impossible. Thus, (ii) has no Hamiltonian cycle. For (i), a 4x4 grid has a known Hamiltonian cycle (e.g., a snake pattern that closes). Thus, (i) is possible, (ii) is not.

Learning route:

Understand the goal: A trip visiting every city exactly once and returning to the start is a Hamiltonian cycle.
Analyze Graph (ii): It has 5 vertices. The top-left, bottom, and top-right vertices each have exactly 2 connections (degree 2).
Apply the Degree-Two Vertex Rule: In any Hamiltonian cycle, if a vertex has degree 2, both of its edges must be part of the cycle.
Trace the forced edges in (ii): The three degree-2 vertices force 6 edges. However, these edges all converge on the central vertex, giving it a degree of 3 in the supposed cycle. A cycle can only have degree 2 for every vertex. This is a contradiction, so (ii) is impossible.
Analyze Graph (i): It is a 4x4 grid graph. It is bipartite with 8 black and 8 white vertices. Since the partitions are equal, a Hamiltonian cycle is possible. We can explicitly construct one by tracing the perimeter and weaving through the center without repeating vertices.
Conclusion: Possible for (i), not for (ii).

Question 33 · Analytical Aptitude · 2026_Set2 MCQ

The figure in Panel I below is a grid of cells with four rows and four columns. The numbers on the top and on the left represent the number of cells that are to be shaded in that column and row, respectively. Which one of the options shown in Panel II below represents the grid shaded correctly?

A.
(i)
B.
(ii)
C.
(iii)
D.
(iv)

Correct Answer:

Step-by-Step Solution

Insight: Verify total row and column sums first, then use forced moves starting with the most constrained row or column.

Exam route: Row sums = 3 + 1 + 2 + 2 = 8. Column sums = 2 + 2 + 2 + 2 = 8. Consistency check passed. Row 2 requires exactly 1 shaded cell. Inspecting the options: Option (i) has 2 shaded in Row 2 (invalid). Option (iii) has 2 shaded in Row 2 (invalid). Option (ii) has 1 shaded in Row 2. Verify Option (ii) columns: Col 1 has 2, Col 2 has 2, Col 3 has 2, Col 4 has 2. All constraints satisfied. Option (ii) is correct.

Learning route:

Step 1: Consistency Check. Sum of row requirements (3+1+2+2 = 8) must equal sum of column requirements (2+2+2+2 = 8). They match.

Step 2: Identify Extremes. Row 2 requires only 1 shaded cell out of 4. This is the tightest constraint.

Step 3: Option Elimination. Instead of solving the grid from scratch (which is time-consuming), evaluate the given options against the tightest constraint.

Step 4: Check Row 2 in all options. Option (i) shows 2 shaded cells. Option (iii) shows 2 shaded cells. Both are immediately discarded.

Step 5: Verify the survivor. Option (ii) has exactly 1 shaded cell in Row 2. Now verify its columns: Col 1 (Rows 1, 4) = 2. Col 2 (Rows 2, 4) = 2. Col 3 (Rows 1, 3) = 2. Col 4 (Rows 1, 3) = 2. All column sums are exactly 2. Option (ii) is the unique valid configuration.

Question 34 · Verbal Aptitude · 2026_Set2 MCQ

Expedite, Hasten, Hurry, __________

Fill the blank by choosing a word with a meaning similar to that of the words given above.

A.
Accelerate
B.
Retard
C.
Provide
D.
Disable

Correct Answer:

Step-by-Step Solution

Insight: This is a synonym series question testing semantic clustering, not just random vocabulary.

Exam route: "Expedite", "Hasten", and "Hurry" all mean to make something happen faster. We need a fourth word in this cluster. "Accelerate" means to increase speed. "Retard" is the opposite. "Provide" and "Disable" are unrelated.

Learning route:

Step 1: Identify the core shared meaning of the given words. "Expedite", "Hasten", and "Hurry" all share the core meaning of increasing speed or making an action occur sooner.

Step 2: Determine the required relationship. The prompt asks for a word with a "similar" meaning, placing it in the same semantic cluster.

Step 3: Evaluate options against the cluster. "Accelerate" means to gain speed or cause something to happen faster, fitting the cluster perfectly. "Retard" means to delay or slow down (antonym). "Provide" and "Disable" have entirely different meanings.

Step 4: Conclude that "Accelerate" is the only logically consistent choice.

Question 35 · Verbal Aptitude · 2026_Set2 MCQ

Water : P :: Food : Q

Choose the P and Q combination from the options below to form a meaningful analogy.

A.
P = Thirst; Q = Hunger
B.
P = Drink; Q = Hunger
C.
P = Thirst; Q = Satiated
D.
P = Wet; Q = Critic

Correct Answer:

Step-by-Step Solution

Key idea: This is a need-based functional analogy, recognizable because the first word in each pair is an item that satisfies a specific biological or physiological need represented by the second word.

Step 1: Analyze the first pair. Water is a substance consumed to satisfy or quench the physiological need of Thirst.

Step 2: Apply the exact same relationship to the second pair. Food is a substance consumed to satisfy or quench the physiological need of Hunger.

Step 3: Evaluate the options to find the pair that matches this "Item : Need it satisfies" structure. Option A provides P = Thirst and Q = Hunger, which perfectly aligns with the established relationship.

Step 4: Check other options to ensure no better fit. Option B uses "Drink" (an action, not a need). Option C uses "Satiated" (a state of being, not a need). Option D uses unrelated words.

Answer: A

Question 36 · Spatial Aptitude · 2026_Set2 MCQ

A black square PQRS has been cut into two parts. One part of it is shown in Panel I. Which one of the shapes in Panel II is the other part?

A.
(i)
B.
(ii)
C.
(iii)
D.
(iv)

Correct Answer:

Step-by-Step Solution

Key idea: This is a shape assembly problem requiring us to find the complementary piece that perfectly interlocks with the given piece to form a square.

Step 1: Analyze the given piece.

Panel I shows a black square with a white cut-out. The white cut-out represents the exact shape of the missing "other part".

Step 2: Identify the boundary features.

Trace the perimeter of the white cut-out. It has specific protrusions and indentations of defined lengths (e.g., a 35-unit horizontal segment, a 30-unit vertical drop, etc.).

Step 3: Evaluate the options for the inverse shape.

The correct option must have the exact geometric inverse of this boundary. When mentally rotated or flipped, its protrusions must fit perfectly into the given piece's indentations, and vice versa.

Step 4: Verify the outer boundary.

The combined shape must form a perfect square. Option (iii) provides the necessary straight outer edges to complete the square's boundary while perfectly matching the internal cut pattern.

Answer: C

Question 37 · Spatial Aptitude · 2026_Set2 MCQ

Two tiles are missing in Panel I. Which one of the options in Panel II is the appropriate choice for the missing tiles?

A.
(i)
B.
(ii)
C.
(iii)
D.
(iv)

Correct Answer:

Step-by-Step Solution

Key idea: This is a missing-part completion problem in a 3x3 grid, solvable by identifying the numerical pattern governing the tiles.

Step 1: Analyze the given tiles.

Each tile is a 3x3 grid of dots, which are either open (white) or black.

Step 2: Count the number of open dots in each visible tile.

Row 1: Tile 1 has 1, Tile 2 has 8, Tile 3 has 3. Sum = 1 + 8 + 3 = 12.

Row 2: Tile 4 has 6, Tile 5 has 4. To make the row sum 12, the missing Tile 6 must have 12 - 6 - 4 = 2 open dots.

Row 3: Tile 7 has 5, Tile 8 has 0. To make the row sum 12, the missing Tile 9 must have 12 - 5 - 0 = 7 open dots.

Step 3: Verify with columns.

Column 1: 1 + 6 + 5 = 12.

Column 2: 8 + 4 + 0 = 12.

Column 3: 3 + 2 + 7 = 12. The pattern holds perfectly for both rows and columns.

Step 4: Match with options.

We need an option that provides a tile with 2 open dots for the first missing position (Row 2, Col 3), and a tile with 7 open dots for the second missing position (Row 3, Col 3). Option A matches this requirement exactly.

Answer: A

Question 38 · Quantitative Aptitude · 2026_Set2 MCQ

The values of Stock A and Stock B on a particular day are Rs. 50 and Rs. 80, respectively. An investor invests Rs. 100 in Stock A and Rs. 80 in Stock B. He sells all the stocks the next day when the value of Stock A is Rs. 55 and Stock B is Rs. 70. The profit made by the investor is Rs. ________

A.
0
B.
5
C.
10
D.
20

Correct Answer:

Step-by-Step Solution

Insight: Calculate the number of shares purchased for each stock using the initial investment and price, then find the total selling value.

Exam route: Shares of A = 100 / 50 = 2. Shares of B = 80 / 80 = 1. Selling value = 2 55 + 1 70 = 110 + 70 = 180. Total cost = 180. Profit = 180 - 180 = 0.

Learning route:

Step 1: Find the number of shares bought for Stock A. Investment = Rs. 100, Price = Rs. 50. Shares of A = 100 / 50 = 2.

Step 2: Find the number of shares bought for Stock B. Investment = Rs. 80, Price = Rs. 80. Shares of B = 80 / 80 = 1.

Step 3: Calculate the total selling value the next day. Price of A = Rs. 55, Price of B = Rs. 70.

Selling value of A = 2 * 55 = 110.

Selling value of B = 1 * 70 = 70.

Total selling value = 110 + 70 = 180.

Step 4: Calculate profit. Total cost = 100 + 80 = 180. Profit = Total selling value - Total cost = 180 - 180 = 0.

Trap warning: A common mistake is to just average the percentage changes or add the price differences (55 - 50 + 70 - 80 = -5) without weighting by the number of shares.

Verification: Cost = 180. Final value = 180. Profit = 0. Matches option A.

Section-wise Paper Structure

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 2026_Set2 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

Paper breakdown

Free sample questions from GATE CS 2026_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

Other GATE CS papers