GATE 2026 Computer Science (CS1) Question Paper with Solutions | All 65 Questions

 

GATE 2026 Computer Science (CS1) Question Paper with Solutions

Welcome to our GATE 2026 Computer Science and Information Technology (CS1) question paper solution series. In this post, you will find all 65 questions from the GATE 2026 CS1 examination along with their answers and detailed explanations. This resource is designed to help students understand important concepts, practise exam-level questions and improve their preparation for the GATE Computer Science examination.

The GATE Computer Science examination covers several important subjects, including Programming and Data Structures, Algorithms, Operating Systems, Computer Networks, Database Management Systems, Computer Organization and Architecture, Theory of Computation, Compiler Design, Digital Logic and Engineering Mathematics. Practising questions from these subjects can help students strengthen their fundamentals and develop better problem-solving skills.

What You Will Get in This Post

• All 65 questions from the GATE 2026 CS1 question paper.
• Multiple Choice Questions (MCQs) with answer checking.
• Multiple Select Questions (MSQs) with correct options.
• Numerical Answer Type (NAT) questions with answer checking.
• Step-by-step explanations to understand the solutions.
• Interactive practice so you can attempt questions before viewing solutions.

                 

Why Practise GATE 2026 Questions?

Solving the complete question paper is a useful way to test your knowledge and identify topics that need more attention. Instead of simply memorising answers, try to solve each question yourself first. After attempting it, check the correct answer and read the explanation carefully. This approach can help you understand concepts, improve accuracy and manage your time more effectively.

Start Your Practice

Whether you are preparing for GATE 2027 or revising for another Computer Science examination, these GATE 2026 CS1 questions can be useful for practice. Attempt the questions one by one, review your mistakes and keep revising the concepts regularly.

Best of Luck!
Keep practising, stay consistent and work towards your GATE preparation goals.

Question 1

The antonym of the word protagonist is ________.

A agnostic

B antagonist

C arsonist

D anarchist

Correct Answer: (B) antagonist

A protagonist is the main character or leading figure, while an antagonist opposes the protagonist. Therefore, “antagonist” is the correct antonym.

Question 2

The figure shows two 4-tile patterns. Either one or both of the patterns can be used any number of times and in any orientation to construct a new pattern. Which one of the options below cannot be constructed by using only these two 4-tile patterns assuming there are no overlaps among them?

Given 4-tile patterns

A

B

C

D

Correct Answer: (C)

Each available pattern contains 4 tiles. Therefore, any pattern constructed from these pieces must contain a total number of tiles divisible by 4.

Option C contains 15 tiles, and 15 is not divisible by 4. Hence, option C cannot be constructed using only the given 4-tile patterns.

Question 3

Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player. The last undefeated player is declared the winner of the tournament. If there are 64 players in the beginning of the tournament, how many games should be played in total to declare the winner of the tournament?

A 127

B 64

C 63

D 32

Correct Answer: (C) 63

Initially, there are 64 players. Each game eliminates exactly one player. To declare one winner, 63 players must be eliminated.

Therefore,
Total games = 64 − 1
Answer = 63

Question 4

A student needs to enroll for a minimum of 60 credits. A student cannot enroll for more than 70 credits. The credits are divided amongst project and three distinct sets of courses namely, core courses, specialization courses, and elective courses. It is compulsory for a student to enroll for exactly 15 credits of core courses and exactly 20 credits of project. In addition, a student has to enroll for a minimum of 10 credits of specialization courses. The maximum credits of elective courses that a student can enroll for is ______

A10

B15

C20

D25

Correct Answer: (D) 25

Maximum total credits = 70

Required core credits = 15
Required project credits = 20
Minimum specialization credits = 10

Maximum elective credits = 70 − 15 − 20 − 10 = 25.

Therefore, the correct option is (D) 25.

Question 5

‘When the teacher is in the room, all students stand silently.’

If the above statement is true, which one of the following statements is not necessarily true?

A If any student is not standing silently, then the teacher is not in the room.

B When the teacher is in the room, all students are silent.

C If all students are standing, then the teacher is in the room.

D When the teacher is in the room, all students are standing.

Correct Answer: (C)

The given statement says that if the teacher is in the room, all students stand silently.

This does not mean that if all students are standing, the teacher must be in the room. Students could be standing even when the teacher is absent.

Therefore, option (C) is not necessarily true.

Question 6 · 2 Marks

Combinatorics deals with problems involving counting. For example, “How many distinct arrangements of N distinct objects in M spaces on a circle are possible?” is a typical problem in combinatorics. This kind of counting is sometimes used in the modeling of several physical phenomena. Often, in such models, the different combinatorial possibilities are assigned probability values. Assigning probabilities enables the computation of the average values of physical quantities.

Consider the following statements:

P: Combinatorics is always invoked in the modeling of physical phenomena.

Q: Modeling some physical phenomena involves assigning probabilities to combinatorial possibilities in order to compute average values of physical quantities.

Based on the passage above, what can be inferred about statements P and Q?

A P is False and Q is False

B P is False and Q is True

C P is True and Q is False

D P is True and Q is True

Correct Answer: (B) P is False and Q is True

Statement P is False: The passage says combinatorial counting is “sometimes” used in modeling physical phenomena, not that it is always used.

Statement Q is True: The passage explicitly states that some models assign probabilities to combinatorial possibilities to compute average physical quantities.

GATE 2026 · CS1 Question 7 · MCQ · 2 Marks

In Panel I of the figure below, the front view and top view of a structure are shown. Which one of the 3D structures shown in Panel II possesses the views shown in Panel I?

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

Solution

The question requires comparing the front and top views in Panel I with the four 3D structures in Panel II.

Note: The original figure has not been reproduced here, as requested. Please refer to the question paper figure to compare the options.

Question 8 · 2 Marks

For positive real numbers S and K, the function H_K(S) is defined as:

H_K(S) = max(S − K, 0)
max(a, b) = a, when a > b
max(a, b) = b, when a ≤ b

The graph below shows the plot of a function N(S) versus S. N(S) can be expressed as _____.

A H₁₀(S) − H₂₀(S)

B H₁₀(S) − 2H₂₀(S)

C −H₁₀(S) + H₂₀(S)

D H₁₅(S) − H₂₀(S)

Correct Answer: (A)

H₁₀(S) = max(S − 10, 0) and H₂₀(S) = max(S − 20, 0).

For S ≤ 10, both terms are zero, so N(S) = 0. Between S = 10 and S = 20, the function rises as S − 10. For S ≥ 20, the difference is (S − 10) − (S − 20) = 10.

This matches the given graph. Therefore, N(S) = H₁₀(S) − H₂₀(S).

Question 9 · 2 Marks

In the 2020 summer Olympics’ Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. There were six rounds of throws with each athlete having one throw per round. The best of all the throws of each athlete is considered for the medal. Following were the observations about the throws:

i. The first and second rounds were dominated by Neeraj Chopra with a gold medal performance in his second throw, while the other two athletes did not have any medal winning throws in these rounds.

ii. The throws in the last round by both Jakub Vadlejch and Vitezlav Vesely were fouls and were not considered for scoring.

iii. After four rounds, Vitezlav Vesely was in the second position and could not improve upon his best throw in the succeeding rounds.

iv. In the fourth round, the throw by Jakub Vadlejch was the best in that round.

In which round did Vitezlav Vesely have his best throw?

A Third

B Fourth

C Fifth

D Sixth

Correct Answer: (A) Third

Step 1: From observation (i), Vesely's best throw was not in the first or second round.

Step 2: From observation (ii), his sixth-round throw was a foul, so it cannot be his best throw.

Step 3: From observation (iii), Vesely could not improve his best throw in rounds five and six. Therefore, his best throw occurred by the end of round four.

Step 4: Observation (iv) says Jakub had the best throw in round four. Since Vesely was in second position after four rounds, Vesely's best throw must have occurred before round four.

