3D.1.2-3D.1.4 Bin packing, sorting, Eulerian graphs and planarity Quiz: Pearson Edexcel Further Maths, Unit 35

The 20 questions

1. What is the primary objective of the bin packing problem?

   • Fastest sorting
   • Maximum items
   • Shortest path
   • Minimum bins

2. What sorting algorithm repeatedly swaps adjacent elements if they are in the wrong order?

   • Bubble sort
   • Quick sort
   • Merge sort
   • Bin sort

3. A graph is Eulerian when every vertex has

   • even degree
   • odd degree
   • degree exactly 3
   • degree at most 4

4. How many vertices of odd degree does a semi-Eulerian graph have?

   • Zero
   • Four
   • Two
   • One

5. What does an Eulerian cycle include exactly once?

   • Every vertex
   • The starting edge
   • Only odd vertices
   • Every edge

6. What does a Hamiltonian cycle visit exactly once before returning?

   • Every vertex
   • Every edge
   • The starting region
   • Only even vertices

7. In a planar graph, where may edges meet?

   • Only at faces
   • At any midpoint
   • At shared vertices
   • Anywhere

8. Items of sizes 6, 5, 4, 3 and 2 are packed into bins of capacity 10. What is the minimum number of bins?

   • 4
   • 2
   • 5
   • 3

9. Items of sizes 8, 5, 4 and 3 are packed into bins of capacity 10. What is the minimum number of bins?

   • 5
   • 4
   • 2
   • 3

10. A connected graph has vertex degrees 4, 4, 2, 2 and 4. What type of graph is it?

    • Semi-Eulerian
    • Tree
    • Eulerian
    • Non-Eulerian

11. Where must an Eulerian trail start and end in a graph with two odd vertices A and B?

    • Anywhere
    • At A and B
    • At vertex C
    • Both at A

12. How many edges does the complete graph K6 have?

    • 30
    • 15
    • 6
    • 12

13. Using quick sort with the middle item as the pivot, what is the pivot for the list 5, 2, 9, 1, 7?

    • 7
    • 9
    • 1
    • 5

14. A graph has 4 vertices, each of degree 3. How many edges does it have?

    • 12
    • 4
    • 6
    • 3

15. Which simple graph always contains an Eulerian cycle?

    • Triangle
    • Tree
    • Star graph
    • Path graph

16. Which complete graph is planar?

    • K4
    • K7
    • K5
    • K6

17. Items of sizes 5, 5, 4, 4, 3 and 3 are packed into bins of capacity 10. What is the minimum number of bins?

    • 5
    • 3
    • 2
    • 4

18. Can a connected graph with four odd vertices have an Eulerian trail?

    • No
    • Only if planar
    • Yes
    • Always

19. What is the main drawback of using a greedy bin packing heuristic?

    • Infinite execution time
    • Guaranteed optimal fit
    • High computational cost
    • Suboptimal global results

20. A graph has seven vertices with degrees 3, 3, 3, 3, 3, 3 and 2. How many edges does it have?

    • 9
    • 10
    • 12
    • 20

Related quizzes

• Algorithms and the order of an algorithm Quiz · 3D.1.1 · 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