Arrays — Paper 4 · A Level Computer Science 9618

1 An unordered linked list uses a 1D array to store the data. Each item in the linked list is of a record type, node, with a field data and a field nextNode. The current contents of the linked list are: startPointer 0 Index data nextNode 0 1 1 emptyList 5 1 5 4 2 6 7 3 7 -1 4 2 2 5 0 6 6 0 8 7 56 3 8 0 9 9 0 -1 (a) The following is pseudocode for the record type node. TYPE node DECLARE data : INTEGER DECLARE nextNode : INTEGER ENDTYPE Write program code to declare the record type node. Save your program as question1. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) Write program code for the main program. Declare a 1D array of type node with the identifier linkedList, and initialise it with the data shown in the table on page 2. Declare the pointers. Save your program. Copy and paste the program code into part 1(b) in the evidence document. [4] (c) The procedure outputNodes() takes the array and startPointer as parameters. The procedure outputs the data from the linked list by following the nextNode values. (i) Write program code for the procedure outputNodes(). Save your program. Copy and paste the program code into part 1(c)(i) in the evidence document. [6] (ii) Edit the main program to call the procedure outputNodes(). Take a screenshot to show the output of the procedure outputNodes(). Save your program. Copy and paste the screenshot into part 1(c)(ii) in the evidence document. [1] (d) The function, addNode(), takes the linked list and pointers as parameters, then takes as input the data to be added to the end of the linkedList. The function adds the node in the next available space, updates the pointers and returns True. If there are no empty nodes, it returns False. (i) Write program code for the function addNode(). Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [7] (ii) Edit the main program to: • call addNode() • output an appropriate message depending on the result returned from addNode() • call outputNodes() twice; once before calling addNode() and once after calling addNode(). Save your program. Copy and paste the program code into part 1(d)(ii) in the evidence document. [3] (iii) Test your program by inputting the data value 5 and take a screenshot to show the output. Save your program. Copy and paste the screenshot into part 1(d)(iii) in the evidence document. [1]

24 marks

Mark scheme: 1(a) 1 mark per bullet point • Declaring record/class with name node… • …declaring data and next node (both as Integers) Example code: Visual Basic Structure node Dim Data As Integer Dim nextNode As Integer End Structure Python class node: def __init__(self, theData, nextNodeNumber): self. Data = theData self.nextNode = nextNodeNumber Java class node{ private Integer Data; private Integer nextNode; public node(Integer dataP, Integer nextNodeP){ this.Data = dataP; this.nextNode = nextNodeP; } } Question Answer Marks 1(b) 1 mark per bullet point • Declaring array named linkedList with data type node • Assigning all nodes correctly as record/object nodes … • …with correct values stored • declaring startPointer as 0, emptyList as 5 Example code: Visual Basic Dim linkedList(9) As node linkedList(0).data = 1 linkedList(0).nextNode = 1 linkedList(1).data = 5 linkedList(1).nextNode = 4 linkedList(2).data = 6 linkedList(2).nextNode = 7 linkedList(3).data = 7 linkedList(3).nextNode = -1 linkedList(4).data = 2 linkedList(4).nextNode = 2 linkedList(5).data = 0 linkedList(5).nextNode = 6 linkedList(6).data = 0 linkedList(6).nextNode = 8 linkedList(7).data = 56 linkedList(7).nextNode = 3 linkedList(8).data = 0 linkedList(8).nextNode = 9 linkedList(9).data = 0 linkedList(9).nextNode = -1 Dim startPointer As Integer = 0 Dim emptyList As Integer = 5 4 Question Answer Marks 1(b) Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(0,6), node(0,8),node(56,3),node(0,9),node(0,-1)] startPointer = 0 emptyList = 5 Java public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(0,6); linkedList[6] = new node(0,8); linkedList[7] = new node(56, 3); linkedList[8] = new node(0,9); linkedList[9] = new node(0,-1); Integer startPointer = 0; Integer emptyList = 5; } Question Answer Marks 1(c)(i) 1 mark per bullet point • Procedure outputNodes … • …taking linked list and start pointer as parameters • Looping until nextNode/pointer is –1 • Outputting the node data in the correct order, i.e. following pointers • Updating pointer to current node’s nextNode • Using the correct record/class field/properties throughout Example code: Visual Basic Sub outputNodes(ByRef linkedList, ByVal currentPointer) While (currentPointer <> -1) Console.WriteLine(linkedList(currentPointer).data) currentPointer = linkedList(currentPointer).nextNode End While End Sub Python def outputNodes(linkedList, currentPointer): while(currentPointer != -1): print(str(linkedList[currentPointer].data)) currentPointer = linkedList[currentPointer].nextNode Java public static void outputNodes(node[] linkedList, Integer currentPointer){ while(currentPointer != -1){ System.out.println(linkedList[currentPointer].data); currentPointer = linkedList[currentPointer].nextNode; } } 6 Question Answer Marks 1(c)(ii) Screenshot showing: 1 5 2 6 56 7 1 1(d)(i) 1 mark per bullet point to max 7 • Function taking list and both pointers as parameters • Taking (integer) data as input • Checking if list is full … • … and returning False • Insert the input data to the empty list node’s data • Following pointers to find last node in Linked List … • …and updating last node’s pointer to empty list/location where new node is added • Updating empty list to it’s first elements pointer • Returning true when added successfully Example code: Visual Basic Function addNode(ByRef linkedList() As node, ByVal currentPointer As Integer, ByRef emptyList As Integer) Console.WriteLine("Enter the data to add") Dim dataToAdd As Integer = Console.ReadLine() Dim previousPointer As Integer = 0 Dim newNode As node If emptyList < 0 Or emptyList > 9 Then Return False Else newNode.data = dataToAdd newNode.nextNode = -1 7 Question Answer Marks 1(d)(i) linkedList(emptyList) = newNode previousPointer = 0 While (currentPointer <> -1) previousPointer = currentPointer currentPointer = linkedList(currentPointer).nextNode End While Dim valueToWrite As Integer = emptyList linkedList(previousPointer).nextNode = valueToWrite emptyList = linkedList(emptyList).nextNode Return True End If End Function Python def addNode(linkedList, currentPointer, emptyList): dataToAdd = input("Enter the data to add") if emptyList <0 or emptyList > 9: return False else: newNode = node(int(dataToAdd), -1) linkedList[emptyList] = (newNode) previousPointer = 0 while(currentPointer != -1): previousPointer = currentPointer currentPointer = linkedList[currentPointer].nextNode linkedList[previousPointer].nextNode = emptyList emptyList = linkedList[emptyList].nextNode return True Question Answer Marks 1(d)(i) Java public static Boolean addNode(node[] linkedList, Integer currentPointer, Integer emptyList){ Integer dataToAdd; Integer previousPointer; node newNode; Scanner in = new Scanner(System.in); System.out.println("Enter the data to add"); dataToAdd = in.nextInt(); if(emptyList < 0 || emptyList > 9){ return false; }else{ newNode = new node(dataToAdd, -1); linkedList[emptyList] = newNode; previousPointer = 0; while(currentPointer != -1){ previousPointer = currentPointer; currentPointer = linkedList[currentPointer].nextNode; } linkedList[previousPointer].nextNode = emptyList; emptyList = linkedList[emptyList].nextNode; return true; } } Question Answer Marks 1(d)(ii) 1 mark per bullet point • Call addNode() with list, start and empty pointers and store/check return value … • …output appropriate message if True returned and if False returned • Calling outputNodes() with list and start pointer before and after addNode() Example code: Visual Basic Sub Main() Dim linkedList(10) As node linkedList(0).data = 1 linkedList(0).nextNode = 1 linkedList(1).data = 5 linkedList(1).nextNode = 4 linkedList(2).data = 6 linkedList(2).nextNode = 7 linkedList(3).data = 7 linkedList(3).nextNode = -1 linkedList(4).data = 2 linkedList(4).nextNode = 2 linkedList(5).data = -1 linkedList(5).nextNode = 6 linkedList(6).data = -1 linkedList(6).nextNode = 7 linkedList(7).data = 56 linkedList(7).nextNode = 3 linkedList(8).data = -1 linkedList(8).nextNode = 9 linkedList(9).data = -1 linkedList(9).nextNode = -1 Dim startPointer As Integer = 0 Dim emptyList As Integer = 5 outputNodes(linkedList, startPointer) Dim returnValue As Boolean returnValue = addNode(linkedList, startPointer, emptyList) 3 Question Answer Marks 1(d)(ii) If returnValue = True Then Console.WriteLine("Item successfully added") Else Console.WriteLine("Item not added, list full") End If outputNodes(linkedList, startPointer) Console.ReadLine() End Sub Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(-1,6), node(-1,7),node(56,3),node(-1,9),node(-1,-1)] startPointer = 0 emptyList = 5 outputNodes(linkedList, startPointer) returnValue = addNode(linkedList, startPointer, emptyList) if returnValue == True: print("Item successfully added") else: print("Item not added, list full") outputNodes(linkedList, startPointer) Java public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(-1,6); linkedList[6] = new node(-1,7); linkedList[7] = new node(56, 3); linkedList[8] = new node(-1,9); Question Answer Marks 1(d)(ii) linkedList[9] = new node(-1,-1); Integer startPointer = 0; Integer emptyList = 5; outputNodes(linkedList, startPointer); Boolean returnValue; returnValue = addNode(linkedList, startPointer, emptyList); if (returnValue == true){ System.out.println("Item successfully added"); }else{ System.out.println("Item not added, list full"); } outputNodes(linkedList, startPointer); } 1(d)(iii) 1 mark for screenshot showing : • Linked list output • 5 input • Message saying Successfully added or equivalent • Linked list output with 5 at the end. Example: 1 5 2 6 56 7 5 (being input) 1 5 2 6 56 7 5 1

This question in 9618/41 May/June 2021

2 A program stores the following ten integers in a 1D array with the identifier arrayData. 10 5 6 7 1 12 13 15 21 8 (a) Write program code for a new program to: • declare the global 1D array, arrayData, with ten elements • initialise arrayData in the main program using the data values shown. Save your program as question2. Copy and paste the program code into part 2(a) in the evidence document. [2] (b) (i) A function, linearSearch(), takes an integer as a parameter and performs a linear search on arrayData to find the parameter value. It returns True if it was found and False if it was not found. Write program code for the function linearSearch(). Save your program. Copy and paste the program code into part 2(b)(i) in the evidence document. [6] (ii) Edit the main program to: • allow the user to input an integer value • pass the value to linearSearch() as the parameter • output an appropriate message to tell the user whether the search value was found or not. Save your program. Copy and paste the program code into part 2(b)(ii) in the evidence document. [4] (iii) Test your program with one value that is in the array and one value that is not in the array. Take a screenshot to show the result of each test. Save your program. Copy and paste the screenshots into part 2(b)(iii) in the evidence document. [2] (c) The following bubble sort pseudocode algorithm sorts the data in theArray into descending numerical order. There are five incomplete statements. PROCEDURE bubbleSort() DECLARE temp : INTEGER FOR x 0 to ………………………………… FOR y 0 to ………………………………… IF theArray[y] ………………………………… theArray[y + 1] THEN temp theArray[y] theArray[y] theArray[y + 1] ENDIF NEXT y NEXT x ENDPROCEDURE Write program code for the procedure bubbleSort() to sort the data in arrayData into descending order. Save your program. Copy and paste the program code into part 2(c) in the evidence document. [6]

20 marks

Mark scheme: 2(a) 1 mark per bullet point • Array with identifier arrayData • correct 10 data items added Example code: Visual Basic Dim arrayData(9) As Integer Sub Main() arrayData(0) = 10 arrayData(1) = 5 arrayData(2) = 6 arrayData(3) = 7 arrayData(4) = 1 arrayData(5) = 12 arrayData(6) = 13 arrayData(7) = 15 arrayData(8) = 21 arrayData(9) = 8 End Sub Python arrayData = [10, 5, 6, 7, 1, 12, 13, 15, 21, 8] Java int[] arrayData = new int[]; public static void main(String[] args){ arrayData[0] = 10; arrayData[1] = 5; arrayData[2] = 6; arrayData[3] = 7; arrayData[4] = 1; arrayData[5] = 12; arrayData[6] = 13; Question Answer Marks 2(a) arrayData[7] = 15; arrayData[8] = 21; arrayData[9] = 8; } 2(b)(i) 1 mark per bullet point • function linearSearch with correct identifier • …taking integer search value as a parameter • Searching 10 times/through all array elements … • …comparing each element to search value • returning True if found • returning False if not found Example code: Visual Basic Function linearSearch(ByRef searchValue As Integer) For x = 0 To 9 If arrayData(x) = searchValue Then Return True End If Next Return False End Function 6 Question Answer Marks 2(b)(i) Python def linearSearch(searchValue): for x in range(0, 10): if arrayData[x] == searchValue: return True return False Java public static Boolean linearSearch(Integer searchValue){ for (int x = 0; x < 10; x++){ if(arrayData[x] == searchValue){ return true; } } return false; } Question Answer Marks 2(b)(ii) 1 mark per bullet point to max 4 • Taking value as input… • …checking/casting to Integer • Calling linearSearch and sending input as parameter • Storing and checking return value… • …outputting appropriate message if found and if not found Example code: Visual Basic Dim arrayData(10) As Integer Sub Main() arrayData(0) = 10 arrayData(1) = 5 arrayData(2) = 6 arrayData(3) = 7 arrayData(4) = 1 arrayData(5) = 12 arrayData(6) = 13 arrayData(7) = 15 arrayData(8) = 12 arrayData(9) = 8 Console.WriteLine("Enter a number to search for") Dim searchValue As Integer = Console.ReadLine() Dim returnValue As Boolean = linearSearch(searchValue) If returnValue = True Then Console.WriteLine("Found it") Else Console.WriteLine("Didn't find it") End If End Sub 4 Question Answer Marks 2(b)(ii) Python arrayData = [10, 5, 6, 7, 1, 12, 13, 15, 21, 8] searchValue = int(input("Enter the number to search for")) returnValue = linearSearch(searchValue) if returnValue == True: print("It was found") else: print("It was not found") Java Integer[] arrayData = new Integer[10]; public static void main(String[] args){ arrayData[0] = 10; arrayData[1] = 5; arrayData[2] = 6; arrayData[3] = 7; arrayData[4] = 1; arrayData[5] = 12; arrayData[6] = 13; arrayData[7] = 15; arrayData[8] = 12; arrayData[9] = 8; System.out.println("Enter the number to search for"); Integer searchValue; Scanner in = new Scanner(System.in); searchValue = in.nextInt(); Boolean returnValue; returnValue = linearSearch(searchValue); if (returnValue == true){ System.out.println("It was found"); }else{ System.out.println("It was not found"); } } Question Answer Marks 2(b)(iii) 1 mark for screenshot showing input and output for number found 1 mark for screenshot showing input and output for number not found 2 2(c) 1 mark per bullet point • Correct outer loop stop • Correct inner loop stop • Correct < in the IF • Correct theArray(y + 1) • Correct temp • Remainder matching pseudocode Example code: Visual Basic Sub bubbleSort() Dim temp As Integer = 0 For x = 0 To 9 For y = 0 To 8 If theArray(y) < theArray(y + 1) Then temp = theArray(y) theArray(y) = theArray(y + 1) theArray(y + 1) = temp End If Next Next End Sub 6 Question Answer Marks 2(c) Python def bubbleSort(): for x in range (0, 10): for y in range(0, 9): if theArray[y] < theArray[y + 1]: temp = theArray[y] theArray[y] = theArray[y + 1] theArray[y + 1] = temp Java public static void bubbleSort(){ int temp; for (int x = 0; x < 10; x++){ for (int y = 0; y < 9; y++){ if(theArray[y] < theArray[y+1]){ temp = theArray[y]; theArray[y] = theArray[y+1]; theArray[y+1] = temp; } } } }

This question in 9618/41 May/June 2021

1 An unordered linked list uses a 1D array to store the data. Each item in the linked list is of a record type, node, with a field data and a field nextNode. The current contents of the linked list are: startPointer 0 Index data nextNode 0 1 1 emptyList 5 1 5 4 2 6 7 3 7 -1 4 2 2 5 0 6 6 0 8 7 56 3 8 0 9 9 0 -1 (a) The following is pseudocode for the record type node. TYPE node DECLARE data : INTEGER DECLARE nextNode : INTEGER ENDTYPE Write program code to declare the record type node. Save your program as question1. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) Write program code for the main program. Declare a 1D array of type node with the identifier linkedList, and initialise it with the data shown in the table on page 2. Declare the pointers. Save your program. Copy and paste the program code into part 1(b) in the evidence document. [4] (c) The procedure outputNodes() takes the array and startPointer as parameters. The procedure outputs the data from the linked list by following the nextNode values. (i) Write program code for the procedure outputNodes(). Save your program. Copy and paste the program code into part 1(c)(i) in the evidence document. [6] (ii) Edit the main program to call the procedure outputNodes(). Take a screenshot to show the output of the procedure outputNodes(). Save your program. Copy and paste the screenshot into part 1(c)(ii) in the evidence document. [1] (d) The function, addNode(), takes the linked list and pointers as parameters, then takes as input the data to be added to the end of the linkedList. The function adds the node in the next available space, updates the pointers and returns True. If there are no empty nodes, it returns False. (i) Write program code for the function addNode(). Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [7] (ii) Edit the main program to: • call addNode() • output an appropriate message depending on the result returned from addNode() • call outputNodes() twice; once before calling addNode() and once after calling addNode(). Save your program. Copy and paste the program code into part 1(d)(ii) in the evidence document. [3] (iii) Test your program by inputting the data value 5 and take a screenshot to show the output. Save your program. Copy and paste the screenshot into part 1(d)(iii) in the evidence document. [1]

24 marks

