📚

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 11 of 15 • Questions 101-110 of 142

Q101medium

[GATE CS 2024 Set-1 Q42] Consider the following recurrence relation: √𝑛𝑇(√𝑛)+𝑛 for 𝑛 ≥ 1, 𝑇(𝑛) = { 1 for 𝑛 = 1. Which one of the following options is CORRECT?

A)𝑇(𝑛) = Θ(𝑛 loglog𝑛)

B)𝑇(𝑛) = Θ(𝑛 log𝑛)

C)𝑇(𝑛) = Θ(𝑛2 log𝑛)

D)𝑇(𝑛) = Θ(𝑛2loglog𝑛)

Q102medium

[GATE CS 2024 Set-1 Q43] Consider a binary min-heap containing 105 distinct elements. Let 𝑘 be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of 𝑘 is

A)53

B)52

C)27

D)1 Page 27 of 36 Organizing Institute: IISc Bengaluru Computer Science and Information Technology Set 1 (CS1)

Q103medium

[GATE CS 2024 Set-1 Q44] The symbol → indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

A)(𝑋,𝑌) → (𝑍,𝑊) implies 𝑋 → (𝑍,𝑊)

B)(𝑋,𝑌) → (𝑍,𝑊) implies (𝑋,𝑌) → 𝑍

C)((𝑋,𝑌) → 𝑍 and 𝑊 → 𝑌) implies (𝑋,𝑊) → 𝑍

D)(𝑋 → 𝑌 and 𝑌 → 𝑍) implies 𝑋 → 𝑍

Q104medium

[GATE CS 2024 Set-1 Q45] Let 𝐺 be a directed graph and 𝑇 a depth first search (DFS) spanning tree in 𝐺 that is rooted at a vertex 𝑣. Suppose 𝑇 is also a breadth first search (BFS) tree in 𝐺, rooted at 𝑣. Which of the following statements is/are TRUE for every such graph 𝐺 and tree 𝑇 ?

A)There are no back-edges in 𝐺 with respect to the tree 𝑇

B)There are no cross-edges in 𝐺 with respect to the tree 𝑇

C)There are no forward-edges in 𝐺 with respect to the tree 𝑇

D)The only edges in 𝐺 are the edges in 𝑇 Page 28 of 36 Organizing Institute: IISc Bengaluru Computer Science and Information Technology Set 1 (CS1)

Q105medium

[GATE CS 2024 Set-1 Q46] Consider the following read-write schedule 𝑆 over three transactions 𝑇 , 𝑇 , and 𝑇 , where the subscripts in the schedule indicate transaction IDs: 1 2 3 𝑆: 𝑟 (𝑧); 𝑤 (𝑧); 𝑟 (𝑥); 𝑟 (𝑦); 𝑤 (𝑦); 𝑟 (𝑦); 𝑤 (𝑥); 𝑤 (𝑦); 1 1 2 3 3 2 2 2 Which of the following transaction schedules is/are conflict equivalent to 𝑆 ?

A)𝑇 𝑇 𝑇 1 2 3

B)𝑇 𝑇 𝑇 1 3 2

C)𝑇 𝑇 𝑇 3 2 1

D)𝑇 𝑇 𝑇 3 1 2

Q106medium

[GATE CS 2024 Set-1 Q47] Consider a Boolean expression given by 𝐹(𝑋,𝑌,𝑍) = ∑(3,5,6,7). Which of the following statements is/are CORRECT?

A)𝐹(𝑋,𝑌,𝑍) = Π(0,1,2,4)

B)𝐹(𝑋,𝑌,𝑍) = 𝑋𝑌+𝑌𝑍+𝑋𝑍

C)𝐹(𝑋,𝑌,𝑍) is independent of input 𝑌

D)𝐹(𝑋,𝑌,𝑍) is independent of input 𝑋 Page 29 of 36 Organizing Institute: IISc Bengaluru Computer Science and Information Technology Set 1 (CS1)

Q107medium

[GATE CS 2024 Set-1 Q48] Consider the following C function definition. int f(int x, int y) { for (int i=0; i<y; i++) { x=x+x+y; } return x; } Which of the following statements is/are TRUE about the above function?

A)If the inputs are x=20, y=10, then the return value is greater than 220

B)If the inputs are x=20, y=20, then the return value is greater than 220

C)If the inputs are x=20, y=10, then the return value is less than 210

D)If the inputs are x=10, y=20, then the return value is greater than 220

Q108medium

[GATE CS 2024 Set-1 Q49] Let 𝐴 be any 𝑛×𝑚 matrix, where 𝑚 > 𝑛. Which of the following statements is/are TRUE about the system of linear equations 𝐴𝑥 = 0 ?

A)There exist at least 𝑚−𝑛 linearly independent solutions to this system There exist 𝑚−𝑛 linearly independent vectors such that every solution is a linear

B)combination of these vectors

C)There exists a non-zero solution in which at least 𝑚−𝑛 variables are 0

D)There exists a solution in which at least 𝑛 variables are non-zero Page 30 of 36 Organizing Institute: IISc Bengaluru Computer Science and Information Technology Set 1 (CS1)

Q109medium

[GATE CS 2024 Set-1 Q50] Consider the 5-state DFA 𝑀 accepting the language 𝐿(𝑀) ⊂ (0 + 1)∗ shown below. For any string 𝑤 ∈ (0 + 1)∗ let 𝑛 (𝑤) be the number of 0′𝑠 in 𝑤 and 0 𝑛 (𝑤) be the number of 1′𝑠 in 𝑤. 1 Which of the following statements is/are FALSE?

A)States 2 and 4 are distinguishable in 𝑀

B)States 3 and 4 are distinguishable in 𝑀

C)States 2 and 5 are distinguishable in 𝑀

D)Any string 𝑤 with 𝑛 (𝑤) = 𝑛 (𝑤) is in 𝐿(𝑀) 0 1 Page 31 of 36 Organizing Institute: IISc Bengaluru Computer Science and Information Technology Set 1 (CS1)

Q110medium

[GATE CS 2024 Set-1 Q51] The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let 𝐺 be any graph with 𝑛 vertices and chromatic number 𝑘. Which of the following statements is/are always TRUE?

A)𝐺 contains a complete subgraph with 𝑘 vertices

B)𝐺 contains an independent set of size at least 𝑛/𝑘

C)𝐺 contains at least 𝑘(𝑘−1)/2 edges

D)𝐺 contains a vertex of degree at least 𝑘

......

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