GATE Computer Science & IT 2026 — GATE 2026 · CS · Set 2

For two different persons 𝑥 and 𝑦, the predicate 𝑀(𝑥, 𝑦) 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?

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

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

Which one of the following statements is equivalent to the following assertion? Turing machine 𝑀 decides the language 𝐿 ⊆ {0,1}∗

The probability density function 𝑓(𝑥) of a random variable 𝑋 which takes real values is

Which one of the following statements is correct about the random variable 𝑋 ?

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

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

Which one of the following options is not a property of Boolean Algebra?
(+ denotes OR, . denotes AND, ′ denotes NOT)

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

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?

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

Which one of the following statements is true?

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

Consider a file of size 4 million bytes being transferred between two hosts connected via 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.

What is the total time (in seconds) to transfer the file?
Note: 1M=106 , 1k=103

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

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

Consider the following functions where n is a positive integer:

n1/3, log⁡(n), log⁡(n!), 2log⁡(n)

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

Note: Assume the base of log to be 2.

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

Let R be a binary relation on the set {1,2,…,10}, where (x,y)∈R if the product of x andy is a perfect square.
Which of the following properties are satisfied by R?

For a real number a, let

Which of the following statements is/are true?

In a system, numbers are represented using 4-bit two’s complement form.
N1​=1011, N2​=1101, N3​=1010, N4​=1001
Which of the following operations will result in arithmetic overflow?

Which of the following grammars are ambiguous?

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the hash function:

h(k)=k mod 9

Collisions are resolved by chaining.

After all keys are inserted, the length of the longest chain is:

Consider the system of linear equations:

ax+y=b
16x+ay=24

Suppose the values of a and b are chosen such that the system produces multiple solutions.

The product of a and b is:

