Explore topic-wise MCQs in Data Structures and Algorithms.

This section includes 28 Mcqs, each offering curated multiple-choice questions to sharpen your Data Structures and Algorithms knowledge and support exam preparation. Choose a topic below to get started.

1.

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

A. Θ(|E| + |V|)
B. Θ(|E||V|)
C. Θ(|E| log |V|)
D. Θ(|V|)
Answer» E.
Discussion
2.

Depth First Search graph search algorithm uses _______ data structure for its implementation.

A. Dequeue
B. Queue
C. tree
D. Stack
Answer» E.
Discussion
3.

Consider a directed graph G = {V, E} with vertex set V = {A, B, C, D} and edge set E = {AB, AC, BC, BD, DC}. Which of the following is a valid topological ordering of graph G?

A. ABCD
B. BACD
C. BADC
D. ABDC
Answer» E.
Discussion
4.

G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?

A. v2v4
B. v1v4
C. v4v5
D. v3v4
Answer» C. v4v5
Discussion
5.

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 option is/are correct?

A. If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
B. Root of T is an articulation point in G if and only if it has 2 or more children.
C. Root of T can never be an articulation point in G.
D. A leaf of T can be an articulation point in G.
Answer» C. Root of T can never be an articulation point in G.
Discussion
6.

Consider the directed graph given below.Which one of the following is TRUE?

A. The graph does not have any topological ordering
B. Both PQRS and SRQP are topological orderings
C. Both PSRQ and SPRQ are topological orderings
D. PSRQ is the only topological ordering
Answer» D. PSRQ is the only topological ordering
Discussion
7.

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 changeQ: Shortest path between any pair of vertices does not change

A. P only
B. Q only
C. Neither P nor Q
D. Both P and Q
Answer» B. Q only
Discussion
8.

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?

A. I only
B. II only
C. Both I and II
D. Neither I nor II
Answer» D. Neither I nor II
Discussion
9.

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 if u is at depth i and v is at depth j in TB , then |

A. I only
B. II only
C. Both I and II
D. Neither I nor II
Answer» B. II only
Discussion
10.

A weighted complete graph with n vertices has weight 2|i - j| at edges (vi, vj). The weight of a minimum spanning tree is

A. \(\frac{{{n^2}}}{2}\)
B. \(\frac{n}{2}\)
C. 2n - 2
D. n - 2
Answer» D. n - 2
Discussion
11.

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?

A. I only
B. II only
C. Both I and II
D. Neither I nor II
Answer» B. II only
Discussion
12.

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 eII. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

A. I only
B. II only
C. both I and II
D. neither I nor II
Answer» C. both I and II
Discussion
13.

Let G be a connected undirected weighted graph. Consider the following two statements.S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?

A. S1 is false and S2 is true.
B. S1 is true and S2 is false.
C. Both S1 and S2 are true.
D. Both S1 and S2 are false.
Answer» B. S1 is true and S2 is false.
Discussion
14.

Consider the graph given below: Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is?

A. AD, AE, AG, GC, GB, BF
B. GC, GB, BF, GA, AD, AE
C. GC, AD, GB, GA, BF, AE
D. AD, AG, GC, AE, GB, BF
Answer» D. AD, AG, GC, AE, GB, BF
Discussion
15.

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?

A. Θ (n)
B. Θ (n + m)
C. Θ (n2)
D. Θ (m2)
Answer» D. Θ (m2)
Discussion
16.

Given below are some algorithms, and some algorithm design paradigms.1. Dijkstra’s Shortest Pathi. Divide and Conquer2. Floyd-Warshall algorithm to compute all pairs shortest pathii. Dynamic Programming3. Binary search on a sorted arrayiii. Greedy design4. Backtracking search on a graphiv. Depth-first search v. Breadth-first search Match the above algorithms on the left to the corresponding design paradigm they follow.

A. 1 – i, 2 – iii, 3 – i, 4 – v.
B. 1 – iii, 2 – iii, 3 – i, 4 – v.
C. 1 – iii, 2 – ii, 3 – i, 4 – iv.
D. 1 – iii, 2 – ii, 3 – i, 4 – v.
Answer» D. 1 – iii, 2 – ii, 3 – i, 4 – v.
Discussion
17.

