Algorithms (graph traversal, tree traversal, Dijkstra, searching & sorting, RPN) – A-level Computer Science exam questions with mark scheme

1Core3 marks

The list below is sorted in ascending order, with indexes starting at 0.

[3, 8, 12, 17, 23, 29, 35, 41, 50]

A binary search uses mid = (low + high) DIV 2, starting with low = 0 and high = 8.

(a) Show the values of mid and the item examined at each step when searching for 12. [2]

(b) State why a binary search cannot be used on an unsorted list. [1]

(a) Step 1: mid = 4, item 23 examined (the comparison and new low/high values shown in brackets here are not required for the mark: 12 < 23 so high becomes 3)(1)
(a) Step 2: mid = 1, item 8 examined (12 > 8 so low becomes 2); step 3: mid = 2, item 12 examined and found – both mid values 1 and 2 (with items 8 and 12) needed for the mark; ignore extra working such as low/high values(1)
(b) The algorithm relies on the items being in order to decide which half of the list to discard at each step; in an unsorted list the item could be in the discarded half (allow: it could not tell whether the item is before or after the middle)(1)
Answer: (a) mid = 4 (23), mid = 1 (8), mid = 2 (12, found) (b) It relies on the ordering to discard half the list.
Examiner tip: Show every mid value and the item at it – examiners award the method marks for the sequence, not just the final index.

2Standard5 marks

The binary tree below stores integers.

(a) Write the order in which the nodes are visited in a pre-order traversal. [1]

(b) Write the order in which the nodes are visited in an in-order traversal. [1]

(d) The tree is a binary search tree. Explain how your answer to part (b) shows this. [2]

(a) 40, 25, 15, 32, 60, 50, 75(1)
(b) 15, 25, 32, 40, 50, 60, 75(1)
(c) 15, 32, 25, 50, 75, 60, 40(1)
(d) In-order traversal gives the values in ascending (sorted) order(1)
(d) Because every value in a left subtree is smaller than its parent and every value in the right subtree is larger, visiting left, root, right produces ascending order(1)
Answer: (a) 40, 25, 15, 32, 60, 50, 75 (b) 15, 25, 32, 40, 50, 60, 75 (c) 15, 32, 25, 50, 75, 60, 40 (d) In-order gives sorted order.
Examiner tip: Pre-order is root-left-right, in-order is left-root-right, post-order is left-right-root – say the rule to yourself before you trace.

3Hard6 marks

The weighted graph below shows the distances, in km, between six locations.

Dijkstra's algorithm is used to find the shortest route from A to every other node. At each step, the unfinalised node with the smallest working distance is permanently labelled (finalised), and the working distance of each of its unfinalised neighbours is updated if the route through the finalised node is shorter.

(a) State the order in which the nodes are permanently labelled (finalised). [2]

(b) State the length of the shortest path from A to F. [1]

(d) Explain why the working value for B changes from 4 to 3 during the algorithm. [1]

(e) State one real-world application of Dijkstra's shortest path algorithm. [1]

(a) A, C, B – first three nodes in the correct order (allow the start node A omitted, i.e. C, B first)(1)
(a) D, E, F – remaining nodes in the correct order after A, C, B(1)
(b) 13 km (allow 13 with no units)(1)
(c) A–C–B–D–E–F(1)
(d) When C is finalised (distance 2), the route A–C–B gives 2 + 1 = 3, which is less than the direct edge A–B of 4(1)
(e) Any one valid application, e.g. satellite navigation / route planning (shortest or fastest road route); routing packets across a network (e.g. OSPF / link-state routing); planning shortest delivery or travel routes in logistics or games (pathfinding); finding cheapest flight or rail connections. Must be an application of finding a shortest/least-cost path; reject just ‘finding the shortest path’ with no context(1)
Answer: (a) A, C, B, D, E, F (b) 13 km (c) A–C–B–D–E–F (d) Going via C gives 2 + 1 = 3, which is less than the direct edge of 4 (e) e.g. satellite navigation (finding the shortest road route) or routing packets through a network.
Examiner tip: Update a working value only when the new total is smaller, and always finalise the unfinalised node with the smallest working value next.

4Standard4 marks

(a) Convert the infix expression (3 + 4) * (8 - 2) to reverse Polish notation (RPN). [2]

(b) Evaluate the RPN expression 5 1 2 + 4 * + 3 -. Show the contents of the stack as you work. [2]

(a) 3 4 + – the first bracket converted correctly(1)
(a) 3 4 + 8 2 - * – complete expression with * last(1)
(b) Evidence of correct stack use, e.g. 1 and 2 added to give 3, then 3 × 4 = 12 (stack 5, 12)(1)
(b) 5 + 12 = 17, then 17 − 3 = 14(1)
Answer: (a) 3 4 + 8 2 - * (b) 14
Examiner tip: Operands keep their order in RPN; only operators move – and for subtraction the first value popped is the right-hand operand.

5Standard5 marks

A bubble sort is used to sort [6, 2, 9, 4, 1] into ascending order. Each pass compares adjacent pairs from the start of the list, swapping them if they are out of order. The algorithm stops after a pass in which no swaps are made. No optimisation is made to shorten later passes.

