Skills101
← All practice quizzes

Quiz: Minimum Spanning Trees

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Connect every node at the lowest total cost. What a spanning tree is, Kruskal's algorithm with Union-Find, Prim's algorithm with a heap, why the greedy choice is safe, and which one to pick, in Python and Java.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    A connected graph has 8 nodes. How many edges does any spanning tree of it have?

  2. Question 2

    In Kruskal's algorithm, an edge u–v is skipped when:

  3. Question 3

    What does this print?

    edges = sorted([(3, "A", "B"), (1, "B", "C"), (2, "A", "C"), (4, "C", "D")])
    parent = {x: x for x in "ABCD"}
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    total = 0
    for w, u, v in edges:
        if find(u) != find(v):
            parent[find(u)] = find(v)
            total += w
    print(total)
    
  4. Question 4

    Which data structure makes Kruskal's cycle check fast?

  5. Question 5

    Prim's algorithm, at each step, adds:

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →