A-LevelComputer ScienceAlgorithm design and problem-solving9618/22 · Oct/Nov 2023 · Q39 Marks

The diagram represents a linked list Abstract Data Type (ADT). • Ptr1 is the start pointer. Ptr2 is the free list pointer. • Labels D40, D32, D11 and D100 represent the data items of nodes in the list. • Labels F1, F2, F3 and F4 represent the data items of nodes in the free list. • The symbol Ø represents a null pointer. [Figure showing linked list structure]

(a)The linked list is implemented using two variables and two 1D arrays as shown. The pointer variables and the elements of the Pointer array store the indices (index numbers) of elements in the Data array. Complete the diagram to show how the linked list as shown above may be represented using the variables and arrays. Variable Value Start_Pointer Free_List_Pointer 5 Index Data array Pointer array 1 D32 2 2 3 4 D40 5 6 F2 7 7 8[5]
(b)The original linked list is to be modified. A new node D6 is inserted between nodes D32 and D11. [Figure showing the initial linked list] The algorithm required is expressed in four steps as shown. Complete the steps. 1. Assign the data item ... to ... 2. Set the ... of this node to point to ... 3. Set Ptr2 to point to ... 4. Set pointer of ... to point to ...[4]

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 (Oct/Nov 2023). The mark or mark type is shown in brackets.

[5] Mark as follows:
One mark for Start_Pointer value
One mark each group of row(s):
2
3 and 4
5
7 and 8
For null pointer: accept 0 / Ø / an out-of-bound index value less than 1, greater than 8
[4] One mark per step:
1 Assign the data item D6 to F1
2 Set the pointer of this node to point to D11
3 Set Ptr2 to point to F2
4 Set pointer of D32 to point to D6

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.