Computer Science

1. 1.

   Trace a linear search for 7 in [4, 9, 7, 2], scanning left to right and stopping at the first match. State zero-based index and comparison count.

   [3 marks] · no calculator
2. 2.

   Explain the precondition for binary search and why applying it directly to [8, 2, 9, 1] can miss an existing value.

   [3 marks] · no calculator
3. 3.

   Binary-search [3, 7, 11, 15, 19, 23, 27] for 23 with inclusive bounds and mid = floor((low+high)/2), zero-based indexing. Record midpoint indices until found.

   [3 marks] · no calculator
4. 4.

   Perform insertion sort on [5, 2, 4, 1], inserting each next item into the sorted prefix. Give the array after each outer pass.

   [3 marks] · no calculator
5. 5.

   An algorithm runs FOR i=1 TO n and inside it FOR j=1 TO i, performing one operation per inner iteration. Derive operation count and time complexity; evaluate whether doubling n exactly quadruples the count.

   [4 marks] · no calculator
6. 6.

   Prove that a left-to-right algorithm storing the largest value seen returns the maximum of a nonempty array. Include initialisation, maintenance and termination, and explain why initialising largest to zero is unsafe.

   [4 marks] · no calculator

Original, unofficial practice questions from SubjectScout — not official past-paper questions.