Rounds one, two, four, five and six are eliminated. Hence, Vesely's best throw was in the third round (Option A).

Question 10 · 1 Mark

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 number appearing in the second roll is an integer multiple of the number appearing in the first roll is __________.

A 16

B 518

C 718

D 56

Correct Answer: (C) 7/18

Two dice rolls produce 6 × 6 = 36 equally likely ordered outcomes.

Count the valid second-roll values for each first-roll value:

First roll = 1: second roll can be 1, 2, 3, 4, 5, 6 → 6 outcomes.
First roll = 2: second roll can be 2, 4, 6 → 3 outcomes.
First roll = 3: second roll can be 3, 6 → 2 outcomes.
First roll = 4: second roll can be 4 → 1 outcome.
First roll = 5: second roll can be 5 → 1 outcome.
First roll = 6: second roll can be 6 → 1 outcome.

Total favourable outcomes = 6 + 3 + 2 + 1 + 1 + 1 = 14.

Probability = 14/36 = 7/18.

Question 11 · 1 Mark

An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put back in the urn. The probability that there are equal number of red and blue balls after two steps is

A1/4

B1/3

C1/2

D2/3

Correct Answer: (B) 1/3

Initially, there is 1 red ball and 1 blue ball.

Step 1: After the first draw, either red or blue is added to the urn. The counts become either (2 red, 1 blue) or (1 red, 2 blue).

Step 2: To have equal numbers after two steps, the second draw must be the opposite color from the first draw.

If red was drawn first, the probability of drawing blue next is 1/3. If blue was drawn first, the probability of drawing red next is also 1/3.

Therefore, total probability = (1/2 × 1/3) + (1/2 × 1/3) = 1/3.

Question 12 · 1 Mark

Consider 4 × 4 matrices with their elements from {0, 1}. The number of such matrices with even number of 1s in every row and every column is

0	1	1	0
1	0	1	0
1	1	0	0
0	0	0	0

Illustrative binary matrix

A512

B1025

C1023

D255

Correct Answer: (A) 512

A 4 × 4 binary matrix has 16 entries. Choose the entries in the first 3 rows and first 3 columns freely. There are 9 such entries, each with 2 possible values.

Therefore, the number of choices is \(2^9 = 512\).

The even-parity condition for each of the first 3 rows determines the last entry in that row. Similarly, the condition for each of the first 3 columns determines the last entry in that column. The bottom-right entry is then fixed, and its row and column parity conditions are automatically satisfied.

Hence, the total number of matrices is 512.

Question 13 · 1 Mark

For n > 1, the maximum multiplicity of any eigenvalue of an n × n matrix with elements from ℝ is

A ∈ ℝ^n×n

An

Bn − 1

C1

Dn + 1

Correct Answer: (A) n

The maximum possible algebraic multiplicity of an eigenvalue of an n × n matrix is n.

For example, consider the identity matrix multiplied by a constant: A = λI_n.

Its characteristic polynomial is det(xI − A) = (x − λ)ⁿ.

Therefore, the eigenvalue λ has algebraic multiplicity n, which is the maximum possible. Hence, the answer is (A) n.

Question 14 · 1 Mark

Match each addressing mode in List I with a data element or an element of a data structure (in a high-level language) in List II:

List I

P. Immediate

Q. Indirect

R. Base with index

S. Base with offset/displacement

List II

1. Element of an array

2. Pointer

3. Element of a record

4. Constant

AP–4, Q–3, R–1, S–2

BP–4, Q–2, R–1, S–3

CP–1, Q–4, R–3, S–2

DP–2, Q–3, R–1, S–4

Correct Answer: (B) P–4, Q–2, R–1, S–3

P. Immediate → 4. Constant
Immediate addressing uses the value itself as a constant operand.

Q. Indirect → 2. Pointer
Indirect addressing uses a pointer or address to locate the operand.

R. Base with index → 1. Element of an array
An array element can be accessed using a base address and an index.

S. Base with offset/displacement → 3. Element of a record
A record field can be located using a base address and its fixed offset.

Therefore, the correct matching is P–4, Q–2, R–1, S–3 (Option B).

Question 15 · 1 Mark

Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand.

Which one of the following sequences of instructions corresponds to the high-level language statement Z = X + Y?

Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.

A ADD Z, X, Y

B LOAD R0, X ADD Z, R0, Y

C ADD R0, X, Y STORE Z, R0

D LOAD R0, X LOAD R1, Y ADD R2, R0, R1 STORE Z, R2

Correct Answer: (D)

Step 1: LOAD R0, X
Memory operand X ki value register R0 mein load hoti hai.

Step 2: LOAD R1, Y
Memory operand Y ki value register R1 mein load hoti hai.

Step 3: ADD R2, R0, R1
R0 aur R1 ki values add hoti hain aur result R2 mein store hota hai. Pehla operand destination hai.

Step 4: STORE Z, R2
Result ko register R2 se memory location Z mein store kiya jata hai.

Load-store architecture mein arithmetic operation registers par hota hai; memory operands ko pehle registers mein load karna padta hai. Isliye Option (D) sahi hai.

Question 16

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

Correct Answer: (B) Read-after-write

Explanation: Read-after-write (RAW) hazard occurs when a later instruction tries to read a register before an earlier instruction has finished writing its result to that register.

Example:

I1: R1 = R2 + R3

I2: R4 = R1 + R5

Instruction I2 needs the new value of R1 produced by I1. If that value is not ready when I2 reads it, a data hazard occurs.

Question 17

Consider the following recurrence relations:

For all n > 1,
T₁(n) = 4T₁(n/2) + T₂(n)
T₂(n) = 5T₂(n/4) + Θ(log₂ n)

Assume that for all n ≤ 1, T₁(n) = 1 and T₂(n) = 1.
Which one of the following options is correct?

Correct Answer: (A)

First, solve:

T₂(n) = 5T₂(n/4) + Θ(log n)

By the Master Theorem, T₂(n) = Θ(n^{log₄ 5}).

Now substitute into the first recurrence:

T₁(n) = 4T₁(n/2) + Θ(n^{log₄ 5})

Since log₄ 5 is less than 2, the additional term grows more slowly than n².

Applying the Master Theorem again gives T₁(n) = Θ(n²).

Question 18

With respect to a TCP connection between a client and a server, which one of the following statements is true?

Correct Answer: (D)

TCP supports simultaneous connection termination. Both the client and the server can independently initiate closing the connection at approximately the same time.

(A) is incorrect because TCP establishes a connection using a three-way handshake. (B) is incorrect because either side can initiate closing. (C) is incorrect because TCP is full-duplex, allowing data transmission in both directions.

Question 19

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?

(A) HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, if the objects are stored in the same server. (B) HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, even if they are stored in different servers. (C) HTTP 1.1 facilitates sending a request for downloading one object without waiting for a previously requested object to be downloaded completely. (D) HTTP 1.1 facilitates downloading multiple webpages on the same server to be downloaded over a single TCP connection.

Correct Answers: (A), (C) and (D)

(A) True: HTTP/1.1 supports persistent TCP connections, allowing multiple objects from the same server to use one connection.

(B) False: Objects hosted on different servers do not generally share the same TCP connection.

(C) True: HTTP/1.1 supports pipelining, which allows multiple requests to be sent without waiting for each earlier response to finish.

(D) True: A persistent connection can be reused to request multiple webpages from the same server.

Question 20

Let n > 1. Consider an n × n matrix M with its elements from ℝ. Let the vector (0, 1, 0, 0, …, 0) ∈ ℝⁿ be in the null space of M.

Which of the following options is/are always correct?

(A) Determinant of M is 1 (B) Determinant of M is 0 (C) Rank of M is 1 (D) There are at least two non-zero vectors in the null space of M

Correct Answers: (B) and (D)

(B) A non-zero vector is in the null space, so M is singular and det(M) = 0.

(D) If v = (0, 1, 0, …, 0) is in the null space, then 2v is also in the null space. Both are non-zero vectors.

