A-LevelComputer ScienceData types and structures9618/31 · May/June 2025 · Q47 Marks

A linked list of nodes is used to store an ordered list of integers. Each node consists of the data, a left pointer and a right pointer, for example: Left pointer Data Right pointer [Figure showing a node with '20' in the data box and empty pointer boxes] The linked list will be organised as a binary tree. -1 is used to represent a null pointer.

(a)Complete the binary tree, including null pointers, to show how the data will be organised after the following integers have been added: 6, 15, 41, 66 [Figure showing a partial binary tree with Root pointer to 36, 12 as left child, 40 as right child][4]
(b)Describe what is meant by recursion.[2]
(c)A binary tree is a suitable Abstract Data Type (ADT) that a designer can implement using recursive algorithms. Identify one other ADT that a designer can implement using recursive algorithms.[1]

This question uses a diagram from the original paper, which isn't shown here. Open the full paper from the past papers archive to see it.

Mark scheme

Marking points from the official mark scheme (May/June 2025). The mark or mark type is shown in brackets.

[1] Any two nodes added correctly with correct data (6, 15, 41, 66) and arrows
[1] Remaining two nodes added with correct data (6, 15, 41, 66) and all nodes with connecting arrows starting from pointer boxes
[1] Correct null pointers (-1) added throughout
[1] All nodes correctly positioned and connected, with no entries in other pointer boxes
[1] A technique used to solve problems using a function/procedure/subroutine that calls itself (general case)
[1] ... until the terminating condition / base case is achieved, when no further recursive calls are made
[1] Stack

On Oracle Prep you can write or photograph your own answer and have it marked by AI against this mark scheme, with feedback on what you missed.