Singapore H2 Computing Wiki

Paper 1 Search and Sort Drills

3 min read

Paper 1 Search and Sort Drills

These are original Paper 1-style practice questions. They focus on explanation, tracing, comparison, pseudocode reading, and worst-case time complexity.

Detailed answers are in Paper 1 Search and Sort Answers.

Revise these first:

Questions

Question 1: Linear Search Trace

Linear search is used on the list [17, 4, 29, 8, 13] to find the target 13.

Complete a trace table showing each item checked and state the returned index. [4]

Question 2: Linear Search Absent Case

Linear search is used on [9, 2, 15, 6] to find the target 7.

  1. State how many items are checked. [1]
  2. State the value returned by a standard linear search that returns -1 when the target is absent. [1]
  3. Explain why the algorithm must have a return statement after the loop. [2]

Question 3: Binary Search Trace

Binary search is used on the sorted list below to find 44.

index:  0   1   2   3   4   5   6   7   8
value:  3   7  12  18  25  31  44  58  63

Complete the trace until the target is found. Use integer division for mid. [4]

Steplowhighmidmiddle valueaction
1
2

Question 4: Preconditions and Complexity

A student wants to use binary search on [14, 2, 19, 7, 31, 11].

  1. Explain why binary search should not be used directly on this list. [1]
  2. State the worst-case time complexity of linear search. [1]
  3. State the worst-case time complexity of binary search on a sorted list. [1]
  4. Give one reason why linear search may be suitable for a very small list. [1]

Question 5: Bubble Sort Trace

Bubble sort is used to sort [6, 2, 9, 1, 5] in ascending order.

  1. Show the list after the first complete pass. [2]
  2. Show the list after the second complete pass. [2]
  3. Explain why a large value moves right during a pass. [2]

Question 6: Insertion Sort Trace

Insertion sort is used on [7, 3, 5, 2].

Show the list after 3 is inserted into the sorted section, then after 5 is inserted into the sorted section. [4]

Question 7: Merge Sort Idea

Merge sort is applied to [8, 1, 6, 3].

  1. Show the split-down phase until each sublist has one item. [2]
  2. Show the merge-up phase that produces the sorted list. [3]
  3. State the worst-case time complexity of merge sort. [1]

Question 8: Quicksort Partition

Quicksort chooses the first value as the pivot for the list [5, 9, 2, 7, 1].

  1. State the pivot. [1]
  2. Show the less, equal, and greater groups after partitioning. [3]
  3. Explain why quicksort can have worst-case time. [2]

A hash table stores keys in buckets. Two different keys may hash to the same bucket.

  1. Name this situation. [1]
  2. Explain why this can make hash table search slower in the worst case. [2]
  3. State one feature of a good hash function. [1]

The pseudocode below is intended to perform binary search.

WHILE low < high
    mid <- (low + high) DIV 2
    IF items[mid] = target THEN
        RETURN mid
    ELSE IF target > items[mid] THEN
        low <- mid
    ELSE
        high <- mid
    ENDIF
ENDWHILE
RETURN -1

Identify two errors or weaknesses in the update/loop logic and state how they should be corrected. [4]

Review Checklist

You should be able to:

  • trace linear and binary search using indexes;
  • explain binary search’s sorted-data precondition;
  • trace bubble and insertion sort by state changes;
  • explain split/merge and pivot/partition ideas;
  • compare worst-case Big-O for syllabus algorithms.

Graph View

Backlinks