A-LevelComputer ScienceData types and structures9618/22 · May/June 2025 · Q69 Marks

Two arrays Data and Pointer are accessed by the procedure Place() Data and Pointer are both global arrays of type INTEGER The contents of these two arrays are shown: Data 1 1018 2 1007 3 1010 4 1056 5 1092 6 1062 7 1034 8 0 9 0 10 0 Pointer 1 7 2 3 3 1 4 6 5 -1 6 5 7 4 8 9 9 10 10 -1 Study the pseudocode: PROCEDURE Place(Value : INTEGER, Start : INTEGER, Unused : INTEGER) DECLARE New, Current, Last : INTEGER CONSTANT NullPointer = -1 New ← Unused Last ← NullPointer Current ← Start WHILE Current <> NullPointer AND Data[Current] < Value Last ← Current Current ← Pointer[Current] ENDWHILE Pointer[New] ← Pointer[Last] Pointer[Last] ← New Data[New] ← Value ENDPROCEDURE

(a)(i)Complete the trace table below by dry running the procedure Place() when it is called by the statement: CALL Place (1043, 2,8) Value Start Unused New Last Current[4]
(a)(ii)Complete the diagram showing the contents of the global arrays Data and Pointer after the procedure Place() has run to completion when called as shown in part (a)(i). Data 1 1018 2 1007 3 1010 4 1056 5 1092 6 1062 7 1034 8 9 10 Pointer 1 2 3 4 5 6 7 8 9 10[3]
(b)The operation carried out by procedure Place() together with the arrays form part of the implementation of an Abstract Data Type (ADT). Identify the ADT and state the operation carried out by procedure Place()[2]

Mark scheme

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

[4] Value Start Unused New Last Current 1043 2 8 8 -1 2 Value Start Unused New Last Current 1043 2 8 8 -1 2 1043 2 8 8 2 3 1043 2 8 8 3 1 1043 2 8 8 1 7 1043 2 8 8 7 4 Award 1 mark per region
[3] Data 1 1018 2 1007 3 1010 4 1056 5 1092 6 1062 7 1034 8 1043 9 0 10 0 Pointer 1 7 2 3 3 1 4 6 5 -1 6 5 7 8 8 4 9 10 10 -1 Mark as follows: 1 mark for global array Data row 8 containing the value 1043 1 mark for global array Pointer row 7 containing the value 8 and row 8 containing the value 4 1 mark for all other rows in both arrays
[2] Example answer: The ADT is a linked list and the procedure Place() inserts / add a new node / value into it / the linked list Mark as follows: 1. 1 mark for identifying the ADT as a linked list 2. 1 mark for identifying operation as inserting / adding a value / node into a linked list

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.