67 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.
Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.
Showing 67 of 67 questions · 0 correct of 0 attempted · marks 0 / 103
GATE 2025 CS1 · Q18MCQ1 markGraph Algorithms
Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices u and v, let d1(u, v) and d2(u, v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v?
Consider the following recurrence relation: T(n) = 2T(n − 1) + n·2n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?
GATE 2025 CS2 · Q29MSQ1 markGraph Algorithms
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q33NAT1 markSorting & Searching
The pseudocode of a function fun() is given below:
fun(int A[0..n−1]) {
for i = 0 to n − 2: for j = 0 to n − i − 2: if (A[j] > A[j + 1]) then swap A[j] and A[j + 1]
}
Let A[0..29] be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with A[0..29] as argument, is ______.
GATE 2025 CS2 · Q37MCQ2 marksGraph Algorithms
Let G 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 G before and after the edge weight update?
GATE 2025 CS2 · Q41MCQ2 marksSorting & Searching
An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] 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?
GATE 2025 CS1 · Q43MCQ2 marksGraph Algorithms
Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value of d(u, v), u, v ∈ V such that u ≠ v, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?
Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n − 1) − 6T(n − 2) for n ≥ 2. Which one of the following statements is TRUE?
Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
GATE 2024 CS1 · Q34NAT1 markGraph Algorithms
The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is ______.
Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array [2, 5, 3, 1, 4, 2, 6] is ______.
Consider an array X that contains n positive integers. A subarray of X is a sequence of array locations with consecutive indices. The C code snippet below computes the length of the longest subarray of X that contains at most two distinct integers, with two missing expressions (P) and (Q):
int first = 0, second = 0, len1 = 0, len2 = 0, maxlen = 0;
for (i = 0; i < n; i++) {
if (X[i] == first) {
len2++;
len1++;
} else if (X[i] == second) {
len2++;
len1 = (P);
second = first;
} else {
len2 = (Q);
len1 = 1;
second = first;
}
if (len2 > maxlen) maxlen = len2;
first = X[i];
}
(Hint: at the end of the i-th iteration, len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)
GATE 2024 CS1 · Q45MSQ2 marksGraph Algorithms
Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following statements is/are TRUE for every such graph G and tree T?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q51MSQ2 marksGraph Algorithms
Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q60NAT2 marksGraph Algorithms
The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is ______.
Consider functions Function 1 and Function 2 expressed in pseudocode as follows. Function 1: while n > 1 do { for i = 1 to n do x = x + 1; n = ⌊n/2⌋ }. Function 2: for i = 1 to 100·n do x = x + 1. Let f1(n) and f2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively. Which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q55MSQ2 marksGraph Algorithms
Let G be a simple, finite, undirected graph with vertex set {v1, …, vn}. Let Δ(G) denote the maximum degree of G and let N = {1, 2, …} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1, …, n: color(vi) ← min{ j ∈ N : no neighbour of vi is colored j }. Which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q56NAT2 marksGraph Algorithms
Let U = {1, 2, 3}. Let 2U denote the powerset of U. Consider an undirected graph G whose vertex set is 2U. For any A, B ∈ 2U, (A, B) is an edge in G if and only if (i) A ≠ B, and (ii) either A ⊊ B or B ⊊ A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A). If ∅ denotes the empty set, then the cardinality of B(∅) is ______.
Which one of the following statements is TRUE for all positive functions f(n)?
GATE 2022 · Q30NAT1 markGraph Algorithms
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ______.
GATE 2022 · Q37MCQ2 marksGraph Algorithms
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
GATE 2022 · Q49MSQ2 marksGraph Algorithms
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
Consider the following recurrence: f(1) = 1; f(2n) = 2f(n) − 1, for n ≥ 1; f(2n + 1) = 2f(n) + 1, for n ≥ 1. Then, which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2022 · Q52MSQ2 marksGraph Algorithms
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q2MCQ1 markSorting & Searching
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?
GATE 2021 Set 1 · Q3MCQ1 markAsymptotic Analysis & Recurrences
Consider the following three functions: f1 = 10n, f2 = nlog n, f3 = n√n. Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
GATE 2021 Set 1 · Q9MCQ1 markSorting & Searching
Consider the following array: 23 32 45 69 72 73 89 97. Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
GATE 2021 Set 1 · Q16NAT1 markGraph Algorithms
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______.
GATE 2021 Set 1 · Q17NAT1 markGraph Algorithms
Consider the following undirected graph with edge weights as shown. The graph is a 3 × 3 grid of nine vertices. Top row: edges 0.1 and 0.1. Top-to-middle verticals: 0.9, 0.9, 0.9. Middle row: edges 0.1 and 0.9. Middle-to-bottom verticals: 0.1, 0.1, 0.1. Bottom row: edges 0.9 and 0.1. The number of minimum-weight spanning trees of the graph is ______.
GATE 2021 Set 1 · Q36MCQ2 marksGraph Algorithms
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as diam(G) = max over u, v ∈ V of {the length of the shortest path between u and v}. Let M be the adjacency matrix of G. Define graph G2 on the same set of vertices with adjacency matrix N, where Nij = 1 if Mij > 0 or Pij > 0, where P = M², and 0 otherwise. Which one of the following statements is true?
Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices: p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18. Which of the following statements is/are correct about R7?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q41MSQ2 marksGraph Algorithms
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?
One or more options may be correct. Select all that apply, then submit.
For parameters a and b, both of which are ω(1), T(n) = T(n1/a) + 1, and T(b) = 1. Then T(n) is
GATE 2020 · Q31MCQ2 marksGraph Algorithms
Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) ∈ V × V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
GATE 2020 · Q40MCQ2 marksGraph Algorithms
Let G = (V, E) be a directed, weighted graph with weight function w: E → ℝ. For some function f: V → ℝ, for each edge (u, v) ∈ E, define w'(u, v) as w(u, v) + f(u) − f(v). Which one of the options completes the following sentence so that it is TRUE? "The shortest paths in G under w are shortest paths under w' too, ______."
GATE 2020 · Q49NAT2 marksGraph Algorithms
Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i − j|. The weight of minimum spanning tree of G is ______.
GATE 2019 Set 2 · Q20NAT1 markSorting & Searching
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ______.
Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0]. The subsequence sum S(i, j) = Σk=i..j A[k]. Determine the maximum of S(i, j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used.) Answer: ______.
GATE 2019 Set 2 · Q37MCQ2 marksSorting & Searching
There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is
GATE 2019 Set 2 · Q38MCQ2 marksGraph Algorithms
Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?
GATE 2018 · Q30MCQ2 marksGraph Algorithms
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u, v) of G, if u is at depth i and v is at depth j in TB, then |i − j| = 1. Which of the statements above must necessarily be true?
Assume that multiplying a matrix G1 of dimension p × q with another matrix G2 of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G1G2…Gn can be done by parenthesizing in different ways. Define GiGi+1 as an explicitly computed pair for a given parenthesization if they are directly multiplied. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2 × 25, 25 × 3, 3 × 16, 16 × 1 and 1 × 1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pair(s) is/are
GATE 2018 · Q43NAT2 marksGraph Algorithms
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y + 10z = ______.
Consider the weights and values of items listed below. Note that there is only one unit of each item. Items (weight in Kg, value in rupees): 1 (10, 60), 2 (7, 28), 3 (4, 20), 4 (2, 24). The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. The value of Vopt − Vgreedy is ______.
GATE 2017 Set 1 · Q4MCQ1 markAsymptotic Analysis & Recurrences
Consider the following functions from positive integers to real numbers: 10, √n, n, log2 n, 100/n. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
GATE 2017 Set 1 · Q20NAT1 markGraph Algorithms
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ______.
GATE 2017 Set 1 · Q26MCQ2 marksGraph Algorithms
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum Spanning Tree of G is always unique. (II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?
GATE 2016 Set 1 · Q13MCQ1 markSorting & Searching
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
GATE 2016 Set 1 · Q14MCQ1 markGraph Algorithms
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change. Q: Shortest path between any pair of vertices does not change.
GATE 2016 Set 1 · Q27NAT2 marksAsymptotic Analysis & Recurrences
Consider the recurrence relation a1 = 8, an = 6n² + 2n + an−1. Let a99 = K × 104. The value of K is ______.
GATE 2016 Set 1 · Q38NAT2 marksGraph Algorithms
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry Wij in the matrix W = [[0, 2, 8, 5], [2, 0, 5, 8], [8, 5, 0, x], [5, 8, x, 0]]. The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ______.
GATE 2016 Set 1 · Q39NAT2 marksGraph Algorithms
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is ______.
GATE 2016 Set 1 · Q40MCQ2 marksGraph Algorithms
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e. II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.
GATE 2014 Set 1 · Q3MCQ1 markGraph Algorithms
Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
GATE 2014 Set 1 · Q11MCQ1 markGraph Algorithms
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
GATE 2014 Set 1 · Q14MCQ1 markSorting & Searching
Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
GATE 2014 Set 1 · Q39NAT2 marksSorting & Searching
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ______.
GATE 2014 Set 1 · Q42MCQ2 marksAsymptotic Analysis & Recurrences
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2; for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3
A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1, 1, 2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1, 1)} and the set of all 3-pennants is {(2, 1), (1, 1, 1), (1, 2)}. Note that the pennant (1, 2) is not the same as the pennant (2, 1). The number of 10-pennants is ______.
GATE 2013 Code A · Q19MCQ1 markGraph Algorithms
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
GATE 2013 Code A · Q25MCQ1 markGraph Algorithms
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
GATE 2013 Code A · Q31MCQ2 marksAsymptotic Analysis & Recurrences
Consider the following function:
int unknown(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j*2) k = k + n/2;
return (k);
}
The return value of the function is
GATE 2012 Code A · Q16MCQ1 markAsymptotic Analysis & Recurrences
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
GATE 2012 Code A · Q17MCQ1 markGraph Algorithms
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
GATE 2012 Code A · Q18MCQ1 markAsymptotic Analysis & Recurrences
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?