(A) Incorrect because the determinant is zero.

(C) Incorrect because the rank is not necessarily 1.

Question 21

Consider the following Boolean expression of a function F:

F(P, Q) = (P̅ + Q) ⊕ (P̅Q)

Which of the following expressions is/are equivalent to F?

(A) P ⊕ Q (B) P ⊕ Q (C) P̅ ⊕ Q (D) P̅ ⊕ Q̅

Correct Answers: (A) and (C)

Given:

F(P,Q) = (P̅ + Q) ⊕ (P̅Q)

Using the Boolean identity:

(X + Y) ⊕ (XY) = X ⊕ Y

Put X = P̅ and Y = Q:

F = P̅ ⊕ Q

This is also equivalent to the complement of P ⊕ Q.

Therefore, options A and C are correct.

Question 22

Consider the 8-bit signed integers X, Y and Z represented using the sign-magnitude form. The binary representations of X and Y are as follows:

X : 10110100
Y : 01001100

Which of the following operations to compute Z result(s) in an arithmetic overflow?

(A) Z = X + Y (B) Z = X − Y (C) Z = −X + Y (D) Z = −X − Y

Correct Answers: (B) and (C)

Step 1: Convert X and Y into decimal.

X = 10110100 = −52 (sign bit 1 means negative).

Y = 01001100 = +76 (sign bit 0 means positive).

8-bit sign-magnitude range: −127 to +127.

(A) X + Y: −52 + 76 = 24. No overflow.

(B) X − Y: −52 − 76 = −128. Overflow.

(C) −X + Y: 52 + 76 = 128. Overflow.

(D) −X − Y: 52 − 76 = −24. No overflow.

Therefore, options B and C result in arithmetic overflow.

Question 23

Let n be an odd number greater than 100. Consider a binary minheap with n elements stored in an array P whose index starts from 1.

Which of the following indices of P do/does NOT correspond to any leaf node of the minheap?

(A) (n + 1) / 2 (B) (n − 1) / 2 (C) (n − 3) / 2 (D) n

Correct Answers: (B) and (C)

For a 1-indexed binary heap:

Internal nodes have indices from 1 to ⌊n/2⌋.

Leaf nodes have indices from ⌊n/2⌋ + 1 to n.

Since n is odd, let n = 2k + 1.

(A) (n + 1)/2 = k + 1 → Leaf node.

(B) (n − 1)/2 = k → Internal node, not a leaf.

(C) (n − 3)/2 = k − 1 → Internal node, not a leaf.

(D) n = last array index → Leaf node.

Therefore, options B and C do not correspond to leaf nodes.

Question 24

Consider a hash table P[0, 1, …, 10] that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is:

h(x) = (x + 7) mod 11

Consider the following sequence of insertions performed on P:

1, 13, 22, 15, 11, 24

Which of the following positions in the hash table is/are empty after these insertions are performed?

(A)   0 (B)   10 (C)   2 (D)   1

Correct Answer: (C) 2

Using the hash function h(x) = (x + 7) mod 11:

• 1 → 8
• 13 → 9
• 22 → 7
• 15 → 0
• 11 → 7 (collision), so linear probing places it at 10.
• 24 → 9 (collision), then 10, 0 are occupied, so it is placed at 1.

Occupied positions: 0, 1, 7, 8, 9, 10.

Empty positions: 2, 3, 4, 5, 6.

Therefore, among the given options, only position 2 is empty.

Question 25

Consider the following grammar where S is the start symbol, and a and b are terminal symbols.

S → aSbS   |   bS   |   ε

Which of the following statements is/are true?

(A) The grammar is ambiguous (B) The string abb has two distinct derivations in this grammar (C) The string abab has only one rightmost derivation (D) The language generated by the grammar is undecidable

Correct Answers: (A), (B) and (C)

Option (A) – True: The grammar is ambiguous because the same string can have two different derivations.

Option (B) – True: The string abb has two distinct derivations:

Derivation 1:
S → aSbS → abS → abbS → abb

Derivation 2:
S → aSbS → abSbS → abbS → abb

Thus, the same string abb can be generated in two different ways.

Option (C) – True: The string abab has only one rightmost derivation. Its rightmost derivation is:

S → aSbS
→ aSbaSbS
→ aSbaSb
→ aSbab
→ abab

Option (D) – False: The grammar is context-free, and every context-free language is decidable.

Question 26

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet.

Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to M?

(A)   32 (B)   65 (C)   1 (D)   128

Correct Answers: (B) 65 and (D) 128

Given that the NFA has 6 states.

Using subset construction, the maximum number of states in the equivalent DFA is:

2ⁿ = 2⁶ = 64

Therefore, the equivalent DFA can have at most 64 states. The minimal DFA cannot have more than 64 states either.

• (A) 32: Possible, because it is less than or equal to 64.
• (B) 65: Not possible, because it exceeds 64.
• (C) 1: Possible, because a DFA can have just one state.
• (D) 128: Not possible, because it exceeds 64.

Hence, the correct answers are (B) and (D).

Question 27

Consider the following C statements:

char *str1 = "Hello;    /* Statement S1 */

char *str2 = "Hello;";   /* Statement S2 */

int *str3 = "Hello";     /* Statement S3 */

Which of the following options is/are correct?

(A) S1 and S2 have syntactic errors (B) S2 has a lexical error and S3 has a syntactic error (C) S1 has a lexical error and S3 has a semantic error (D) S1 has a syntactic error and S3 has a semantic error

Correct Answer: (C)

Statement S1 – Lexical Error:
The string literal starts with a double quotation mark but does not have a closing double quotation mark. Therefore, it has an unterminated string literal (lexical error).

Statement S2 – Correct:
The string literal "Hello;" is properly enclosed in double quotation marks. The semicolon is part of the string.

Statement S3 – Semantic Error:
The string literal is of character-array type, but the pointer str3 is declared as int *. These pointer types are incompatible, resulting in a semantic constraint violation in C.

Hence, option (C) is correct.

Question 28

Which of the following statements is/are true?

(A) LL(1) parser uses backtracking (B) For a grammar to be LL(1), it must be left-recursive (C) For a grammar to be LL(1), it must be left-factored (D) The LL(1) parsers are more powerful than the SLR parsers

Correct Answer: (C)

(A) False: LL(1) parser is a predictive parser and does not use backtracking.

(B) False: An LL(1) grammar cannot be left-recursive. Left recursion must be eliminated.

(C) True: Left factoring helps make a grammar suitable for predictive parsing by removing common prefixes.

(D) False: SLR parsers are more powerful than LL(1) parsers in terms of the class of grammars they can handle.

Hence, option (C) is correct.

Question 29

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

(A) Banker's algorithm is used to prevent deadlocks (B) Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed (C) An assignment edge in a resource allocation graph is marked from a process to a resource (D) A safe state guarantees that all processes can finish without formation of a deadlock

Correct Answers: (A) and (C)

(A) False: Banker's algorithm is used for deadlock avoidance, not deadlock prevention.

(B) True: If the hold and wait condition is eliminated, deadlock can be prevented.

(C) False: An assignment edge in a resource allocation graph is directed from a resource to a process, not from a process to a resource.

(D) True: A safe state means there exists a safe sequence in which all processes can complete without deadlock.

Hence, the false statements are (A) and (C).

Question 30

Let P, Q, R and S be the attributes of a relation in a relational schema. Let X → Y indicate functional dependency in the context of a relational database, where X, Y ⊆ {P, Q, R, S}.

X → Y   (Functional Dependency)

Which of the following options is/are always true?

(A) If ({P, Q} → {R} and {P} → {R}), then {Q} → {R} (B) If {P, Q} → {R}, then ({P} → {R} or {Q} → {R}) (C) If ({P} → {R} and {Q} → {S}), then {P, Q} → {R, S} (D) If {P} → {R}, then {P, Q} → {R}

Correct Answers: (C) and (D)