Mark scheme: 1(a) 1 mark per bullet point • Declaring record/class with name node… • …declaring data and next node (both as Integers) Example code: Visual Basic Structure node Dim Data As Integer Dim nextNode As Integer End Structure Python class node: def __init__(self, theData, nextNodeNumber): self. Data = theData self.nextNode = nextNodeNumber Java class node{ private Integer Data; private Integer nextNode; public node(Integer dataP, Integer nextNodeP){ this.Data = dataP; this.nextNode = nextNodeP; } } Question Answer Marks 1(b) 1 mark per bullet point • Declaring array named linkedList with data type node • Assigning all nodes correctly as record/object nodes … • …with correct values stored • declaring startPointer as 0, emptyList as 5 Example code: Visual Basic Dim linkedList(9) As node linkedList(0).data = 1 linkedList(0).nextNode = 1 linkedList(1).data = 5 linkedList(1).nextNode = 4 linkedList(2).data = 6 linkedList(2).nextNode = 7 linkedList(3).data = 7 linkedList(3).nextNode = -1 linkedList(4).data = 2 linkedList(4).nextNode = 2 linkedList(5).data = 0 linkedList(5).nextNode = 6 linkedList(6).data = 0 linkedList(6).nextNode = 8 linkedList(7).data = 56 linkedList(7).nextNode = 3 linkedList(8).data = 0 linkedList(8).nextNode = 9 linkedList(9).data = 0 linkedList(9).nextNode = -1 Dim startPointer As Integer = 0 Dim emptyList As Integer = 5 4 Question Answer Marks 1(b) Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(0,6), node(0,8),node(56,3),node(0,9),node(0,-1)] startPointer = 0 emptyList = 5 Java public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(0,6); linkedList[6] = new node(0,8); linkedList[7] = new node(56, 3); linkedList[8] = new node(0,9); linkedList[9] = new node(0,-1); Integer startPointer = 0; Integer emptyList = 5; } Question Answer Marks 1(c)(i) 1 mark per bullet point • Procedure outputNodes … • …taking linked list and start pointer as parameters • Looping until nextNode/pointer is –1 • Outputting the node data in the correct order, i.e. following pointers • Updating pointer to current node’s nextNode • Using the correct record/class field/properties throughout Example code: Visual Basic Sub outputNodes(ByRef linkedList, ByVal currentPointer) While (currentPointer <> -1) Console.WriteLine(linkedList(currentPointer).data) currentPointer = linkedList(currentPointer).nextNode End While End Sub Python def outputNodes(linkedList, currentPointer): while(currentPointer != -1): print(str(linkedList[currentPointer].data)) currentPointer = linkedList[currentPointer].nextNode Java public static void outputNodes(node[] linkedList, Integer currentPointer){ while(currentPointer != -1){ System.out.println(linkedList[currentPointer].data); currentPointer = linkedList[currentPointer].nextNode; } } 6 Question Answer Marks 1(c)(ii) Screenshot showing: 1 5 2 6 56 7 1 1(d)(i) 1 mark per bullet point to max 7 • Function taking list and both pointers as parameters • Taking (integer) data as input • Checking if list is full … • … and returning False • Insert the input data to the empty list node’s data • Following pointers to find last node in Linked List … • …and updating last node’s pointer to empty list/location where new node is added • Updating empty list to it’s first elements pointer • Returning true when added successfully Example code: Visual Basic Function addNode(ByRef linkedList() As node, ByVal currentPointer As Integer, ByRef emptyList As Integer) Console.WriteLine("Enter the data to add") Dim dataToAdd As Integer = Console.ReadLine() Dim previousPointer As Integer = 0 Dim newNode As node If emptyList < 0 Or emptyList > 9 Then Return False Else newNode.data = dataToAdd newNode.nextNode = -1 7 Question Answer Marks 1(d)(i) linkedList(emptyList) = newNode previousPointer = 0 While (currentPointer <> -1) previousPointer = currentPointer currentPointer = linkedList(currentPointer).nextNode End While Dim valueToWrite As Integer = emptyList linkedList(previousPointer).nextNode = valueToWrite emptyList = linkedList(emptyList).nextNode Return True End If End Function Python def addNode(linkedList, currentPointer, emptyList): dataToAdd = input("Enter the data to add") if emptyList <0 or emptyList > 9: return False else: newNode = node(int(dataToAdd), -1) linkedList[emptyList] = (newNode) previousPointer = 0 while(currentPointer != -1): previousPointer = currentPointer currentPointer = linkedList[currentPointer].nextNode linkedList[previousPointer].nextNode = emptyList emptyList = linkedList[emptyList].nextNode return True Question Answer Marks 1(d)(i) Java public static Boolean addNode(node[] linkedList, Integer currentPointer, Integer emptyList){ Integer dataToAdd; Integer previousPointer; node newNode; Scanner in = new Scanner(System.in); System.out.println("Enter the data to add"); dataToAdd = in.nextInt(); if(emptyList < 0 || emptyList > 9){ return false; }else{ newNode = new node(dataToAdd, -1); linkedList[emptyList] = newNode; previousPointer = 0; while(currentPointer != -1){ previousPointer = currentPointer; currentPointer = linkedList[currentPointer].nextNode; } linkedList[previousPointer].nextNode = emptyList; emptyList = linkedList[emptyList].nextNode; return true; } } Question Answer Marks 1(d)(ii) 1 mark per bullet point • Call addNode() with list, start and empty pointers and store/check return value … • …output appropriate message if True returned and if False returned • Calling outputNodes() with list and start pointer before and after addNode() Example code: Visual Basic Sub Main() Dim linkedList(10) As node linkedList(0).data = 1 linkedList(0).nextNode = 1 linkedList(1).data = 5 linkedList(1).nextNode = 4 linkedList(2).data = 6 linkedList(2).nextNode = 7 linkedList(3).data = 7 linkedList(3).nextNode = -1 linkedList(4).data = 2 linkedList(4).nextNode = 2 linkedList(5).data = -1 linkedList(5).nextNode = 6 linkedList(6).data = -1 linkedList(6).nextNode = 7 linkedList(7).data = 56 linkedList(7).nextNode = 3 linkedList(8).data = -1 linkedList(8).nextNode = 9 linkedList(9).data = -1 linkedList(9).nextNode = -1 Dim startPointer As Integer = 0 Dim emptyList As Integer = 5 outputNodes(linkedList, startPointer) Dim returnValue As Boolean returnValue = addNode(linkedList, startPointer, emptyList) 3 Question Answer Marks 1(d)(ii) If returnValue = True Then Console.WriteLine("Item successfully added") Else Console.WriteLine("Item not added, list full") End If outputNodes(linkedList, startPointer) Console.ReadLine() End Sub Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(-1,6), node(-1,7),node(56,3),node(-1,9),node(-1,-1)] startPointer = 0 emptyList = 5 outputNodes(linkedList, startPointer) returnValue = addNode(linkedList, startPointer, emptyList) if returnValue == True: print("Item successfully added") else: print("Item not added, list full") outputNodes(linkedList, startPointer) Java public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(-1,6); linkedList[6] = new node(-1,7); linkedList[7] = new node(56, 3); linkedList[8] = new node(-1,9); Question Answer Marks 1(d)(ii) linkedList[9] = new node(-1,-1); Integer startPointer = 0; Integer emptyList = 5; outputNodes(linkedList, startPointer); Boolean returnValue; returnValue = addNode(linkedList, startPointer, emptyList); if (returnValue == true){ System.out.println("Item successfully added"); }else{ System.out.println("Item not added, list full"); } outputNodes(linkedList, startPointer); } 1(d)(iii) 1 mark for screenshot showing : • Linked list output • 5 input • Message saying Successfully added or equivalent • Linked list output with 5 at the end. Example: 1 5 2 6 56 7 5 (being input) 1 5 2 6 56 7 5 1

This question in 9618/42 May/June 2021

2 A program stores the following ten integers in a 1D array with the identifier arrayData. 10 5 6 7 1 12 13 15 21 8 (a) Write program code for a new program to: • declare the global 1D array, arrayData, with ten elements • initialise arrayData in the main program using the data values shown. Save your program as question2. Copy and paste the program code into part 2(a) in the evidence document. [2] (b) (i) A function, linearSearch(), takes an integer as a parameter and performs a linear search on arrayData to find the parameter value. It returns True if it was found and False if it was not found. Write program code for the function linearSearch(). Save your program. Copy and paste the program code into part 2(b)(i) in the evidence document. [6] (ii) Edit the main program to: • allow the user to input an integer value • pass the value to linearSearch() as the parameter • output an appropriate message to tell the user whether the search value was found or not. Save your program. Copy and paste the program code into part 2(b)(ii) in the evidence document. [4] (iii) Test your program with one value that is in the array and one value that is not in the array. Take a screenshot to show the result of each test. Save your program. Copy and paste the screenshots into part 2(b)(iii) in the evidence document. [2] (c) The following bubble sort pseudocode algorithm sorts the data in theArray into descending numerical order. There are five incomplete statements. PROCEDURE bubbleSort() DECLARE temp : INTEGER FOR x 0 to ………………………………… FOR y 0 to ………………………………… IF theArray[y] ………………………………… theArray[y + 1] THEN temp theArray[y] theArray[y] theArray[y + 1] ENDIF NEXT y NEXT x ENDPROCEDURE Write program code for the procedure bubbleSort() to sort the data in arrayData into descending order. Save your program. Copy and paste the program code into part 2(c) in the evidence document. [6]

20 marks

Mark scheme: 2(a) 1 mark per bullet point • Array with identifier arrayData • correct 10 data items added Example code: Visual Basic Dim arrayData(9) As Integer Sub Main() arrayData(0) = 10 arrayData(1) = 5 arrayData(2) = 6 arrayData(3) = 7 arrayData(4) = 1 arrayData(5) = 12 arrayData(6) = 13 arrayData(7) = 15 arrayData(8) = 21 arrayData(9) = 8 End Sub Python arrayData = [10, 5, 6, 7, 1, 12, 13, 15, 21, 8] Java int[] arrayData = new int[]; public static void main(String[] args){ arrayData[0] = 10; arrayData[1] = 5; arrayData[2] = 6; arrayData[3] = 7; arrayData[4] = 1; arrayData[5] = 12; arrayData[6] = 13; Question Answer Marks 2(a) arrayData[7] = 15; arrayData[8] = 21; arrayData[9] = 8; } 2(b)(i) 1 mark per bullet point • function linearSearch with correct identifier • …taking integer search value as a parameter • Searching 10 times/through all array elements … • …comparing each element to search value • returning True if found • returning False if not found Example code: Visual Basic Function linearSearch(ByRef searchValue As Integer) For x = 0 To 9 If arrayData(x) = searchValue Then Return True End If Next Return False End Function 6 Question Answer Marks 2(b)(i) Python def linearSearch(searchValue): for x in range(0, 10): if arrayData[x] == searchValue: return True return False Java public static Boolean linearSearch(Integer searchValue){ for (int x = 0; x < 10; x++){ if(arrayData[x] == searchValue){ return true; } } return false; } Question Answer Marks 2(b)(ii) 1 mark per bullet point to max 4 • Taking value as input… • …checking/casting to Integer • Calling linearSearch and sending input as parameter • Storing and checking return value… • …outputting appropriate message if found and if not found Example code: Visual Basic Dim arrayData(10) As Integer Sub Main() arrayData(0) = 10 arrayData(1) = 5 arrayData(2) = 6 arrayData(3) = 7 arrayData(4) = 1 arrayData(5) = 12 arrayData(6) = 13 arrayData(7) = 15 arrayData(8) = 12 arrayData(9) = 8 Console.WriteLine("Enter a number to search for") Dim searchValue As Integer = Console.ReadLine() Dim returnValue As Boolean = linearSearch(searchValue) If returnValue = True Then Console.WriteLine("Found it") Else Console.WriteLine("Didn't find it") End If End Sub 4 Question Answer Marks 2(b)(ii) Python arrayData = [10, 5, 6, 7, 1, 12, 13, 15, 21, 8] searchValue = int(input("Enter the number to search for")) returnValue = linearSearch(searchValue) if returnValue == True: print("It was found") else: print("It was not found") Java Integer[] arrayData = new Integer[10]; public static void main(String[] args){ arrayData[0] = 10; arrayData[1] = 5; arrayData[2] = 6; arrayData[3] = 7; arrayData[4] = 1; arrayData[5] = 12; arrayData[6] = 13; arrayData[7] = 15; arrayData[8] = 12; arrayData[9] = 8; System.out.println("Enter the number to search for"); Integer searchValue; Scanner in = new Scanner(System.in); searchValue = in.nextInt(); Boolean returnValue; returnValue = linearSearch(searchValue); if (returnValue == true){ System.out.println("It was found"); }else{ System.out.println("It was not found"); } } Question Answer Marks 2(b)(iii) 1 mark for screenshot showing input and output for number found 1 mark for screenshot showing input and output for number not found 2 2(c) 1 mark per bullet point • Correct outer loop stop • Correct inner loop stop • Correct < in the IF • Correct theArray(y + 1) • Correct temp • Remainder matching pseudocode Example code: Visual Basic Sub bubbleSort() Dim temp As Integer = 0 For x = 0 To 9 For y = 0 To 8 If theArray(y) < theArray(y + 1) Then temp = theArray(y) theArray(y) = theArray(y + 1) theArray(y + 1) = temp End If Next Next End Sub 6 Question Answer Marks 2(c) Python def bubbleSort(): for x in range (0, 10): for y in range(0, 9): if theArray[y] < theArray[y + 1]: temp = theArray[y] theArray[y] = theArray[y + 1] theArray[y + 1] = temp Java public static void bubbleSort(){ int temp; for (int x = 0; x < 10; x++){ for (int y = 0; y < 9; y++){ if(theArray[y] < theArray[y+1]){ temp = theArray[y]; theArray[y] = theArray[y+1]; theArray[y+1] = temp; } } } }

This question in 9618/42 May/June 2021

1 An unordered linked list uses a 1D array to store the data. Each item in the linked list is of a record type, node, with a field data and a field nextNode. The current contents of the linked list are: startPointer 0 Index data nextNode 0 1 1 emptyList 5 1 5 4 2 6 7 3 7 -1 4 2 2 5 0 6 6 0 8 7 56 3 8 0 9 9 0 -1 (a) The following is pseudocode for the record type node. TYPE node DECLARE data : INTEGER DECLARE nextNode : INTEGER ENDTYPE Write program code to declare the record type node. Save your program as question1. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) Write program code for the main program. Declare a 1D array of type node with the identifier linkedList, and initialise it with the data shown in the table on page 2. Declare the pointers. Save your program. Copy and paste the program code into part 1(b) in the evidence document. [4] (c) The procedure outputNodes() takes the array and startPointer as parameters. The procedure outputs the data from the linked list by following the nextNode values. (i) Write program code for the procedure outputNodes(). Save your program. Copy and paste the program code into part 1(c)(i) in the evidence document. [6] (ii) Edit the main program to call the procedure outputNodes(). Take a screenshot to show the output of the procedure outputNodes(). Save your program. Copy and paste the screenshot into part 1(c)(ii) in the evidence document. [1] (d) The function, addNode(), takes the linked list and pointers as parameters, then takes as input the data to be added to the end of the linkedList. The function adds the node in the next available space, updates the pointers and returns True. If there are no empty nodes, it returns False. (i) Write program code for the function addNode(). Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [7] (ii) Edit the main program to: • call addNode() • output an appropriate message depending on the result returned from addNode() • call outputNodes() twice; once before calling addNode() and once after calling addNode(). Save your program. Copy and paste the program code into part 1(d)(ii) in the evidence document. [3] (iii) Test your program by inputting the data value 5 and take a screenshot to show the output. Save your program. Copy and paste the screenshot into part 1(d)(iii) in the evidence document. [1]

24 marks

