What DFS discovery/finish time options NEVER occur on a DAG in GATE 2026 CS Set 1?

The correct answers are B and D. For a DAG (no cycles), DFS produces only tree edges and forward edges — no back edges or cross edges within a DFS tree. For an edge (u,v) in the DAG: Option A (d[u]<d[v]<f[v]<f[u]) is possible (tree/forward edge). Option C (d[v]<f[v]<d[u]<f[u]) is possible (cross edge — v finishes before u starts). Option B (d[v]<d[u]<f[u]<f[v]) would mean u is a descendant of v, requiring a path v→u, but combined with edge (u,v) this creates a cycle — impossible in a DAG. Option D (d[u]<d[v]<f[u]<f[v]) means u finishes before v finishes but after v starts — impossible for tree/forward edge in DFS (u must finish after all its descendants).

What are the true statements about 2-colorable graphs in GATE 2026 CS Set 1?

The correct answers are B and C. B: A 2-colorable (bipartite) graph MAY contain cycles of even length — TRUE (bipartite graphs can have even cycles, e.g., a 4-cycle is bipartite). C: Testing 2-colorability using BFS/DFS runs in Θ(|V|+|E|) time with adjacency list — TRUE. A is FALSE (2-colorable graphs cannot have odd cycles — this is the defining theorem of bipartite graphs). D is FALSE (the optimal algorithm is Θ(|V|+|E|), not Θ(|E|log|V|)).

What is the vertex cover constraint for v to always be in S in GATE 2026 CS Set 1?

The correct answer is Option A: The degree of v is at least k+1. If deg(v) ≥ k+1, vertex v has more than k neighbors. Any vertex cover must cover all edges incident to v. If v is not in the cover, then all k+1 or more neighbors of v must be in the cover — but the minimum vertex cover has size k. This is a contradiction. Therefore v must be in every minimum vertex cover S of size k.

CS and IT Gate 2026 Set-1 Questions with Answer

Q: What are the true statements about 2-colorable graphs in GATE 2026 CS Set 1?

The correct answers are B and C. B: A 2-colorable (bipartite) graph MAY contain cycles of even length — TRUE (bipartite graphs can have even cycles, e.g., a 4-cycle is bipartite). C: Testing 2-colorability using BFS/DFS runs in Θ(|V|+|E|) time with adjacency list — TRUE. A is FALSE (2-colorable graphs cannot have odd cycles — this is the defining theorem of bipartite graphs). D is FALSE (the optimal algorithm is Θ(|V|+|E|), not Θ(|E|log|V|)).

Q: What is the vertex cover constraint for v to always be in S in GATE 2026 CS Set 1?

The correct answer is Option A: The degree of v is at least k+1. If deg(v) ≥ k+1, vertex v has more than k neighbors. Any vertex cover must cover all edges incident to v. If v is not in the cover, then all k+1 or more neighbors of v must be in the cover — but the minimum vertex cover has size k. This is a contradiction. Therefore v must be in every minimum vertex cover S of size k.

1 2 3 4 5

Ques 14 GATE 2026 SET-1

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

The server cannot initiate closing of the connection before the client initiates closing of the connection

The client and server can initiate closing of the connection at the same time

The client and server use a two-way handshake mechanism before the start of data transmission

The TCP connection is half duplex.

(b) is the correct answer.

Option A — False.
Either the client or the server can initiate the closing of a TCP connection. TCP uses a 4-way handshake (FIN, ACK, FIN, ACK) for connection termination and either side is free to send the first FIN. It is not restricted to the client only.
Option B - True.
TCP supports simultaneous close. Both the client and server can send a FIN segment at the same time without waiting for the other side to initiate first. This is a valid and well-defined scenario in TCP's connection termination process.
Option C - False.
TCP uses a 3-way handshake (SYN, SYN-ACK, ACK) before data transfer begins — not a 2-way handshake. A 2-way handshake is insufficient for TCP as it cannot confirm that both sides are ready to communicate reliably.
Option D - False.
TCP is a full duplex protocol. Data can be sent and received simultaneously in both directions over the same connection. Half duplex would mean only one side can transmit at a time.
The correct statement is B - The client and server can initiate closing of the connection at the same time (Option B)

Ques 15 GATE 2026 SET-1

Consider the implementation of sliding window protocol over a lossless link, with a window size of 𝑊 frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (1 k = 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 𝑊 (in number of frames) required to achieve 100% link utilization?

(a) is the correct answer.

The correct answer is Option A: 21 frames.
To achieve 100% link utilization, the sender must keep transmitting without ever going idle while waiting for an acknowledgement.
Transmission time of one frame:
T_t = Frame size / Bandwidth = 1000 bits / 100,000 bps = 10 ms
Round Trip Time (RTT):
RTT = 2 × Propagation delay = 2 × 100 ms = 200 ms
(ACK transmission time = 0, processing time = 0)
Minimum window size for 100% utilization:
W = (T_t + RTT) / T_t = (10 + 200) / 10 = 210 / 10 = 21 frames
With W = 21, the sender continuously transmits 21 frames in the time it takes for the first ACK to arrive back, keeping the link fully busy at all times.

Ques 16 GATE 2026 SET-1

Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from one track to an adjacent track is 2 ms. The average seek time is 5 ms. The disk has 400 sectors per track.

The average time to read a random sector is _______. (answer in integer, in ms)

(7) is the correct answer.

Ques 17 GATE 2026 SET-1

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.

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)

