7.04a-c Shortest paths, minimum spanning trees and nearest neighbour Quiz: OCR Further Maths, Unit 4

The 20 questions

1. In Prim's algorithm, which vertex is selected as the starting node?

   • The highest degree
   • Any arbitrary vertex
   • The lowest degree
   • The lexicographical first

2. What condition must edge weights satisfy for Dijkstra's algorithm to work correctly?

   • Non-negative weights
   • Positive integers only
   • Negative weights allowed
   • Integer weights

3. Which algorithm builds a minimum spanning tree by considering edges in ascending order of weight?

   • Prim's algorithm
   • Kruskal's algorithm
   • Nearest neighbour algorithm
   • Dijkstra's algorithm

4. How many edges does a minimum spanning tree with n vertices contain?

   • n + 1
   • n
   • n - 1
   • 2n - 1

5. What must be avoided when adding an edge during Kruskal's algorithm?

   • Connecting components
   • Creating a cycle
   • Exceeding weight limit
   • Adding odd vertices

6. What does the Nearest Neighbour algorithm find for a Travelling Salesperson Problem?

   • A minimum tree
   • The exact optimum
   • An upper bound
   • A lower bound

7. What is the very first step in applying Kruskal's algorithm?

   • Order edges by weight
   • Delete heaviest edge
   • Find all cycles
   • Select start vertex

8. In Dijkstra's algorithm, what type of label is assigned permanently to a visited node?

   • Temporary label
   • Heuristic label
   • Spanning label
   • Permanent label

9. When using Prim's algorithm on a distance matrix, what action represents choosing a vertex?

   • Squaring the matrix
   • Deleting columns
   • Crossing out rows
   • Adding matrix entries

10. How is a TSP lower bound calculated using deleted vertex shortcuts?

    • Total weight halved
    • MST plus longest edge
    • Maximum spanning tree
    • RMST plus two shortest

11. What does Dijkstra's algorithm find between a start node and all other nodes?

    • Shortest paths
    • Minimum spanning tree
    • Hamiltonian cycle
    • Eulerian trail

12. If Nearest Neighbour gives 45 and the lower bound is 40, what is the optimal tour range?

    • Greater than 45
    • Exactly 42.5
    • Between 35 and 40
    • Between 40 and 45

13. A connected graph has 8 vertices. How many edges will its minimum spanning tree have?

    • 7
    • 8
    • 14
    • 6

14. From the current vertex, which vertex does the Nearest Neighbour algorithm visit next?

    • Visited closest vertex
    • Unvisited furthest vertex
    • Random unvisited vertex
    • Unvisited closest vertex

15. In a complete graph K5, how many edges does any minimum spanning tree contain?

    • 4
    • 5
    • 20
    • 10

16. Which minimum spanning tree algorithm maintains a single growing connected tree at every step?

    • Kruskal's algorithm
    • Dijkstra's algorithm
    • Chinese Postman algorithm
    • Prim's algorithm

17. What is the final step in completing a Nearest Neighbour tour?

    • Add shortest edge
    • Delete origin vertex
    • Stop at last
    • Return to start

18. When updating a temporary label in Dijkstra's algorithm, when is it changed?

    • If new distance higher
    • When degree increases
    • Only on first visit
    • If new distance lower

19. How can a simple TSP upper bound be obtained from a Minimum Spanning Tree weight W?

    • 2W
    • W / 2
    • W + 1
    • W

20. What graph property is required to guarantee a single minimum spanning tree exists?

    • Bipartite graph
    • Complete graph
    • Connected graph
    • Directed graph

Related quizzes

• Existence problems, set notation and the pigeonhole principle Quiz · 7.01a-c · 20 questions
• Arrangements, multiplicative principle and inclusion-exclusion Quiz · 7.01d-k · 20 questions
• Graph terminology, complete and bipartite graphs Quiz · 7.02a-e · 20 questions
• Eulerian and Hamiltonian graphs, isomorphism, digraphs, planarity and networks Quiz · 7.02g-p · 20 questions
• Algorithms, tracing and efficiency Quiz · 7.03a-e · 20 questions
• Sorting algorithms and bin packing Quiz · 7.03i-m · 20 questions
• Route inspection and choosing a network algorithm Quiz · 7.04e-f · 20 questions
• Critical path analysis Quiz · 7.05a · 20 questions
• Formulating linear programming problems and slack variables Quiz · 7.06a-b · 20 questions
• Graphical solutions and the effect of changing constraints Quiz · 7.06c-e · 20 questions