(A) False: From P → R and PQ → R, we cannot conclude that Q → R. The dependency P → R already determines R using P alone.

(B) False: PQ → R does not imply that either P → R or Q → R individually. Both attributes together may be needed to determine R.

(C) True: Given P → R and Q → S, by the union rule: PQ → RS.

(D) True: By the augmentation rule, if P → R, then adding Q to both sides gives PQ → RQ. By the decomposition rule, PQ → R.

Hence, options (C) and (D) are always true.

Question 31

In the context of relational database normalization, which of the following statements is/are true?

(A) It is always possible to obtain a dependency-preserving 3NF decomposition of a relation. (B) It is always possible to obtain a dependency-preserving 1NF decomposition of a relation. (C) It is not always possible to obtain a dependency-preserving BCNF decomposition of a relation. (D) It is not always possible to obtain a dependency-preserving 2NF decomposition of a relation.

Correct Answers: (A), (B) and (C)

(A) True: The 3NF synthesis algorithm can always produce a dependency-preserving 3NF decomposition.

(B) True: A relation in 1NF can be retained as it is; therefore, a dependency-preserving 1NF decomposition is possible.

(C) True: BCNF decomposition is possible, but it is not always possible to preserve all functional dependencies.

(D) False: A dependency-preserving 2NF decomposition can be obtained by decomposing relations to remove partial dependencies while retaining the relevant dependencies.

Hence, options (A), (B) and (C) are true.

Question 32

Consider the function f : ℝ → ℝ defined as follows:

f(x) = { c₁e^x − c₂ log_e(1/x),   if x > 0
     3,   otherwise

where c₁, c₂ ∈ ℝ. If f is continuous at x = 0, then c₁ + c₂ = _________.
(Answer in integer)

Enter your answer:

Correct Answer: 3

For continuity at x = 0:

lim_x→0⁺ f(x) = f(0) = 3

Therefore,

lim_x→0⁺ [c₁e^x − c₂ ln(1/x)] = 3

As x → 0⁺:

• e^x → 1
• ln(1/x) → ∞

For the limit to be finite, we must have:

c₂ = 0

Then:

c₁ × 1 = 3, so c₁ = 3

Hence,

c₁ + c₂ = 3 + 0 = 3

Question 32

GATE 2026 · CS1

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (answer in integer)

Your Answer:

Solution:

In a full binary tree, every internal node has exactly 2 children.

To obtain maximum height, we keep one child as a leaf and continue the longest path through the other child.

For height h, the minimum number of nodes required is:

N = 2h + 1

Given N = 23:

23 = 2h + 1

2h = 22

h = 11

Correct Answer: 11

Question 34

GATE 2026 · CS1

Consider the following program in C:

#include <stdio.h>

void func(int i, int j) {
    if(i < j) {
        int i = 0;
        while (i < 10) {
            j += 2;
            i++;
        }
    }
    printf("%d", i);
}

int main() {
    int i = 9, j = 10;
    func(i, j);
    return 0;
}

The output of the program is _________. (answer in integer)

Your Answer:

Solution:

In main(), the values passed to func() are i = 9 and j = 10.

Since 9 < 10, the if condition is true.

Inside the if block, a new local variable int i = 0; is declared. This variable shadows the function parameter i.

The while loop runs until this local i becomes 10. However, the original function parameter i remains unchanged at 9.

After the if block ends, the local variable goes out of scope. Therefore, printf("%d", i) refers to the function parameter.

Correct Answer: 9

Question 35

GATE 2026 · CS1

Consider a system consisting of k instances of a resource R, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource R and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.

The minimum value of k for the system to be deadlock-free is _________. (answer in integer)

Your Answer:

Solution:

Given:

• Number of processes = 5
• Maximum resource requirement per process = 2

For n processes, each requiring a maximum of 2 instances, the minimum number of resource instances required to guarantee a deadlock-free system is:

k = n(2 − 1) + 1

Putting n = 5:

k = 5 × 1 + 1 = 6

If only 5 instances are available, all 5 processes could hold one instance each and wait for another, causing deadlock.

Correct Answer: 6

Question 36

GATE 2026 · CS1

Consider the real valued variables X, Y and Z represented using the IEEE 754 single-precision floating-point format. The binary representations of X and Y in hexadecimal notation are as follows:

X : 35C00000
Y : 34A00000

Let Z = X + Y.

Which one of the following is the binary representation of Z, in hexadecimal notation?

(A)   35C80000 (B)   35CC0000 (C)   35E80000 (D)   35EC0000

Solution:

Given:

X = 35C00000

Y = 34A00000

IEEE 754 single-precision format contains 1 sign bit, 8 exponent bits and 23 fraction bits.

Converting the given hexadecimal representations into decimal values:

X = 0.000001430511474609375

Y = 0.000000298023223876953125

Therefore,

Z = X + Y

Z = 0.000001728534698486328125

Converting the result back into IEEE 754 single-precision hexadecimal representation:

Z = 35E80000

Correct Answer: Option (C)

Question 37

GATE 2026 · CS1

Consider a 2-bit saturating up/down counter that performs the saturating up count when the input P is 0, and the saturating down count when P is 1. The Next State table of the counter is as shown. The counter is built as a synchronous sequential circuit using D flip-flops.

input P	current state Q₁	current state Q₀	next state Q₁⁺	next state Q₀⁺
0	0	0	0	1
0	0	1	1	0
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	0	1
1	1	1	1	0

Which one of the following options corresponds to the expressions for the inputs of the D flip-flops, D₁ and D₀?

(A)
D₁ = P Q₁ + P̅ Q₀ + Q₁Q₀
D₀ = P Q₀ + P̅ Q₁ + Q₁Q̅₀ (B)
D₁ = P̅ Q₁ + P̅ Q₀ + Q₁Q₀
D₀ = P̅ Q̅₀ + P̅ Q₁ + Q₁Q̅₀ (C)
D₁ = P̅ Q̅₁ + P̅ Q₀ + Q₁Q₀
D₀ = P̅ Q₀ + P̅ Q₁ + Q₁Q̅₀ (D)
D₁ = P Q̅₁ + P̅ Q₀ + Q₁Q₀
D₀ = P Q̅₀ + P̅ Q₁ + Q₁Q̅₀

Solution:

For D flip-flops:

D₁ = Q₁⁺ and D₀ = Q₀⁺

From the given next-state table, the Boolean expressions are:

D₁ = P̅Q₁ + P̅Q₀ + Q₁Q₀

D₀ = P̅Q̅₀ + P̅Q₁ + Q₁Q̅₀

These expressions match option (B).

Correct Answer: Option (B)

Question 38

GATE 2026 · CS1

The size of the physical address space of a processor is 2³² bytes. The capacity of a cache memory unit is 2²³ bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a K-way set-associative cache, where K = 2^L and L ∈ {1, 2, 3}. Let the length of the TAG field be M bits for the direct mapped cache, and N bits for the set-associative cache.

Which one of the following options is true?

(A)   N = M + L (B)   N = M − L (C)   N = M + K (D)   N = M − K

Solution:

Given:

Physical address space = 2³² bytes

Cache capacity = 2²³ bytes

Block size = 128 = 2⁷ bytes

Step 1: Direct mapped cache

Number of cache lines = 2²³ / 2⁷ = 2¹⁶

Index bits = 16

Block offset bits = 7

Therefore,

M = 32 − 16 − 7 = 9 bits

Step 2: K-way set-associative cache

Given K = 2^L

Number of sets = 2¹⁶ / 2^L = 2^(16−L)

Set index bits = 16 − L

Therefore,

N = 32 − (16 − L) − 7

N = 9 + L

Since M = 9, we get:

N = M + L

Correct Answer: Option (A)

Question 39

GATE 2026 · CS1

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
    int elt;
    struct node *next;
};