Mark scheme: 1(a) 1 mark per bullet point • Declaring record/class with name node… • …declaring data and next node (both as Integers) Example code: Visual Basic Structure node Dim Data As Integer Dim nextNode As Integer End Structure Python class node: def __init__(self, theData, nextNodeNumber): self. Data = theData self.nextNode = nextNodeNumber Java class node{ private Integer Data; private Integer nextNode; public node(Integer dataP, Integer nextNodeP){ this.Data = dataP; this.nextNode = nextNodeP; } } Question Answer Marks 1(b) 1 mark per bullet point • Declaring array named linkedList with data type node • Assigning all nodes correctly as record/object nodes … • …with correct values stored • declaring startPointer as 0, emptyList as 5 Example code: Visual Basic Dim linkedList(9) As node linkedList(0).data = 1 linkedList(0).nextNode = 1 linkedList(1).data = 5 linkedList(1).nextNode = 4 linkedList(2).data = 6 linkedList(2).nextNode = 7 linkedList(3).data = 7 linkedList(3).nextNode = -1 linkedList(4).data = 2 linkedList(4).nextNode = 2 linkedList(5).data = 0 linkedList(5).nextNode = 6 linkedList(6).data = 0 linkedList(6).nextNode = 8 linkedList(7).data = 56 linkedList(7).nextNode = 3 linkedList(8).data = 0 linkedList(8).nextNode = 9 linkedList(9).data = 0 linkedList(9).nextNode = -1 Dim startPointer As Integer = 0 Dim emptyList As Integer = 5 4 Question Answer Marks 1(b) Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(0,6), node(0,8),node(56,3),node(0,9),node(0,-1)] startPointer = 0 emptyList = 5 Java public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(0,6); linkedList[6] = new node(0,8); linkedList[7] = new node(56, 3); linkedList[8] = new node(0,9); linkedList[9] = new node(0,-1); Integer startPointer = 0; Integer emptyList = 5; } Question Answer Marks 1(c)(i) 1 mark per bullet point • Procedure outputNodes … • …taking linked list and start pointer as parameters • Looping until nextNode/pointer is –1 • Outputting the node data in the correct order, i.e. following pointers • Updating pointer to current node’s nextNode • Using the correct record/class field/properties throughout Example code: Visual Basic Sub outputNodes(ByRef linkedList, ByVal currentPointer) While (currentPointer <> -1) Console.WriteLine(linkedList(currentPointer).data) currentPointer = linkedList(currentPointer).nextNode End While End Sub Python def outputNodes(linkedList, currentPointer): while(currentPointer != -1): print(str(linkedList[currentPointer].data)) currentPointer = linkedList[currentPointer].nextNode Java public static void outputNodes(node[] linkedList, Integer currentPointer){ while(currentPointer != -1){ System.out.println(linkedList[currentPointer].data); currentPointer = linkedList[currentPointer].nextNode; } } 6 Question Answer Marks 1(c)(ii) Screenshot showing: 1 5 2 6 56 7 1 1(d)(i) 1 mark per bullet point to max 7 • Function taking list and both pointers as parameters • Taking (integer) data as input • Checking if list is full … • … and returning False • Insert the input data to the empty list node’s data • Following pointers to find last node in Linked List … • …and updating last node’s pointer to empty list/location where new node is added • Updating empty list to it’s first elements pointer • Returning true when added successfully Example code: Visual Basic Function addNode(ByRef linkedList() As node, ByVal currentPointer As Integer, ByRef emptyList As Integer) Console.WriteLine("Enter the data to add") Dim dataToAdd As Integer = Console.ReadLine() Dim previousPointer As Integer = 0 Dim newNode As node If emptyList < 0 Or emptyList > 9 Then Return False Else newNode.data = dataToAdd newNode.nextNode = -1 7 Question Answer Marks 1(d)(i) linkedList(emptyList) = newNode previousPointer = 0 While (currentPointer <> -1) previousPointer = currentPointer currentPointer = linkedList(currentPointer).nextNode End While Dim valueToWrite As Integer = emptyList linkedList(previousPointer).nextNode = valueToWrite emptyList = linkedList(emptyList).nextNode Return True End If End Function Python def addNode(linkedList, currentPointer, emptyList): dataToAdd = input("Enter the data to add") if emptyList <0 or emptyList > 9: return False else: newNode = node(int(dataToAdd), -1) linkedList[emptyList] = (newNode) previousPointer = 0 while(currentPointer != -1): previousPointer = currentPointer currentPointer = linkedList[currentPointer].nextNode linkedList[previousPointer].nextNode = emptyList emptyList = linkedList[emptyList].nextNode return True Question Answer Marks 1(d)(i) Java public static Boolean addNode(node[] linkedList, Integer currentPointer, Integer emptyList){ Integer dataToAdd; Integer previousPointer; node newNode; Scanner in = new Scanner(System.in); System.out.println("Enter the data to add"); dataToAdd = in.nextInt(); if(emptyList < 0 || emptyList > 9){ return false; }else{ newNode = new node(dataToAdd, -1); linkedList[emptyList] = newNode; previousPointer = 0; while(currentPointer != -1){ previousPointer = currentPointer; currentPointer = linkedList[currentPointer].nextNode; } linkedList[previousPointer].nextNode = emptyList; emptyList = linkedList[emptyList].nextNode; return true; } } Question Answer Marks 1(d)(ii) 1 mark per bullet point • Call addNode() with list, start and empty pointers and store/check return value … • …output appropriate message if True returned and if False returned • Calling outputNodes() with list and start pointer before and after addNode() Example code: Visual Basic Sub Main() Dim linkedList(10) As node linkedList(0).data = 1 linkedList(0).nextNode = 1 linkedList(1).data = 5 linkedList(1).nextNode = 4 linkedList(2).data = 6 linkedList(2).nextNode = 7 linkedList(3).data = 7 linkedList(3).nextNode = -1 linkedList(4).data = 2 linkedList(4).nextNode = 2 linkedList(5).data = -1 linkedList(5).nextNode = 6 linkedList(6).data = -1 linkedList(6).nextNode = 7 linkedList(7).data = 56 linkedList(7).nextNode = 3 linkedList(8).data = -1 linkedList(8).nextNode = 9 linkedList(9).data = -1 linkedList(9).nextNode = -1 Dim startPointer As Integer = 0 Dim emptyList As Integer = 5 outputNodes(linkedList, startPointer) Dim returnValue As Boolean returnValue = addNode(linkedList, startPointer, emptyList) 3 Question Answer Marks 1(d)(ii) If returnValue = True Then Console.WriteLine("Item successfully added") Else Console.WriteLine("Item not added, list full") End If outputNodes(linkedList, startPointer) Console.ReadLine() End Sub Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(-1,6), node(-1,7),node(56,3),node(-1,9),node(-1,-1)] startPointer = 0 emptyList = 5 outputNodes(linkedList, startPointer) returnValue = addNode(linkedList, startPointer, emptyList) if returnValue == True: print("Item successfully added") else: print("Item not added, list full") outputNodes(linkedList, startPointer) Java public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(-1,6); linkedList[6] = new node(-1,7); linkedList[7] = new node(56, 3); linkedList[8] = new node(-1,9); Question Answer Marks 1(d)(ii) linkedList[9] = new node(-1,-1); Integer startPointer = 0; Integer emptyList = 5; outputNodes(linkedList, startPointer); Boolean returnValue; returnValue = addNode(linkedList, startPointer, emptyList); if (returnValue == true){ System.out.println("Item successfully added"); }else{ System.out.println("Item not added, list full"); } outputNodes(linkedList, startPointer); } 1(d)(iii) 1 mark for screenshot showing : • Linked list output • 5 input • Message saying Successfully added or equivalent • Linked list output with 5 at the end. Example: 1 5 2 6 56 7 5 (being input) 1 5 2 6 56 7 5 1

This question in 9618/43 May/June 2021

2 A program stores the following ten integers in a 1D array with the identifier arrayData. 10 5 6 7 1 12 13 15 21 8 (a) Write program code for a new program to: • declare the global 1D array, arrayData, with ten elements • initialise arrayData in the main program using the data values shown. Save your program as question2. Copy and paste the program code into part 2(a) in the evidence document. [2] (b) (i) A function, linearSearch(), takes an integer as a parameter and performs a linear search on arrayData to find the parameter value. It returns True if it was found and False if it was not found. Write program code for the function linearSearch(). Save your program. Copy and paste the program code into part 2(b)(i) in the evidence document. [6] (ii) Edit the main program to: • allow the user to input an integer value • pass the value to linearSearch() as the parameter • output an appropriate message to tell the user whether the search value was found or not. Save your program. Copy and paste the program code into part 2(b)(ii) in the evidence document. [4] (iii) Test your program with one value that is in the array and one value that is not in the array. Take a screenshot to show the result of each test. Save your program. Copy and paste the screenshots into part 2(b)(iii) in the evidence document. [2] (c) The following bubble sort pseudocode algorithm sorts the data in theArray into descending numerical order. There are five incomplete statements. PROCEDURE bubbleSort() DECLARE temp : INTEGER FOR x 0 to ………………………………… FOR y 0 to ………………………………… IF theArray[y] ………………………………… theArray[y + 1] THEN temp theArray[y] theArray[y] theArray[y + 1] ENDIF NEXT y NEXT x ENDPROCEDURE Write program code for the procedure bubbleSort() to sort the data in arrayData into descending order. Save your program. Copy and paste the program code into part 2(c) in the evidence document. [6]

20 marks

Mark scheme: 2(a) 1 mark per bullet point • Array with identifier arrayData • correct 10 data items added Example code: Visual Basic Dim arrayData(9) As Integer Sub Main() arrayData(0) = 10 arrayData(1) = 5 arrayData(2) = 6 arrayData(3) = 7 arrayData(4) = 1 arrayData(5) = 12 arrayData(6) = 13 arrayData(7) = 15 arrayData(8) = 21 arrayData(9) = 8 End Sub Python arrayData = [10, 5, 6, 7, 1, 12, 13, 15, 21, 8] Java int[] arrayData = new int[]; public static void main(String[] args){ arrayData[0] = 10; arrayData[1] = 5; arrayData[2] = 6; arrayData[3] = 7; arrayData[4] = 1; arrayData[5] = 12; arrayData[6] = 13; Question Answer Marks 2(a) arrayData[7] = 15; arrayData[8] = 21; arrayData[9] = 8; } 2(b)(i) 1 mark per bullet point • function linearSearch with correct identifier • …taking integer search value as a parameter • Searching 10 times/through all array elements … • …comparing each element to search value • returning True if found • returning False if not found Example code: Visual Basic Function linearSearch(ByRef searchValue As Integer) For x = 0 To 9 If arrayData(x) = searchValue Then Return True End If Next Return False End Function 6 Question Answer Marks 2(b)(i) Python def linearSearch(searchValue): for x in range(0, 10): if arrayData[x] == searchValue: return True return False Java public static Boolean linearSearch(Integer searchValue){ for (int x = 0; x < 10; x++){ if(arrayData[x] == searchValue){ return true; } } return false; } Question Answer Marks 2(b)(ii) 1 mark per bullet point to max 4 • Taking value as input… • …checking/casting to Integer • Calling linearSearch and sending input as parameter • Storing and checking return value… • …outputting appropriate message if found and if not found Example code: Visual Basic Dim arrayData(10) As Integer Sub Main() arrayData(0) = 10 arrayData(1) = 5 arrayData(2) = 6 arrayData(3) = 7 arrayData(4) = 1 arrayData(5) = 12 arrayData(6) = 13 arrayData(7) = 15 arrayData(8) = 12 arrayData(9) = 8 Console.WriteLine("Enter a number to search for") Dim searchValue As Integer = Console.ReadLine() Dim returnValue As Boolean = linearSearch(searchValue) If returnValue = True Then Console.WriteLine("Found it") Else Console.WriteLine("Didn't find it") End If End Sub 4 Question Answer Marks 2(b)(ii) Python arrayData = [10, 5, 6, 7, 1, 12, 13, 15, 21, 8] searchValue = int(input("Enter the number to search for")) returnValue = linearSearch(searchValue) if returnValue == True: print("It was found") else: print("It was not found") Java Integer[] arrayData = new Integer[10]; public static void main(String[] args){ arrayData[0] = 10; arrayData[1] = 5; arrayData[2] = 6; arrayData[3] = 7; arrayData[4] = 1; arrayData[5] = 12; arrayData[6] = 13; arrayData[7] = 15; arrayData[8] = 12; arrayData[9] = 8; System.out.println("Enter the number to search for"); Integer searchValue; Scanner in = new Scanner(System.in); searchValue = in.nextInt(); Boolean returnValue; returnValue = linearSearch(searchValue); if (returnValue == true){ System.out.println("It was found"); }else{ System.out.println("It was not found"); } } Question Answer Marks 2(b)(iii) 1 mark for screenshot showing input and output for number found 1 mark for screenshot showing input and output for number not found 2 2(c) 1 mark per bullet point • Correct outer loop stop • Correct inner loop stop • Correct < in the IF • Correct theArray(y + 1) • Correct temp • Remainder matching pseudocode Example code: Visual Basic Sub bubbleSort() Dim temp As Integer = 0 For x = 0 To 9 For y = 0 To 8 If theArray(y) < theArray(y + 1) Then temp = theArray(y) theArray(y) = theArray(y + 1) theArray(y + 1) = temp End If Next Next End Sub 6 Question Answer Marks 2(c) Python def bubbleSort(): for x in range (0, 10): for y in range(0, 9): if theArray[y] < theArray[y + 1]: temp = theArray[y] theArray[y] = theArray[y + 1] theArray[y + 1] = temp Java public static void bubbleSort(){ int temp; for (int x = 0; x < 10; x++){ for (int y = 0; y < 9; y++){ if(theArray[y] < theArray[y+1]){ temp = theArray[y]; theArray[y] = theArray[y+1]; theArray[y+1] = temp; } } } }

This question in 9618/43 May/June 2021

