Unit 7: Data Structures and Algorithms · 17 questions · about 20 minutes. Press End Mock any time to see your score and the correct answers.
Statement 1: su Given a graph G=(V, E) in which each vertex v € V has an associated positive weight w(v), we can Q use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Statement 2 : Q The lower bound can be found by maximizing the following ∑n w(v)x(v) v∈V subject to Q x(u) + x(v) ≥ 1 for each (u, v) ∈ V x(v) ≤ 1 for each v ∈ V x(v) ≥ 0 for each v ∈ V In the light of the above statements, choose the most appropriate answer from the options given below:
Correct answer: C. Statement I is correct but Statement II is incorrect
The LP relaxation of weighted vertex cover gives a lower bound on the optimal weight (Statement I true). It must minimize Σ w(v)x(v), with constraints over edges (u, v) ∈ E, not maximize, so Statement II is incorrect.
For the graph shown, the following depth-first search sequences are given: (A) abcghf (B) abfchg (C) abfhgc (D) afghbc. Which of the following is correct?
Correct answer: D. (A), (C) and (D) only
A sequence is a valid DFS if each new vertex is adjacent to the most recent vertex that still has unvisited neighbours. Checking each sequence against the figure's edges, the official key accepts (A), (C) and (D); in (B), the step after f to c is not possible by DFS.
Consider the following graph.
Among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e Which are depth first traversals of the above graph?
Correct answer: D. I, III, and IV only
Edges: a–b, a–e, a–f, b–e, b–f, b–h, f–h, f–g, h–g, e–g. I (a b e g h f) and III (a b f h g e) and IV (a f g h b e) each move to an unvisited neighbour of the latest vertex. In II, after a b f the next vertex e is not adjacent to f while f still has unvisited neighbours, so II is not a DFS.
Match each graph algorithm with its time complexity (n vertices, m edges). List I: A. Bellman-Ford, B. Kruskal's algorithm, C. Floyd-Warshall, D. Topological sorting. List II: I. O(m log n), II. O(n³), III. O(n·m), IV. O(n + m).
Correct answer: A. A ‐ III, B ‐ I, C ‐ II, D ‐ IV
Bellman–Ford is O(nm); Kruskal is O(m log n); Floyd–Warshall is O(n³); topological sort is O(n + m).
Let be a directed graph whose vertex set is the set of numbers from 1 to 100 . There is an i j edge from a vertex to a vertex if and only if j = i + 1 j = 3i either or . The minimum G number of edges in a path in from vertex 1 to vertex 100 is ____
Correct answer: D. 7 L = L ∩ L
Working backwards from 100: 100 ← 99 ← 33 ← 11 ← 10 ← 9 ← 3 ← 1. The path 1 → 3 → 9 → 10 → 11 → 33 → 99 → 100 uses 7 edges.
Match List I with List II. List I: A. Topological sort of a DAG, B. Kruskal's MST algorithm, C. Bellman-Ford single-source shortest path, D. Floyd-Warshall all-pairs shortest path. List II: I. O(V + E), II. O(VE), III. θ(V + E), IV. θ(V³).
Correct answer: C. A-III, B-I, C-II, D-IV
Topological sort is Θ(V + E), Bellman–Ford O(VE), Floyd–Warshall Θ(V³), leaving O(V + E) for Kruskal in the key's matching.
Note: Kruskal's algorithm actually runs in O(E log V); the official key pairs it with O(V + E).
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?
Correct answer: C. (a,b), (b,c), (c,i), (c,f), (f,g), (g,h), (c,d), (d,e)
From a: (a,b) 4; then (b,c) 8 (tie with (a,h) 8); (c,i) 2; (c,f) 4; (f,g) 2; (g,h) 1; (c,d) 7; (d,e) 9. Each step adds the cheapest edge leaving the tree, matching option C.
G T Let be a simple undirected graph, D be a DFS G T tree on , and B be the BFS tree on G. Consider the following statements. G
Statement I : No edge of is a cross with T respect to D (u, v) G u
Statement II : For every edge of , if is i v j T at depth and is at depth in B then |i − j| = 1 . In the light of the above statements, choose the correct answer from the options given below
Correct answer: C. Statement I is correct but Statement II is false
In an undirected graph, DFS produces only tree and back edges — no cross edges (I true). In a BFS tree an edge's endpoints differ in depth by at most 1, and they can be at the same depth, so |i − j| = 1 is not always true (II false).
The weight of minimum spanning tree in graph G, calculated using Kruskal's algorithm is :
Correct answer: B. 15
Take edges in increasing order: 2, 3, 4 (no cycle); 5 would close a cycle with 3 and 4, so skip it; 6 joins the last vertex. Total = 2 + 3 + 4 + 6 = 15.
When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?
Correct answer: C. Shortest path always passes through least number of vertices
Dijkstra finds the cheapest path, not the one with the fewest vertices, so C is false. It always visits the closest unvisited node next and needs non-negative weights.
Match List I with List II. List I: (a) Prim's algorithm, (b) Dijkstra's algorithm, (c) Faster all-pairs shortest path, (d) Edmonds-Karp algorithm. List II: (i) O(V³ lg V), (ii) O(VE²), (iii) O(E lg V), (iv) O(V²).
Correct answer: B. (a)-(iii); (b)-(iv); (c)-(i); (d)-(ii)
Prim (binary heap) is O(E lg V); Dijkstra with an array is O(V²); repeated-squaring all-pairs is O(V³ lg V); Edmonds–Karp is O(VE²).
Consider the following properties with respect to G = (V , E) a flow network in which a flow is a f : V × V → R real-valued function : P : For all u, v ∈ V , f(u, v) = −f(v, u) 1 P : ∑ f(u, v) = 0 for all u ∈ V 2 v∈V Which one of the following is/are correct? P
Correct answer: C. Both 1 and 2 P P
CLRS's net-flow formulation uses skew symmetry f(u, v) = −f(v, u) and flow conservation Σ f(u, v) = 0.
Note: Flow conservation (P2) holds for every vertex except the source and sink; the official key accepts both.
Consider the graph shown below :
Use Kruskal's algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
Correct answer: C. 16
Take the three weight-1 edges, then the weight-2 edges that join new components (three of them), then a weight-3 edge to the lower-left vertex and a weight-4 spoke to the bottom vertex: 3 × 1 + 3 × 2 + 3 + 4 = 16 for the 8 edges on 9 vertices.
Match List I with List II and choose the correct answer from the code given below.
Where V and E are the number of vertices and edges in the graph respectively.
Correct answer: B. (a)-(iii), (b)-(i), (c)-(ii), (d)-(iv)
Dijkstra with an array is O(V²); Kruskal is O(E log E); Floyd–Warshall is O(V³); topological sort is O(V + E).
A K-colouring of an undirected graph G = (V, E) is a function c : V → {0, 1, …, K − 1} such that c(u) ≠ c(v) for every edge (u, v) ∈ E. For a 2-colourable graph G, which of the following is not correct?
Correct answer: C. G has cycles of odd length
2-colourable ⇔ bipartite ⇔ no odd cycle. So 'G has cycles of odd length' is the incorrect statement.
Which of the following algorithms solves the single-source shortest paths ?
Correct answer: D. Dijkstra’s algorithm
Dijkstra solves single-source shortest paths. Prim builds MSTs; Floyd–Warshall and Johnson solve all-pairs.
E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford-Fulberson algorithm is bounded by :
Correct answer: A. O(E · f)
With integer capacities each augmentation raises the flow by at least 1, and each costs O(E): O(E · f).