int getListSize (struct node *head)
{
    if( E1 ) return 1;
    return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

(A)
E1: head == NULL
E2: 1 + getListSize(head) (B)
E1: head->next == NULL
E2: 1 + getListSize(head->next) (C)
E1: head == NULL
E2: 1 + getListSize(head->next) (D)
E1: head->next == NULL
E2: 1 + getListSize(head)

Solution:

We need to count the nodes of a non-empty singly linked list.

Base condition: If head->next == NULL, the current node is the last node. Therefore, return 1.

Recursive condition: Count the current node (1) and recursively count the remaining nodes using head->next.

Thus:

E1: head->next == NULL

E2: 1 + getListSize(head->next)

Correct Answer: Option (B)

Question 40

GATE 2026 · CS1

Let P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is inserted?

(A)   4 (B)   2 (C)   10 (D)   5

Solution:

There are 15 elements (1 to 15). A complete binary tree with 15 nodes has the following perfect structure:

Final BST structure

Step 1: The first inserted element must be 8, because it becomes the root of the BST.

Step 2: The second element can be 4 or 12, since these are the root's children.

Step 3: The third element must be a child of one of the already inserted nodes.

• 4 is possible if 12 is inserted second.
• 2 is possible if 4 is inserted second.
• 10 is possible if 12 is inserted second.
• 5 is not possible because its parent 6 and its ancestor 4 must be inserted before it.

Correct Answer: Option (D) – 5

Question 41

GATE 2026 · CS1

Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let s ∈ V be a vertex in G. For every u ∈ V and for every k ≥ 0, let d_k(u) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then d_k(u) = ∞.

Consider the statements:

S1: For every k ≥ 0 and u ∈ V, d_k+1(u) ≤ d_k(u).

S2: For every (u, v) ∈ E, if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every k ≥ 0, d_k(u) ≤ d_k(v).

Which one of the following options is correct?

(A)   Only S1 is true (B)   Only S2 is true (C)   Both S1 and S2 are true (D)   Neither S1 nor S2 is true

Solution:

Statement S1:

d_k(u) is the shortest path weight when the path length is at most k.

When k increases to k+1, the set of allowed paths can only increase. The previously available paths are still available.

Therefore:

d_k+1(u) ≤ d_k(u)

Hence, S1 is true.

Statement S2:

Consider an edge (u, v) that belongs to a shortest path from s to v. This does not guarantee that the shortest path to u with length at most k has weight less than or equal to the shortest path to v with length at most k.

For example, take a graph with edges s–u of weight 10, s–v of weight 1, and u–v of weight 1. The shortest path from s to v is the direct edge of weight 1, so the condition about (u, v) is not met in this example. More generally, the stated condition does not imply the inequality for every k.

Thus, S2 is false.

Correct Answer: Option (A) – Only S1 is true.

Question 42 

GATE 2026 · CS1

Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?

Note: All the variables are integers.

(A)
B4: { b + i }
B5: { c + m } (B)
B4: { g * k }
B5: { c + m } (C)
B4: { g * k, b + i }
B5: { } (D)
B4: { g * k }
B5: { }

Solution:

Step 1: Basic Block B4

In B2, the expression g * k is computed.

In B3, the expression g * k is also computed.

Since g and k are not modified in either block, the expression g * k is available on both paths reaching B4. Hence, it is redundant in B4.

The expression b + i is not redundant because B3 modifies b using b = c + m.

Step 2: Basic Block B5

The expression c + m is computed in B3, but it is not computed in B2. Therefore, it is not available on every path reaching B5.

Hence, B5 has no redundant expression.

Correct Answer: Option (D)

GATE 2026 · CS1 Question 43

Consider a relational database schema with two relations R(P, Q) and S(X, Y).

Let

E = {⟨u⟩ | ∃v ∃w ⟨u, v⟩ ∈ R ∧ ⟨v, w⟩ ∈ S}

be a tuple relational calculus expression.

Which one of the following relational algebraic expressions is equivalent to E?

(A)   Π_P (R ⋈_{R.P = S.X} S) (B)   Π_P (S ⋈_{S.X = R.Q} R) (C)   Π_P (R ⋈_{R.P = S.Y} S) (D)   Π_P (S ⋈_{S.Y = R.Q} R)

Solution

Given: ⟨u, v⟩ ∈ R and ⟨v, w⟩ ∈ S.

Relation R(P, Q) mein u = P aur v = Q hoga. Relation S(X, Y) mein v = X aur w = Y hoga.

Isliye join condition: R.Q = S.X

Humein final result mein sirf u chahiye, jo P hai. Isliye P par projection lagayenge.

Π_P (S ⋈_{S.X = R.Q} R)

Correct Answer: Option (B)

GATE 2026 · CS1 Question 44

A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism’s slow-start threshold is set to 10000 segments. Assume that the round-trip time is fixed at 1 millisecond. Assume that the sender always has data to send, the segments are numbered from 1, and no segment is lost. Let t denote the time (in milliseconds) at which the transmission of segment number 2000 starts.

Which one of the following options is correct?

(A)   9 ≤ t < 10 (B)   10 ≤ t < 11 (C)   11 ≤ t < 12 (D)   12 ≤ t < 13

Solution

Given:

• Initial congestion window = 1 segment
• RTT = 1 millisecond
• Slow-start threshold = 10000 segments
• No segment is lost.

In TCP slow start, the congestion window doubles after every RTT.

Time (ms)	Segments transmitted
0	1
1	2 – 3
2	4 – 7
3	8 – 15
...	...
9	512 – 1023
10	1024 – 2047

Segment number 2000 lies in the range 1024–2047. Therefore, its transmission starts at 10 ms.

10 ≤ t < 11

Correct Answer: Option (B)

GATE 2026 · CS1 Question 45

Consider the implementation of sliding window protocol over a lossless link, with a window size of W frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (1k = 10³) and the one-way propagation delay is 100 milliseconds. Assume that processing times at the sender and receiver are zero and the transmission time of acknowledgements is also zero.

Which one of the following options gives the minimum size of W (in number of frames) required to achieve 100% link utilization?

(A)   10 (B)   21 (C)   20 (D)   11

Solution

Given:

• Frame size = 1000 bits
• Bandwidth = 100 kbps = 100000 bits/sec
• One-way propagation delay = 100 ms
• ACK transmission time = 0

Step 1: Frame transmission time

T_t = 1000 / 100000 = 0.01 sec = 10 ms

Step 2: Round-trip propagation delay

RTT = 2 × 100 = 200 ms

Step 3: Minimum window size

For 100% link utilization, the sender must be able to transmit enough frames before the ACK for the first frame returns.

W × T_t ≥ RTT + T_t

W × 10 ≥ 200 + 10
W ≥ 210 / 10
W = 21 frames

Correct Answer: Option (B)

GATE 2026 · CS1 Question 46 · MSQ

Let f : ℝ → ℝ be defined as follows:

f(x) = ( |x|/2 − x ) ( x − |x|/2 )

Which of the following statements is/are true?

(A)   f has a local maximum (B)   f has a local minimum (C)   f′ is continuous over ℝ (D)   f′ is not differentiable over ℝ

Solution

Given:

f(x) = (|x|/2 − x)(x − |x|/2)

Case 1: x ≥ 0

Here |x| = x.

f(x) = (x/2 − x)(x − x/2)
f(x) = −x²/4

Case 2: x < 0

Here |x| = −x.

f(x) = (−x/2 − x)(x + x/2)
f(x) = −9x²/4

Step 3: First derivative

f′(x) =
−9x/2,   x < 0
0,   x = 0
−x/2,   x > 0

At x = 0, f(0) = 0 and for all nearby x ≠ 0, f(x) < 0. Therefore, f has a local maximum at x = 0.

The left and right limits of f′(x) at 0 are both 0. Hence f′ is continuous over ℝ.

But the left derivative of f′ at 0 is −9/2 and the right derivative is −1/2. They are unequal, so f′ is not differentiable at x = 0.

Final Answers:

A, C and D

GATE 2026 · CS1 Question 47

Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V′ ⊆ V such that for every (u, v) ∈ E, u ∈ V′ or v ∈ V′. Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k.

For a vertex v ∈ V, which of the following constraints will always ensure that v ∈ S?

(A)   The degree of v is at least k + 1 (B)   The vertex v is on a path of length k + 1 (C)   The vertex v is on a cycle of length k + 1 (D)   The vertex v is a part of a clique of size k

Solution

Given:

• Minimum vertex cover size = k
• Size of S = k
• Degree of vertex v ≥ k + 1 (Option A)

Consider Option (A)

Assume that v ∉ S.

Vertex cover ki property ke according, v se connected har edge ka doosra endpoint S mein hona chahiye.

Since degree(v) ≥ k + 1, v ke kam se kam k + 1 neighbours honge.

|S| ≥ k + 1

Lekin given hai ki |S| = k. Yeh contradiction hai.

Isliye hamara assumption galat hai aur v ∈ S hona zaroori hai.

Correct Answer: Option (A)

GATE 2026 · CS1 Question 48 · MSQ

Consider a Boolean function F with the following minterm expression:

F(P,Q,R,S) = Σ m(1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal sum-of-products expression(s) of F?

(A)   P̅S + QR̅ + P̅Q̅R + Q̅RS̅ (B)   P̅S + QR̅ + P̅Q̅R + PRS̅ (C)   P̅S + QR̅ + PQS̅ + PRS̅ (D)   P̅S + QR̅ + PQS̅ + Q̅RS̅

Solution

Given minterms:

F = Σm(1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Step 1: Identify the common terms

The term P̅S covers minterms 1, 3, 5, 7 and the term QR̅ covers minterms 4, 5, 12, 13.

Step 2: Check each option

Option	Result
A	Minterm 14 is missing.
B	Covers all given minterms.
C	Covers all given minterms.
D	Covers all given minterms.

Options B, C and D each represent the given function using four product terms. Option A is not equivalent because it does not cover minterm 14.

Correct Answers: B, C and D

GATE 2026 · CS1 Question 49 · MSQ

Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST) of G is/are true?

(A)   In every cycle C of G, the edge with the largest weight in C is not in any MST (B)   In every cycle C of G, the edge with the smallest weight in C is in every MST (C)   For every vertex v ∈ V, the edge with the largest weight incident on v is not in any MST (D)   For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST

Solution

Option (A) — True

Cycle property ke according, kisi bhi cycle mein unique largest-weight edge kisi bhi MST ka part nahi ho sakti.

Option (B) — False

Cycle ka smallest-weight edge har MST mein hona zaroori nahi hai. Example:

A cycle with weights 3, 4, 5 may have an external edge of weight 1 connecting the same two sides. Then the weight-3 edge need not be in the MST.

Option (C) — False

Largest incident edge kisi vertex par bridge bhi ho sakti hai. Agar woh bridge hai, toh use MST mein include karna zaroori hai. Isliye yeh statement always true nahi hai.

Option (D) — True

Kisi vertex v ke liye cut {v} aur baaki sabhi vertices ke beech minimum-weight incident edge unique hai. Cut property ke according, yeh edge har MST mein include hoti hai.

Correct Answers: A and D

GATE 2026 · CS1 Question 50 · MSQ

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V, E) as input, where d[v] and f[v] are the discovery time and finishing time, respectively, of the vertex v ∈ V.

DFS(G):
unmark all v ∈ V
t ← 0
for each v ∈ V
  if v is unmarked
    t ← Explore(G,v,t)
  end if
end for

Explore(G,v,t):
mark v
t ← t + 1
d[v] ← t
for each (v,w) ∈ E
  if w is unmarked
    t ← Explore(G,w,t)
  end if
end for
t ← t + 1
f[v] ← t
return t

Suppose that the input directed graph G(V, E) is a directed acyclic graph (DAG).

For an edge (u, v) ∈ E, which of the following options will NEVER be correct?

(A)   d[u] < d[v] < f[v] < f[u] (B)   d[v] < d[u] < f[u] < f[v] (C)   d[v] < f[v] < d[u] < f[u] (D)   d[u] < d[v] < f[u] < f[v]

Solution

DFS mein har vertex ka discovery time d[v] aur finishing time f[v] hota hai. Kisi bhi do vertices ke DFS intervals ya toh nested hote hain ya disjoint.

Option (A) — Possible

Agar DFS vertex u se start karke edge (u,v) ko explore karta hai, toh v, u ka descendant ban sakta hai. Isliye:

d[u] < d[v] < f[v] < f[u]

Option (B) — Never correct

Is order ka matlab hai ki v ka DFS interval u ke interval ko contain karta hai. Yaani v, DFS tree mein u ka ancestor hai.

Lekin given edge u → v ancestor ki taraf ja raha hai. Yeh back edge banegi aur directed cycle create karegi. DAG mein cycle nahi hoti.

Option (C) — Possible

Agar v ka DFS pehle complete ho jaata hai aur uske baad u discover hota hai, toh dono intervals disjoint honge. Edge u → v ek cross edge ho sakti hai.

d[v] < f[v] < d[u] < f[u]

Option (D) — Never correct

Is order mein u aur v ke DFS intervals overlap karte hain, lekin ek doosre ke andar completely nested nahi hain.

DFS mein aise overlapping intervals possible nahi hote. Agar ek vertex doosre ke explore hone ke dauraan discover hota hai, toh uska finishing time pehle aata hai.

Correct Answers: B and D

GATE 2026 · CS1 Question 51

Let L₁ and L₂ be two languages over a finite alphabet, such that L₁ ∩ L₂ and L₂ are regular languages.

Which of the following statements is/are always true?

(A)   L₁ is regular (B)   L₁ ∪ L₂ is regular (C)   L₂ is context-free (D)   L₁ is context-free

Solution

Given:

L₁ ∩ L₂ is regular
L₂ is regular

Option (A) — Not always true

Intersection of L₁ and L₂ being regular does not guarantee that L₁ itself is regular.

Option (B) — Not always true

Union of two languages is guaranteed to be regular only when both languages are regular. Here, L₁ is not necessarily regular.

Option (C) — Always true

Regular languages are closed under complement. Since L₂ is regular, its complement is also regular.

L₂ regular
↓
Complement of L₂ is regular
↓
Every regular language is context-free

Option (D) — Not always true

Given conditions do not guarantee that L₁ is context-free.

Correct Answer: Option (C)

GATE 2026 · CS1 Question 52 · MSQ

Consider the following context-free grammar G.

S → abaABAbba
A → aaBBAb | bB abaa
B → aBb | ab

In the above grammar, S is the start symbol, a and b are terminal symbols, and A and B are non-terminal symbols.

Let L(G) be the language generated by the grammar G. For a string s ∈ L(G), let n₁(s) be the number of a's in s and n₂(s) be the number of b's in s.

Which of the following statements is/are true?

(A)   There is a string s ∈ L(G) such that n₁(s) < n₂(s) (B)   For every string s ∈ L(G), n₁(s) ≥ n₂(s) (C)   There is a string s ∈ L(G) such that n₁(s) > 2n₂(s) (D)   For every string s ∈ L(G), n₁(s) ≤ 2n₂(s)

Solution

Let the difference between the number of a's and b's be:

Δ = n₁ − n₂

Step 1: Analyse B

B → ab gives equal numbers of a and b.

B → aBb adds one a and one b. Therefore, every string generated by B has equal numbers of a and b.

For B: Δ = 0

Step 2: Analyse A

For A → aaBBAb, the additional terminals contribute 2 a's and 1 b.

For A → bBabaa, the additional terminals contribute 3 a's and 2 b's.

Since B contributes equal numbers of a and b, every production of A gives a positive difference. Thus:

For A: Δ ≥ 1

Step 3: Analyse S

S → abaABAbba. The fixed terminals aba and bba together contribute equal numbers of a and b. The B contributes zero difference, while each A contributes at least 1.

Δ(S) = Δ(A) + Δ(B) + Δ(A)
Δ(S) ≥ 2

Therefore, for every generated string: n₁(s) > n₂(s).

Step 4: Check the options

Also, each A production adds at most twice as many a's as b's, and B always has equal numbers. The fixed terminals in S also satisfy the required upper bound. Hence:

n₁(s) ≤ 2n₂(s)

• (A) False: n₁(s) is never less than n₂(s).
• (B) True: n₁(s) is always greater than n₂(s).
• (C) False: n₁(s) never exceeds 2n₂(s).
• (D) True: n₁(s) is always at most 2n₂(s).

Correct Answers: B and D

GATE 2026 · CS1 Question 53 · MSQ

Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.

SDD1 (G1)

Grammar

D → T V
T → int
T → float
V → V₁ id
V → id

Semantic Rules

D.type = T.type
V.type = T.type
T.type = int
T.type = float
V₁.type = V.type
put(id.entry, V.type)

SDD2 (G2)

Grammar

D → D₁ id
D → T id
T → int
T → float

Semantic Rules

D.type = D₁.type
put(id.entry, D₁.type)
D.type = T.type
put(id.entry, T.type)
T.type = int
T.type = float

D is the start symbol, and int, float and id are the three terminals. The non-terminal V₁ is the same as V and the non-terminal D₁ is the same as D. Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function put updates the symbol table with the type information for an identifier.

Let P and Q be the languages specified by grammars G1 and G2, respectively.
Which of the following statements is/are true?

(A)   The languages P and Q are the same (B)   SDD2 is S-attributed and contains only synthesized attributes (C)   SDD1 is L-attributed and contains only inherited attributes (D)   The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table

Solution

1. Option A — True

G1 generates declarations in which a type (int or float) is followed by one or more identifiers. G2 also generates the same form using its left-recursive production D → D₁ id and base production D → T id. Hence, P = Q.

2. Option B — True

In SDD2, D.type is computed from the attributes of its children D₁ or T. The attributes are synthesized, and no inherited attributes are used. Therefore, SDD2 is S-attributed.

3. Option C — False

In SDD1, T.type is synthesized from the production T → int or T → float. The value is then passed to V.type, and V.type is passed to V₁. Thus, SDD1 uses both synthesized and inherited attributes. It is L-attributed, but does not contain only inherited attributes.

4. Option D — True

Both SDDs assign the same declared type to every identifier. For example, in int a b c, both specifications add a, b and c to the symbol table with type int. The same holds for float declarations.

Correct Answers: A, B and D

GATE 2026 · CS1 Question 54

Consider a system that has a cache memory unit and a memory management unit (MMU). The address input to the cache memory is a physical address. The MMU has a translation lookaside buffer (TLB). Assume that when a page is evicted from the main memory, the corresponding blocks in the cache are marked as invalid.

For a given memory reference, which of the following sequences of events can NEVER happen?

(A)   TLB miss, Page table hit, Cache hit (B)   TLB hit, Page table miss, Cache hit (C)   TLB miss, Page table miss, Cache hit (D)   TLB miss, Page table miss, Cache miss

Solution

First understand the sequence:

CPU → TLB → Page Table → Physical Address → Cache

(A) TLB miss, Page table hit, Cache hit

Possible. TLB miss hone par page table check hoti hai. Agar page table hit hai, physical address mil jata hai. Us physical address par cache hit ho sakta hai.

(B) TLB hit, Page table miss, Cache hit

Impossible. TLB hit hone par address translation TLB se mil jati hai. Page table lookup ki zarurat nahi hoti, isliye is memory reference ke liye page table miss nahi ho sakta.

(C) TLB miss, Page table miss, Cache hit

Impossible. Page table miss ka matlab page main memory mein available nahi hai. Question ke according, page evict hone par uske corresponding cache blocks invalid mark ho jaate hain. Isliye cache hit nahi ho sakta.

(D) TLB miss, Page table miss, Cache miss

Possible. Page table miss ke baad page ko main memory mein load karna padega. Uske baad cache miss ho sakta hai.

Correct Answers: B and C

GATE 2026 · CS1 Question 55 · MSQ

An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists a function c: V → {0, 1} such that for every (u, v) ∈ E, c(u) ≠ c(v).

Which of the following statements about 2-colorable graphs is/are true?

(A)   If G is 2-colorable, then G may contain cycles of odd length (B)   If G is 2-colorable, then G may contain cycles of even length (C)   An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V| + |E|), if G is represented as an adjacency list (D)   An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|E| log|V|), if G is represented as an adjacency list

