BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

PDSA · Graphs, BFS, DFS & topological sort

18 questions · 67 marks · 6 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Programming, Data Structures and Algorithms using Python

Graphs, BFS, DFS & topological sort

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MCQ: Exactly 1 option is correct. Negative marking applies.
MSQ: One or more options correct. Select all to score.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

Quiz 1 · 26 Oct 2025 (AN)Quiz 1

Q1MSQ3 Marks·Choose all correct options
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
5. E
Q2MSQ3 Marks·Choose all correct options
Key ↓
Consider a connected, undirected graph G with n vertices. A Breadth-First Search (BFS) traversal is performed starting from a source vertex s. Let d(s, v) denote the shortest distance (in terms of number of edges) from s to vertex v. Which of the following statements is true about the BFS traversal?
1. AAll vertices at distance k from s are visited before any vertex at distance k + 1 from s.
2. BOnce a vertex is visited, it is never visited again during the traversal.
3. CBFS may fail to visit some vertices, even if the graph is connected.
4. DThe time complexity of BFS using an adjacency list representation is O(n^2).
Q3NAT3 Marks·Write the number
Asked 6 times Key ↓
Your answer:
Q4NAT3 Marks·Write the number
Key ↓
Your answer:
Q5NAT3 Marks·Write the number
Key ↓
Your answer:

End Term · 31 Aug 2025 (FN)End Term

Q6MCQ4 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q7MCQ4 Marks·Choose one option
Key ↓
1. A
2. B
3. C
Q8NAT4 Marks·Write the number
Asked 6 times Key ↓
An undirected graph has 300 edges. What is the minimum number of vertices it must have?
Your answer:

End Term · 31 Aug 2025 (AN)End Term

Q9MCQ4 Marks·Choose one option
Key ↓
Consider the following statements: 1. While creating a DFS tree for a directed graph, among non-tree edges, only back edges correspond to cycles. 2. The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex. Choose the correct option.
1. AOnly statement 1 is true
2. BOnly statement 2 is true
3. CBoth statements 1 and 2 are true
4. DBoth statements 1 and 2 are false
Q10MSQ4 Marks·Choose all correct options
Key ↓
1. A1
2. B5
3. C3
4. D4
5. E6
6. F7
Q11NAT4 Marks·Write the number
Asked 6 times Key ↓
What is the maximum number of edges in a directed graph with 9 vertices?
Your answer:

End Term · 13 Apr 2025 (AN)End Term

Q12MCQ4 Marks·Choose one option
Asked 6 times Key ↓
1. A
2. B
3. C
4. D
Q13MCQ4 Marks·Choose one option
Asked 3 times Key ↓
Consider a graph G with V vertices and E edges represented using an adjacency list. What is the worst case complexity for Breadth First Search?
1. A
2. B
3. C
4. D
Q14MSQ4 Marks·Choose all correct options
Key ↓
Which of the following statement is/are false?
1. A
2. B
3. C
4. D

End Term · 22 Dec 2024 (FN)End Term

Q15MSQ4 Marks·Choose all correct options
Asked 2 times Key ↓
1. AP Q R S T U V
2. BP R Q V S U T
3. CP Q R S V U T
4. DP R Q S V T U
Q16NAT4 Marks·Write the number
Asked 6 times Key ↓
Your answer:

End Term · 22 Dec 2024 (AN)End Term

Q17MCQ4 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q18NAT4 Marks·Write the number
Asked 6 times Key ↓
Your answer:

Official Key

Master Answer Key & Explanations

Official answer keys from IIT Madras BS past papers. Click any question to review.

Reveal Key

Q1B, E

Q2A, B

Q3190

Q44

Q52

Q6C

Q7B

Q825

Q9C

Q10A, C, E

Q1172

Q12A

Q13B

Q14A, C, D

Q15B, D

Q169

Q17C

Q188

Questions and answer keys are reproduced from the official IIT Madras BS papers. Topics and repeated question types are BTechi’s own grouping. BTechi is not affiliated with IIT Madras.