(a) Write the contents of the list at the end of each pass until the algorithm stops. [3]

(b) State the total number of comparisons made. [1]

(a) After pass 1: [2, 6, 4, 1, 9]; after pass 2: [2, 4, 1, 6, 9](1)
(a) After pass 3: [2, 1, 4, 6, 9]; after pass 4: [1, 2, 4, 6, 9](1)
(a) Pass 5 makes no swaps: [1, 2, 4, 6, 9], so the algorithm stops(1)
(b) 20 (5 passes of 4 comparisons)(1)
(c) O(n²)(1)
Answer: (a) [[2, 6, 4, 1, 9], [2, 4, 1, 6, 9], [2, 1, 4, 6, 9], [1, 2, 4, 6, 9], [1, 2, 4, 6, 9]] (b) 20 (c) O(n^2)
Examiner tip: Don't forget the final pass with no swaps – that is the pass that tells the algorithm to stop, and its comparisons count.

6Hard6 marks

The undirected graph below is stored as an adjacency list. When choosing which neighbour to visit next, always choose the neighbour that is earliest alphabetically.

(a) Write the order in which nodes are visited in a breadth-first traversal starting at A. [2]

(b) Write the order in which nodes are visited in a depth-first traversal starting at A. [2]

(d) State the data structure that a depth-first traversal uses, either explicitly or through recursion. [1]

(a) First four correct: A, B, C, D(1)
(a) Complete order: A, B, C, D, E, F, G(1)
(b) First four correct: A, B, D, E(1)
(b) Complete order: A, B, D, E, F, C, G(1)
(c) Queue(1)
(d) Stack (the call stack when recursive)(1)
Answer: (a) A, B, C, D, E, F, G (b) A, B, D, E, F, C, G (c) queue (d) stack
Examiner tip: Depth-first goes as deep as possible before backtracking: after D you must return to B and carry on from E, not jump to C.

7Hard5 marks

A merge sort is used to sort [38, 27, 43, 3, 9, 82, 10] into ascending order. When a list has an odd number of items, the extra item goes in the left half.

(a) Show the two lists produced by the first split. [1]

(b) The lists are split until each contains one item, and are then merged back in pairs. Show the lists that exist after the first round of merging (a list with no partner is left unchanged). [2]

(d) State the time complexity of merge sort. [1]

(a) [38, 27, 43, 3] and [9, 82, 10](1)
(b) [27, 38] and [3, 43] from the left half(1)
(b) [9, 82] and [10] from the right half ([10] has no partner so is unchanged)(1)
(c) [3, 9, 10, 27, 38, 43, 82](1)
(d) O(n log n)(1)
Answer: (a) [38,27,43,3] | [9,82,10] (b) [27,38] [3,43] [9,82] [10] (c) [3,9,10,27,38,43,82] (d) O(n log n)
Examiner tip: Merge sort is divide-and-conquer: all the splitting happens first, then merging rebuilds sorted lists level by level.

8Stretch7 marks

A sorted list Data is stored in an array with indexes starting at 0.

(a) Write a recursive subroutine BinarySearch(Data, target, low, high) that returns the index of target within Data[low..high], or −1 if it is not present. The middle index must be found using (low + high) DIV 2. You may write your answer in pseudo-code or a programming language you have studied. [4]

(b) The list contains 16 items. State the greatest number of items that need to be examined by the search in the worst case. [1]

(a) Base case: IF low > high THEN RETURN −1 (must be checked before Data[mid] is accessed)(1)
(a) mid ← (low + high) DIV 2 and Data[mid] compared with target; RETURN mid if they are equal(1)
(a) If target < Data[mid], RETURN BinarySearch(Data, target, low, mid − 1) – the result of the recursive call is returned (allow the tests in the other order, e.g. target > Data[mid] tested first, provided each branch searches the correct half)(1)
(a) Otherwise RETURN BinarySearch(Data, target, mid + 1, high) – the result of the recursive call is returned (do not award if mid rather than mid ± 1 is passed, as the search may never end)(1)
(b) 5(1)
(c) Each recursive call creates a new stack frame (parameters, return address, local variables) on the call stack(1)
(c) Up to about log₂ n frames exist at the same time, whereas an iterative version only needs a fixed number of variables (constant memory)(1)

Answer: (a)

SUBROUTINE BinarySearch(Data, target, low, high)
  IF low > high THEN
    RETURN -1
  ENDIF
  mid ← (low + high) DIV 2
  IF Data[mid] = target THEN
    RETURN mid
  ELSEIF target < Data[mid] THEN
    RETURN BinarySearch(Data, target, low, mid - 1)
  ELSE
    RETURN BinarySearch(Data, target, mid + 1, high)
  ENDIF
ENDSUBROUTINE

(b) 5 (c) Every call adds a stack frame, so memory use grows with the recursion depth (about log₂ n); the iterative version uses a fixed amount.

Examiner tip: In (a), write RETURN in front of each recursive call: without it the result of the inner call is thrown away and the subroutine returns nothing.

Still losing marks on this topic?

Book a free introductory session and we'll find exactly which step is costing you.

Book a free intro