Solution

Concept: Bipartite Graph

A graph is 2-colorable if and only if it is bipartite. In a bipartite graph, every edge connects vertices of different colors.

(A) False

A 2-colorable graph cannot contain an odd-length cycle. If we alternate two colors around an odd cycle, the last vertex and the first vertex would need the same color despite having an edge between them.

(B) True

Even-length cycles are possible. For example, a cycle of length 4 can be colored alternately using two colors.

Example: Even cycle (4 vertices)

Two colors alternate around the cycle.

(C) True

BFS or DFS can test bipartiteness by coloring adjacent vertices with opposite colors. With an adjacency-list representation, every vertex and edge is processed in O(|V| + |E|) time. This is optimal because the graph must be examined.

(D) False

Θ(|E| log|V|) is not the optimal running time. The optimal bound using BFS or DFS is Θ(|V| + |E|).

Correct Answers: B and C

GATE 2026 · CS1 Question 56 · MSQ

An ISP having an address block 202.16.0.0/15 assigns a block of 6000 IP addresses to a client, using the classless internet domain routing (CIDR) super-netting approach. Which of the following address blocks can be assigned by the ISP?

(A)   202.16.0.0/19 (B)   202.17.64.0/19 (C)   202.16.32.0/19 (D)   202.17.24.0/19