(165) is the correct answer.

Ques 18 GATE 2026 SET-1

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 (Addressing Mode)	List-II (Description)
P. Immediate	1. Element of an array
Q. Indirect	2. Pointer
R. Base with index	3. Element of a record
S. Base with offset	4. Constant

P-3, Q-1, R-3, S-1

P-4, Q-2, R-1, S-3

P-1, Q-2, R-4, S-3

P-2, Q-1, R-3, S-4

(b) is the correct answer.

Analysing each addressing mode:
P. Immediate → 4. Constant
In immediate addressing, the operand is directly embedded in the instruction itself. This is used to represent a constant value. Example: MOV R1, #5 (5 is a constant).
Q. Indirect → 2. Pointer
In indirect addressing, the address field contains a pointer — the address of a memory location that holds the actual address of the operand. This is exactly how pointers work.
R. Base with index → 1. Element of an array
Base register holds the starting address of an array and the index register holds the offset for each element. This is the classic way to access array elements. Example: Base + Index = address of arr[i].
S. Base with offset → 3. Element of a record
Base register holds the starting address of a record (struct) and a fixed offset is used to access a specific field within it. This is how struct members are accessed in memory.
The correct match is P-4, Q-2, R-1, S-3 (Option B)

Ques 19 GATE 2026 SET-1

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.

Load R₀, x
Load R₁, y
ADD R₂, R₀, R₁
Store Z, R₂

Load R₀, x
ADD Z, R₀, y

ADD R₀, x, y
Store Z, R₀

ADD Z, x, y

(a) is the correct answer.

The correct answer is Option A.
In a load-store architecture, arithmetic and logic instructions can only operate on register operands — they cannot directly access memory. Memory is accessed exclusively through Load (memory → register) and Store (register → memory) instructions. This is the fundamental characteristic of RISC-style processors.
To compute z = x + y where x, y, z are memory operands, the correct sequence is:
Load R0, x - bring x from memory into register R0
Load R1, y - bring y from memory into register R1
ADD R2, R0, R1 - add R0 and R1, store result in R2 (first operand R2 is the destination)
Store Z, R2 - write result from R2 back to memory location z
This is exactly Option A and it correctly follows all load-store rules.
Option B - ADD Z, R0, y: uses memory operand y directly in ADD. Not allowed in load-store ISA.
Option C - ADD R0, x, y: uses two memory operands in ADD. Not allowed.
Option D - ADD Z, x, y: uses memory as both operands and destination in ADD. Not allowed.
The rule is simple - in load-store ISA, ADD never touches memory. Load and Store are the only instructions that do.

Ques 20 GATE 2026 SET-1

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

Write-after-write

Read-after-write

Write-after-read

Write-after-write

The correct answer is Option C: Read-after-write.
Among all register dependencies, RAW is the one that causes a true data hazard in a pipelined processor. It happens when a later instruction needs to read a register that an earlier instruction is still in the process of writing. Since the pipeline overlaps instruction execution, the later instruction may read a stale (old) value before the write is completed - this is a genuine hazard.
Here"s a quick summary of all four dependencies:
• RAW (Read after Write): True data dependency - causes real hazards. The pipeline must stall or use data forwarding to resolve it.
• WAR (Write after Read): Anti-dependency - not a hazard in a simple in-order pipeline since the read always happens before the write in program order.
• WAW (Write after Write): Output dependency - not a hazard in a basic in-order pipeline; writes complete in program order.
• RAR (Read after Read): Not a dependency at all - reading a register from multiple instructions simultaneously causes no conflict whatsoever.

Ques 21 GATE 2026 SET-1

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?

35C80000

35CC0000

35E80000

35EC0000

(b) is the correct answer.

Ques 22 GATE 2026 SET-1

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?

N = M + L

N = M − L

N = M + K

N = M − K

(a) is the correct answer.

Ques 23 GATE 2026 SET-1

The following sequence corresponds to the preorder traversal of a binary search tree T:
50, 25, 13, 10, 30, 60, 55, 70, 65, 80, 75, 90

The position of the element 60 in the postorder traversal of T is ______. (answer in integer)
Note: The position begins with 1.

(11) is the correct answer.

Ques 24 GATE 2026 SET-1

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?

(n + 1) / 2

(n − 1) / 2

(n − 3) / 2

(b,c) is the correct answer.

Ques 25 GATE 2026 SET-1

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,b) is the correct answer.

Ques 26 GATE 2026 SET-1

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)

(11) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2026 Set-1 Questions with Answer

Question Options

Sign in to ExamPrev