Let G be a simple undirected graph, TD be a DFS tree on G, and TB be the BFS tree on G.Consider the following statements.Statement I: No edge of G is a cross with respect to TDStatement 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. In the light of the above statements, choose the correct answer from the options given below

A. Both Statement I and Statement II are true
B. Both Statement I and Statement II are false
C. Statement I is correct but Statement II is false
D. Statement I is incorrect but Statement II is true
Answer» D. Statement I is incorrect but Statement II is true
Discussion
18.

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ϵ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?

A. -1
B. 0
C. 1
D. 2
Answer» E.
Discussion
19.

Match the following:P) Prim’s algorithm for minimum spanning tree (i) BacktrackingQ) Floyd-Warshall algorithm for all pairs shortest paths (ii) Greedy methodR) Mergesort (iii) Dynamic programmingS) Hamiltonian circuit (iv) Divide and conquer

A. P – iii, Q – ii, R – iv, S – i
B. P – i, Q – ii, R – iv, S – iii
C. P – ii, Q – iii, R – iv, S – i
D. P – ii, Q – i, R – iii, S – iv
Answer» D. P – ii, Q – i, R – iii, S – iv
Discussion
20.

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

A. 23
B. 99
C. 4
D. 7
Answer» E.
Discussion
21.

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

A. the shortest path between every pair of vertices
B. the shortest path from W to every vertex in the graph
C. the shortest paths from W to only those nodes that are leaves of T.
D. the longest path in the graph.
Answer» C. the shortest paths from W to only those nodes that are leaves of T.
Discussion
22.

An undirected graph G (V, E) contains n (n > 2) nodes named ν1, ν2, ....νn. Two nodes νi, and νj are connected if and only if 0 < |i - j| ≤ 2. Each edge (νi, νj) is assigned a weight i + j.The cost of the minimum spanning tree of such a graph with 10 nodes is :

A. 88
B. 91
C. 49
D. 21
Answer» C. 49
Discussion
23.

Queue structure is used in _______.

A. Breadth First Search algorithm
B. Depth First Search algorithm
C. Polynomial addition
D. Recursion
Answer» B. Depth First Search algorithm
Discussion
24.

Let G be an undirected connected graph with distinct edge weights . Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false.

A. Every minimum spanning tree of G must contain emin
B. If emax is in a minimum spanning tree, then its removal must be disconnected G.
C. No minimum spanning tree contains emax
D. G has a unique minimum spanning tree.
Answer» D. G has a unique minimum spanning tree.
Discussion
25.

Let ‘m’ and ‘n’ be the number of edges and vertices in a graph G, respectively. Which of the following is the time complexity of the Kruskal’s algorithm to find minimum spanning tree of G?

A. O(n log n)
B. O(m log m)
C. O(n2)
D. O(m2)
Answer» C. O(n2)
Discussion
26.

Consider the undirected graph below:Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree ?

A. (a, b), (a, h), (g, h), (f, g), (c, f), (c, i), (c, d), (d, e)
B. (a, b), (b, h), (g, h), (g, i), (c, i), (c, f), (c, d), (d, e)
C. (a, b), (b, c), (c, i), (c, f), (f, g), (g, h), (c, d), (d, e)
D. (a, b), (g, h), (g, f), (c, f), (c, i), (f, e), (b, c), (d, e)
Answer» D. (a, b), (g, h), (g, f), (c, f), (c, i), (f, e), (b, c), (d, e)
Discussion
27.

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, ______”.

A. for every f: v → ℝ
B. if and only if ∀u ϵ V, f(u) is positive
C. if and only if ∀u ϵ V, f(u) is negative
D. if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G
Answer» B. if and only if ∀u ϵ V, f(u) is positive
Discussion
28.

In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

A. Θ(n2)
B. Θ(n + m)
C. Θ(m2)
D. Θ(n4)
Answer» C. Θ(m2)
Discussion