7.03i-m Sorting algorithms and bin packing Quiz: OCR Further Maths, Unit 4

The 20 questions

1. What is the maximum number of passes required to complete a bubble sort on n items?

   • n²
   • n
   • n - 1
   • n + 1

2. Which bin packing algorithm requires the list of items to be placed in descending order first?

   • First Fit Decreasing
   • Next Fit
   • Full Bin
   • First Fit

3. What is the lower bound for the number of capacity 10 bins needed for total item weight 27?

   • 2
   • 3
   • 4
   • 2.7

4. How many comparisons are made during the first pass of a bubble sort on n items?

   • n - 1
   • n / 2
   • n²
   • n

5. What is the worst-case order of time complexity for the Bubble Sort algorithm?

   • O(n log n)
   • O(n²)
   • O(log n)
   • O(n)

6. An item of size 4 is placed using First Fit into bins with remaining space [3, 5, 2]. Which bin receives it?

   • Bin 4
   • Bin 3
   • Bin 2
   • Bin 1

7. Which bin packing algorithm only checks the current open bin before starting a new bin?

   • Best Fit
   • First Fit
   • Full Bin
   • Next Fit

8. Items of sizes 6, 5, 4, and 3 are packed into capacity 10 bins using Next Fit. How many bins are used?

   • 3
   • 5
   • 2
   • 4

9. What is the main advantage of using First Fit Decreasing instead of standard First Fit?

   • Requires no sorting
   • Uses fewer bins
   • Always gives optimal
   • Faster execution time

10. Six items with total weight 25 are packed into bins of capacity 10. What is the lower bound?

    • 3
    • 4
    • 2
    • 2.5

11. In a quick sort pass, what are created on either side of the pivot element?

    • Two sorted lists
    • Equal pairs
    • Two sub-lists
    • Two empty bins

12. Items 7, 5, 4, and 3 are packed into capacity 10 bins using First Fit. How many bins are used?

    • 1
    • 4
    • 3
    • 2

13. What is the best-case time complexity of an insertion sort on an already sorted list?

    • O(log n)
    • O(1)
    • O(n)
    • O(n²)

14. In a quick sort on 7 items, how many comparisons are made in the first pass?

    • 6
    • 7
    • 5
    • 49

15. What is the maximum total number of comparisons needed to bubble sort a list of 5 items?

    • 5
    • 25
    • 10
    • 15

16. Which bin packing algorithm is classified as an offline algorithm because all data must be known in advance?

    • Next Fit
    • First Fit Decreasing
    • First Fit
    • Full Bin

17. What is the maximum number of swaps possible in a single pass of bubble sort on n items?

    • n - 1
    • n²
    • n
    • n / 2

18. How many passes are required to bubble sort the list [3, 1, 4, 2] into ascending order?

    • 2
    • 4
    • 1
    • 3

19. What is the primary objective when selecting combinations of items in the full bin packing method?

    • Fill bins completely
    • Maximise unused space
    • Sort items first
    • Minimise total passes

20. Which sorting algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order?

    • Bin packing
    • Kruskal's algorithm
    • Quick sort
    • Bubble sort

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
• Shortest paths, minimum spanning trees and nearest neighbour Quiz · 7.04a-c · 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