1 The text file HighScore.txt stores the players who have scored the top ten scores in a game, in descending order of score. The file stores the 3-character name of the player, and their integer score, in the order: player, score. For example, the current top player in the text file: FYI is the player name 10 000 is the score The program: • reads in the data from HighScore.txt • allows the user to enter a new player name and their score • if appropriate, inserts the new player (name and score) into the top ten • writes the top ten players (name and score) into a new text file NewHighScore.txt (a) The program stores the players and their scores in an array of 11 elements (10 elements to be read from the file, 1 element to be inserted by the user). Write a program to declare one or more arrays, as global data structures, to store the player names and their scores. Save your program as Question1_J2022. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) The procedure ReadHighScores() opens the file HighScore.txt and reads the data into the data structure(s) declared in part 1(a). Write program code to declare the procedure ReadHighScores(). Save your program. Copy and paste the program code into part 1(b) in the evidence document. [6] (c) The procedure OutputHighScores() outputs all the values in the data structure(s) in the format: PlayerName Score For example, the first two data items: FYI 10 000 ABC 9 092 Write program code to declare the procedure OutputHighScores(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [3] (d) The main program should first call ReadHighScores() and then OutputHighScores(). (i) Write the program code for the main program. Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [2] (ii) Test your program. Take a screenshot to show the output from part 1(d)(i). Copy and paste the screenshot into part 1(d)(ii) in the evidence document. [1] (e) The main program needs to ask the user to input a new player name and a score. If this score is in the top ten then it will create a new top ten list that includes this score. (i) Amend the main program to ask the user to input a 3-character player name and an integer score that must be between 1 and 100 000 inclusive. Save your program. Copy and paste the program code into part 1(e)(i) in the evidence document. [3] (ii) Write program code to declare a procedure that: • takes the player name and score as parameters • creates a new top ten list that includes the parameter if appropriate. Save your program. Copy and paste the program code into part 1(e)(ii) in the evidence document. [5] (iii) Amend the main program to call the procedure from part 1(e)(ii). Output the contents of the array before inserting the new player name and score, and output the contents of the array after inserting the new player name and score. Save your program. Copy and paste the program code into part 1(e)(iii) in the evidence document. [2] (iv) Test your program by entering the player name "JKL" and the score "9999". Take a screenshot to show the output. Copy and paste the screenshot into part 1(e)(iv) in the evidence document. [1] (f) The procedure WriteTopTen() stores the new top ten player names and scores in a text file called NewHighScore.txt Write program code to declare the procedure WriteTopTen(). Save your program. Copy and paste the program code into part 1(f) in the evidence document. [4]

29 marks

Mark scheme: 1(a) 1 mark per mark point  declaration of at least 1 array with appropriate identifier  … 11 elements (and appropriate data type(s)) Example program code: Java Public static String[][] FileData = new String[10][2]; VB.NET Dim FileData(0 To 9, 0 To 1) As String Python FileData = [[""] *2 for i in range(11)] #string Question Answer Marks 1(b) 1 mark per mark point to max 6  procedure declaration (and end)  Opening the text file (to read)  Looping 10 times // looping until end of file (e.g. 10 pairs of data)  Reading in each pair of lines …  … storing player name and score in data structure(s)  closing the file  Try and catch on file handling …  … with suitable output Example program code: Java public static void ReadHighScores(){ String Filename = "HighScore.txt"; try{ FileReader F = new FileReader(Filename); BufferedReader Reader = new BufferedReader(F); for(Integer x = 0; x < 10; x++){ FileData[x][0] = Reader.readLine(); FileData[x][1] = Reader.readLine(); } Reader.close(); }catch(FileNotFoundException ex){ System.out.println("No file found"); } catch(IOException ex){ System.out.println("No file found"); } } 6 Question Answer Marks 1(b) Python def ReadHighScores(): Filename = "HighScore.txt" File = open(Filename, 'r') for x in range(0, 10): FileData[x][0] = File.readline()[:3] FileData[x][1] = File.readline() File.close VB.NET Sub ReadHighScores() Dim Textfile As String = "HighScore.txt" Dim FileReader As New System.IO.StreamReader(textfile) Dim DataEntered As Integer = 0 While FileReader.Peek <> -1 and DataEntered < 10 FileData(DataEntered, 0) = FileReader.ReadLine() FileData(DataEntered, 1) = FileReader.ReadLine() DataEntered = DataEntered + 1 End While FileReader.Close() End Sub Question Answer Marks 1(c) 1 mark per mark point  procedure heading and end  looping through all data structure elements  outputting player name, space, score. Each player must start on a new line Example program code: Java public static void OutputHighScores(){ for(Integer x = 0; x < 11; x++){ System.out.println(FileData[x][0] + " " + FileData[x][1]); } } Python def OutputHighScores (): for x in range(0, 11): Output = FileData[x][0] + " " + FileData[x][1] print(Output) VB.NET Sub OutputHighScores () For x = 0 To 10 Console.WriteLine(FileData(x, 0) & " " & FileData(x,1)) Next End Sub 3 Question Answer Marks 1(d)(i) 1 mark per mark point  (Main program) calls ReadHighScores()  … then calls OutputHighScores() Example program code: Java public static void main(String[] args){ ReadHighScores(); OutputHighScores(); } Python ReadHighScores() OutputHighScore() VB.NET Sub Main() ReadHighScores() OutputHighScore() Console.ReadLine() End Sub 2 Question Answer Marks 1(d)(ii) 1 mark for screenshot showing the 10 names and scores from the file (and one extra blank space may, or may not be included) e.g. 1 Question Answer Marks 1(e)(i) 1 mark per mark point  Read in a username and score  Validate username input (3-characters, or just selecting the first 3 characters if there are definitely 3 characters)  Validate score input (integer (cast) between 1 and 100 000 inclusive) Example program code: Java public static void main(String[] args){ Scanner scanner = new Scanner(System.in); ReadHighScores(); OutputHighScores(); String Username = "ABCD" do{ System.out.println("Enter your Username"); Username = scanner.nextLine(); }while(Username.length != 3) String Score = "-1"; do{ System.out.println("Enter your score"); Score = scanner.nextLine(); }while(Integer.parseInt(Score) < 1 || Integer.parseInt(Score) > 100000); } Python Username = "ABCD" while len(Username) != 3: Username = input("Enter your Username") score = -1 while Score < 1 or Score > 100000: Score = int(input("Enter score")) 3 Question Answer Marks 1(e)(i) VB.NET Console.WriteLine("Enter Username") Username = "ABCD" While Username.length <> 3 Username = Console.ReadLine() End While Score = -1 While Score < 1 Or Score > 100000 Console.WriteLine("Enter score") Score = Console.ReadLine() End While Question Answer Marks 1(e)(ii) 1 mark per mark point  procedure declaration (and close where appropriate) taking 1 string and 1 integer parameter  looping through each array element  … finding the position to input the score  storing the array data in the correct position  storing the name and score in the correct position Example program code: Java public static void Arrange(String Username, String Score){ String Temp1; String Temp2; String Second1; String Second2; for(Integer x = 0; x < 10; x++){ if (Integer.parseInt(Score) > Integer.parseInt(FileData[x][1])){ Temp1 = FileData[x][0]; Temp2 = FileData[x][1]; FileData[x][0] = Username; FileData[x][1] = Score; for(Integer Count = x+1; Count < 10; Count++){ second1 = FileData[count][0]; second2 = FileData[count][1]; FileData[Count][0] = Temp1; FileData[Count][1] = Temp2; Temp1 = Second1; Temp2 = Second2; x = 11; } } } } 5 Question Answer Marks 1(e)(ii) Python def Arrange(Username, Score): for x in range(0, 10): if Score > FileData[x][1]: Temp1 = FileData[x][0] Temp2 = FileData[x][1] FileData[x][0] = Username FileData[x][1] = Score Count = x+1 while(Count < 10): Second1 = FileData[Count][0] Second2 = FileData[Count][1] FileData[Count][0] = Temp1 FileData[Count][1] = Temp2 Temp1 = Second1 Temp2 = Second2 Count = Count + 1 break; Question Answer Marks 1(e)(ii) VB.NET Sub Arrange(Username, Score) Dim Temp1 As String Dim Temp2 As String Dim Second1 As String Dim Second2 As String For x = 0 To 9 If Score > Integer.Parse(FileData(x, 1)) Then Temp1 = FileData(x, 0) Temp2 = FileData(x, 1) FileData(x, 0) = Username FileData(x, 1) = Score.ToString For Count = x + 1 To 9 Second1 = FileData(Count, 0) Second2 = FileData(Count, 1) FileData(Count, 0) = Temp1 FileData(Count, 1) = Temp2 Temp1 = Second1 Temp2 = Second2 x = 10 Next End If Next End Sub Question Answer Marks 1(e)(iii) 1 mark per mark point  Calling sorting procedure with correct parameters  Outputting the array before and after procedure call Example program code: Java public static void main(String[] args){ Scanner scanner = new Scanner(System.in); ReadHighScores(); OutputHighScores(); System.out.println("Enter your Username"); String Username = scanner.nextLine(); String Score = "-1"; do{ System.out.println("Enter your score"); Score = scanner.nextLine(); }while(Integer.parseInt(Score) < 0 || Integer.parseInt(Score) > 100000); arrange(Username, Score); OutputHighScores(); } Python ReadHighScores() OutputHighScore() Username = input("Enter your Username") Score = -1 while Score < 0 or Score > 100000: Score = int(input("Enter score")) Arrange(Username, Score) OutputHighScore() 2 Question Answer Marks 1(e)(iii) VB.NET OutputHighScore() Username = Console.ReadLine() Score = -1 While(score < 0 or Score > 100000) Score = Console.ReadLine() End While Arrange(Username, Score) OutputHighScore() 1(e)(iv) 1 mark for screenshot. JKL, 9999 entered. After shows JKL in the second position. e.g. 1 Question Answer Marks 1(f) 1 mark per mark point to max 4  procedure header and end (where appropriate) and opening the file NewHighScore.txt to write  Closing the file  Looping through all 10 array values …  … writing the username, then the score  Exception handling and appropriate output Example program code: Java public static void WriteTopTen(){ String Filename = "NewHighScore.txt"; try{ FileWriter F = new FileWriter(Filename); BufferedWriter Out = new BufferedWriter(F); for(Integer x = 0; x < 10; x++){ Out.write(FileData[x][0] + "\n"); Out.write(FileData[x][1] + "\n"); } Out.close(); } catch(Exception e){ System.err.println("No file"); } } Python def WriteTopTen(): Filename = " NewHighScore.txt" Filename = open(Filename, 'w') for x in range(0, 10): Filename.write(str(FileData[x][0]) + '\n') Filename.write(str(FileData[x][1]) + '\n') Filename.close 4 Question Answer Marks 1(f) VB.NET Sub WriteTopTen() Dim Filename As String = " NewHighScore.txt" Dim NewFile As New System.IO.StreamWriter(Filename) For x = 0 To 9 NewFile.WriteLine(FileData(x, 0)) NewFile.WriteLine(FileData(x, 1)) Next NewFile.Close() End Sub

This question in 9618/41 May/June 2022

3 A program uses a circular queue to store strings. The queue is created as a 1D array, QueueArray, with 10 string items. The following data is stored about the queue: • the head pointer initialised to 0 • the tail pointer initialised to 0 • the number of items in the queue initialised to 0. (a) Declare the array, head pointer, tail pointer and number of items. If you are writing in Python, include attribute declarations using comments. Save your program as Question3_J2022. Copy and paste the program code into part 3(a) in the evidence document. [2] (b) The function Enqueue is written in pseudocode. The function adds DataToAdd to the queue. It returns FALSE if the queue is full and returns TRUE if the item is added. The function is incomplete, there are five incomplete statements. FUNCTION Enqueue(BYREF QueueArray[] : STRING, BYREF HeadPointer : INTEGER, BYREF TailPointer : INTEGER, NumberItems : INTEGER, DataToAdd : STRING) RETURNS BOOLEAN IF NumberItems = …………………………………… THEN RETURN …………………………………… ENDIF QueueArray[……………………………………] DataToAdd ← IF TailPointer >= 9 THEN TailPointer …………………………………… ← ELSE TailPointer TailPointer + 1 ← ENDIF NumberItems NumberItems …………………………………… ← RETURN TRUE ENDFUNCTION Write program code for the function Enqueue(). Save your program. Copy and paste the program code into part 3(b) in the evidence document. [7] (c) The function Dequeue() returns "FALSE" if the queue is empty, or it returns the next data item in the queue. Write program code for the function Dequeue(). Save your program. Copy and paste the program code into part 3(c) in the evidence document. [6] (d) (i) Amend the main program to: • take as input 11 string values from the user • use the Enqueue() function to add each element to the queue • output an appropriate message to state whether each addition was successful, or not • call Dequeue() function twice and output the return value each time. Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document. [5] (ii) Test your program with the input data: "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" Take a screenshot to show the output. Copy and paste the screenshot into part 3(d)(ii) in the evidence document. [1]

21 marks

Mark scheme: 3(a) 1 mark per mark point  Declaring variables: head pointer, tail pointer and number of items all initialised as 0 (integer)  QueueArray declared as 1D array as string with 10 elements Example program code: Java public static void main(String[] args){ String[] QueueArray = new String[10]; Integer QueueHeadPointer = 0; Integer QueueTailPointer = 0; Integer NumberOfItems = 0; } Python QueueArray = ['','','','','','','','','',''] #string QueueHeadPointer = 0 #integer QueueTailPointer = 0 #integer NumberOfItems = 0 #integer VB.NET Sub Main() Dim QueueArray(0 To 9) As String Dim QueueHeadPointer As Integer = 0 Dim QueueTailPointer As Integer = 0 Dim NumberOfItems As Integer = 0 End Sub Question Answer Marks 3(b) 1 mark per complete statement (5) 1 mark for function heading and end, dealing with ByRef 1 mark for remainder of function correct and following the logic FUNCTION Enqueue(BYREF QueueArray[] : STRING, BYREF HeadPointer : Integer, BYREF TailPointer : Integer, NumberItems : INTEGER, DataToAdd : STRING) RETURNS BOOLEAN IF NumberItems = 10 THEN RETURN FALSE ENDIF QueueArray[TailPointer]  DataToAdd IF TailPointer >= 9 THEN TailPointer  0 ELSE TailPointer  TailPointer + 1 ENDIF NumberItems  NumberItems + 1 RETURN TRUE ENDFUNCTION Example program code: Java public static Boolean Enqueue(String DataToAdd){ if(NumberOfItems == 10){ return false; } QueueArray[QueueTailPointer] = DataToAdd; if(QueueTailPointer >= 9){ QueueTailPointer = 0; }else{ QueueTailPointer = QueueTailPointer + 1; } NumberOfItems = NumberOfItems + 1; return true; } 7 Question Answer Marks 3(b) Python def Enqueue(Queue, Head, Tail, NumItems, InputData): if NumItems >= 10: return (False, Queue, Head, Tail, NumItems) Queue[Tail] = InputData if Tail >= 9: Tail = 0 else: Tail = Tail + 1 NumItems = NumItems + 1 return (True, Queue, Head, Tail, NumItems) VB.NET Function Enqueue(ByRef Queue() As String, ByRef Head As Integer, ByRef Tail As Integer, ByRef NumItems As Integer, ByRef InputData As String) If NumItems = 10 Then Return False End If Queue(Tail) = InputData If Tail >= 9 Then Tail = 0 Else Tail = Tail + 1 Question Answer Marks 3(c) 1 mark per mark point to max 6  Function header and end  checking if queue is empty …  … returning False  If not empty accessing and returning item at head pointer  … incrementing head pointer …  … changing head pointer to 0 if it's more than 9 after incrementing  … decrement number of items Example program code: Java public static String Dequeue(){ if(NumberOfItems == 0){ return "FALSE"; }else{ String ReturnValue = QueueArray[QueueHeadPointer]; QueueHeadPointer = QueueHeadPointer + 1; if(QueueHeadPointer >= 9){ QueueHeadPointer = 0; } NumberOfItems = NumberOfItems – 1; return ReturnValue; } } Python def Dequeue(Queue, Head, Tail, NumItems): if NumItems == 0: return (false, Queue, Head, Tail, NumItems) else: ReturnValue = Queue(Head) Head = Head + 1 if Head >= 9: Head = 0 NumItems = NumItems - 1 return(ReturnValue, Queue, Head, Tail, NumItems) 6 Question Answer Marks 3(c) VB.NET Function Dequeue(ByRef QueueArray() As String, ByRef QueueHeadPointer As Integer, ByRef QueueTailpointer As Integer, ByRef NumberOfItems As Integer) If NumberOfItems = 0 Then Return "False" Else Dim ReturnValue = QueueArray(QueueHeadPointer) QueueHeadPointer = QueueHeadPointer + 1 If QueueHeadPointer >= 9 Then QueueHeadPointer = 0 End If NumberOfItems = NumberOfItems - 1 Return ReturnValue End If End Function Question Answer Marks 3(d)(i) 1 mark per mark point  Taking 11 inputs…  … calling Enqueue with each of the 11 inputs …  … outputting an appropriate message if added or not added  Calling Dequeue twice …  … outputting return value each time Example program code: Java public static void main(String args[]){ String InputString; for(Integer x = 0; x < 11; x++){ System.out.println("Enter a string"); Scanner scanner = new Scanner(System.in); InputString = scanner.nextLine(); if(Enqueue(InputString)){ System.out.println("Successful"); }else{ System.out.println("Unsuccessful"); } } System.out.println(Dequeue()); System.out.println(Dequeue()); } 5 Question Answer Marks 3(d)(i) Python for x in range(0, 11): InputString = input("Enter a string") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString) if ReturnValue == True: print("Successful") else: print("Unsuccessful") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) VB.NET For x = 0 To 10 Console.WriteLine("Enter a string") InputString = Console.ReadLine If(Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString)) Then Console.WriteLine("Successful") Else Console.WriteLine("Unsuccessful") End If Next Console.WriteLine(Dequeue) Console.WriteLine(Dequeue) Question Answer Marks 3(d)(ii) 1 mark for showing inputs and outputs: A – J input and successful. K input and unsuccessful. Output: A, B e.g. 1

This question in 9618/41 May/June 2022

1 A program needs to use a stack data structure. The stack can store up to 10 integer elements. A 1D array StackData is used to store the stack globally. The global variable StackPointer points to the next available space in the stack and is initialised to 0. (a) Write program code to declare the array and pointer as global data structures. Initialise the pointer to 0. Save your program as Question1_J22. Copy and paste the program code into part 1(a) in the evidence document. [3] (b) Write a procedure to output all 10 elements in the stack and the value of StackPointer. Save your program. Copy and paste the program code into part 1(b) in the evidence document. [3] (c) The function Push() takes an integer parameter and returns FALSE if the stack is full. If the stack is not full, it puts the parameter value on the stack, updates the relevant pointer and returns TRUE. Write program code for the function Push(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [6] (d) (i) Edit the main program to test the Push() function. The main program needs to: • allow the user to enter 11 numbers and attempt to add these to the stack • output an appropriate message when a number is added to the stack • output an appropriate message when a number is not added to the stack if it is full • output the contents of the stack after attempting to add all 11 numbers. Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [5] (ii) Test your program from part 1(d)(i) with the following 11 inputs: 11 12 13 14 15 16 17 18 19 20 21 Take a screenshot to show the output. Copy and paste the screenshot into part 1(d)(ii) in the evidence document. [1] (e) The function Pop() returns −1 if the stack is empty. If the stack is not empty, it returns the element at the top of the stack and updates the relevant pointer. (i) Write program code for the function Pop(). Save your program. Copy and paste the program code into part 1(e)(i) in the evidence document. [5] (ii) After the code you wrote in the main program for part 1(d)(i), add program code to: • remove two elements from the stack using Pop() • output the updated contents of the stack. Test your program and take a screenshot to show the output. Copy and paste the screenshot into part 1(e)(ii) in the evidence document. [2]

25 marks

Mark scheme: 1(a) 1 mark per mark point  declaring array StackData and pointer StackPointer as (global data structures)  StackData has 10 integer elements  StackPointer initialised to 0 Example program code: VB.NET Dim StackData(9) As Integer Dim StackPointer As Integer Sub Main() StackPointer = 0 end Sub Python global StackData #integer global StackPointer StackData = [0,0,0,0,0,0,0,0,0,0] #integer StackPointer = 0 Java import java.util.Scanner; class Question1{ public static Integer[] StackData; public static Integer StackPointer; public static void main(String args[]){ StackData = new Integer[10]; StackPointer = 0; } } Question Answer Marks 1(b) 1 mark per mark point  procedure header with sensible identifier (and end where appropriate)  outputting StackPointer  outputting all 10 elements in array Example program code: VB.NET Sub PrintArray() Console.WriteLine(StackPointer) For x = 0 To 9 Console.WriteLine(StackData(x)) Next End Sub Python def PrintArray(): global StackData global StackPointer print(StackPointer) for x in range (0, 10): print(StackData[x]) Java public static void PrintArray(){ System.out.println(StackPointer); for(int x = 0; x < 10 ;x++){ System.out.println(StackData[x]); } } 3 Question Answer Marks 1(c) 1 mark per mark point  function Push() taking an integer parameter  checking if stack is full …  …and returning FALSE  (if not full) storing parameter to stack at StackPointer …  …incrementing StackPointer  …returning TRUE Example program code: VB.Net Function Push(DataToPush) If StackPointer = 10 Then Return False Else StackData(StackPointer) = DataToPush StackPointer = StackPointer + 1 Return True End If End Function Python def Push(DataToPush): global StackData global StackPointer if StackPointer == 10: return False else: StackData[StackPointer] = DataToPush StackPointer = StackPointer + 1 return True 6 Question Answer Marks 1(c) Java public static Boolean Push(Integer DataToPush){ if(StackPointer == 10){ return false; }else{ StackData[StackPointer] = DataToPush; StackPointer = StackPointer + 1; return true; } } Question Answer Marks 1(d)(i) 1 mark per mark point  Inputting 11 numbers …  …calling Push() with each number input as a parameter …  …outputting appropriate message if TRUE returned  …outputting appropriate message if FALSE returned  Calling their output procedure after all 11 additions Example program code: VB.NET Sub Main() StackPointer = 0 Dim TempNumber As Integer For x = 0 To 10 Console.WriteLine("Enter a number") TempNumber = Console.ReadLine() If Push(TempNumber) Then Console.WriteLine("Stored") Else Console.WriteLine("Stack full") End If Next PrintArray() Console.ReadLine() End Sub 5 Question Answer Marks 1(d)(i) Python #main StackPointer = 0 StackData = [0,0,0,0,0,0,0,0,0,0] for x in range(0, 11): TempNumber = int(input("Enter a number")) if Push(TempNumber) == True: print("Stored") else: print("Stack full") PrintArray() Java public static void main(String[] args){ StackData = new Integer[10]; StackPointer = 0; Integer TempNumber = 0; for(int x = 0; x < 10; x++){ System.out.println("Enter a number"); Scanner scanner = new Scanner(System.in); TempNumber = Integer.parseInt(scanner.nextLine()); if(Push(TempNumber)){ System.out.println("Stored"); }else{ System.out.println("Stack full"); } } PrintArray(); } Question Answer Marks 1(d)(ii) 1 mark for inputting all 11 numbers, message for first 10 saying added (11 to 20), message stating 11th number stating stack full. Full array contents output (11 12 13 14 15 16 17 18 19 20). e.g. 1 Question Answer Marks 1(e)(i) 1 mark per mark point  Pop() function header (and close where appropriate) and returning a number in all possible situations  checking if stack is empty (StackPointer is 0) and returning -1  (otherwise) accessing the item at the top of the stack …  …decrementing the stack pointer  …returning the item removed Example Program code: VB.NET Function Pop() Dim ReturnData As Integer If StackPointer = 0 Then Return -1 Else ReturnData = StackData(StackPointer – 1) StackPointer = StackPointer - 1 Return ReturnData End If End Function Python def Pop(): global StackData global StackPointer if StackPointer == 0: return -1 else: ReturnData = StackData[StackPointer - 1] StackPointer = StackPointer - 1 return ReturnData 5 Question Answer Marks 1(e)(i) Java public static Integer Pop(){ Integer ReturnData = 0; if(StackPointer == 0){ return -1; }else{ ReturnData = StackData[StackPointer - 1]; StackPointer = StackPointer - 1; return ReturnData; } } 1(e)(ii) 1 mark per mark point  output of before removed with 11 inputs  output of stack (after, this could be 11–20, 11–18, or 11–18 then ‘null’ ‘null’s) e.g. 2

This question in 9618/42 May/June 2022

2 A 2D array stores data entered by a user. (a) The main program declares a 2D array of 10 by 10 integer elements. The array is initialised with a random number between 1 and 100 in each element. Write program code for the main program. Save your program as Question2_J22. Copy and paste the program code into part 2(a) in the evidence document. [4] (b) The following bubble sort pseudocode algorithm sorts the data in the first dimension of the 2D array into ascending numerical order. ArrayLength 10 FOR X 0 TO ArrayLength - 1 FOR Y 0 TO ArrayLength - 2 FOR Z 0 TO ArrayLength - Y - 2 IF ArrayData[X, Z] > ArrayData[X, Z + 1] THEN TempValue ArrayData[X, Z] ArrayData[X, Z] ArrayData[X, Z+1] ArrayData[X, Z + 1] TempValue ENDIF NEXT Z NEXT Y NEXT X (i) Amend your main program by writing program code to implement the bubble sort algorithm after the initialisation of the array elements. You must not use any built-in sorting functions for your programming language. Save your program. Copy and paste the program code into part 2(b)(i) in the evidence document. [5] (ii) Write program code for a procedure to output all the values in the 2D array. The values should be output as a 2D grid, with values in rows and columns. Call the procedure before and after your bubble sort code. Save your program. Copy and paste the program code into part 2(b)(ii) in the evidence document. [3] (iii) Test your program. Take a screenshot to show the output. Copy and paste the screenshot into part 2(b)(iii) in the evidence document. [1] (c) The following pseudocode function uses recursion to perform a binary search in the first row of the array, for the value SearchValue in the array SearchArray. The function returns −1 if the item was not found, or it returns the index where it is found. There are six incomplete statements. FUNCTION BinarySearch(SearchArray, Lower, Upper, SearchValue)RETURNS INTEGER IF Upper >= Lower THEN Mid (Lower + (Upper – 1)) DIV ………………………………… IF SearchArray[0, Mid] = ………………………………… THEN RETURN ………………………………… ELSE IF SearchArray[0, Mid] > SearchValue THEN RETURN BinarySearch(SearchArray, …………………………………, Mid – 1, SearchValue) ELSE RETURN BinarySearch(SearchArray, Mid + 1, …………………………………, SearchValue) ENDIF ENDIF ENDIF RETURN ………………………………… ENDFUNCTION Note: the arithmetic operator DIV performs integer division, e.g. the result of 10 DIV 3 will be 3. (i) Write program code for the recursive function BinarySearch(). Save your program. Copy and paste the program code into part 2(c)(i) in the evidence document. [8] (ii) In the main program, test the function BinarySearch() twice, outputting the returned value each time. One test should be for a number that is in the first line of the array. One test should be for a number that is not in the first line of the array. Take a screenshot to show the output. Copy and paste the screenshot into part 2(c)(ii) in the evidence document. [2]

23 marks

Mark scheme: 2(a) 1 mark per mark point  in main local 2D array declared …  … with 10  10 integer elements  initialising all array elements to a number…  …that is random between 1 and 100 (allow inclusive or exclusive) Example program code: VB.NET Sub Main() Dim Random As New Random Dim ArrayData(10, 10) As Integer For x = 0 To 9 For y = 0 To 9 ArrayData(x, y) = Random.Next(1, 100) Next Next Console.ReadLine() End Sub Python import random #main ArrayData= [[0]*10 for i in range(10)] #integer for x in range(0, 10): for y in range(0,10): ArrayData[x][y] = random.randint(1, 100) Question Answer Marks 2(a) Java import java.util.Scanner; import java.util.Random; class Question2{ public static Integer[][] ArrayData; public static void main(String args[]){ Random Rand = new Random(); ArrayData = new Integer[10][10]; for(int x=0; x < 10; x++){ for(int y = 0; y < 10; y++){ ArrayData[x][y] = Rand.nextInt(100);} } } } Question Answer Marks 2(b)(i) 1 mark per mark point  1st outer loop (dimension 1)  2nd loop (dimension 2)  inner for loop for all second dimension  Selection statement …  …swapping the numbers correctly Example program code: VB.NET Dim TempNumber As Integer Dim ArrayLength As Integer = 10 For X = 0 To ArrayLength - 1 For Y = 0 To ArrayLength - 2 For Z = 0 To ArrayLength - Y - 2 if ArrayData(X, Z) > ArrayData(X, Z + 1) then TempNumber = ArrayData(X, Z) ArrayData(X, Z) = ArrayData(X, Z+1) ArrayData(X, Z + 1) = TempNumber end if Next Z Next Y Next X Python ArrayLength = 10 for X in range(0, ArrayLength): for Y in range(0, ArrayLength-1): for Z in range(0, ArrayLength - Y - 1): if(ArrayData[X][Z] > ArrayData[X][Z+1]): TempNumber = ArrayData[X][Z] ArrayData[X][Z] = ArrayData[X][Z+1] ArrayData[X][Z+1] = TempNumber Accept for MP5: ArrayData[X][Z], ArrayData[X][Z+1] = ArrayData[X][Z+1], ArrayData[X][Z] 5 Question Answer Marks 2(b)(i) Java Integer ArrayLength = 10; for(int X = 0; X < ArrayLength; X++){ for(int Y = 0; Y < ArrayLength; Y++){ for(int Z = 0; Z < ArrayLength - Y - 1; Z++){ if(ArrayData[X][Z] > ArrayData[X][Z + 1]){ TempNumber = ArrayData[X][Z]; ArrayData[X][Z] = ArrayData[X][Z+1]; ArrayData[X][Z + 1] = TempNumber; } } } } Question Answer Marks 2(b)(ii) 1 mark per mark point  procedure header (and end where appropriate)  Outputting all 10  10 values with each 2nd dimension on a complete line  Calling procedure before and after bubble sort Example program code: VB.NET Sub Main() Dim random As New Random Dim ArrayData(10, 10) As Integer For x = 0 To 9 For y = 0 To 9 ArrayData(x, y) = random.Next(1, 100) Next Next Console.WriteLine("before") printarray(ArrayData) Dim TempNumber As Integer Dim ArrayLength As Integer = 10 For X = 0 To ArrayLength - 1 For Y = 0 To ArrayLength - 2 For Z = 0 To ArrayLength - Y - 2 if ArrayData(X, Z) > ArrayData(X, Z + 1) then TempNumber = ArrayData(X, Z) ArrayData(X, Z) = ArrayData(X, Z+1) ArrayData(X, Z + 1) = TempNumber end if Next Z Next Y Next X Console.WriteLine("after") printarray(ArrayData) Console.ReadLine() End Sub 3 Question Answer Marks 2(b)(ii) Sub Printarray(ByRef ArrayData(,) As Integer) For x = 0 To 9 For y = 0 To 9 Console.Write(ArrayData(x, y) & " ") Next Console.WriteLine() Next End Sub Python import random def Printarray(ArrayData): for x in range(0, 10): for y in range(0, 10): print(ArrayData[x][y], " ", end='') print("") #main ArrayData= [[0]*10 for i in range(10)] #integer for x in range(0, 10): for y in range(0,10): ArrayData[x][y] = random.randint(1, 100) print("Before") printarray(ArrayData) ArrayLength = 10 for X in range(0, ArrayLength): for Y in range(0, ArrayLength): for Z in range(0, ArrayLength - Y - 1): if(ArrayData[X][Z] > ArrayData[X][Z+1]): TempNumber = ArrayData[X][Z] ArrayData[X][Z] = ArrayData[X][Z+1] ArrayData[X][Z+1] = TempNumber print("After") Printarray(ArrayData) Question Answer Marks 2(b)(ii) Java import java.util.Scanner; import java.util.Random; class Question2{ public static Integer[][] ArrayData; public static void printArray(Integer[][] theArrayData){ for(int x = 0; x < 10; x++){ for(int y = 0; y < 10; y++){ System.out.printf(theArrayData[x][y] + " "); } System.out.println(); } } public static void main(String args[]){ Random rand = new Random(){ ArrayData = new Integer[10][10]; for(int x=0; x < 10; x++){ for(int y = 0; y < 10; y++){ ArrayData[x][y] = rand.nextInt(100); } } Integer TempNumber = 0; System.out.println("Before"); printArray(ArrayData); Integer ArrayLength = 10; for(int X = 0; X < ArrayLength; X++){ for(int Y = 0; Y < ArrayLength; Y++){ for(int Z = 0; Z < ArrayLength - Y - 1; Z++){ if(ArrayData[X][Z] > ArrayData[X][Z + 1]){ Question Answer Marks 2(b)(ii) TempNumber = ArrayData[X][Z]; ArrayData[X][Z] = ArrayData[X][Z+1]; ArrayData[X][Z + 1] = TempNumber; } } } } System.out.println("After"); PrintArray(ArrayData); } } Question Answer Marks 2(b)(iii) 1 mark for output showing array unsorted and then sorted on 1 of the dimensions e.g. 1 Question Answer Marks 2(c)(i) 1 mark for each completed statement (6) 1 mark per mark point  function declaration taking appropriate parameters and recursive calls  remainder of the function is accurate including appropriate DIV operator. Example program code: VB.NET Function BinarySearch(ByVal SearchArray(,) As Integer, Lower As Integer, Upper As Integer, SearchValue As Integer) Dim Mid As Integer If Upper >= 0 Then Mid = (Lower + (Upper - 1)) \ 2 If SearchArray(0, Mid) = SearchValue Then Return Mid ElseIf SearchArray(0, Mid) > SearchValue Then Return BinarySearch(SearchArray, Lower, Mid - 1, SearchValue) Else Return BinarySearch(SearchArray, Mid + 1, Upper, SearchValue) End If End If Return -1 End Function Python def BinarySearch(SearchArray, Lower, Upper, SearchValue): if Upper >= 0: Mid = int((Lower + (Upper - 1)) / 2) If SearchArray[0][Mid] == SearchValue: return Mid elif SearchArray[0][Mid] > SearchValue: return BinarySearch(SearchArray, Lower, Mid-1, SearchValue) else: return BinarySearch(SearchArray, Mid+1, Upper, SearchValue) return -1 8 Question Answer Marks 2(c)(i) Java public static Integer BinarySearch(Integer[][] SearchArray, Integer Lower, Integer Upper, Integer SearchValue){ Integer Mid = 0; If Upper >= 0 { Mid = (Lower + (Upper - 1)) / 2; If SearchArray[0][Mid] == SearchValue ){ return Mid; }else if SearchArray[0][Mid] > SearchValue { return BinarySearch(SearchArray, Lower, Mid-1, SearchValue); }else{ return BinarySearch(SearchArray, Mid+1, Upper, SearchValue); } } return -1; } Question Answer Marks 2(c)(ii) 1 mark per mark point  screenshot outputting the index when Number is found  screenshot outputting –1 with a Number not found e.g. 2

This question in 9618/42 May/June 2022

1 The text file HighScore.txt stores the players who have scored the top ten scores in a game, in descending order of score. The file stores the 3-character name of the player, and their integer score, in the order: player, score. For example, the current top player in the text file: FYI is the player name 10 000 is the score The program: • reads in the data from HighScore.txt • allows the user to enter a new player name and their score • if appropriate, inserts the new player (name and score) into the top ten • writes the top ten players (name and score) into a new text file NewHighScore.txt (a) The program stores the players and their scores in an array of 11 elements (10 elements to be read from the file, 1 element to be inserted by the user). Write a program to declare one or more arrays, as global data structures, to store the player names and their scores. Save your program as Question1_J2022. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) The procedure ReadHighScores() opens the file HighScore.txt and reads the data into the data structure(s) declared in part 1(a). Write program code to declare the procedure ReadHighScores(). Save your program. Copy and paste the program code into part 1(b) in the evidence document. [6] (c) The procedure OutputHighScores() outputs all the values in the data structure(s) in the format: PlayerName Score For example, the first two data items: FYI 10 000 ABC 9 092 Write program code to declare the procedure OutputHighScores(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [3] (d) The main program should first call ReadHighScores() and then OutputHighScores(). (i) Write the program code for the main program. Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [2] (ii) Test your program. Take a screenshot to show the output from part 1(d)(i). Copy and paste the screenshot into part 1(d)(ii) in the evidence document. [1] (e) The main program needs to ask the user to input a new player name and a score. If this score is in the top ten then it will create a new top ten list that includes this score. (i) Amend the main program to ask the user to input a 3-character player name and an integer score that must be between 1 and 100 000 inclusive. Save your program. Copy and paste the program code into part 1(e)(i) in the evidence document. [3] (ii) Write program code to declare a procedure that: • takes the player name and score as parameters • creates a new top ten list that includes the parameter if appropriate. Save your program. Copy and paste the program code into part 1(e)(ii) in the evidence document. [5] (iii) Amend the main program to call the procedure from part 1(e)(ii). Output the contents of the array before inserting the new player name and score, and output the contents of the array after inserting the new player name and score. Save your program. Copy and paste the program code into part 1(e)(iii) in the evidence document. [2] (iv) Test your program by entering the player name "JKL" and the score "9999". Take a screenshot to show the output. Copy and paste the screenshot into part 1(e)(iv) in the evidence document. [1] (f) The procedure WriteTopTen() stores the new top ten player names and scores in a text file called NewHighScore.txt Write program code to declare the procedure WriteTopTen(). Save your program. Copy and paste the program code into part 1(f) in the evidence document. [4]

29 marks

Mark scheme: 1(a) 1 mark per mark point  declaration of at least 1 array with appropriate identifier  … 11 elements (and appropriate data type(s)) Example program code: Java Public static String[][] FileData = new String[10][2]; VB.NET Dim FileData(0 To 9, 0 To 1) As String Python FileData = [[""] *2 for i in range(11)] #string Question Answer Marks 1(b) 1 mark per mark point to max 6  procedure declaration (and end)  Opening the text file (to read)  Looping 10 times // looping until end of file (e.g. 10 pairs of data)  Reading in each pair of lines …  … storing player name and score in data structure(s)  closing the file  Try and catch on file handling …  … with suitable output Example program code: Java public static void ReadHighScores(){ String Filename = "HighScore.txt"; try{ FileReader F = new FileReader(Filename); BufferedReader Reader = new BufferedReader(F); for(Integer x = 0; x < 10; x++){ FileData[x][0] = Reader.readLine(); FileData[x][1] = Reader.readLine(); } Reader.close(); }catch(FileNotFoundException ex){ System.out.println("No file found"); } catch(IOException ex){ System.out.println("No file found"); } } 6 Question Answer Marks 1(b) Python def ReadHighScores(): Filename = "HighScore.txt" File = open(Filename, 'r') for x in range(0, 10): FileData[x][0] = File.readline()[:3] FileData[x][1] = File.readline() File.close VB.NET Sub ReadHighScores() Dim Textfile As String = "HighScore.txt" Dim FileReader As New System.IO.StreamReader(textfile) Dim DataEntered As Integer = 0 While FileReader.Peek <> -1 and DataEntered < 10 FileData(DataEntered, 0) = FileReader.ReadLine() FileData(DataEntered, 1) = FileReader.ReadLine() DataEntered = DataEntered + 1 End While FileReader.Close() End Sub Question Answer Marks 1(c) 1 mark per mark point  procedure heading and end  looping through all data structure elements  outputting player name, space, score. Each player must start on a new line Example program code: Java public static void OutputHighScores(){ for(Integer x = 0; x < 11; x++){ System.out.println(FileData[x][0] + " " + FileData[x][1]); } } Python def OutputHighScores (): for x in range(0, 11): Output = FileData[x][0] + " " + FileData[x][1] print(Output) VB.NET Sub OutputHighScores () For x = 0 To 10 Console.WriteLine(FileData(x, 0) & " " & FileData(x,1)) Next End Sub 3 Question Answer Marks 1(d)(i) 1 mark per mark point  (Main program) calls ReadHighScores()  … then calls OutputHighScores() Example program code: Java public static void main(String[] args){ ReadHighScores(); OutputHighScores(); } Python ReadHighScores() OutputHighScore() VB.NET Sub Main() ReadHighScores() OutputHighScore() Console.ReadLine() End Sub 2 Question Answer Marks 1(d)(ii) 1 mark for screenshot showing the 10 names and scores from the file (and one extra blank space may, or may not be included) e.g. 1 Question Answer Marks 1(e)(i) 1 mark per mark point  Read in a username and score  Validate username input (3-characters, or just selecting the first 3 characters if there are definitely 3 characters)  Validate score input (integer (cast) between 1 and 100 000 inclusive) Example program code: Java public static void main(String[] args){ Scanner scanner = new Scanner(System.in); ReadHighScores(); OutputHighScores(); String Username = "ABCD" do{ System.out.println("Enter your Username"); Username = scanner.nextLine(); }while(Username.length != 3) String Score = "-1"; do{ System.out.println("Enter your score"); Score = scanner.nextLine(); }while(Integer.parseInt(Score) < 1 || Integer.parseInt(Score) > 100000); } Python Username = "ABCD" while len(Username) != 3: Username = input("Enter your Username") score = -1 while Score < 1 or Score > 100000: Score = int(input("Enter score")) 3 Question Answer Marks 1(e)(i) VB.NET Console.WriteLine("Enter Username") Username = "ABCD" While Username.length <> 3 Username = Console.ReadLine() End While Score = -1 While Score < 1 Or Score > 100000 Console.WriteLine("Enter score") Score = Console.ReadLine() End While Question Answer Marks 1(e)(ii) 1 mark per mark point  procedure declaration (and close where appropriate) taking 1 string and 1 integer parameter  looping through each array element  … finding the position to input the score  storing the array data in the correct position  storing the name and score in the correct position Example program code: Java public static void Arrange(String Username, String Score){ String Temp1; String Temp2; String Second1; String Second2; for(Integer x = 0; x < 10; x++){ if (Integer.parseInt(Score) > Integer.parseInt(FileData[x][1])){ Temp1 = FileData[x][0]; Temp2 = FileData[x][1]; FileData[x][0] = Username; FileData[x][1] = Score; for(Integer Count = x+1; Count < 10; Count++){ second1 = FileData[count][0]; second2 = FileData[count][1]; FileData[Count][0] = Temp1; FileData[Count][1] = Temp2; Temp1 = Second1; Temp2 = Second2; x = 11; } } } } 5 Question Answer Marks 1(e)(ii) Python def Arrange(Username, Score): for x in range(0, 10): if Score > FileData[x][1]: Temp1 = FileData[x][0] Temp2 = FileData[x][1] FileData[x][0] = Username FileData[x][1] = Score Count = x+1 while(Count < 10): Second1 = FileData[Count][0] Second2 = FileData[Count][1] FileData[Count][0] = Temp1 FileData[Count][1] = Temp2 Temp1 = Second1 Temp2 = Second2 Count = Count + 1 break; Question Answer Marks 1(e)(ii) VB.NET Sub Arrange(Username, Score) Dim Temp1 As String Dim Temp2 As String Dim Second1 As String Dim Second2 As String For x = 0 To 9 If Score > Integer.Parse(FileData(x, 1)) Then Temp1 = FileData(x, 0) Temp2 = FileData(x, 1) FileData(x, 0) = Username FileData(x, 1) = Score.ToString For Count = x + 1 To 9 Second1 = FileData(Count, 0) Second2 = FileData(Count, 1) FileData(Count, 0) = Temp1 FileData(Count, 1) = Temp2 Temp1 = Second1 Temp2 = Second2 x = 10 Next End If Next End Sub Question Answer Marks 1(e)(iii) 1 mark per mark point  Calling sorting procedure with correct parameters  Outputting the array before and after procedure call Example program code: Java public static void main(String[] args){ Scanner scanner = new Scanner(System.in); ReadHighScores(); OutputHighScores(); System.out.println("Enter your Username"); String Username = scanner.nextLine(); String Score = "-1"; do{ System.out.println("Enter your score"); Score = scanner.nextLine(); }while(Integer.parseInt(Score) < 0 || Integer.parseInt(Score) > 100000); arrange(Username, Score); OutputHighScores(); } Python ReadHighScores() OutputHighScore() Username = input("Enter your Username") Score = -1 while Score < 0 or Score > 100000: Score = int(input("Enter score")) Arrange(Username, Score) OutputHighScore() 2 Question Answer Marks 1(e)(iii) VB.NET OutputHighScore() Username = Console.ReadLine() Score = -1 While(score < 0 or Score > 100000) Score = Console.ReadLine() End While Arrange(Username, Score) OutputHighScore() 1(e)(iv) 1 mark for screenshot. JKL, 9999 entered. After shows JKL in the second position. e.g. 1 Question Answer Marks 1(f) 1 mark per mark point to max 4  procedure header and end (where appropriate) and opening the file NewHighScore.txt to write  Closing the file  Looping through all 10 array values …  … writing the username, then the score  Exception handling and appropriate output Example program code: Java public static void WriteTopTen(){ String Filename = "NewHighScore.txt"; try{ FileWriter F = new FileWriter(Filename); BufferedWriter Out = new BufferedWriter(F); for(Integer x = 0; x < 10; x++){ Out.write(FileData[x][0] + "\n"); Out.write(FileData[x][1] + "\n"); } Out.close(); } catch(Exception e){ System.err.println("No file"); } } Python def WriteTopTen(): Filename = " NewHighScore.txt" Filename = open(Filename, 'w') for x in range(0, 10): Filename.write(str(FileData[x][0]) + '\n') Filename.write(str(FileData[x][1]) + '\n') Filename.close 4 Question Answer Marks 1(f) VB.NET Sub WriteTopTen() Dim Filename As String = " NewHighScore.txt" Dim NewFile As New System.IO.StreamWriter(Filename) For x = 0 To 9 NewFile.WriteLine(FileData(x, 0)) NewFile.WriteLine(FileData(x, 1)) Next NewFile.Close() End Sub

This question in 9618/43 May/June 2022

3 A program uses a circular queue to store strings. The queue is created as a 1D array, QueueArray, with 10 string items. The following data is stored about the queue: • the head pointer initialised to 0 • the tail pointer initialised to 0 • the number of items in the queue initialised to 0. (a) Declare the array, head pointer, tail pointer and number of items. If you are writing in Python, include attribute declarations using comments. Save your program as Question3_J2022. Copy and paste the program code into part 3(a) in the evidence document. [2] (b) The function Enqueue is written in pseudocode. The function adds DataToAdd to the queue. It returns FALSE if the queue is full and returns TRUE if the item is added. The function is incomplete, there are five incomplete statements. FUNCTION Enqueue(BYREF QueueArray[] : STRING, BYREF HeadPointer : INTEGER, BYREF TailPointer : INTEGER, NumberItems : INTEGER, DataToAdd : STRING) RETURNS BOOLEAN IF NumberItems = …………………………………… THEN RETURN …………………………………… ENDIF QueueArray[……………………………………] DataToAdd ← IF TailPointer >= 9 THEN TailPointer …………………………………… ← ELSE TailPointer TailPointer + 1 ← ENDIF NumberItems NumberItems …………………………………… ← RETURN TRUE ENDFUNCTION Write program code for the function Enqueue(). Save your program. Copy and paste the program code into part 3(b) in the evidence document. [7] (c) The function Dequeue() returns "FALSE" if the queue is empty, or it returns the next data item in the queue. Write program code for the function Dequeue(). Save your program. Copy and paste the program code into part 3(c) in the evidence document. [6] (d) (i) Amend the main program to: • take as input 11 string values from the user • use the Enqueue() function to add each element to the queue • output an appropriate message to state whether each addition was successful, or not • call Dequeue() function twice and output the return value each time. Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document. [5] (ii) Test your program with the input data: "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" Take a screenshot to show the output. Copy and paste the screenshot into part 3(d)(ii) in the evidence document. [1]

21 marks

Mark scheme: 3(a) 1 mark per mark point  Declaring variables: head pointer, tail pointer and number of items all initialised as 0 (integer)  QueueArray declared as 1D array as string with 10 elements Example program code: Java public static void main(String[] args){ String[] QueueArray = new String[10]; Integer QueueHeadPointer = 0; Integer QueueTailPointer = 0; Integer NumberOfItems = 0; } Python QueueArray = ['','','','','','','','','',''] #string QueueHeadPointer = 0 #integer QueueTailPointer = 0 #integer NumberOfItems = 0 #integer VB.NET Sub Main() Dim QueueArray(0 To 9) As String Dim QueueHeadPointer As Integer = 0 Dim QueueTailPointer As Integer = 0 Dim NumberOfItems As Integer = 0 End Sub Question Answer Marks 3(b) 1 mark per complete statement (5) 1 mark for function heading and end, dealing with ByRef 1 mark for remainder of function correct and following the logic FUNCTION Enqueue(BYREF QueueArray[] : STRING, BYREF HeadPointer : Integer, BYREF TailPointer : Integer, NumberItems : INTEGER, DataToAdd : STRING) RETURNS BOOLEAN IF NumberItems = 10 THEN RETURN FALSE ENDIF QueueArray[TailPointer]  DataToAdd IF TailPointer >= 9 THEN TailPointer  0 ELSE TailPointer  TailPointer + 1 ENDIF NumberItems  NumberItems + 1 RETURN TRUE ENDFUNCTION Example program code: Java public static Boolean Enqueue(String DataToAdd){ if(NumberOfItems == 10){ return false; } QueueArray[QueueTailPointer] = DataToAdd; if(QueueTailPointer >= 9){ QueueTailPointer = 0; }else{ QueueTailPointer = QueueTailPointer + 1; } NumberOfItems = NumberOfItems + 1; return true; } 7 Question Answer Marks 3(b) Python def Enqueue(Queue, Head, Tail, NumItems, InputData): if NumItems >= 10: return (False, Queue, Head, Tail, NumItems) Queue[Tail] = InputData if Tail >= 9: Tail = 0 else: Tail = Tail + 1 NumItems = NumItems + 1 return (True, Queue, Head, Tail, NumItems) VB.NET Function Enqueue(ByRef Queue() As String, ByRef Head As Integer, ByRef Tail As Integer, ByRef NumItems As Integer, ByRef InputData As String) If NumItems = 10 Then Return False End If Queue(Tail) = InputData If Tail >= 9 Then Tail = 0 Else Tail = Tail + 1 Question Answer Marks 3(c) 1 mark per mark point to max 6  Function header and end  checking if queue is empty …  … returning False  If not empty accessing and returning item at head pointer  … incrementing head pointer …  … changing head pointer to 0 if it's more than 9 after incrementing  … decrement number of items Example program code: Java public static String Dequeue(){ if(NumberOfItems == 0){ return "FALSE"; }else{ String ReturnValue = QueueArray[QueueHeadPointer]; QueueHeadPointer = QueueHeadPointer + 1; if(QueueHeadPointer >= 9){ QueueHeadPointer = 0; } NumberOfItems = NumberOfItems – 1; return ReturnValue; } } Python def Dequeue(Queue, Head, Tail, NumItems): if NumItems == 0: return (false, Queue, Head, Tail, NumItems) else: ReturnValue = Queue(Head) Head = Head + 1 if Head >= 9: Head = 0 NumItems = NumItems - 1 return(ReturnValue, Queue, Head, Tail, NumItems) 6 Question Answer Marks 3(c) VB.NET Function Dequeue(ByRef QueueArray() As String, ByRef QueueHeadPointer As Integer, ByRef QueueTailpointer As Integer, ByRef NumberOfItems As Integer) If NumberOfItems = 0 Then Return "False" Else Dim ReturnValue = QueueArray(QueueHeadPointer) QueueHeadPointer = QueueHeadPointer + 1 If QueueHeadPointer >= 9 Then QueueHeadPointer = 0 End If NumberOfItems = NumberOfItems - 1 Return ReturnValue End If End Function Question Answer Marks 3(d)(i) 1 mark per mark point  Taking 11 inputs…  … calling Enqueue with each of the 11 inputs …  … outputting an appropriate message if added or not added  Calling Dequeue twice …  … outputting return value each time Example program code: Java public static void main(String args[]){ String InputString; for(Integer x = 0; x < 11; x++){ System.out.println("Enter a string"); Scanner scanner = new Scanner(System.in); InputString = scanner.nextLine(); if(Enqueue(InputString)){ System.out.println("Successful"); }else{ System.out.println("Unsuccessful"); } } System.out.println(Dequeue()); System.out.println(Dequeue()); } 5 Question Answer Marks 3(d)(i) Python for x in range(0, 11): InputString = input("Enter a string") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString) if ReturnValue == True: print("Successful") else: print("Unsuccessful") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) VB.NET For x = 0 To 10 Console.WriteLine("Enter a string") InputString = Console.ReadLine If(Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString)) Then Console.WriteLine("Successful") Else Console.WriteLine("Unsuccessful") End If Next Console.WriteLine(Dequeue) Console.WriteLine(Dequeue) Question Answer Marks 3(d)(ii) 1 mark for showing inputs and outputs: A – J input and successful. K input and unsuccessful. Output: A, B e.g. 1

This question in 9618/43 May/June 2022

1 The text file IntegerData.txt stores 100 integer numbers between 1 and 100 inclusive. A program is required to read in this data and perform searching and sorting on the data. (a) Write program code to declare a global 1D array, DataArray, with space for 100 integer values. Save your program as Question1_N22. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) The procedure ReadFile() must read in the numbers from the text file and store each one in the array. Use appropriate exception handling. Write program code for the procedure ReadFile(). Save your program. Copy and paste the program code into part 1(b) in the evidence document. [6] (c) The function FindValues() asks the user to enter a number to search for in the array. The number input must be a whole number between 1 and 100 inclusive. The function then returns the number of times the number input appears in the array. Write program code for the function FindValues(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [7] (d) (i) Write program code to call ReadFile() and FindValues() from the main program. The return value from FindValues() must be output with an appropriate message. Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [3] (ii) Test your program using the number 61 as input. Take a screenshot to show the output. Copy and paste the screenshot into part 1(d)(ii) in the evidence document. [1] (e) The procedure BubbleSort() needs to perform a bubble sort on the array and print the contents of the sorted array. Write program code for the procedure BubbleSort() and call it from the main program. Save your program. Copy and paste the program code into part 1(e) in the evidence document. [4]

23 marks

Mark scheme: Question Answer Marks 1(a) 1 mark per point: 2 • (global) 1D (Integer) array DataArray • 100 elements Example program code: Python DataArray = [0 for I in range (100)] Java public static Integer[] DataArray = new Integer[100]; VB.NET Dim DataArray(99) As Integer 1(b) 1 mark per point: 6 • Procedure ReadFile() header (and end where appropriate) • opening file IntegerData.txt (for read) • looping through the 100 elements // looping to end of file • reading each (and all) value from file and storing in array • closing file (in appropriate place) 1 mark per point: • Exception Handling (for opening the file, or for reading values from the file)… • …with appropriate catch and output messages Example program code: Python def ReadFile(): global DataArray try: TextFile = "IntegerData.txt" File = open(TextFile, 'r') for X in range(0, 100): DataArray[X] = File.readline() DataArray[X].rstrip('\n') DataArray[X] = int(DataArray[X]) File.close() except IOError: print("Count not find file") 1(b) Java public static void ReadFile(){ String Filename = "IntegerData.txt"; try{ FileReader F = new FileReader(Filename); BufferedReader Reader = new BufferedReader(F); for(Integer X = 0; X < 100; X++){ DataArray[X] = Integer.parseInt(Reader.readLine()); } Reader.close(); } catch(FileNotFoundException ex){ System.out.println("No file found"); } catch(IOException ex){ System.out.println("No file found"); } } VB.NET Sub ReadFile() try Dim TextFile As String = "IntegerData.txt" Dim FileReader As New System.IO.StreamReader(TextFile) For X = 0 To 99 DataArray(X) = FileReader.ReadLine() Next FileReader.Close() Catch ex As Exception Console.WriteLine("Invalid file") End Try End Sub 1(c) 1 mark per point: 7 • Function FindValues() (and end where appropriate) and input of data to search for in the array • …validation/casting(/storing as) of input as integer • …validation of input between 1 and 100 (inclusive) • looping through all 100 array elements… • …comparing input to each array element… • …initialising counter to 0 and then adding 1 each time it is found… • Returning the total 1(c) Example program code: Python def FindValues(): global DataArray DataToFind = -1 while(DataToFind < 1 or DataToFind > 100): DataToFind = int(input("Enter a number between 1 and 100")) Total = 0 for X in range(0, 99): if DataArray[X] == DataToFind: Total = Total + 1 return Total VB.NET Function FindValues() Dim DataToFind As Integer Do Console.WriteLine("Enter a number between 1 and 100") DataToFind = Console.ReadLine() Loop Until (DataToFind >= 1 And DataToFind <= 100) Dim Total As Integer = 0 For X = 0 To 99 If DataArray(X) = DataToFind Then Total = Total + 1 End If Next Return Total End Function Java public static Integer FindValues(){ Integer DataToFind = -1; while(DataToFind < 1 || DataToFind > 100){ System.out.println("Enter a number between 1 and 100"); Scanner in = new Scanner(System.in); DataToFind = in.nextInt(); } Integer Total = 0; for(Integer X = 0; X < 100; X++){ if(DataArray[X] == DataToFind){ Total = Total + 1; } } return Total; } 1(d)(i) 1 mark per point: 3 • Calling ReadFile() and then FindValues() (in the main program) • storing/using return value from FindValues() … • …outputting return value with appropriate message Example program code: Python ReadFile() print("The number appears " + str(FindValues()) + " times") Java public static void main(String[] args){ ReadFile(); Integer ReturnValue = FindValues(); System.out.println("The number was found " + ReturnValue + " times"); } VB.NET Sub Main() ReadFile() Dim ReturnValue As Integer = FindValues() Console.WriteLine("The number was found " & ReturnValue & " times") End Sub 1(d)(ii) Screenshot showing 61 input and 2 output, e.g. 1 1(e) 1 mark per point: 4 • procedure declaration (and end where appropriate) and outputting array contents at end of procedure and calling procedure from main program • correct outer loop … • … correct inner loop … • … swapping all elements if in incorrect order Example program code: Python def BubbleSort(): global DataArray N = 100 for I in range(N-1): for J in range(0, N-I-1): if DataArray[J] > DataArray[J+1]: DataArray[J], DataArray[J+1] = DataArray[J+1], DataArray[J] #main ReadFile() print("The number appears " + str(FindValues()) + " times") BubbleSort() print(DataArray) Java public static void BubbleSort(){ Integer Temp = 0; for(Integer I = 0; I < 100-1; I++){ for(Integer J = 0; J < 100-I-1; J++){ if(DataArray[J] > DataArray[J+1]){ Temp = DataArray[J]; DataArray[J] = DataArray[J+1]; DataArray[J+1] = Temp; } } } for(Integer X = 0; X < 100; X ++){ System.out.println(DataArray[X]); } } public static void main(String[] args){ ReadFile(); Integer ReturnValue = FindValues(); System.out.println("The number was found " + ReturnValue + " times"); BubbleSort(); } 1(e) VB.NET Sub Bubblesort() Dim Outer As Integer = 100 - 1 Dim Swap As Boolean Dim Inner As Integer Dim Temp As Integer Do Inner = 0 Swap = False Do If DataArray(Inner) > DataArray(Inner + 1) Then Temp = DataArray(Inner) DataArray(Inner) = DataArray(Inner + 1) DataArray(Inner + 1) = Temp Swap = True End If Inner = Inner + 1 Loop Until Inner = Outer Outer = Outer - 1 Loop Until Swap = False Or Outer = 0 For X = 0 To 99 Console.WriteLine(DataArray(X)) Next End Sub Sub Main() ReadFile() Dim ReturnValue As Integer = FindValues() Console.WriteLine("The number was found " & ReturnValue & " times") Bubblesort() End Sub

This question in 9618/41 Oct/Nov 2022

3 A binary tree consists of nodes. Each node has 3 integer values: a left pointer, data and a right pointer. The binary tree is stored using a global 2D array. The pseudocode declaration for the array is: DECLARE ArrayNodes : ARRAY[0:19, 0:2] OF INTEGER For example: • ArrayNodes[0, 0] stores the left pointer for the first node. • ArrayNodes[0, 1] stores the data for the first node. • ArrayNodes[0, 2] stores the right pointer for the first node. –1 indicates a null pointer, or null data. (a) Write program code to: • declare the global 2D array ArrayNodes • initialise all 3 integer values to –1 for each node. Save your program as Question3_N22. Copy and paste the program code into part 3(a) in the evidence document. [3] (b) The binary tree stores the following values: Index Left pointer Data Right pointer 0 1 20 5 1 2 15 –1 2 –1 3 3 3 –1 9 4 4 –1 10 –1 5 –1 58 –1 6 –1 –1 –1 FreeNode stores the index of the first free element in the array, initialised to 6. RootPointer stores the index of the first node in the tree, initialised to 0. Amend your program by writing program code to store the given data in ArrayNodes and initialise the free node and root node pointers. Save your program. Copy and paste the program code into part 3(b) in the evidence document. [2] (c) The following recursive pseudocode function searches the binary tree for a given value. If the value is found, the function must return the index of the value. If the value is not found, the function must return –1. The function is incomplete. There are four incomplete statements. FUNCTION SearchValue(Root : INTEGER, ValueToFind : INTEGER) RETURNS INTEGER IF Root = –1 THEN RETURN –1 ELSE IF ArrayNodes[Root, 1] = ValueToFind THEN RETURN … ELSE IF ArrayNodes[Root, 1] = –1 THEN RETURN –1 ENDIF ENDIF ENDIF IF ArrayNodes[Root, 1] … ValueToFind THEN RETURN SearchValue(ArrayNodes[ … , 0], ValueToFind) ENDIF IF ArrayNodes[Root, … ] < ValueToFind THEN RETURN SearchValue(ArrayNodes[Root, 2], ValueToFind) ENDIF ENDFUNCTION Write program code for the function SearchValue(). Save your program. Copy and paste the program code into part 3(c) in the evidence document. [5] (d) A post order traversal performs the following operation: • visit the left node • visit the right node • output the root. For example, in the following tree, the output would be: 3 9 25 60 50 50 25 60 3 9 An outline of the PostOrder() procedure is: • If left node is not empty, make a recursive call with the left node as the root. • If right node is not empty, make a recursive call with the right node as the root. • Output the current root node. The procedure PostOrder() takes the root node as a parameter. Write program code for the procedure PostOrder(). Save your program. Copy and paste the program code into part 3(d) in the evidence document. [7]

17 marks

Mark scheme: 3(a) 1 mark per point: 3 • Declaring (global) 2D array ArrayNodes • looping through all 20  3 elements of array … • …. storing −1 in each element Example program code: Java public static Integer[][] ArrayNodes = new Integer[20][3]; for(Integer X = 0; X<20; X++){ for(Integer Y = 0; Y<3; Y++){ ArrayNodes[X][Y] = -1 }} Python ArrayNodes = [] for x in range(0, 20): ArrayNodes.append([-1, -1, -1]) VB.NET Dim ArrayNodes(19, 2) As Integer Sub main() For X = 0 To 19 For Y = 0 To 2 ArrayNodes(X, Y) = -1 Next Next End Sub 3(b) 1 mark per point: 2 • initialising each of the first 6 array elements correctly • declaring and initialising FreeNode to 6 and RootPointer to 0 Example program code: Python ArrayNodes = [[1,20,5],[2,15,-1],[-1,3,3],[-1,9,4],[- 1,10,-1],[-1,58,-1]] FreeNodes = 6 RootPointer = 0 Java ArrayNodes[0][0] = 1; ArrayNodes[0][1] = 20; ArrayNodes[0][2] = 5; ArrayNodes[1][0] = 2; ArrayNodes[1][1] = 15; ArrayNodes[1][2] = -1; ArrayNodes[2][0] = -1; ArrayNodes[2][1] = 3; ArrayNodes[2][2] = 3; ArrayNodes[3][0] = -1; ArrayNodes[3][1] = 9; ArrayNodes[3][2] = 4; ArrayNodes[4][0] = -1; ArrayNodes[4][1] = 10; ArrayNodes[4][2] = -1; ArrayNodes[5][0] = -1; ArrayNodes[5][1] = 58; ArrayNodes[5][2] = -1; Integer FreeNode = 6; Integer RootPointer = 0; 3(b) VB.NET ArrayNodes(0, 0) = 1 ArrayNodes(0, 1) = 20 ArrayNodes(0, 2) = 5 ArrayNodes(1, 0) = 2 ArrayNodes(1, 1) = 15 ArrayNodes(1, 2) = -1 ArrayNodes(2, 0) = -1 ArrayNodes(2, 1) = 3 ArrayNodes(2, 2) = 3 ArrayNodes(3, 0) = -1 ArrayNodes(3, 1) = 9 ArrayNodes(3, 2) = 4 ArrayNodes(4, 0) = -1 ArrayNodes(4, 1) = 10 ArrayNodes(4, 2) = -1 ArrayNodes(5, 0) = -1 ArrayNodes(5, 1) = 58 ArrayNodes(5, 2) = -1 Dim FreeNode As Integer = 6 Dim RootPointer As Integer = 0 3(c) 1 mark for each completed statement (4) 5 1 mark for remainder of function correct Pseudocode: FUNCTION SearchValue(BYVAL Root : INTEGER, ValueToFind : INTEGER) IF Root = -1 THEN RETURN -1 ELSE IF ArrayNodes[Root,1] = ValueToFind THEN RETURN Root ELSE IF ArrayNodes[Root, 1] = -1 THEN RETURN -1 ENDIF ENDIF ENDIF IF ArrayNodes[Root,1] > ValueToFind THEN RETURN SearchValue(ArrayNodes[Root,0], ValueToFind) ENDIF IF ArrayNodes[Root,1] < ValueToFind THEN RETURN SearchValue(ArrayNodes[Root,2], ValueToFind) ENDIF ENDFUNCTION Example program code: Python def SearchValue(Root, ValueToFind): global ArrayNodes if Root == -1: return -1 elif ArrayNodes[Root][1] == ValueToFind: return Root elif ArrayNodes[Root][1] == -1: return -1 if(ArrayNodes[Root][1] > ValueToFind): return SearchValue(ArrayNodes[Root][0], ValueToFind) if(ArrayNodes[Root][1] < ValueToFind): return SearchValue(ArrayNodes[Root][2], ValueToFind) 3(c) Java public static Integer SearchValue(Integer Root, Integer ValueToFind){ if(Root == -1){ return -1; }else if(ArrayNodes[Root][1] == ValueToFind){; return Root; }else if(ArrayNodes[Root][1] == -1){ return -1; } if(ArrayNodes[Root][1] > ValueToFind){ return(SearchValue(ArrayNodes[Root][0], ValueToFind)); } if(ArrayNodes[Root][1] < ValueToFind){ return(SearchValue(ArrayNodes[Root][2], ValueToFind)); } return -1; } VB.NET Function SearchValue(ByVal Root, ByVal ValueToFind) If ArrayNodes(Root, 1) = ValueToFind Then Return Root ElseIf ArrayNodes(Root, 1) = -1 Then Return -1 End If If ArrayNodes(Root, 1) > ValueToFind Then Return SearchValue(ArrayNodes(Root, 0), ValueToFind) End If If ArrayNodes(Root, 1) < ValueToFind Then Return SearchValue(ArrayNodes(Root, 2), ValueToFind) End If Return -1 End Function 3(d) 1 mark per point (Max 7): 7 • (procedure) header (and end where appropriate) with one parameter (root node or index of root node) and at least one recursive call • checking if left node is −1 … • … if not recursive call with parameter as ArrayNodes[RootNode[0]] • checking if right node is −1 … • …if not recursive call with parameter as ArrayNodes[RootNode[2]] • outputting the element at the parameter RootNode[] • all 3 in the correct order Example program code: Python def PostOrder(RootNode): if RootNode[0] != -1: PostOrder(ArrayNodes[RootNode[0]]) if RootNode[2] != -1: PostOrder(ArrayNodes[RootNode[2]]) print(str(RootNode[1])) Java public static void PostOrder(Integer[] RootNode){ if(RootNode[0] != -1){ PostOrder(ArrayNodes[RootNode[0]]); } if(RootNode[2] != -1){ PostOrder(ArrayNodes[RootNode[2]]); } System.out.println(RootNode[1]); } VB.NET Sub PostOrder(RootNode() As Integer) Dim TempArray(2) As Integer If RootNode(0) <> -1 Then TempArray(0) = ArrayNodes(RootNode(0), 0) TempArray(1) = ArrayNodes(RootNode(0), 1) TempArray(2) = ArrayNodes(RootNode(0), 2) PostOrder(TempArray) End If If RootNode(2) <> -1 Then TempArray(0) = ArrayNodes(RootNode(2), 0) TempArray(1) = ArrayNodes(RootNode(2), 1) TempArray(2) = ArrayNodes(RootNode(2), 2) PostOrder(TempArray) End If Console.WriteLine(RootNode(1)) End Sub 3(e)(i) 1 mark per point: 3 • calling SearchValue() with 15 and rootPointer as a parameter … • … if return value > -1 output returned index and if return value = -1 output not found Both as appropriate messages • Calling PostOrder() with ArrayNodes[RootPointer] as a parameter Example program code: Python ReturnValue = SearchValue(RootPointer, 15) if ReturnValue == -1: print("Not found") else: print("Found at " + str(ReturnValue)) PostOrder(ArrayNodes[RootPointer]) Java Integer ReturnValue = SearchValue(RootPointer, 15); if(ReturnValue == -1){ System.out.println("Not found"); } else { System.out.println("Found at " + ReturnValue); } PostOrder(ArrayNodes[RootPointer]); VB.NET Dim returnvalue As Integer = SearchValue(RootPointer, 15) If returnvalue = -1 Then Console.WriteLine("Not found") Else Console.WriteLine("Found at " & returnvalue) End If Console.WriteLine("Post order") Dim TempArray(2) As Integer TempArray(0) = ArrayNodes(RootPointer, 0) TempArray(1) = ArrayNodes(RootPointer, 1) TempArray(2) = ArrayNodes(RootPointer, 2) PostOrder(TempArray) 3(e)(ii) Screenshot with result as shown, for example: 1

This question in 9618/41 Oct/Nov 2022

1 A computer program is needed to store jobs in order of priority. Each job has a job number (for example, 123) and a priority from 1 to 10, with 1 being the highest priority and 10 the lowest. The program stores the jobs in a global 2D array. The pseudocode declaration for the array is: DECLARE Jobs : ARRAY[0:99, 0:1] OF INTEGER For example: • Jobs[0, 0] stores the job number of the first job. • Jobs[0, 1] stores the priority of the first job. The global variable, NumberOfJobs, stores the number of jobs currently in the array. (a) Write program code to declare the global 2D array Jobs and the global variable NumberOfJobs. Save your program as Question1_N22. Copy and paste the program code into part 1(a) in the evidence document. [3] (b) The procedure Initialise() stores –1 in each of the array elements and assigns 0 to NumberOfJobs. Write program code for the procedure Initialise(). Save your program. Copy and paste the program code into part 1(b) in the evidence document. [3] (c) The procedure AddJob(): • takes a job number and priority as parameters • stores the job in the next free array element • outputs ‘Added’ if the job was successfully stored in the array • outputs ‘Not added’ if the job was not successfully stored in the array. Write program code for the procedure AddJob(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [5] (d) The main program should call the procedure Initialise() and then use the AddJob() procedure to store the following jobs in the order given: Job number Priority 12 10 526 9 33 8 12 9 78 1 Write program code for the main program and perform the tasks described. Save your program. Copy and paste the program code into part 1(d) in the evidence document. [2] (e) When a new job has been added, the array is sorted into ascending numerical order of priority using an insertion sort. Write program code for the procedure InsertionSort() to sort the data into ascending numerical order of priority. Save your program. Copy and paste the program code into part 1(e) in the evidence document. [5] (f) The procedure PrintArray() outputs each job number and priority on a line, for example: 123 priority 1 39 priority 3 120 priority 7 Write program code for the procedure PrintArray(). Save your program. Copy and paste the program code into part 1(f) in the evidence document. [3] (g) The main program needs to sort the array and then output the contents of the array. (i) Amend the main program by writing program code to call procedures InsertionSort() and PrintArray(). Save your program. Copy and paste the program code into part 1(g)(i) in the evidence document. [1] (ii) Test your program. Take a screenshot of the output. Copy and paste the screenshot into part 1(g)(ii) in the evidence document. [1]

23 marks

Mark scheme: Question Answer Marks 1(a) 1 mark per point: 3 • (global) 2-D array Jobs with correct identifier (and Integer data type) • … with 100 elements by 2 elements • (global) NumberOfJobs declared as variable (as Integer) Example program code: Java public static Integer[][] Jobs = new Integer[100][2]; public static Integer NumberOfJobs; Python Jobs # global integer, 100 by 2 elements NumberOfJobs # global integer VB.NET Dim Jobs(99, 1) As Integer Dim NumberOfJobs As Integer 1(b) 1 mark per point: 3 • procedure heading (and end where appropriate) and assigns 0 to NumberOfJobs • looping through both array element dimensions • … assigns −1 to all elements Example program code: Java public static void Initialise(){ for(Integer x = 0; x<100;x++){ for(Integer y = 0; y<2; y++){ Jobs[x][y] = -1; } } NumberOfJobs = 0; } Python def Initialise(): global Jobs global NumberOfJobs for x in range(0, 100): Jobs.append([-1,-1]) NumberOfJobs = 0 VB.NET Sub Initialise() For X = 0 To 99 For Y = 0 To 1 Jobs(X, Y) = -1 Next Next NumberOfJobs = 0 End Sub 1(c) 1 mark per point (Max 5): 5 • Function header (and end where appropriate) with two (integer) parameters • Checks if array is full … • … if full outputs "Not added" • Storing parameters job number and priority to only the next available array position • Incrementing NumberOfJobs • Outputting "Added" if successful Example program code: Java public static void AddJob(Integer Description, Integer Priority){ if(NumberOfJobs == 100){ System.out.println("Not added"); }else{ Jobs[NumberOfJobs][0] = Description; Jobs[NumberOfJobs][1] = Priority; NumberOfJobs = NumberOfJobs + 1; System.out.println("Added"); } } Python def AddJob(JobNumber, Priority): global NumberOfJobs global Jobs if NumberOfJobs == 100: print("Not added") else: Jobs[NumberOfJobs] = [JobNumber, Priority] print("Added") NumberOfJobs = NumberOfJobs + 1 VB.NET Sub AddJob(JobNumber, Priority) If NumberOfJobs = 100 Then Console.WriteLine("Not added") Else Jobs(NumberOfJobs, 0) = JobNumber Jobs(NumberOfJobs, 1) = Priority NumberOfJobs = NumberOfJobs + 1 Console.WriteLine("Added") End If End Sub 1(d) 1 mark per point: 2 • Calls Initialise() (in the main program) • 5 AddJob calls with correct values as parameters in correct order Example program code: Java public static void main(String args[]){ Initialise(); AddJob(12, 10); AddJob(526, 9); AddJob(33,8); AddJob(12,9); AddJob(78,1); } Python Initialise() AddJob(12,10) AddJob(526,9) AddJob(33,8) AddJob(12,9) AddJob(78,1) VB.NET Sub Main() Initialise() AddJob(12, 10) AddJob(526, 9) AddJob(33, 8) AddJob(12, 9) AddJob(78, 1) End Sub 1(e) 1 mark per point: 5 • Procedure header (and end where appropriate) • Outer loop through all 5 elements / number of jobs … • … inner loop through array elements … • …and comparing priority (second index) … • …moving the elements up and inserting correctly Example program code: Python def InsertionSort(): global Jobs global NumberOfJobs for I in range(1, NumberOfJobs): Current1 = Jobs[I][0] Current2 = Jobs[I][1] while I > 0 and Jobs[I-1][1] > Current2: Jobs[I][0] = Jobs[I-1][0] Jobs[I][1] = Jobs[I-1][1] I = I - 1 Jobs[I][0] = Current1 Jobs[I][1] = Current2 Java public static void InsertionSort(){ Integer Current1; Integer Current2; Integer Counter; Integer Placed; for(Integer i = 1; i < NumberOfJobs; i++){ Current1 = Jobs[i][0]; Current2 = Jobs[i][1]; while(i > 0 && Jobs[i-1][1] > Current2){ Jobs[i][0] = Jobs[i-1][0]; Jobs[i][1] = Jobs[i-1][1]; i = i - 1; } Jobs[i][0] = Current1; Jobs[i][1] = Current2; } } 1(e) VB.NET Sub InsertionSort() Dim Tempa As Integer Dim Tempb As Integer Dim Counter As Integer Dim Placed As Boolean For i = 1 To NumberOfJobs - 1 Tempa = Jobs(i, 0) Tempb = Jobs(i, 1) Counter = i Placed = False While (Counter > 0 And Not Placed) If (Jobs(Counter - 1, 1) > Tempb) Then Jobs(Counter, 0) = Jobs(Counter - 1, 0) Jobs(Counter, 1) = Jobs(Counter - 1, 1) Counter = Counter - 1 Else Placed = True End If End While Jobs(Counter, 0) = Tempa Jobs(Counter, 1) = Tempb Next i End Sub 1(f) 1 mark per point: 3 • procedure heading (and end where appropriate) and outputting all job numbers and priorities • Outputting the job and priority for each element on the same line, with a line break between each job … • … with 'priority' between job number and priority Example program code: Java public static void PrintArray(){ for(Integer x = 0; x < NumberOfJobs; x++){ System.out.println(Jobs[x][0] + " priority " + Jobs[x][1]); } } Python def PrintArray(): global Jobs global NumberOfJobs for X in range(0, NumberOfJobs): print(str(Jobs[X][0]), " priority ", str(Jobs[X][1])) VB.NET Sub PrintArray() For X = 0 To NumberOfJobs - 1 Console.WriteLine(Jobs(X, 0) & " priority " & Jobs(X, 1)) Next End Sub 1(g)(i) • calling both subroutines in the main program in the correct order 1 Example program code: Java InsertionSort(); PrintArray(); Python InsertionSort() PrintArray() VB.NET InsertionSort() PrintArray() 1(g)(ii) 1 mark for added 5 times and jobs in order. 1 526 and 12 can be reversed

This question in 9618/42 Oct/Nov 2022

3 A program uses a linear queue to store up to 100 integers. (a) A 1D array, Queue, is used to store the data. The head pointer points to the first number stored in the queue and the tail pointer points to the next free space in the queue. Write program code to: • declare the global array Queue • declare the global variable head pointer and assign an appropriate initial value • declare the global variable tail pointer and assign an appropriate initial value. Save your program as Question3_N22. Copy and paste the program code into part 3(a) in the evidence document. [3] (b) The function Enqueue() takes an integer value as a parameter and stores it in the queue. It returns TRUE if the value was successfully stored and FALSE otherwise. Write program code for the function Enqueue(). Save your program. Copy and paste the program code into part 3(b) in the evidence document. [6] (c) The main program uses the Enqueue() function to store the numbers 1 to 20 (inclusive) in the queue, in ascending numerical order. The program should output ‘Successful’ if all numbers are successfully enqueued, and ‘Unsuccessful’ otherwise. Amend the main program by writing program code to perform this task. Save your program. Copy and paste the program code into part 3(c) in the evidence document. [4] (d) The following iterative pseudocode function calculates the total of all the values stored in the queue. FUNCTION IterativeOutput(Start: INTEGER) RETURNS INTEGER DECLARE Total : INTEGER Total 0 ← FOR Count Start - 1 TO HeadPointer STEP -1 ← Total Total + Queue[Count] ← NEXT Count RETURN Total ENDFUNCTION Rewrite the function as a recursive function using program code. Save your program. Copy and paste the program code into part 3(d) in the evidence document. [6] (e) The main program calls the recursive function from part 3(d) and outputs the value returned. (i) Amend the main program by writing program code to perform this task. Save your program. Copy and paste the program code into part 3(e)(i) in the evidence document. [1] (ii) Test your program. Take a screenshot to show the output. Copy and paste the screenshot into part 3(e)(ii) in the evidence document. [1]

21 marks

Mark scheme: 3(a) 1 mark per point: 3 • 1D array with 100 (Integer) spaces • head pointer declared initialised to appropriate value e.g. −1 • tail pointer declared initialised to 0 Example program code: Java public Integer[] queue = new Integer[100]; public Integer HeadPointer = -1; public Integer TailPointer = 0; Python Queue = [-1 for I in range(100)] #Integer HeadPointer = -1 TailPointer = 0 VB.NET Dim Queue(0 To 99) As Integer Dim HeadPointer As Integer = -1 Dim TailPointer As Integer = 0 3(b) 1 mark per point: 6 • Function header (and close where appropriate) with integer parameter • Checking if queue full and returning false • If not full adding parameter to queue at tail pointer … • … incrementing tail pointer (after adding to queue) • … and returning true • Changing head pointer to 0 if this is the first element in array Example program code: Java public Boolean Enqueue(Integer Data){ if(TailPointer < 100){ if(HeadPointer == -1){ HeadPointer = 0; } Queue[TailPointer] = Data; TailPointer = TailPointer + 1; return true; } return false; } Python def Enqueue(Data): global Queue global TailPointer if(TailPointer < 100): if HeadPointer == -1: HeadPointer = 0 Queue[TailPointer] = Data TailPointer = TailPointer + 1 return True return False VB.NET Function Enqueue(Data) If TailPointer < 100 Then If HeadPointer = -1 Then HeadPointer = 0 End If Queue(TailPointer) = data TailPointer = TailPointer + 1 Return True End If Return False End Function 3(c) 1 mark per point: 4 • Looping 20 times • … using Enqueue() with each number 1 to 20 in ascending numerical order… • … and storing/using the return value • … based on return value, outputting "Successful" and "Unsuccessful" if all numbers are added Example program code: Java public static void main(String[] args){ Boolean success = false; for(Integer count = 1; count <= 20; count++){ success = enqueue(count); } if(success == false){ System.Out.Println("Unsuccessful ") else{ System.Out.Println("Successful ") } } Python Success = False for Count in range(1, 21): Success = Enqueue(Count) if(Success == False): print("Unsuccessful") else: print("Successful") VB.NET Dim Success As Boolean For Count = 1 To 20 Success = Enqueue(Count) Next If Success = False THEN Console.WriteLine("Unsuccessful") ELSE Console.WriteLine("Successful") ENDIF 3(d) 1 mark per point: 6 • function call (and end where appropriate) taking a parameter • checking if at start of queue//20 … • …returning the last value in the queue • (otherwise) adding return value to a total // adding value in queue before recursive call and using this in the recursive call … • recursive call with Start/pointer −1 • returning the final total Example program code: Java public static Integer RecursiveOutput(Integer Start){ if(Start == 0){ return Queue[Start]; }else{ return Queue[Start] + RecursiveOutput(Start -1); }} Python def RecursiveOutput(Start): if(Start == 0): return Queue[Start] else: return Queue[Start] + RecursiveOutput(Start - 1) VB.NET Function RecursiveOutput(ByVal Start) If (Start = 0) Then Return Queue(Start) Else Return Queue(Start) + RecursiveOutput(Start - 1) End If End Function 3(e)(i) 1 mark for calling function and outputting return value. 1 Example program code: Java System.out.println(RecursiveOutput(TailPointer-1)); Python print(str(RecursiveOutput(TailPointer - 1))) VB.NET Console.WriteLine(RecursiveOutput(TailPointer - 1)) 3(e)(ii) 1 mark for screenshot showing 210, for example: 1

This question in 9618/42 Oct/Nov 2022

1 The text file IntegerData.txt stores 100 integer numbers between 1 and 100 inclusive. A program is required to read in this data and perform searching and sorting on the data. (a) Write program code to declare a global 1D array, DataArray, with space for 100 integer values. Save your program as Question1_N22. Copy and paste the program code into part 1(a) in the evidence document. [2] (b) The procedure ReadFile() must read in the numbers from the text file and store each one in the array. Use appropriate exception handling. Write program code for the procedure ReadFile(). Save your program. Copy and paste the program code into part 1(b) in the evidence document. [6] (c) The function FindValues() asks the user to enter a number to search for in the array. The number input must be a whole number between 1 and 100 inclusive. The function then returns the number of times the number input appears in the array. Write program code for the function FindValues(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [7] (d) (i) Write program code to call ReadFile() and FindValues() from the main program. The return value from FindValues() must be output with an appropriate message. Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [3] (ii) Test your program using the number 61 as input. Take a screenshot to show the output. Copy and paste the screenshot into part 1(d)(ii) in the evidence document. [1] (e) The procedure BubbleSort() needs to perform a bubble sort on the array and print the contents of the sorted array. Write program code for the procedure BubbleSort() and call it from the main program. Save your program. Copy and paste the program code into part 1(e) in the evidence document. [4]

23 marks

Mark scheme: Question Answer Marks 1(a) 1 mark per point: 2 • (global) 1D (Integer) array DataArray • 100 elements Example program code: Python DataArray = [0 for I in range (100)] Java public static Integer[] DataArray = new Integer[100]; VB.NET Dim DataArray(99) As Integer 1(b) 1 mark per point: 6 • Procedure ReadFile() header (and end where appropriate) • opening file IntegerData.txt (for read) • looping through the 100 elements // looping to end of file • reading each (and all) value from file and storing in array • closing file (in appropriate place) 1 mark per point: • Exception Handling (for opening the file, or for reading values from the file)… • …with appropriate catch and output messages Example program code: Python def ReadFile(): global DataArray try: TextFile = "IntegerData.txt" File = open(TextFile, 'r') for X in range(0, 100): DataArray[X] = File.readline() DataArray[X].rstrip('\n') DataArray[X] = int(DataArray[X]) File.close() except IOError: print("Count not find file") 1(b) Java public static void ReadFile(){ String Filename = "IntegerData.txt"; try{ FileReader F = new FileReader(Filename); BufferedReader Reader = new BufferedReader(F); for(Integer X = 0; X < 100; X++){ DataArray[X] = Integer.parseInt(Reader.readLine()); } Reader.close(); } catch(FileNotFoundException ex){ System.out.println("No file found"); } catch(IOException ex){ System.out.println("No file found"); } } VB.NET Sub ReadFile() try Dim TextFile As String = "IntegerData.txt" Dim FileReader As New System.IO.StreamReader(TextFile) For X = 0 To 99 DataArray(X) = FileReader.ReadLine() Next FileReader.Close() Catch ex As Exception Console.WriteLine("Invalid file") End Try End Sub 1(c) 1 mark per point: 7 • Function FindValues() (and end where appropriate) and input of data to search for in the array • …validation/casting(/storing as) of input as integer • …validation of input between 1 and 100 (inclusive) • looping through all 100 array elements… • …comparing input to each array element… • …initialising counter to 0 and then adding 1 each time it is found… • Returning the total 1(c) Example program code: Python def FindValues(): global DataArray DataToFind = -1 while(DataToFind < 1 or DataToFind > 100): DataToFind = int(input("Enter a number between 1 and 100")) Total = 0 for X in range(0, 99): if DataArray[X] == DataToFind: Total = Total + 1 return Total VB.NET Function FindValues() Dim DataToFind As Integer Do Console.WriteLine("Enter a number between 1 and 100") DataToFind = Console.ReadLine() Loop Until (DataToFind >= 1 And DataToFind <= 100) Dim Total As Integer = 0 For X = 0 To 99 If DataArray(X) = DataToFind Then Total = Total + 1 End If Next Return Total End Function Java public static Integer FindValues(){ Integer DataToFind = -1; while(DataToFind < 1 || DataToFind > 100){ System.out.println("Enter a number between 1 and 100"); Scanner in = new Scanner(System.in); DataToFind = in.nextInt(); } Integer Total = 0; for(Integer X = 0; X < 100; X++){ if(DataArray[X] == DataToFind){ Total = Total + 1; } } return Total; } 1(d)(i) 1 mark per point: 3 • Calling ReadFile() and then FindValues() (in the main program) • storing/using return value from FindValues() … • …outputting return value with appropriate message Example program code: Python ReadFile() print("The number appears " + str(FindValues()) + " times") Java public static void main(String[] args){ ReadFile(); Integer ReturnValue = FindValues(); System.out.println("The number was found " + ReturnValue + " times"); } VB.NET Sub Main() ReadFile() Dim ReturnValue As Integer = FindValues() Console.WriteLine("The number was found " & ReturnValue & " times") End Sub 1(d)(ii) Screenshot showing 61 input and 2 output, e.g. 1 1(e) 1 mark per point: 4 • procedure declaration (and end where appropriate) and outputting array contents at end of procedure and calling procedure from main program • correct outer loop … • … correct inner loop … • … swapping all elements if in incorrect order Example program code: Python def BubbleSort(): global DataArray N = 100 for I in range(N-1): for J in range(0, N-I-1): if DataArray[J] > DataArray[J+1]: DataArray[J], DataArray[J+1] = DataArray[J+1], DataArray[J] #main ReadFile() print("The number appears " + str(FindValues()) + " times") BubbleSort() print(DataArray) Java public static void BubbleSort(){ Integer Temp = 0; for(Integer I = 0; I < 100-1; I++){ for(Integer J = 0; J < 100-I-1; J++){ if(DataArray[J] > DataArray[J+1]){ Temp = DataArray[J]; DataArray[J] = DataArray[J+1]; DataArray[J+1] = Temp; } } } for(Integer X = 0; X < 100; X ++){ System.out.println(DataArray[X]); } } public static void main(String[] args){ ReadFile(); Integer ReturnValue = FindValues(); System.out.println("The number was found " + ReturnValue + " times"); BubbleSort(); } 1(e) VB.NET Sub Bubblesort() Dim Outer As Integer = 100 - 1 Dim Swap As Boolean Dim Inner As Integer Dim Temp As Integer Do Inner = 0 Swap = False Do If DataArray(Inner) > DataArray(Inner + 1) Then Temp = DataArray(Inner) DataArray(Inner) = DataArray(Inner + 1) DataArray(Inner + 1) = Temp Swap = True End If Inner = Inner + 1 Loop Until Inner = Outer Outer = Outer - 1 Loop Until Swap = False Or Outer = 0 For X = 0 To 99 Console.WriteLine(DataArray(X)) Next End Sub Sub Main() ReadFile() Dim ReturnValue As Integer = FindValues() Console.WriteLine("The number was found " & ReturnValue & " times") Bubblesort() End Sub

This question in 9618/43 Oct/Nov 2022

3 A binary tree consists of nodes. Each node has 3 integer values: a left pointer, data and a right pointer. The binary tree is stored using a global 2D array. The pseudocode declaration for the array is: DECLARE ArrayNodes : ARRAY[0:19, 0:2] OF INTEGER For example: • ArrayNodes[0, 0] stores the left pointer for the first node. • ArrayNodes[0, 1] stores the data for the first node. • ArrayNodes[0, 2] stores the right pointer for the first node. –1 indicates a null pointer, or null data. (a) Write program code to: • declare the global 2D array ArrayNodes • initialise all 3 integer values to –1 for each node. Save your program as Question3_N22. Copy and paste the program code into part 3(a) in the evidence document. [3] (b) The binary tree stores the following values: Index Left pointer Data Right pointer 0 1 20 5 1 2 15 –1 2 –1 3 3 3 –1 9 4 4 –1 10 –1 5 –1 58 –1 6 –1 –1 –1 FreeNode stores the index of the first free element in the array, initialised to 6. RootPointer stores the index of the first node in the tree, initialised to 0. Amend your program by writing program code to store the given data in ArrayNodes and initialise the free node and root node pointers. Save your program. Copy and paste the program code into part 3(b) in the evidence document. [2] (c) The following recursive pseudocode function searches the binary tree for a given value. If the value is found, the function must return the index of the value. If the value is not found, the function must return –1. The function is incomplete. There are four incomplete statements. FUNCTION SearchValue(Root : INTEGER, ValueToFind : INTEGER) RETURNS INTEGER IF Root = –1 THEN RETURN –1 ELSE IF ArrayNodes[Root, 1] = ValueToFind THEN RETURN … ELSE IF ArrayNodes[Root, 1] = –1 THEN RETURN –1 ENDIF ENDIF ENDIF IF ArrayNodes[Root, 1] … ValueToFind THEN RETURN SearchValue(ArrayNodes[ … , 0], ValueToFind) ENDIF IF ArrayNodes[Root, … ] < ValueToFind THEN RETURN SearchValue(ArrayNodes[Root, 2], ValueToFind) ENDIF ENDFUNCTION Write program code for the function SearchValue(). Save your program. Copy and paste the program code into part 3(c) in the evidence document. [5] (d) A post order traversal performs the following operation: • visit the left node • visit the right node • output the root. For example, in the following tree, the output would be: 3 9 25 60 50 50 25 60 3 9 An outline of the PostOrder() procedure is: • If left node is not empty, make a recursive call with the left node as the root. • If right node is not empty, make a recursive call with the right node as the root. • Output the current root node. The procedure PostOrder() takes the root node as a parameter. Write program code for the procedure PostOrder(). Save your program. Copy and paste the program code into part 3(d) in the evidence document. [7]

17 marks

Mark scheme: 3(a) 1 mark per point: 3 • Declaring (global) 2D array ArrayNodes • looping through all 20  3 elements of array … • …. storing −1 in each element Example program code: Java public static Integer[][] ArrayNodes = new Integer[20][3]; for(Integer X = 0; X<20; X++){ for(Integer Y = 0; Y<3; Y++){ ArrayNodes[X][Y] = -1 }} Python ArrayNodes = [] for x in range(0, 20): ArrayNodes.append([-1, -1, -1]) VB.NET Dim ArrayNodes(19, 2) As Integer Sub main() For X = 0 To 19 For Y = 0 To 2 ArrayNodes(X, Y) = -1 Next Next End Sub 3(b) 1 mark per point: 2 • initialising each of the first 6 array elements correctly • declaring and initialising FreeNode to 6 and RootPointer to 0 Example program code: Python ArrayNodes = [[1,20,5],[2,15,-1],[-1,3,3],[-1,9,4],[- 1,10,-1],[-1,58,-1]] FreeNodes = 6 RootPointer = 0 Java ArrayNodes[0][0] = 1; ArrayNodes[0][1] = 20; ArrayNodes[0][2] = 5; ArrayNodes[1][0] = 2; ArrayNodes[1][1] = 15; ArrayNodes[1][2] = -1; ArrayNodes[2][0] = -1; ArrayNodes[2][1] = 3; ArrayNodes[2][2] = 3; ArrayNodes[3][0] = -1; ArrayNodes[3][1] = 9; ArrayNodes[3][2] = 4; ArrayNodes[4][0] = -1; ArrayNodes[4][1] = 10; ArrayNodes[4][2] = -1; ArrayNodes[5][0] = -1; ArrayNodes[5][1] = 58; ArrayNodes[5][2] = -1; Integer FreeNode = 6; Integer RootPointer = 0; 3(b) VB.NET ArrayNodes(0, 0) = 1 ArrayNodes(0, 1) = 20 ArrayNodes(0, 2) = 5 ArrayNodes(1, 0) = 2 ArrayNodes(1, 1) = 15 ArrayNodes(1, 2) = -1 ArrayNodes(2, 0) = -1 ArrayNodes(2, 1) = 3 ArrayNodes(2, 2) = 3 ArrayNodes(3, 0) = -1 ArrayNodes(3, 1) = 9 ArrayNodes(3, 2) = 4 ArrayNodes(4, 0) = -1 ArrayNodes(4, 1) = 10 ArrayNodes(4, 2) = -1 ArrayNodes(5, 0) = -1 ArrayNodes(5, 1) = 58 ArrayNodes(5, 2) = -1 Dim FreeNode As Integer = 6 Dim RootPointer As Integer = 0 3(c) 1 mark for each completed statement (4) 5 1 mark for remainder of function correct Pseudocode: FUNCTION SearchValue(BYVAL Root : INTEGER, ValueToFind : INTEGER) IF Root = -1 THEN RETURN -1 ELSE IF ArrayNodes[Root,1] = ValueToFind THEN RETURN Root ELSE IF ArrayNodes[Root, 1] = -1 THEN RETURN -1 ENDIF ENDIF ENDIF IF ArrayNodes[Root,1] > ValueToFind THEN RETURN SearchValue(ArrayNodes[Root,0], ValueToFind) ENDIF IF ArrayNodes[Root,1] < ValueToFind THEN RETURN SearchValue(ArrayNodes[Root,2], ValueToFind) ENDIF ENDFUNCTION Example program code: Python def SearchValue(Root, ValueToFind): global ArrayNodes if Root == -1: return -1 elif ArrayNodes[Root][1] == ValueToFind: return Root elif ArrayNodes[Root][1] == -1: return -1 if(ArrayNodes[Root][1] > ValueToFind): return SearchValue(ArrayNodes[Root][0], ValueToFind) if(ArrayNodes[Root][1] < ValueToFind): return SearchValue(ArrayNodes[Root][2], ValueToFind) 3(c) Java public static Integer SearchValue(Integer Root, Integer ValueToFind){ if(Root == -1){ return -1; }else if(ArrayNodes[Root][1] == ValueToFind){; return Root; }else if(ArrayNodes[Root][1] == -1){ return -1; } if(ArrayNodes[Root][1] > ValueToFind){ return(SearchValue(ArrayNodes[Root][0], ValueToFind)); } if(ArrayNodes[Root][1] < ValueToFind){ return(SearchValue(ArrayNodes[Root][2], ValueToFind)); } return -1; } VB.NET Function SearchValue(ByVal Root, ByVal ValueToFind) If ArrayNodes(Root, 1) = ValueToFind Then Return Root ElseIf ArrayNodes(Root, 1) = -1 Then Return -1 End If If ArrayNodes(Root, 1) > ValueToFind Then Return SearchValue(ArrayNodes(Root, 0), ValueToFind) End If If ArrayNodes(Root, 1) < ValueToFind Then Return SearchValue(ArrayNodes(Root, 2), ValueToFind) End If Return -1 End Function 3(d) 1 mark per point (Max 7): 7 • (procedure) header (and end where appropriate) with one parameter (root node or index of root node) and at least one recursive call • checking if left node is −1 … • … if not recursive call with parameter as ArrayNodes[RootNode[0]] • checking if right node is −1 … • …if not recursive call with parameter as ArrayNodes[RootNode[2]] • outputting the element at the parameter RootNode[] • all 3 in the correct order Example program code: Python def PostOrder(RootNode): if RootNode[0] != -1: PostOrder(ArrayNodes[RootNode[0]]) if RootNode[2] != -1: PostOrder(ArrayNodes[RootNode[2]]) print(str(RootNode[1])) Java public static void PostOrder(Integer[] RootNode){ if(RootNode[0] != -1){ PostOrder(ArrayNodes[RootNode[0]]); } if(RootNode[2] != -1){ PostOrder(ArrayNodes[RootNode[2]]); } System.out.println(RootNode[1]); } VB.NET Sub PostOrder(RootNode() As Integer) Dim TempArray(2) As Integer If RootNode(0) <> -1 Then TempArray(0) = ArrayNodes(RootNode(0), 0) TempArray(1) = ArrayNodes(RootNode(0), 1) TempArray(2) = ArrayNodes(RootNode(0), 2) PostOrder(TempArray) End If If RootNode(2) <> -1 Then TempArray(0) = ArrayNodes(RootNode(2), 0) TempArray(1) = ArrayNodes(RootNode(2), 1) TempArray(2) = ArrayNodes(RootNode(2), 2) PostOrder(TempArray) End If Console.WriteLine(RootNode(1)) End Sub 3(e)(i) 1 mark per point: 3 • calling SearchValue() with 15 and rootPointer as a parameter … • … if return value > -1 output returned index and if return value = -1 output not found Both as appropriate messages • Calling PostOrder() with ArrayNodes[RootPointer] as a parameter Example program code: Python ReturnValue = SearchValue(RootPointer, 15) if ReturnValue == -1: print("Not found") else: print("Found at " + str(ReturnValue)) PostOrder(ArrayNodes[RootPointer]) Java Integer ReturnValue = SearchValue(RootPointer, 15); if(ReturnValue == -1){ System.out.println("Not found"); } else { System.out.println("Found at " + ReturnValue); } PostOrder(ArrayNodes[RootPointer]); VB.NET Dim returnvalue As Integer = SearchValue(RootPointer, 15) If returnvalue = -1 Then Console.WriteLine("Not found") Else Console.WriteLine("Found at " & returnvalue) End If Console.WriteLine("Post order") Dim TempArray(2) As Integer TempArray(0) = ArrayNodes(RootPointer, 0) TempArray(1) = ArrayNodes(RootPointer, 1) TempArray(2) = ArrayNodes(RootPointer, 2) PostOrder(TempArray) 3(e)(ii) Screenshot with result as shown, for example: 1

This question in 9618/43 Oct/Nov 2022