Consider an array 𝐴 = [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort algorithm is executed on array 𝐴 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 𝐿 and sorted right array 𝑅 is said to be void if the output of the merge operation is the elements of array 𝐿 followed by the elements of array 𝑅. The number of void merge operations among these 7 merge operations is __________. (answer in integer)

If an IP network uses the subnet mask:

255.255.240.0

The maximum number of IP addresses that can be assigned to network interfaces is:

The 32-bit IEEE 754 single precision representation of a number is:

0xC2710000

The number in decimal representation (rounded to two decimal places) is:

A lexical analyzer uses the following token definitions:

For the string given below,

𝑥1 23𝑚𝑚 78 𝑦 7𝑧 𝑧𝑧5 14𝐴 8𝐻 𝐴𝑎𝑌𝑐𝐷

the number of tokens (excluding 𝑤𝑠) that will be produced by the lexical analyzer is_____________.

Consider a complete graph 𝐾𝑛 with 𝑛 vertices (𝑛 > 4). Note that multiple spanning trees can be constructed over 𝐾𝑛. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets. Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of 𝐾𝑛 ?

Let 𝐺 be a weighted directed acyclic graph with 𝑚 edges and 𝑛 vertices. Given 𝐺 and a source vertex 𝑠 in 𝐺, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from 𝑠 to all vertices that are reachable from 𝑠 in 𝐺?

Consider an array 𝐴 of integers of size 𝑛. The indices of 𝐴 run from 1 to 𝑛. An algorithm is to be designed to check whether 𝐴 satisfies the condition given below
∀𝑖,𝑗 ∈ {1, … , 𝑛 − 1} such that 𝑖 > 𝑗, (𝐴[𝑖 + 1] − 𝐴[𝑖]) > (𝐴[𝑗 + 1] − 𝐴[𝑗])
Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?

Consider a table 𝑇, where the elements 𝑇[𝑖][𝑗], 0 ≤ 𝑖,𝑗 ≤ 𝑛, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:
𝑇[0][𝑘] = 𝑇[𝑘][0] = 1 for 𝑘 = 0,1,2, … , 𝑛
𝑇[𝑖][𝑗] = 2𝑇[𝑖 − 1][𝑗] + 3𝑇[𝑖][𝑗 − 1] for 1 ≤ 𝑖,𝑗 ≤ n
Consider the following two algorithms to compute entries of 𝑇. Assume that for both the algorithms, for all 0 ≤ 𝑖,𝑗 ≤ 𝑛, 𝑇[𝑖][𝑗] has been initialized to 1.
Algorithm 𝐵1: For 𝑖 = 1, 2, … , 𝑛
For 𝑗 = 1, 2, … , 𝑛
𝑇[𝑖][𝑗] = 2𝑇[𝑖 − 1][𝑗] + 3𝑇[𝑖][𝑗 − 1]

Algorithm 𝐵2: For 𝑠 = 2, 3, … , 2𝑛
For 𝑖 = 1, 2, … , 𝑛
For 𝑗 = 1, 2, … , 𝑛
If (𝑖 + 𝑗 == 𝑠)
𝑇[𝑖][𝑗] = 2𝑇[𝑖 − 1][𝑗] + 3𝑇[𝑖][𝑗 − 1]

Algorithm 𝐵𝑘, 𝑘 ∈ {1,2} is said to be correct if and only if it calculates the correct values of 𝑇[𝑖][𝑗], for all 0 ≤ 𝑖,𝑗 ≤ 𝑛, (as per the recursive formulation) at the end of the execution of the algorithm 𝐵𝑘.
Which one of the following statements is true?

Consider the Boolean function:

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

where A is MSB and D is LSB.

What is the minimal sum-of-products form?

Consider the canonical LR(0) parsing of the grammar:

Which one of the following options gives the number of shift-reduce conflicts that will occur in the 𝐿𝑅(0) ACTION table?

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 𝑋, 𝑌, and 𝑍 as sets of attributes over a relational schema. The three rules of Armstrong’s Axioms are described as follows
Reflexivity: If 𝑌 ⊆ 𝑋 , then 𝑋 → 𝑌
Augmentation: If 𝑋 → 𝑌, then 𝑋𝑍 → 𝑌𝑍 for any Z
Transitivity: If 𝑋 → 𝑌 and 𝑌 → 𝑍, then 𝑋 → Z
The additional rule of Union is defined as follows.
Union: If 𝑋 → 𝑌 and 𝑋 → 𝑍, then 𝑋 → 𝑌𝑍

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 ?

Consider the transmission of data bits 110001011 over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be 1001, which one of the following options shows the remainder bit pattern appended to the data bits before transmission?

Consider a processor with 16 general-purpose registers and a 2-byte instruction format for every instruction. Variable-sized prefix opcodes are permitted. There are three instruction types: M-type, R-type, and C-type. Each M-type instruction has two register operands and a 6-bit immediate operand. Each R-type instruction has three register operands. Each C-type instruction has one register operand and a 6-bit offset. If there are 2 unique M-type opcodes and 7 unique R-type opcodes, what is the maximum possible number of unique C-type opcodes?

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?

An index in a DBMS is said to be dense if an index entry appears for every search-key value in the indexed file. Otherwise it is called a sparse index. Consider the following two statements.
S1: A hash index must be a dense index
S2: A 𝐵 + tree index can be a sparse index
Which one of the following options is correct?

Consider the following two finite automata 𝐷1 and 𝐷2

Which of the following statements is/are true?

Let Σ = {𝑎, 𝑏, 𝑐, 𝑑} and let 𝐿 = {𝑎 𝑖𝑏 𝑗 𝑐 𝑘𝑑 ℓ ∣ 𝑖,𝑗, 𝑘, ℓ ≥ 0}. Which of the following constraints ensure(s) that the language 𝐿 is context-free?

Consider a binary search tree (BST) with 𝑛 leaf nodes (𝑛 > 0). Given any node 𝑉, the key present in the node is denoted as 𝑉𝑎𝑙(𝑉). All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node 𝑉, let 𝑆𝑢𝑐(𝑉) denote the node that is its inorder successor. If a node 𝑉 does not have an inorder successor, then 𝑆𝑢𝑐(𝑉) is 𝑁𝑈𝐿𝐿. As there are no duplicates, if 𝑆𝑢𝑐(𝑉) is not 𝑁𝑈𝐿𝐿, then 𝑉𝑎𝑙(𝑉) < 𝑉𝑎𝑙(𝑆𝑢𝑐(𝑉)).

Corresponding to every leaf node 𝐿𝑖 that has a non-NULL 𝑆𝑢𝑐(𝐿𝑖), a new key 𝑘𝑖 with the following property is to be inserted into the BST.
𝑉𝑎𝑙(𝐿𝑖) < 𝑘𝑖 < 𝑉𝑎𝑙(𝑆𝑢𝑐(𝐿𝑖))
Let 𝐾 represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?

Consider a stack 𝑆 and a queue 𝑄. Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to 𝑆 (pushed on 𝑆 ) or to 𝑄 (enqueued to 𝑄). Once all the five elements are stored, the output is generated in two steps. First, stack S is emptied by popping all elements. Then queue 𝑄 is emptied by dequeueing all elements. The output obtained by following this process is 4 3 1 2 5 .

Given the output, the objective is to predict whether an element was assigned to 𝑆 or 𝑄.
Which of the following options is/are possible valid assignment(s) of the elements?

Note: In the options, the notation 𝑥𝑆 denotes that element 𝑥 was assigned to 𝑆 and 𝑦𝑄 denotes that element 𝑦 was assigned to 𝑄.

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?

Consider a system with a processor and a 4 KB direct mapped cache with block size of 16 bytes. The system has a 16 MB physical memory. Four words P, Q, R, and S are accessed by the processor in the same order 10 times. That is, there are a total of 40 memory references in the sequence P, Q, R, S, P, Q, R, S,…

Assume that the cache memory is initially empty. The physical addresses of the words are given below (1 word =1 byte).

P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32
Which of the following statements is/are true

Note: 1K=210 and 1M=220

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: 1K=2¹⁰ and 1G=2³⁰

A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB. TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entries. The paging system uses pages of size 4 KB. The virtual address space is 64 GB and physical address space is 1 GB. If each TLB entry stores a 4-bit process id, page number, frame number, and a 2-bit control field, then the size of the TLB (in bytes) is ___________. (answer in integer)
Note: 1K=2¹⁰, 1M=2²⁰, 1G=2³⁰

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order, and they are allocated memory using the best-fit technique. After allocating space to P1 and P2, the number of holes of size less than 8 KB is ____________. (answer in integer)
Note: 1K=2¹⁰

Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache, with block numbers starting from 0. The word with physical address 0xA2C28 is mapped to the cache block number 17610. The maximum possible size of the cache (in KB) for this configuration is ___________. (answer in integer)

Note: 1K=210 and 1M=220

A non-pipelined instruction execution unit that operates at 1.6 GHz clock takes an average of 5 clock cycles to complete the execution of an instruction. To improve the performance, the system was pipelined with a goal of achieving an average throughput of one instruction per clock cycle. However, it could operate only at 1.2 GHz due to pipeline overheads. While executing a program in the pipelined design, 30% of instructions encountered a stall of 2 cycles due to pipeline hazards. The speed-up obtained by the pipelined design over the non-pipelined one for this program is ___________. (rounded off to two decimal places)
Note: 1G=10⁹

Consider a new TCP connection between a sender and a receiver. The receiver advertised window is constant at 48 KB, the maximum segment size (MSS) is 2 KB, and the slow start threshold for TCP congestion control is 16 KB. Assume that there are no timeouts or duplicate acknowledgements. The number of rounds of transmission required for the congestion control algorithm of the TCP connection to reach the congestion avoidance phase is ___________. (answer in integer)
Note: 1K=2¹⁰

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]