Solution

Step 1: Calculate the required block size

Client needs 6000 IP addresses. CIDR allocation requires a block size that is a power of 2.

2¹² = 4096 < 6000
2¹³ = 8192 ≥ 6000

Therefore, the required block contains 8192 addresses.

Step 2: Find the CIDR prefix

IPv4 addresses contain 32 bits. Hence:

32 − 13 = 19
Required prefix = /19

Step 3: Check the ISP address range

ISP block is 202.16.0.0/15.
Its address range is:

202.16.0.0 – 202.17.255.255

Step 4: Check each option

A /19 block contains 8192 addresses. Its third octet must start at a multiple of 32: 0, 32, 64, 96, 128, 160, 192 or 224.

Option	Check	Result
A	202.16.0.0/19	Valid
B	202.17.64.0/19	Valid
C	202.16.32.0/19	Valid
D	202.17.24.0/19	Invalid

Option D is invalid because 24 is not a multiple of 32, so 202.17.24.0 is not a valid /19 network address.

Correct Answers: A, B and C

GATE 2026 · CS1 Question 57 · NAT

Let G be an undirected graph, which is a path on 8 vertices. The number of matchings in G is ______.
(Answer in integer)

Your Answer

Solution

A matching is a set of edges in which no two edges share a common vertex.

Step 1: Form the recurrence

Let M(n) denote the number of matchings in a path with n vertices.

For the last vertex, there are two possibilities:

• Last vertex is unmatched: M(n−1) possibilities.
• Last vertex is matched with the previous vertex: M(n−2) possibilities.

M(n) = M(n−1) + M(n−2)

Step 2: Calculate values

Vertices (n)	Matchings M(n)
0	1
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34

Final Answer: 34

GATE 2026 · CS1 Question 58 · NAT

Let X be a random variable which takes values in the set {1, 2, 3, 4, 5, 6, 7, 8}.

Further,

Pr(X = 1) = Pr(X = 2) = Pr(X = 5) = Pr(X = 7) = ¹/₆
Pr(X = 3) = Pr(X = 4) = Pr(X = 6) = Pr(X = 8) = ¹/₁₂

The expected value of X, denoted by E[X], is equal to ___________.
(Rounded off to two decimal places)

