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

The following diagram shows an ordered binary tree. [Figure X.X - binary tree diagram]

(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. [Figure X.X - linked list template][4]
(b)A user-defined record structure is used to store the nodes of the linked list in part (a). Complete the diagram, using your answer for part (a). [Figure X.X - table template][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 BinTree. 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. [Figure X.X - pseudocode template][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.

11(a) One mark per mark point (Max 4)
11(a) MP1 Four additional nodes with correct data values
11(a) MP2 Correct null pointers in all added nodes (6) with no extra null pointers where the arrow points to the next node
11(a) MP3 Correct arrows to represent pointers joining parent nodes to child nodes
11(a) MP4 All nodes in correct order and no extra data added to pointers.
11(a) [Figure X.X - completed linked list diagram for the binary tree where RootPtr points to Red (data), LeftPtr points to Green, RightPtr points to Yellow. Green's LeftPtr points to Blue, RightPtr points to Orange. Blue's LeftPtr and RightPtr are -1. Orange's LeftPtr points to Indigo, RightPtr is -1. Indigo's LeftPtr and RightPtr are -1. Yellow's LeftPtr points to Violet, RightPtr is -1. Violet's LeftPtr and RightPtr are -1.]
11(b) One mark per mark point (Max 4)
11(b) MP1 Correct Red and Green rows
11(b) MP2 Correct Yellow and Blue rows
11(b) MP3 Correct Orange, Indigo and Violet rows
11(b) MP4 Correct FreePtr with blank row 7
11(b) RootPtr: 0 FreePtr: 7 Index | LeftPtr | Data | RightPtr ------|---------|------|--------- 0 | 1 | Red | 2 1 | 3 | Green| 4 2 | 6 | Yellow| -1 3 | -1 | Blue | -1 4 | 5 | Orange| -1 5 | -1 | Indigo| -1 6 | -1 | Violet| -1 7 | | |
11(c) One mark for any correct row (Max 4)
11(c) FUNCTION SearchTree(Item : STRING) RETURNS INTEGER NowPtr ← RootPtr WHILE NowPtr <> -1 IF BinTree[NowPtr].Data > Item THEN NowPtr ← BinTree[NowPtr].LeftPtr ELSE IF BinTree[NowPtr].Data < Item THEN NowPtr ← BinTree[NowPtr].RightPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NowPtr ENDFUNCTION