Consider the following ANSI-C program.

The output of this program is ____________. (answer in integer)
Note: Assume that the program compiles and runs successfully.

Consider the following ANSI-C function.

The maximum possible value that can be returned from this function is ____________. (answer in integer)
Note: Ignore syntax errors (if any) in the function.

The determinant of a 4 × 4 matrix A is 3. The value of the determinant of 2A is ____________. (answer in integer)

Suppose an unbiased coin is tossed 6 times. Each coin toss is independent of all previous coin tosses. Let 𝐸1 be the event that among the second, fourth, and sixth coin tosses, there are at least two heads. Let 𝐸2 be the event that among the first, second, third, and fifth coin tosses, there are equal number of heads and tails. The conditional probability P(𝐸1 | 𝐸2) is equal to ____________. (rounded off to one decimal place)

Consider a function 𝑓: (0,1) → {0, 1} defined as follows. For a real number 𝑟 ∈ (0,1) , 𝑓(𝑟) = 1 if the second digit after the decimal point in 𝑟 is one of the four digits 2, 3, 6 and 7. Otherwise, 𝑓(𝑟) is equal to 0. The number of points in (0,1) at which 𝑓 is discontinuous is ___________. (answer in integer)

It is necessary to design a link-layer protocol between two hosts that are directly connected over a lossless link of length 3000 kilometers. Assume that the link bandwidth is 108 bits per second and that the propagation delay in the link is 5 nanoseconds per meter (that is, a signal takes 5 ns to travel each meter of the link). Every transmitted data byte is assigned a unique sequence number.

Let 𝑁 be the minimum number of bits needed for the sequence number field in the protocol header such that

i. the sequence numbers do not wrap around before 60 seconds, and

ii. the maximum utilization of the link is achieved.

The value of 𝑁 is ______. (answer in integer)

Expedite, Hasten, Hurry, ________

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

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 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?

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:

• Stock A = Rs. 55

• Stock B = Rs. 70

The profit made by the investor is Rs. ________

“When it is raining, peacocks dance.”

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

Water : P :: Food : Q

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

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

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 remaining city exactly once

• Return to the starting city

Which one of the following options is true?

The figure in Panel I is a 4×4 grid.

The numbers on the top and left represent the number of cells to be shaded in that column and row respectively.

Which one of the options in Panel II represents the correctly shaded grid?

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 ________