Phase 6 Checkpoint: 15 questions on graph traversals, minimum spanning trees and shortest paths.
⏱️
15 questions · 25 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1NAT1 markBFS
BFS from F on the six-town graph: distance (roads) to A?
Numerical answer: ________
Q2MCQ1 markBFS data structure
BFS is normally implemented with a:
- (A) stack
- (B) max-heap
- (C) hash table
- (D) queue
Q3NAT2 marksDFS
In the lesson's directed DFS (u, v, w, x, y, z), what is d[z]?
Numerical answer: ________
Q4MCQ2 marksEdge type
In a DFS of a directed graph, d[p] = 2, f[p] = 9, d[q] = 4, f[q] = 7, and edge q → p is explored. It is a:
- (A) cross edge
- (B) back edge
- (C) forward edge
- (D) tree edge
Q5NAT2 marksTopological orders
DAG on a, b, c, d with edges a → b, a → c, b → d, c → d. Number of topological orders?
Numerical answer: ________
Q6NAT1 markComponents
An undirected forest has 30 vertices and 24 edges. Number of components?
Numerical answer: ________
Q7NAT2 marksSCCs
Directed graph: a → b, b → c, c → a, b → d, d → e, e → f, f → d, g → f, g → h, h → g. Number of SCCs?
Numerical answer: ________
Q8NAT1 markMST
MST weight of the six-town graph?
Numerical answer: ________
Q9MSQ2 marksMST facts
Which are true?
- (A) Kₙ has nⁿ⁻² spanning trees.
- (B) Distinct edge weights give a unique MST.
- (C) Adding 5 to every edge weight changes the MSTs.
- (D) An edge strictly heaviest on a cycle is in no MST.
Q10NAT2 marksKruskal
MST weight of the CLRS graph (a–i) from Lesson 6.2.2?
Numerical answer: ________
Q11NAT2 marksMST count
Number of distinct MSTs of the CLRS graph (a–i)?
Numerical answer: ________
Q12MCQ1 markPrim
Prim from F on the six-town graph adds vertices in which order?
- (A) F, D, E, B, C, A
- (B) F, E, D, B, C, A
- (C) F, E, D, C, B, A
- (D) F, E, B, D, C, A
Q13NAT2 marksDijkstra
Dijkstra from C on the six-town graph: distance to F?
Numerical answer: ________
Q14NAT2 marksBellman–Ford
In the lesson's Bellman–Ford example, final dist[t]?
Numerical answer: ________
Q15NAT2 marksFloyd
In the lesson's Floyd–Warshall final matrix, D[3][2]?
Numerical answer: ________
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 31 mark
F–D–B–A.
Re-read: Lesson 6.1.1 — Breadth-first search: levels and unweighted shortest paths
Q2 Answer: (D)1 mark
FIFO gives level order.
- (A) is wrong: That gives DFS.
- (B) is wrong: Not needed.
- (C) is wrong: Not the frontier.
Re-read: Lesson 6.1.1 — Breadth-first search: levels and unweighted shortest paths
Q3 Answer: 102 marks
w is discovered at 9, then z at 10.
Re-read: Lesson 6.1.2 — Depth-first search: discovery and finish times, edge classification
Q4 Answer: (B)2 marks
p is an ancestor of q (2 < 4 < 7 < 9), so q → p goes back up.
- (A) is wrong: Cross edges join unrelated vertices.
- (C) is wrong: Forward edges go down.
- (D) is wrong: p was already discovered.
Re-read: Lesson 6.1.2 — Depth-first search: discovery and finish times, edge classification
Q5 Answer: 22 marks
b and c in either order.
Re-read: Lesson 6.1.3 — Topological sort, cycle detection, connected and strongly connected components
Q6 Answer: 61 mark
V − E.
Re-read: Lesson 6.1.3 — Topological sort, cycle detection, connected and strongly connected components
Q7 Answer: 32 marks
{a, b, c}, {d, e, f}, {g, h}.
Re-read: Lesson 6.1.3 — Topological sort, cycle detection, connected and strongly connected components
Q8 Answer: 131 mark
1 + 2 + 2 + 3 + 5.
Re-read: Lesson 6.2.1 — Minimum spanning trees: cut and cycle properties, uniqueness
Q9 Answer: (A) (B) (D)2 marks
A constant shift keeps the MSTs.
- (C) is wrong: Every spanning tree gains the same amount.
Re-read: Lesson 6.2.1 — Minimum spanning trees: cut and cycle properties, uniqueness
Q10 Answer: 372 marks
Kruskal trace.
Re-read: Lesson 6.2.2 — Kruskal's algorithm and union–find
Q11 Answer: 22 marks
a–h or b–c (both 8).
Re-read: Lesson 6.2.2 — Kruskal's algorithm and union–find
Q12 Answer: (B)1 mark
F–E 3, E–D 2, D–B 5, B–C 1, C–A 2.
- (A) is wrong: E–F 3 is cheaper than D–F 6.
- (C) is wrong: C is not adjacent to the tree {F, E, D} by a cheaper edge than B–D 5 (C–D is 8, C–E is 10).
- (D) is wrong: B is not adjacent to {F, E}.
Re-read: Lesson 6.2.3 — Prim's algorithm; MST complexities
Q13 Answer: 112 marks
C–B–D–E–F.
Re-read: Lesson 6.3.1 — Relaxation and Dijkstra's algorithm
Q14 Answer: 22 marks
s → y → x → t = 7 − 3 − 2.
Re-read: Lesson 6.3.2 — Bellman–Ford, negative cycles, shortest paths in DAGs
Q15 Answer: 62 marks
3 → 4 → 1 → 2 = 1 + 2 + 3.
Re-read: Lesson 6.3.3 — All-pairs shortest paths: Floyd–Warshall