A-LevelComputer ScienceData types and structures9618/32 · Oct/Nov 2024 · Q1112 Marks

This binary tree shows an ordered list of integers. [Figure 11.1]

(a)A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer. -1 is used to represent a null pointer. Complete this linked list to represent the given binary tree organisation.[4]
(b)A 2D array is used to store the nodes of the linked list in part (a). Complete the diagram using your answer for part (a).[4]
(c)The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer. The following pseudocode represents a function that searches for an element in the array of records LinkList. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found. Complete the pseudocode for the function. FUNCTION SearchList(Item : INTEGER) NullPtr ← –1 NowPtr ← RootPtr WHILE NowPtr <> NullPtr IF LinkList[NowPtr].Data < Item THEN NowPtr ← LinkList[NowPtr].RightPtr ELSE IF NowPtr ← ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NullPtr ENDFUNCTION[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 2024). The mark or mark type is shown in brackets.

[4] One mark per mark point (Max 4)
[4] MP1 Five additional nodes with correct data values
[4] MP2 Correct null pointers in all nodes (7) – no extra null pointers where the arrow points to the next node
[4] MP3 Correct arrows to represent pointers joining parent nodes to child nodes – must come from the correct left or right pointer not the middle
[4] MP4 All nodes in correct order and no additional data in left/right pointer boxes.
[4] [Diagram showing nodes and pointers correctly representing the binary tree: RootPtr -> Node0 (LeftPtr=1, Data=25, RightPtr=2) Node1 (LeftPtr=3, Data=4, RightPtr=4) Node2 (LeftPtr=5, Data=36, RightPtr=6) Node3 (LeftPtr=-1, Data=1, RightPtr=-1) Node4 (LeftPtr=-1, Data=9, RightPtr=-1) Node5 (LeftPtr=-1, Data=16, RightPtr=-1) Node6 (LeftPtr=7, Data=49, RightPtr=-1) Node7 (LeftPtr=-1, Data=64, RightPtr=-1)]
[4] First eight rows of table (Max 3)
[4] Three marks for all eight correct rows
[4] Two marks for six or seven correct rows
[4] One mark for three, four or five correct rows
[4] Last row of table and FreePtr (Max 1)
[4] One mark for correct FreePtr with last row of table completely blank
[4] RootPtr: 0 FreePtr: 8 Index | LeftPtr | Data | RightPtr 0 | 1 | 25 | 2 1 | 3 | 4 | 4 2 | 5 | 36 | 6 3 | -1 | 1 | -1 4 | -1 | 9 | -1 5 | -1 | 16 | -1 6 | 7 | 49 | -1 7 | -1 | 64 | -1 8 | | |
[4] One mark for any correct row (Max 4)
[4] FUNCTION SearchList(Item : INTEGER) RETURNS INTEGER NullPtr ← -1 NowPtr ← RootPtr WHILE NowPtr <> NullPtr IF LinkList[NowPtr].Data < Item THEN NowPtr ← LinkList[NowPtr].RightPtr ELSE IF LinkList[NowPtr].Data > Item THEN NowPtr ← LinkList[NowPtr].LeftPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NullPtr ENDFUNCTION