Cambridge A Level Computer Science 9608 — 2017 May/June Paper 4 · Variant 1

This document consists of 15 printed pages and 1 blank page. DC (RW/SW) 129953/3 © UCLES 2017 [Turn over Cambridge International Examinations Cambridge International Advanced Subsidiary and Advanced Level * 5 0 1 0 7 4 8 6 1 4 * COMPUTER SCIENCE 9608/41 Paper 4 Further Problem-solving and Programming Skills May/June 2017 2 hours Candidates answer on the Question Paper. No Additional Materials are required. No calculators allowed. READ THESE INSTRUCTIONS FIRST Write your Centre number, candidate number and name in the spaces at the top of this page. Write in dark blue or black pen. You may use an HB pencil for any diagrams, graphs or rough working. Do not use staples, paper clips, glue or correction fluid. DO NOT WRITE IN ANY BARCODES. Answer all questions. No marks will be awarded for using brand names of software packages or hardware. At the end of the examination, fasten all your work securely together. The number of marks is given in brackets [ ] at the end of each question or part question. The maximum number of marks is 75.

2 9608/41/M/J/17 © UCLES 2017 1 The following table shows part of the instruction set for a processor which has one general purpose register, the Accumulator (ACC), and an Index Register (IX). Instruction Explanation Op code Operand LDM #n Immediate addressing. Load the number n to ACC. LDD <address> Direct addressing. Load the contents of the location at the given address to ACC. LDI <address> Indirect addressing. The address to be used is at the given address. Load the contents of this second address to ACC. LDX <address> Indexed addressing. Form the address from <address> + the contents of the index register. Copy the contents of this calculated address to ACC. STO <address> Store the contents of ACC at the given address. INC <register> Add 1 to the contents of the register (ACC or IX). DEC <register> Subtract 1 from the contents of the register (ACC or IX). CMP <address> Compare the contents of ACC with the contents of <address>. JMP <address> Jump to given address. JPE <address> Following a compare instruction, jump to <address> if the compare was True. JPN <address> Following a compare instruction, jump to <address> if the compare was False. AND <address> Bitwise AND operation of the contents of ACC with the contents of <address>. XOR <address> Bitwise XOR operation of the contents of ACC with the contents of <address>. OR <address> Bitwise OR operation of the contents of ACC with the contents of <address>. IN Key in a character and store its ASCII value in ACC. OUT Output to the screen the character whose ASCII value is stored in ACC. END Return control to the operating system. (a) A programmer writes a program that: • reads a character from the keyboard (assume it will be a capital letter) • outputs the alphabetical sequence of characters from ‘A’ to the character input. For example, if the character ‘G’ is input, the output is: ABCDEFG The programmer has started to write the program in the table on the following page. The Comment column contains descriptions for the missing instructions, labels and data.

3 9608/41/M/J/17 © UCLES 2017 [Turn over Complete the following program. Use op codes from the given instruction set. Label Op code Operand Comment START: // INPUT character // store in CHAR // Initialise ACC (ASCII value for 'A' is 65) // OUTPUT ACC // compare ACC with CHAR // if equal jump to end of FOR loop // increment ACC // jump to LOOP ENDFOR: END CHAR: [8] (b) The programmer now starts to write a program that: • tests whether an 8-bit two’s complement integer stored at address NUMBER is positive or negative • outputs 'P' for a positive integer and 'N' for a negative integer. Complete the following program. Use op codes from the given instruction set. Show the required value of MASK in binary. Label Op code Operand Comment START: MASK // set to zero all bits except sign bit // compare with 0 // if not equal jump to ELSE THEN: // load ACC with 'P' (ASCII value 80) JMP ENDIF ELSE: // load ACC with 'N' (ASCII value 78) ENDIF: END NUMBER: B00000101 // integer to be tested MASK: // value of mask in binary [7]

4 9608/41/M/J/17 © UCLES 2017 2 A hash table has these associated operations: • create hash table • insert record • search hash table A hash table is to be used to store customer records. Each record consists of a unique customer ID, the record key, and other customer data. (a) The following pseudocode declares a customer record structure. TYPE CustomerRecord CustomerID : INTEGER Data : STRING ENDTYPE The hash table is to be implemented as a 1D array Customer with elements indexed 0 to 199. The procedure to create a hash table will declare and initialise the array by storing 200 records with the CustomerID field in each record set to 0. Complete the pseudocode. PROCEDURE CreateHashTable() … … … … ENDPROCEDURE [4] (b) A hashing function Hash exists, which takes as a parameter the customer ID and returns an integer in the range 0 to 199 inclusive. (i) The procedure, InsertRecord, takes as a parameter the customer record to be inserted into the hash table. The procedure makes use of the function Hash. Collisions will be managed using open hashing. This means a collision is resolved by storing the record in the next available location. The procedure will generate an error message if the hash table is full.

5 9608/41/M/J/17 © UCLES 2017 [Turn over Complete the pseudocode for the procedure. PROCEDURE InsertRecord(BYVALUE NewCustomer : CustomerRecord) TableFull FALSE // generate hash value Index … Pointer Index // initialise Pointer variable to hash value // find a free table element WHILE … Pointer … // wrap back to beginning of table if necessary IF … THEN … ENDIF // check if back to original index IF … THEN TableFull TRUE ENDIF ENDWHILE IF … THEN … ELSE … ENDIF ENDPROCEDURE [9]

6 9608/41/M/J/17 © UCLES 2017 (ii) The function SearchHashTable will search for a record in the hash table. The function takes as a parameter the customer ID to be searched for. The function will return the position in the hash table where the record has been saved. If the hash table does not contain the record, the function will return the value −1. You can assume that there is at least one empty record in the hash table. Complete the pseudocode for the function. FUNCTION SearchHashTable(BYVALUE SearchID : INTEGER) RETURNS INTEGER // generate hash value Index … // check each record from index until found or not there WHILE ( …) AND (…) … // wrap if necessary IF … THEN … ENDIF ENDWHILE // has customer ID been found ? IF … THEN … ELSE … ENDIF ENDFUNCTION [9] (iii) A record that is no longer required is deleted. State the problem that might be caused by this deletion. … …[1]

7 9608/41/M/J/17 © UCLES 2017 [Turn over 3 NameList is a 1D array that stores a sorted list of names. A programmer declares the array in pseudocode as follows: NameList : Array[0 : 100] OF STRING The programmer wants to search the list using a binary search algorithm. The programmer decides to write the search algorithm as a recursive function. The function, Find, takes three parameters: • Name, the string to be searched for • Start, the index of the first item in the list to be searched • Finish, the index of the last item in the list to be searched The function will return the position of the name in the list, or −1 if the name is not found. Complete the pseudocode for the recursive function. FUNCTION Find(BYVALUE Name : STRING, BYVALUE Start : INTEGER, BYVALUE Finish : INTEGER) RETURNS INTEGER // base case IF … THEN RETURN −1 ELSE Middle … IF … THEN RETURN … ELSE // general case IF SearchItem > … THEN … ELSE … ENDIF ENDIF ENDIF ENDFUNCTION [7]

8 9608/41/M/J/17 © UCLES 2017 4 An ordered linked list Abstract Data Type (ADT) has these associated operations: • create list • add item to list • output list to console The ADT is to be implemented using object-oriented programming as a linked list of nodes. Each node consists of data and a pointer. (a) There are two classes, LinkedList and Node. (i) State the term used to describe the relationship between these classes. …[1] (ii) Draw the appropriate diagram to represent this relationship. Do not list the attributes and methods of the classes. [2]

9 9608/41/M/J/17 © UCLES 2017 [Turn over (b) The design for the Node class consists of: • attributes Data : STRING Pointer : INTEGER • methods CreateNode(Data, Pointer) SetData(Data) SetPointer(Pointer) GetData() RETURNS STRING GetPointer() RETURNS INTEGER The constructor method sets the attributes to the initial values that are passed as parameters. Write program code for: • the Node class declaration • the constructor. Programming language used … Program code … … … … … … … … … … … … … … … …[5]

10 9608/41/M/J/17 © UCLES 2017 (c) The identifier table for the LinkedList class is: Identifier Data type Description HeadPointer INTEGER Pointer to the first node in the ordered list. FreeListPointer INTEGER Pointer to the first node in the free list. NodeArray ARRAY[0 : 7] OF Node 1D array stores the nodes that make the ordered linked list. The unused nodes are linked together into a free list. Constructor() Constructor instantiates an object of LinkedList class, initialises HeadPointer to be a null pointer and links all nodes to form the free list. FindInsertionPoint() Procedure that takes the new data item as the parameter NewData and returns two parameters: • PreviousPointer, whose value is: either pointer to node before the insertion point or the null pointer if the new node is to be inserted at the beginning of the list. • NextPointer, whose value is a pointer to node after the insertion point. AddToList(NewString) Procedure that takes as a parameter a unique string and links it into the correct position in the ordered list. OutputListToConsole() Procedure to output all the data from the list pointed to by HeadPointer. The following diagram shows an example of a linked list object. This example list consists of three nodes, linked in alphabetical order of the data strings. The unused nodes are linked to form a free list. Ø Ø node node node node node node node Berlin London Paris FreeListPointer HeadPointer The symbol O represents a null pointer. (i) Explain the meaning of the term null pointer. … …[1]

11 9608/41/M/J/17 © UCLES 2017 [Turn over (ii) Give an appropriate value to represent the null pointer for this design. Justify your answer. … … … …[2] (iii) Write program code for the LinkedList class declaration and the constructor. Programming language used … Program code … … … … … … … … … … … … … … … … … … … … … …[7]

12 9608/41/M/J/17 © UCLES 2017 (iv) Write program code to instantiate a linked list object with the contacts identifier. Programming language used … Program code … …[1] (v) The OutputListToConsole method is to output all the data stored in the linked list. HeadPointer points to the first list node. Write program code for this method. Programming language used … Program code … … … … … … … … … … …[5]

13 9608/41/M/J/17 © UCLES 2017 [Turn over Question 4 continues on page 14.

14 9608/41/M/J/17 © UCLES 2017 (vi) The structured English for the AddToList(NewString) method is as follows: Make a copy of the value of free list pointer, name it NewNodePointer Store new data item in free node pointed to by NewNodePointer Adjust free list pointer to point to next free node IF linked list is currently empty THEN Make this node the first node Set pointer of this node to null pointer ELSE Find insertion point using the FindInsertionPoint method // FindInsertionPoint provides // pointer to previous node and pointer to next node IF previous pointer is null pointer THEN Link this node to front of list ELSE Link this node between previous node and next node The FindInsertionPoint method receives the new data item as the parameter NewString. It returns two parameters: • PreviousPointer, whose value is: either the pointer to the node before the insertion point or the null pointer, if the new node is to be inserted at the beginning of the list. • NextPointer, whose value is the pointer to the node after the insertion point.

15 9608/41/M/J/17 © UCLES 2017 Write program code for the AddToList method. Programming language used … Program code … … … … … … … … … … … … … … … … … … … … … … … … … … …[6]

16 9608/41/M/J/17 © UCLES 2017 BLANK PAGE Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the publisher will be pleased to make amends at the earliest possible opportunity. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge International Examinations Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cie.org.uk after the live examination series. Cambridge International Examinations is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge.

® IGCSE is a registered trademark. This document consists of 13 printed pages. © UCLES 2017 [Turn over Cambridge International Examinations Cambridge International Advanced Subsidiary and Advanced Level COMPUTER SCIENCE 9608/41 Paper 4 Written Paper May/June 2017 MARK SCHEME Maximum Mark: 75 Published This mark scheme is published as an aid to teachers and candidates, to indicate the requirements of the examination. It shows the basis on which Examiners were instructed to award marks. It does not indicate the details of the discussions that took place at an Examiners’ meeting before marking began, which would have considered the acceptability of alternative answers. Mark schemes should be read in conjunction with the question paper and the Principal Examiner Report for Teachers. Cambridge will not enter into discussions about these mark schemes. Cambridge is publishing the mark schemes for the May/June 2017 series for most Cambridge IGCSE®, Cambridge International A and AS Level and Cambridge Pre-U components, and some Cambridge O Level components.

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 2 of 13 Question Answer Marks 1(a) Label Op code Operand Comment START: IN // INPUT character STO CHAR // store in CHAR 1 LDM #65 // Initialise ACC (ASCII value for 'A' is 65) 1 LOOP: OUT // OUTPUT ACC 1 + 1 CMP CHAR // compare ACC with CHAR 1 JPE ENDFOR // if equal jump to end of FOR loop 1 INC ACC // increment ACC 1 JMP LOOP // jump to LOOP 1 ENDFOR: END CHAR: 8 1(b) START: LDD NUMBER 1 AND MASK // set to zero all bits except sign bit 1 CMP #0 // compare with 0 1 JPN ELSE // if not equal jump to ELSE 1 THEN: LDM #80 // load ACC with 'P' (ASCII value 80) 1 JMP ENDIF ELSE: LDM #78 // load ACC with 'N' (ASCII value 78) ENDIF: OUT //output character 1 END NUMBER: B00000101 // integer to be tested MASK: B10000000 // show value of mask in binary here 1 7

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 3 of 13 Question Answer Marks 2(a) 1 mark for the declaration of the array. 1 mark for assigning a 0 to Customer ID (CustomerID ← 0) 1 mark for getting the correct record (Customer[x].) 1 mark for setting up a loop to go from 0 to 199 DECLARE Customer : ARRAY[0 : 199] OF CustomerRecord 1 FOR x ← 0 TO 199 1 Customer[x].CustomerID ← 0 1+1 ENDFOR 4 2(b)(i) PROCEDURE InsertRecord(BYVAL NewCustomer : CustomerRecord) TableFull ← FALSE // generate hash value Index ← Hash(NewCustomer.CustomerID) 1 Pointer ← Index // take a copy of index // find a free table element WHILE Customer[Pointer].CustomerID > 0 1 Pointer ← Pointer + 1 1 // wrap back to beginning of table if necessary IF Pointer > 199 1 THEN Pointer ← 0 1 ENDIF // check if back to original index IF Pointer = Index 1 THEN TableFull ← TRUE ENDIF ENDWHILE IF NOT TableFull 1 THEN Customer[Pointer] ← NewCustomer 1 ELSE OUTPUT "Error" 1 ENDIF ENDPROCEDURE 9

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 4 of 13 Question Answer Marks 2(b)(ii) FUNCTION SearchHashTable(BYVAL SearchID : INTEGER) RETURNS INTEGER // generate hash value Index ← Hash(SearchID) 1 // check each record from index until found or not there WHILE (Customer[Index].CustomerID <> SearchID) 1 AND (Customer[Index].CustomerID > 0) 1 Index ← Index + 1 1 // wrap if necessary IF Index > 199 1 THEN Index ← 0 1 ENDIF ENDWHILE // has customer ID been found? IF Customer[Index].CustomerID = SearchID 1 THEN RETURN Index 1 ELSE RETURN -1 1 ENDIF ENDFUNCTION 9 2(b)(iii) A record out of place may not be found 1

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 5 of 13 Question Answer Marks 3 FUNCTION Find(BYVAL Name : STRING, BYVAL Start : INTEGER, BYVAL Finish : INTEGER) RETURNS INTEGER // base case IF Finish < Start 1 THEN RETURN -1 ELSE Middle ← (Start + Finish) DIV 2 1 IF NameList[Middle] = Name 1 THEN RETURN Middle 1 ELSE // general case IF SearchItem > NameList[Middle] 1 THEN Find(Name, Middle + 1, Finish) 1 ELSE Find(Name, Start, Middle - 1) 1 ENDIF ENDIF ENDIF ENDFUNCTION 7 Question Answer Marks 4(a)(i) containment/aggregation 1 4(a)(ii) 1 mark for the two classes (in boxes) and connection with correct end point 1 mark for 0 ..* 0 Max 2

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 6 of 13 Question Answer Marks 4(b) mark as follows: • Class heading and ending • Constructor heading and ending • Parameters in constructor heading • Declaration of (private) attributes : Pointer, Data • Assignment of parameters to Pointer and Data Python Example class Node: 1 def __init__(self, D, P): 1 + 1 self.__Data = D 1 self.__Pointer = P 1 return Example Pascal type Node = class 1 private 1 Data : String; Pointer : Integer; public constructor Create(D : string; P : integer); procedure SetPointer(P : Integer); procedure SetData(D : String); function GetData() : String; ignore function GetPointer() : Integer; end; constructor Node.Create(D : string; P : integer); 1+1 begin Data := D; Pointer := P; 1 end; Example VB.NET Class Node 1 Private Data As String Private Pointer As Integer 1 Public Sub New(ByVal D As String, ByVal P As Integer) 1+1 Data = D Pointer = P 1 End Sub End Class 5 4(c)(i) A pointer that doesn’t point to any data/node/address 1

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 7 of 13 Question Answer Marks 4(c)(ii) –1 (accept NULL) The array only goes from 0 to 7 // the value is not an array index 2 4(c)(iii) mark as follows: • Class and constructor heading and ending • Declare private attributes (HeadPointer, FreeListPointer, NodeArray) • Initialise HeadPointer to null • Initialise FreeListPointer to 0 • Looping 8 times « • Creating empty node in NodeArray • Use .SetPointer method to point each new node to next node • Set last node pointer to null pointer Python Example class LinkedList: 1 def __init__(self): 1 self.__HeadPointer = - 1 1 self.__FreeListPointer = 0 1 self.__NodeArray = [] for i in range(8): 1 ThisNode = Node("", (i + 1)) 1 self.__NodeArray.append(ThisNode) self.__NodeArray[7].SetPointer(- 1) 1 Example Pascal type LinkedList = class 1 private HeadPointer : Integer; FreeList : Integer; NodeArray : Array[0..7] of Node; public constructor Create(); procedure FindInsertionPoint(NewData : string; var PreviousPointer, NextPointer : integer); procedure AddToList(NewData : string); procedure OutputListToConsole(); end; constructor LinkedList.Create(); 1 var i : integer; begin HeadPointer := -1; 1 FreeList := 0; 1 for i := 0 To 7 do 1 NodeArray[i] := Node.Create('', (i + 1)); 1 NodeArray[7].SetPointer(-1); 1 end; Max 7

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 8 of 13 Question Answer Marks Example VB.NET Class LinkedList 1 Private HeadPointer As Integer Private FreeList As Integer Private NodeArray(7) As Node Public Sub New() 1 HeadPointer = -1 1 FreeList = 0 1 For i = 0 To 7 1 NodeArray(i) = New Node("", (i + 1)) 1 Next NodeArray(7).SetPointer(-1) 1 End Sub End Class 4(c)(iv) • Creating instance of LinkedList assigned to contacts Python Example contacts = LinkedList() Pascal Example var contacts : LinkedList; contacts := LinkedList.Create; VB.NET Example Dim contacts As New LinkedList 1

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 9 of 13 Question Answer Marks 4(c)(v) mark as follows: • Start with HeadPointer • Output node data • Loop until null pointer • Following pointer to next node • Use of getter (ie GetData/GetPointer) Python Example def OutputListToConsole(self) : Pointer = self.__HeadPointer 1 while Pointer != -1 : 1 print(self.__NodeArray[Pointer].GetData()) 1+1 Pointer = self.__NodeArray[Pointer].GetPointer() 1 print() return Pascal Example procedure LinkedList.OutputListToConsole(); var Pointer : integer; begin Pointer := HeadPointer; 1 while Pointer <> -1 do 1 begin WriteLn(NodeArray[Pointer].GetData); 1+1 Pointer := NodeArray[Pointer].GetPointer; 1 end; end; VB.NET Example Public Sub OutputListToConsole() Dim Pointer As Integer Pointer = HeadPointer 1 Do While Pointer <> -1 1 Console.WriteLine(NodeArray(Pointer).GetData) 1+1 Pointer = NodeArray(Pointer).GetPointer 1 Loop End Sub 5

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 10 of 13 Question Answer Marks 4(c)(vi) mark as follows: • Store free list pointer as NewNodePointer • Store new data item in free node • Adjust free pointer • F list is currently empty • Make the node the first node • Set pointer of this node to Null Pointer • Find insertion point • If previous pointer is Null pointer • Link this node to front of list • Link new node between Previous node and next node Python Example def AddToList(self, NewData): NewNodePointer = self.__FreeListPointer self.__NodeArray[NewNodePointer].SetData(NewData) self.__FreeListPointer = self.__NodeArray[self.__FreeListPointer].GetPointer() if self.__HeadPointer == -1: self.__HeadPointer = NewNodePointer self.__NodeArray[NewNodePointer ].SetPointer(-1) else: PreviousPointer, NextPointer = self.FindInsertionPoint(NewData) if PreviousPointer == -1 : self.__NodeArray[NewNodePointer ].SetPointer (self.__HeadPointer) self.__HeadPointer = NewNodePointer else: self.__NodeArray[NewNodePointer ].SetPointer(NextPointer) self.__NodeArray[PreviousPointer].SetPointer(NewNodePointer) Max 6

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 11 of 13 Question Answer Marks Pascal Example procedure LinkedList.AddToList(NewData : string); var NewNodePointer , PreviousPointer, NextPointer : integer; begin // make a copy of free list pointer NewNodePointer := FreeListPointer; // store new data item in free node NodeArray[NewNodePointer].SetData(NewData); // adjust free pointer FreeListPointer := NodeArray[FreeListPointer].GetPointer; // if list is currently empty if HeadPointer = -1 then // make the node the first node begin HeadPointer := NewNodePointer; // set pointer to Null pointer NodeArray[NewNodePointer].SetPointer(-1); end else // find insertion point begin FindInsertionPoint(NewData, PreviousPointer, NextPointer); // if previous pointer is Null pointer if PreviousPointer = -1 then // link node to front of list begin NodeArray[NewNodePointer] .SetPointer(HeadPointer); HeadPointer := NewNodePointer ; end else // link new node between Previous node and next node begin NodeArray[NewNodePointer ] .SetPointer(NextPointer); NodeArray[PreviousPointer] .SetPointer(NewNodePointer); end; end; end;

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 12 of 13 Question Answer Marks VB.NET Example Public Sub AddToList(ByVal NewData As String) Dim NewNodePointer, PreviousPointer, NextPointer As Integer ' make copy of free list pointer NewNodePointer= FreeListPointer ' store new data item in free node NodeArray(NewNodePointer).SetData(NewData) ' adjust free pointer FreeListPointer = NodeArray(FreeListPointer).GetPointer ' if list iscurrently empty If HeadPointer = -1 Then ' make the node the first node HeadPointer = NewNodePointer ' set pointer to Null pointer NodeArray(NewNodePointer).SetPointer(-1) Else ' find insertion point FindInsertionPoint(NewData, PreviousPointer, NextPointer) ' if previous pointer is Null pointer If PreviousPointer = -1 Then ' link to front of list NodeArray(NewNodePointer).SetPointer(HeadPointer) HeadPointer = NewNodePointer Else ' link new node between Previous node and next node NodeArray(NewNodePointer).SetPointer(NextPointer) NodeArray(PreviousPointer).SetPointer(NewNodePointer) End If End If End Sub

9608/41 Cambridge International AS/A Level – Mark Scheme PUBLISHED May/June 2017 © UCLES 2017 Page 13 of 13 Question Answer Marks Pseudocode for reference: PROCEDURE AddToList(NewData) // remember value of free list pointer NewNodePointer ← FreeListPointer // add new data item to free node pointed to by free list NodeArray[NewNodePointer].Data ← NewData // adjust free pointer to point to next free node FreeListPointer ← NodeArray[FreeList].Pointer // is list currently empty? IF HeadPointer = NullPointer THEN // make the node the first node HeadPointer ← NewnodePointer // set pointer of new node to Null pointer NodeArray[NewNodePointer].Pointer ← NullPointer ELSE // find insertion point CALL FindInsertionPoint(NewData, PreviousPPointer, NextPointer) // if previous pointer is Null pointer IF PreviousPointer = NullPointer THEN // link new node to front of list NodeArray[NewNodePointer].Pointer ← HeadPointer HeadPointer ← NewNodePointer ELSE // link new node between previous node and next node NodeArray[NewNodePointer].Pointer ← NextPOinter NodeArray[PreviousPointer].Pointer ← NewNodePointer END IF ENDIF END PROCEDURE