📚

GATE CS - Previous Year Questions

Actual GATE CS exam questions from previous years (2020-2025)

142 questionsâ€¢15 pagesâ€¢~213 min

Use this quiz track to strengthen recall, speed, and exam-style decision making. Attempt one page first, review explanations, and then re-attempt incorrect questions without notes.

A good scoring strategy is to mark uncertain questions, finish known ones quickly, and return with elimination logic. This improves accuracy while keeping momentum under time constraints.

Progress: 0 / 1420%

Page 6 of 15 • Questions 51-60 of 142

Q51medium

[GATE CS 2025 Set-2 Q28] Which of the following is/are part of an Instruction Set Architecture of a processor?

A)The size of the cache memory

B)The clock frequency of the processor

C)The number of cache memory levels

D)The total number of registers

Q52medium

[GATE CS 2025 Set-2 Q29] Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

A)A DFS tree of 𝐺 is a Shortest Path tree of 𝐺.

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

C)If (𝑢,𝑣) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex 𝑠 to 𝑢 and 𝑣 in the BFS tree are within ±1 of each other.

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

Q53medium

[GATE CS 2025 Set-2 Q30] Consider the two lists List I and List II given below: List I List II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complementation (iii) Regular languages (c) Closed under intersection For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

A)(i) – (a), (ii) – (b), and (iii) – (c)

B)(i) – (b), (ii) – (a), and (iii) – (c)

C)(i) – (b), (ii) – (c), and (iii) – (a)

D)(i) – (a), (ii) – (c), and (iii) – (b)

Q54medium

[GATE CS 2025 Set-2 Q31] Consider the following logic circuit diagram. Which is/are the CORRECT option(s) for the output function 𝐹?

A)𝑋̅̅̅ ̅𝑌̅

B)𝑋̅ +𝑌̅ + 𝑋𝑌̅

C)𝑋̅̅̅ ̅𝑌̅ +𝑋̅ + 𝑋𝑌̅

D)𝑋 + 𝑌̅

Q55medium

[GATE CS 2025 Set-2 Q36] Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and the propagation delay between the two nodes is 100 milliseconds. Assume that the processing times at the source and destination are negligible. Also, assume that the size of the acknowledgement packet is negligible. Which ONE of the following most accurately gives the channel utilization for the above scenario in percentage?

A)88.23

B)93.75

C)85.44

D)66.67

Q56medium

[GATE CS 2025 Set-2 Q37] Let 𝐺 be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant 𝛼 is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in 𝐺 before and after the edge weight update?

A)Every MST remains an MST, and every SP remains an SP.

B)MSTs need not remain MSTs, and every SP remains an SP.

C)Every MST remains an MST, and SPs need not remain SPs.

D)MSTs need not remain MSTs, and SPs need not remain SPs.

Q57medium

[GATE CS 2025 Set-2 Q38] A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly linked list with pointers to the head node and tail node of the list. Q: Min-heap implemented using an array. R: Binary Search Tree. Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size 𝑛 of these data structures?

A)P: Θ(1), Q: Θ(𝑛), R: Θ(𝑛)

B)P: Θ(1), Q: Θ(𝑛log𝑛), R: Θ(𝑛)

C)P: Θ(𝑛), Q: Θ(𝑛log𝑛), R: Θ(𝑛2)

D)P: Θ(1), Q: Θ(𝑛), R: Θ(𝑛log𝑛)

Q58medium

[GATE CS 2025 Set-2 Q39] For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block. Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?

A)64 KB and 4 KB

B)128 KB and 16 KB

C)64 KB and 8 KB

D)128 KB and 6 KB

Q59medium

[GATE CS 2025 Set-2 Q40] Given a Context-Free Grammar 𝐺 as follows: 𝑆 → 𝐴𝑎 | 𝑏𝐴𝑐 | 𝑑𝑐 | 𝑏𝑑𝑎 𝐴 → 𝑑 Which ONE of the following statements is TRUE?

A)𝐺 is neither LALR(1) nor SLR(1)

B)𝐺 is CLR(1), not LALR(1)

C)𝐺 is LALR(1), not SLR(1)

D)𝐺 is LALR(1), also SLR(1)

Q60medium

[GATE CS 2025 Set-2 Q41] An array 𝐴 of length 𝑛 with distinct elements is said to be bitonic if there is an index 1 ≤ 𝑖 ≤ 𝑛 such that 𝐴[1..𝑖] is sorted in the non-decreasing order and 𝐴[𝑖 +1 ..𝑛] is sorted in the non-increasing order. Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array 𝐴?

A)Θ(𝑛)

B)Θ(1)

C)Θ(log2𝑛)

D)Θ(log𝑛)

......

Quiz Pages

Navigate directly to paginated quiz sets. These links help you revise by page and make every page discoverable.

Page 1 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7 Page 8 Page 9 Page 10 Page 11 Page 12 Page 13 Page 14 Page 15