7.03a-e Algorithms, tracing and efficiency Quiz: OCR Further Maths, Unit 4

The 20 questions

1. What does Big-O notation measure when evaluating algorithm efficiency?

   • Exact code lines
   • Average execution time
   • Worst-case complexity
   • Best-case speed

2. What is the worst-case time complexity of the bubble sort algorithm?

   • O(n^2)
   • O(n)
   • O(2^n)
   • O(n log n)

3. Pack items of size 4, 3, 5, 2 into bins of capacity 6 using first-fit. How many bins are needed?

   • 2
   • 3
   • 5
   • 4

4. What initial step is performed in first-fit decreasing bin packing?

   • Sort items descending
   • Reverse the items
   • Calculate mean weight
   • Sort items ascending

5. What is the formula for the theoretical lower bound on bins needed for total weight W and capacity V?

   • Ceiling of W/V
   • Ceiling of V/W
   • Floor of W/V
   • W divided by V

6. Which design strategy does Kruskal's algorithm use to find a minimum spanning tree?

   • Divide and conquer
   • Greedy algorithm
   • Backtracking search
   • Dynamic programming

7. In Dijkstra's algorithm, which node is selected for expansion at each step?

   • Highest degree node
   • First visited node
   • Smallest temporary label
   • Largest temporary label

8. What key element is chosen at each stage of a quicksort algorithm?

   • Modulus
   • Pivot
   • Median
   • Root

9. How many odd vertices must a graph have to contain an Eulerian trail?

   • Exactly 1 or 3
   • Exactly 0 or 2
   • Only 4
   • Any even number

10. How many distinct pairings of vertices exist when applying Route Inspection to 4 odd nodes?

    • 2
    • 3
    • 6
    • 4

11. What is the time complexity of standard matrix multiplication for two n by n matrices?

    • O(n^3)
    • O(2^n)
    • O(n log n)
    • O(n^2)

12. In Euler's formula for a connected planar graph, what is V minus E plus F equal to?

    • 2
    • 1
    • 4
    • 0

13. What is the worst-case time complexity of linear search on an unsorted list of n items?

    • O(log n)
    • O(n)
    • O(1)
    • O(n^2)

14. What condition must a list satisfy before applying binary search?

    • All values positive
    • Length is even
    • List is random
    • List is sorted

15. What is the maximum number of comparisons needed for binary search on 16 sorted items?

    • 5
    • 16
    • 4
    • 8

16. How does Prim's algorithm build a minimum spanning tree compared to Kruskal's?

    • Removes heaviest cycles
    • Starts from all leaves
    • Sorts all edges
    • Grows from a vertex

17. How many edges are present in a minimum spanning tree for a connected graph with V vertices?

    • V - 1
    • V + 1
    • V
    • 2V

18. What is the main purpose of creating a trace table when analysing an algorithm?

    • Measure execution time
    • Track variable values
    • Compile source code
    • Count output lines

19. To which complexity class does the optimal bin packing problem belong?

    • Linear
    • Logarithmic
    • Polynomial
    • NP-hard

20. What is the average-case time complexity of quicksort on a list of n items?

    • O(log n)
    • O(n)
    • O(n log n)
    • O(n^2)

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
• Sorting algorithms and bin packing Quiz · 7.03i-m · 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