Paper 2 CS · UNIT 07 · MOCK TEST

Mock 9 – Graph Algorithms (Part 1)

Unit 7: Data Structures and Algorithms · 17 questions · about 20 minutes. Press End Mock any time to see your score and the correct answers.

All 11 topic-wise mocks in this unit

0 / 17 answered 00:00

Q1. Which of the following algorithms use the Greedy strategy?
A. Dijkstra's algorithm
B. Kruskal's algorithm
C. Huffman coding
D. Bellman-Ford algorithm
Choose the correct answer from the options given below:

AA, B and D Only BA, B and C Only CC and D Only DA and D Only

Q2. Maintaining a graph in memory by means of its adjacency matrix is known as

AComplete Representation BLinked Representation CCircular Representation DSequential Representation

Q3. Which of the following algorithms are based on Breadth First Search (BFS)?
A. Prim's algorithm
B. Kruskal's algorithm
C. Dijkstra's algorithm
D. Greedy algorithms
E. Dynamic Programming
Choose the correct answer from the options given below:

AA & B only BA, C & D only CD & E only DA & C only

Q4. Match List I with List II

List I	List II
(A) Dijkstra's Algorithm	(I) Finds the shortest path between all pairs of vertices in a graph with positive or negative edge weights.
(B) Floyd-Warshall Algorithm	(II) Finds the shortest path in a weighted graph with non-negative edge weights.
(C) Bellman-Ford Algorithm	(III) Finds single-source shortest paths with possible negative weights.
(D) Prim's Algorithm	(IV) Finds the Minimum Spanning Tree (MST).

A(A)-(I), (B)-(II), (C)-(III), (D)-(IV) B(A)-(II), (B)-(I), (C)-(III), (D)-(IV) C(A)-(I), (B)-(II), (C)-(IV), (D)-(III) D(A)-(III), (B)-(II), (C)-(IV), (D)-(I)

Q5. In the context of Hamiltonian problems, which of the following are correct?
A. The Hamiltonian cycle problem is NP-complete.
B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian.
C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph.
D. If G is a connected undirected graph with at least three vertices, then G³ (the graph obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian.
E. If any NP-complete problem is polynomial-time solvable, then P = NP.
Choose the most appropriate answer from the options given below:

AA, B, C only BB, D, E only CA, D, E only DA, C, E only

Q6. Match List I with List II.
Choose the correct answer from the options given below:

List I	List II
a. Dijkstra's algorithm	I. Calculates path matrix
b. Prim's algorithm	II. Stores minimum cost edge
c. Warshall's algorithm	III. Stores the total cost from a source node to the current node
d. Kruskal's algorithm	IV. Finds minimum spanning tree

Aa-I, b-II, c-III, d-IV Ba-III, b-II, c-I, d-IV Ca-II, b-I, c-IV, d-III Da-III, b-IV, c-II, d-I

Q7. For the weighted graph below, which of the following orders of adding edges can NOT be produced by a minimum spanning tree algorithm?
Edges (weight): a–b (1), d–f (1), b–f (2), c–d (2), b–c (3), d–e (3), b–d (4), c–e (4), e–f (5), a–c (6), c–f (7)
I. a-b II. d-f III. b-f IV. d-c V. d-e
Choose the correct answer from the options given below:

AI, II, III, IV, V BI, II, IV, III, V CII, I, III, V, IV DII, I, IV, III, V

Q8. Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find a lower bound on the weight of the minimum-weight vertex cover.
Statement II: The lower bound can be found by maximising Σ_v∈V w(v)x(v) subject to x(u) + x(v) ≥ 1 for each (u, v) ∈ V, x(v) ≤ 1 and x(v) ≥ 0 for each v ∈ V.
Choose the most appropriate answer.

ABoth Statement I and Statement II are correct BBoth Statement I and Statement II are incorrect CStatement I is correct but Statement II is incorrect DStatement I is incorrect but Statement II is correct

Q9. Consider the following undirected graph with vertices a, b, c, f, g, h and edges:
a–b, a–c, a–f, b–c, b–f, b–h, c–g, f–g, f–h, g–h
The following depth-first search (DFS) sequences are given:
(A) abcghf
(B) abfchg
(C) abfhgc
(D) afghbc
Which of the following is correct?

A(A), (B) and (D) only B(A), (B), (C) and (D) C(B), (C) and (D) only D(A), (C) and (D) only

Q10. Fill in the blanks:
"An ________ chart is a project schedule representation that presents the project plan as a directed graph. The critical path is the ________ sequence of ________ tasks and it defines the project ________."

AActivity, Shortest, Independent, Cost BActivity, Longest, Dependent, Duration CActivity, Longest, Independent, Duration DActivity, Shortest, Dependent, Duration

Q11. Which of the following are the primary objectives of risk monitoring in software project tracking?
P: To assess whether predicted risks do, in fact, occur.
Q: To ensure that risk aversion steps defined for the risk are being properly applied.
R: To collect information that can be used for future risk analysis.
Choose the correct answer from the options given below:

AOnly P and Q BOnly P and R COnly Q and R DAll of P, Q and R

Q12.

Which of the following algorithms use Greedy strategy?

A. Dijkstra's algorithm

B. Kruskal's algorithm

C. Huffman coding

D. Bellman-Ford algorithm

AA, B and D Only BA, B and C Only CC and D Only DA and D Only

Q13.

Which of the following algorithms are based on the Breadth First Search (BFS) ?

A. Prim's algorithms

B. Kruskal algorithms

C. Dijkstra algorithms

D. Greedy algorithms

E. Dynamic Programming

AA & B only BA, C & D only CD & E only DA & C only

Q14.

Match List - I with List - II.

A(A)-(I), (B)-(II), (C)-(III), (D)-(IV) B(A)-(II), (B)-(I), (C)-(III), (D)-(IV) C(A)-(I), (B)-(II), (C)-(IV), (D)-(III) D(A)-(III), (B)-(II), (C)-(IV), (D)-(I)

Q15.

Which of the following are correct about Hamiltonian problems? A. The Hamiltonian cycle problem is NP-complete. B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian. C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph. D. If G is a connected undirected graph with at least three vertices, then G³ (obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian. E. If any NP-complete problem is polynomial-time solvable, then P = NP.

AA, B, C only BB, D, E only CA, D, E only DA, C, E only

Q16.

Match List I with List II

Aa-I, b-II, c-III, d-IV Ba-III, b-II, c-I, d-IV Ca-II, b-I, c-IV, d-III Da-III, b-IV, c-II, d-I

Q17.

Given the graph below one of the following edges cannot be added in that order to find a minimum spanning tree algorithm.

I. a-b

II. d-f

III. b-f

IV. d-c

V. d-e

AI, II , III, IV,V BI, II, IV, III, V CII, I, III, V, IV DII, I, IV, III, V Q

Next: Mock 10 – Graph Algorithms (Part 2) →