Your Answer

Solution

Expected value of a discrete random variable:

E[X] = Σ x · Pr(X = x)

Step 1: Substitute the given probabilities

E[X] = (1 + 2 + 5 + 7) × ¹/₆
+ (3 + 4 + 6 + 8) × ¹/₁₂

Step 2: Calculate

= 15/6 + 21/12
= 2.5 + 1.75
= 4.25

Final Answer: 4.25

GATE 2026 · CS1 Question 59 · NAT

Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7.

The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)

Your Answer (in milliseconds)

Solution

Step 1: Calculate time for one rotation

Rotational speed = 15000 rpm

15000 / 60 = 250 rotations/second
Time for one rotation = 1/250 second
= 4 ms

Step 2: Average rotational latency

For a randomly located sector, average rotational latency is half the time for one rotation.

Average rotational latency = 4/2 = 2 ms

Step 3: Transfer time for one sector

There are 400 sectors in one rotation.

Time per sector = 4/400 = 0.01 ms

Step 4: Time for 30 sectors

10 randomly located sectors are required on each of 3 tracks.

Total sectors = 10 × 3 = 30
Rotational latency = 30 × 2 = 60 ms
Data transfer time = 30 × 0.01 = 0.3 ms

Step 5: Calculate head movement time

Track 0 → 5 = 5 ms
Track 5 → 12 = 7 ms
Track 12 → 7 = 5 ms
Total seek time = 17 ms

Step 6: Total time

Total = 60 + 0.3 + 17
= 77.3 ms

Final Answer: 77.3

GATE 2026 · CS1 Question 60 · NAT

The EX stage of a pipelined processor performs the memory read operations for LOAD instructions, and the operations for the arithmetic and logic instructions. Let t_EX denote the time taken by the EX stage to perform the operation for an instruction. For each instruction type, the values of t_EX and M (the number of instructions of that type in a sequence of 100 instructions for a program P), are given in the table below.

The duration of the pipeline clock cycle is 1 nanosecond. Assume that the latch time for the interstage buffers in the pipeline is negligible.

Instruction	tEX (ns)	M
LOAD	1.8	15
IMUL	1.5	10
IDIV	2.5	5
FADD	1.7	10
FSUB	1.7	5
FMUL	2.8	15
FDIV	3.2	5
All other instructions	Less than 1.0	35

When program P is executed, the number of clock cycles for which the pipeline is stalled due to structural hazards in the EX stage is ______. (answer in integer)

Your Answer

Solution

Pipeline clock cycle = 1 ns.
EX stage ko jitne clock cycles chahiye, usmein se 1 cycle normal execution ka hai. Baaki cycles structural hazard ke kaaran stall honge.

Stall cycles per instruction = ⌈t_EX / 1⌉ − 1

Step 1: Calculate stall cycles

Instruction	tEX	Stalls per instruction	Total stalls
LOAD	1.8	1	15
IMUL	1.5	1	10
IDIV	2.5	2	10
FADD	1.7	1	10
FSUB	1.7	1	5
FMUL	2.8	2	30
FDIV	3.2	3	15
All other	<1.0	0	0

Step 2: Add all stall cycles

Total = 15 + 10 + 10 + 10 + 5 + 30 + 15
= 95 clock cycles

Final Answer: 95

GATE 2026 · CS1 Question 61 · NAT

Consider the recursive functions represented by the following code segment:

int bar(int n){
    if (n == 1) return 0;
    else return 1 + bar(n/2);
}

int foo(int n){
    if (n == 1) return 1;
    else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______. (answer in integer)

Note: Ignore syntax errors (if any) in the function.

Your Answer

Solution

Given:
bar(n) = 1 + bar(n/2), when n is not 1.
foo(n) = 1 + foo(bar(n)), when n is not 1.

Step 1: Understand foo(n)

foo(1) = 1
For foo(n) = 5, we need four recursive calls before reaching 1:

n → bar(n) → bar(bar(n)) → bar(bar(bar(n))) → 1

Step 2: Work backwards

bar(2) = 1
bar(4) = 2
bar(16) = 4
bar(65536) = 16

Step 3: Verify the sequence

65536 → 16 → 4 → 2 → 1
foo(1) = 1
foo(2) = 2
foo(4) = 3
foo(16) = 4
foo(65536) = 5

Final Answer: 65536

GATE 2026 · CS1 Question 62 · NAT

The following sequence corresponds to the preorder traversal of a binary search tree T:

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

The position of the element 60 in the postorder traversal of T is ______. (answer in integer)

Note: The position begins with 1.

Your Answer

Solution

Given preorder traversal:

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

Step 1: Construct the BST

BST structure from the given preorder sequence

Step 2: Find postorder traversal

Postorder follows: Left subtree → Right subtree → Root.

Left subtree: 13, 30, 47, 40, 25
Right subtree: 70, 60, 77, 80, 75
Root: 50

Step 3: Complete postorder sequence

1. 13   2. 30   3. 47
4. 40   5. 25   6. 70
7. 60
8. 77   9. 80   10. 75
11. 50

Final Answer: 7

GATE 2026 · CS1 Question 63 · NAT

Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process.

int main () {
    int i;
    for (i = 0; i < 3; i++){
        if (fork() == 0){
            continue;
        }
        break;
    }
    printf("Hello!");
    return 0;
}

The total number of times that the printf statement gets executed is ________. (answer in integer)

Your Answer

Solution

Important points:
• fork() creates a child process.
• In the child process, fork() returns 0, so it executes continue.
• In the parent process, fork() returns a non-zero value, so it executes break.

Step 1: Understand process creation

Each parent process breaks out of the loop; the child continues to the next iteration.

Step 2: Count printf executions

Iteration i = 0: Parent prints once; child continues.

Iteration i = 1: Child's parent prints once; new child continues.

Iteration i = 2: Parent prints once; new child continues.

After i = 2, the final child exits the loop and prints once.

Total = 1 + 1 + 1 + 1 = 4

Final Answer: 4

GATE 2026 · CS1 Question 64 · NAT

Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time t = 10, 20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time t = 11, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at t = 10 seconds.

The average waiting time (in seconds) for the 10 processes is ___________. (rounded off to one decimal place)

Your Answer

Solution

FCFS (First Come First Serve) mein processes arrival time ke order mein execute hote hain.

Step 1: Arrange processes by arrival time

A10 → C11 → A20 → C22 → A30 → C33 → A40 → C44 → A50 → C55

Step 2: Calculate waiting time

Waiting Time = Start Time − Arrival Time

Process	Arrival	Start	Waiting
A	10	10	0
C	11	16	5
A	20	24	4
C	22	30	8
A	30	38	8
C	33	44	11
A	40	52	12
C	44	58	14
A	50	66	16
C	55	72	17

Step 3: Calculate average

Total waiting time = 0 + 5 + 4 + 8 + 8 + 11 + 12 + 14 + 16 + 17
= 95 seconds
Average = 95 / 10
= 9.5 seconds

Correction: The final average from the FCFS schedule is 9.5 seconds.

Final Answer: 9.5

GATE 2026 · CS1 Question 65 · NAT

Consider a relational database schema with a relation R(A, B, C, D). If {A, B} and {A, C} are the only two candidate keys of the relation R, then the number of superkeys of relation R is ______. (answer in integer)

Your Answer

Solution

Given candidate keys:
{A, B} and {A, C}

Step 1: Understand superkeys

A superkey is any set of attributes that contains at least one candidate key.

Step 2: Find superkeys containing AB

{A, B}
{A, B, C}
{A, B, D}
{A, B, C, D}

Total = 4

Step 3: Find superkeys containing AC

{A, C}
{A, B, C}
{A, C, D}
{A, B, C, D}

Total = 4

Step 4: Remove duplicate superkeys

The common superkeys are:

{A, B, C}
{A, B, C, D}

Common = 2

Final calculation

Total superkeys = 4 + 4 − 2
= 6

Final Answer: 6