3D.2.1 Minimum spanning trees: Prim's and Kruskal's algorithms Quiz: Pearson Edexcel Further Maths, Unit 36

The 20 questions

1. A spanning tree of a graph with n vertices has how many edges?

   • n(n - 1)/2
   • n + 1
   • n - 1
   • n

2. In Kruskal's algorithm, what is the next edge chosen?

   • Cheapest without cycles
   • First available edge
   • Cheapest overall
   • Longest without cycles

3. In Prim's algorithm, how does the tree grow?

   • Random adjacent vertex
   • Cheapest connecting edge
   • Cheapest total cycle
   • Longest connecting edge

4. What is the defining feature of a minimum spanning tree?

   • Greatest total weight
   • Fewest vertices
   • Shortest single edge
   • Smallest total weight

5. In Prim's distance matrix, what represents no direct edge?

   • Zero
   • Blank space
   • Negative one
   • Infinity symbol

6. What is a connected graph with no cycles called?

   • Tree
   • Trail
   • Cycle
   • Complete graph

7. What must a spanning tree of a graph include?

   • A single cycle
   • All vertices
   • Only odd vertices
   • All edges

8. A network has edges AB 2, BC 3, AC 4, CD 5 and BD 6. What is the total weight of its minimum spanning tree?

   • 10
   • 14
   • 11
   • 9

9. Prim's algorithm starts at vertex A in the network with edges AB 2, BC 3, AC 4, CD 5 and BD 6. Which edge is added first?

   • AC, weight 4
   • BD, weight 6
   • CD, weight 5
   • AB, weight 2

10. A minimum spanning tree on 5 vertices uses edges of weights 2, 2, 3 and 5. What is its total weight?

    • 12
    • 15
    • 13
    • 9

11. A network has edges XY 1, YZ 1, XZ 1, XW 3 and ZW 2. What is the weight of its minimum spanning tree?

    • 3
    • 6
    • 5
    • 4

12. Which algorithm builds a minimum spanning tree by sorting all the edges by weight?

    • Floyd's algorithm
    • Kruskal's algorithm
    • Dijkstra's algorithm
    • Prim's algorithm

13. A square of side 1 has a diagonal of length 1.5, and its four vertices are joined by the sides and the diagonal. What is the weight of a minimum spanning tree?

    • 2.5
    • 4
    • 3
    • 3.5

14. Edges AB 1, BC 2, CA 2 and CD 4 form a network. What is the weight of its minimum spanning tree?

    • 7
    • 5
    • 9
    • 8

15. Prim's algorithm starts at A with edges AB 3, AD 6, BD 2, BC 4 and DC 5. After the tree contains A, B and D, which edge is added next?

    • AB, weight 3
    • DC, weight 5
    • BC, weight 4
    • AD, weight 6

16. Is the minimum spanning tree of a connected network unique when all edge weights are distinct?

    • Always zero
    • Never unique
    • Sometimes unique
    • Always unique

17. What property of Prim's and Kruskal's algorithms ensures they both find a minimum total weight?

    • Greedy choice
    • Random choice
    • Breadth-first
    • Exhaustive search

18. Which edge in a cycle is always excluded from a minimum spanning tree with distinct weights?

    • Middle edge
    • First edge
    • Lightest edge
    • Heaviest edge

19. How many edges does a connected tree with n vertices contain?

    • n plus one
    • n squared
    • n minus one
    • n

20. A network has edges AB 4, AC 3, BC 5, BD 6, CD 2, DE 7 and CE 8. What is the total weight of its minimum spanning tree?

    • 17
    • 19
    • 16
    • 15

Related quizzes

• Shortest paths: Dijkstra's and Floyd's algorithms Quiz · 3D.2.2 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions
• Goodness of fit tests for discrete distributions Quiz · 3B.6.1 · 20 questions