19.1 Algorithms (A Level)
A Level · 77 questions found
What this topic covers
Section titled “What this topic covers”- Linear search: write algorithm, conditions, performance
- Binary search: write algorithm, required conditions, performance vs data size
- Insertion sort and bubble sort: write algorithms; performance depends on data order and size
- Full ADTs — find, insert, delete in: stack, queue, linked list, dictionary, binary tree
- Graph as ADT: key features; A* and Dijkstra’s algorithms for searches
- Implementing ADTs from other ADTs
- Compare algorithms: Big O notation for time and space complexity
Past paper questions
Section titled “Past paper questions”(a) A stack has been implemented using pseudocode to store a maximum of 100 string items using the global variables in the following table:
| Identifier | Data type | Description | Initialisation value |
|---|---|---|---|
| Base | INTEGER | pointer for the bottom of the stack | 0 |
| Top | INTEGER | pointer for the top of the stack | ‑1 |
| StackArray | STRING | 1D array to implement the stack | [0:99] |
| Max | INTEGER | maximum number of items in the stack | 100 |
The value of Top is incremented each time a data item is added to the stack and decremented every time a data item is removed.
(i) Complete the pseudocode for the function to remove a data item from the stack. 5 marks
FUNCTION Pop() DECLARE DataItem : STRING DataItem ""
IF ______ THEN
DataItem
Top ELSE DataItem "You cannot remove data; the stack is empty" ENDIF
ENDFUNCTION
(ii) Write the pseudocode to output the data item removed from the stack with an appropriate message. 1 mark
(b) A stack is used to implement recursion. 3 marks
State the three essential features of recursion.
1
2
3
Show mark scheme
9(a)(i) [5 marks]
One mark for each correctly completed line ( Max 5 ) FUNCTION Pop() RETURNS STRING DECLARE DataItem : STRING DataItem "" // IF Top > –1 Top >= Base THEN DataItem StackArray[Top] Top Top – 1 ELSE DataItem "You cannot remove data; the stack is empty" ENDIF // RETURN DataItem StackArray[Top + 1] ENDFUNCTION
9(a)(ii) [1 mark]
OUTPUT "The data removed from the stack is ", Pop()
9(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 A recursive algorithm must call itself / have a general case MP2 It must have a base case / have a stopping condition MP3 It must change its state and move towards the base case
(a) A stack has been implemented using pseudocode to store a maximum of 100 string items using the global variables in the following table:
| Identifier | Data type | Description | Initialisation value |
|---|---|---|---|
| Base | INTEGER | pointer for the bottom of the stack | 0 |
| Top | INTEGER | pointer for the top of the stack | -1 |
| StackArray | STRING | 1D array to implement the stack | [0:99] |
| Max | INTEGER | maximum number of items in the stack | 100 |
The value of Top is incremented each time a data item is added to the stack and decremented each time a data item is removed. If the stack is full, an appropriate error message is output.
(i) Complete the pseudocode for the procedure to add a data item onto the stack. 4 marks
PROCEDURE Push(______) IF Top < Max – 1 THEN
Top ←
______ ← NewData ELSE
OUTPUT ENDIF ENDPROCEDURE
(ii) Write pseudocode to input a new data item and add it to the stack using Push(). 2 marks
(b) Explain the reasons why a stack is used when a recursive algorithm is executed. 3 marks
Show mark scheme
12(a)(i) [4 marks]
One mark for each correctly completed line ( Max 4 ) PROCEDURE Push( NewData : STRING ) IF Top < Max – 1 THEN Top Top + 1 StackArray[Top] NewData ELSE OUTPUT "Stack full; new data cannot be added" ENDIF ENDPROCEDURE
12(a)(ii) [2 marks]
One mark per mark point ( Max 2 ) MP1 Input with variable, with or without prompt MP2 Procedure call for Push with parameter used matching input variable Example answer INPUT MyData CALL Push(MyData)
12(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 Stacks store data in Last In First Out (LIFO) / First In Last Out (FILO) order MP2 Each time a recursive algorithm calls itself data is pushed onto the stack MP3 When the recursive algorithm reaches its base case / starts to unwind MP4 … data is popped from the stack in the reverse order to which it was pushed onto it.
Calculate the shortest distance between the Start node and each of the nodes in the graph using Dijkstra’s algorithm.
Show your working on the graph or in the working space. Write your answers in the table provided.
Working
Answers: 5 marks
| T | V | W | X | Y | Z |
|---|---|---|---|---|---|
Show mark scheme
8 [5 marks]
One mark per mark point - working ( Max 3 ) May be seen on diagram or in working section MP1 Initialisation – setting Start to 0 MP2 … and the rest of the towns to MP3 Evidence to show values at nodes being updated MP4 Evidence to show ‘visited node(s)’ MP5 Evidence to show a correct calculation of at least one route MP6 Evidence to show more than one route has been calculated for at least one town Correct Answers ( Max 2 ) Two marks for all six correct values One mark for four or five correct values. 6 10 13 18 21 28
A stack, StackArray, is to be implemented using pseudocode, to store a maximum of 100 string items in an appropriate array. Declarations are required so that the stack has a beginning, an end and a maximum size. An array is also required to store the data.
(a) Write pseudocode to declare the variables, constant and array required to implement the stack. 3 marks
(b) Write pseudocode for a procedure to initialise the top and bottom pointers of the stack to appropriate values. 3 marks
Show mark scheme
10(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 Correct declaration of constant Maximum MP2 Both correctly declared integers MP3 Correct array declaration Example answer CONSTANT Maximum = 100 DECLARE Base : INTEGER DECLARE Top : INTEGER DECLARE StackArray : ARRAY[1:100] OF STRING
10(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 Correct procedure definition structure MP2 Base pointer with appropriate value (0 or 1) MP3 Top pointer with appropriate value (–1, 0, 1) Example answer PROCEDURE InitialiseStack() Base 0 Top 0 ENDPROCEDURE
Show mark scheme
12(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 An exception is an unplanned / unexpected event that occurs when a program is running MP2 … due to an error in programming/logic that wasn’t detected during program construction/compilation MP3 The effect of an exception can be that the program halts unexpectedly. One mark per mark point ( Max 2 )
12(b) [2 marks]
MP1 One mark for an example of an exception (see list in guidance) MP2 One mark for the reason for the given exception Example answer Division by zero The processor will not be able to evaluate this answer because a number divided by zero is infinity, so the program will crash.
A program stores 20 unique random integers between 0 and 100 (inclusive) in a 1D array that is local to the main program.
(a) Write program code to declare the array local to the main program and store 20 unique random numbers between 0 and 100 (inclusive) in the array. 3 marks
Save your program as Question2_N25 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) The procedure PrintArray() takes an integer array as a parameter. The procedure outputs the array contents on a single line with a space between each integer. 3 marks
Write the program code for PrintArray()
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The function BubbleSort() : 5 marks
takes an integer array as a parameter
sorts the data into ascending order using a bubble sort
returns the sorted array.
The function needs to work for an array of any length.
Do not use an inbuilt sorting method.
Write program code for BubbleSort()
Save your program.
Copy and paste the program code into part 2(c) in the evidence document. (d) (i) The main program:
outputs the contents of the array using
PrintArray()sorts the array using
BubbleSort()outputs
"Sorted"outputs the contents of the sorted array using
PrintArray()
Write program code for the main program.
Save your program.
Copy and paste the program code into part 2(d)(i) in the evidence document.
(ii) Test your program. 3 marks
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot(s) into part 2(d)(ii) in the evidence document.
(e) The recursive function RecursiveBinarySearch() takes four parameters: 1 mark 6 marks
an integer array
the lower bound of the array
the upper bound of the array
the value to find in the array.
The recursive function performs a binary search to find the index of the value in the array.
The function returns the index of the value if it is found. The function returns –1 if the value is
not found.
Write program code for RecursiveBinarySearch()
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) (i) The main program: 3 marks
prompts the user to enter an integer
takes the integer as input
calls
RecursiveBinarySearch()with the sorted array, appropriate lower bound, appropriate upper bound and the user’s input as parametersoutputs
"Not found"if the input is not within the arrayoutputs
"Found at position"and the index if the input is within the array.
Write program code to amend the main program.
Save your program.
Copy and paste the program code into part 2(f)(i) in the evidence document.
(ii) Test your program three times with each of the inputs described: 2 marks
Test 1: the smallest number in the array
Test 2: the largest number in the array
Test 3: a number not in the array
Take a screenshot of each output.
Save your program.
Copy and paste the screenshot(s) into part 2(f)(ii) in the evidence document.
Show mark scheme
2(a)
Python TheArray = [] TheArray = random.sample(range(0,101),20)
2(b) [3 marks]
1 mark each • Procedure header (and close) taking (array) as parameter • Outputting array contents once … • … on one line with a space between each integer Example program code Java public static void PrintArray(Integer[] DataArray){ String Output = ""; for(Integer X = 0; X < 20; X++){ Output += Integer.toString(DataArray[X]) + " "; } System.out.println(Output); } VB.NET Sub PrintArray(DataArray() As Integer) Dim Output As String = "" For X = 0 To 19 Output = Output + Str(DataArray(X)) + " " Next X Console.WriteLine(Output) End Sub Python def PrintArray(DataArray): Output = "" for Item in DataArray: Output = Output + str(Item) + " " print(Output)
2(c)
VB.NET Function BubbleSort(DataArray() As Integer) Dim Swap As Boolean = True Dim Temp As Integer While Swap = True Swap = False For X = 0 To DataArray.Length - 2 If DataArray(X) > DataArray(X + 1) Then Temp = DataArray(X) DataArray(X) = DataArray(X + 1) DataArray(X + 1) = Temp Swap = True End If Next X End While Return DataArray End Function Python def BubbleSort(DataArray): Swap = True while Swap == True: Swap = False for y in range(0, len(DataArray)-1): if DataArray[y] > DataArray[y+1]: DataArray[y], DataArray[y+1] = DataArray[y+1], DataArray[y] Swap = True return DataArray
2(d)(i) [3 marks]
1 mark each • Calling with array as argument PrintArray() • Calling with array as argument and storing/using return value BubbleSort() • Outputting and calling with (returned) array as argument "Sorted" PrintArray() Example program code Java PrintArray(TheArray); Integer[] SortedArray = new Integer[20]; SortedArray = BubbleSort(TheArray); System.out.println("Sorted"); PrintArray(SortedArray); VB.NET PrintArray(TheArray) Dim SortedArray(19) As Integer SortedArray = BubbleSort(TheArray) Console.WriteLine("Sorted") PrintArray(SortedArray) Python PrintArray(TheArray) SortedArray = BubbleSort(TheArray) print("Sorted") PrintArray(SortedArray)
2(d)(ii) [1 mark]
1 mark • Output shows unsorted array of 20 integers between 0 and 100 inclusive before sorting, “Sorted” output, array of the same integers sorting into ascending order. All screenshots will be unique to the candidate
2(e)
VB.NET Function RecursiveBinarySearch(DataArray() As Integer, Lower As Integer, Upper As Integer, DataToFind As Integer) Dim Middle As Integer If Upper >= Lower Then Middle = Lower + (Upper - Lower) \ 2 If DataArray(Middle) = DataToFind Then Return Middle ElseIf DataArray(Middle) > DataToFind Then Return RecursiveBinarySearch(DataArray, Lower, Middle - 1, DataToFind) Else Return RecursiveBinarySearch(DataArray, Middle + 1, Upper, DataToFind) End If Else Return -1 End If End Function Python def RecursiveBinarySearch(DataArray, Lower, Upper, DataToFind): if Upper >= Lower: Middle = Lower + (Upper - Lower) // 2 if DataArray[Middle] == DataToFind: return Middle elif DataArray[Middle] > DataToFind: return RecursiveBinarySearch(DataArray, Lower, Middle - 1, DataToFind) else: return RecursiveBinarySearch(DataArray, Middle + 1, Upper, DataToFind) else: return -1
2(f)(i) [3 marks]
1 mark each • Prompt and input of integer • Call of RecursiveBinarySearch(SortedArray, 0, 19, input) • Output of if returned and output "Not found" –1 "Found at position" Example program code Java System.out.println("Enter the number to find"); Scanner scanner = new Scanner(System.in); Integer DataToFind = Integer.parseInt(scanner.nextLine()); Integer Location = RecursiveBinarySearch(SortedArray, 0, 19, DataToFind); if(Location == -1){ System.out.println("Not found"); }else{ System.out.println("Found at position " + Location); } VB.NET Console.WriteLine("Enter the number to find ") Dim DataToFind As Integer = Console.ReadLine() Dim Location As Integer = RecursiveBinarySearch(SortedArray, 0, 19, DataToFind) If Location = -1 Then Console.WriteLine("Not found") Else Console.WriteLine("Found at position " & Location) End If Python DataToFind = int(input("Enter the number to find ")) Location = RecursiveBinarySearch(SortedArray, 0, 19, DataToFind) if Location == -1: print("Not found") else: print("Found at position", Location)
2(f)(ii) [2 marks]
1 mark each • screenshot showing smallest number in array input and found message with index 0 number in array input and found message with index 19 • screenshot showing a number not in the array input and an output of "Not found" All screenshots will be unique to the candidate
A program stores integers in ascending order in an ordered binary tree. The tree is implemented as a 2D array.
Each node is stored with three values:
a pointer to the left node
the data
a pointer to the right node.
All null values are stored as –1
The binary tree can store up to 50 nodes.
Nodes cannot be deleted from the binary tree.
(a) The binary tree is stored as a global array with the identifier TreeArray . The left pointer, the data and the right pointer of each node are initialised to –1 The global variable RootPointer stores the index of the root node in the tree, initialised to 3 marks
–1
The global variable FreeNode stores the index of the next free node in the array, initialised
to 0
Write program code to declare and initialise TreeArray, RootPointer and FreeNode
Save your program as Question3_N25 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The procedure AddNode() : 7 marks
takes an integer to store in the binary tree as a parameter
stores the parameter in the next free node in the array
finds the position to store the data in the tree by following the appropriate pointers
updates the pointer of the new node’s parent node.
The procedure outputs "The tree is full" if the parameter cannot be stored because
the tree is full.
Write program code for AddNode()
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The text file TreeData.txt stores 50 integers. Each integer is on a new line in the file. 4 marks
The main program reads each integer from the file and stores each integer in the binary tree in the order they are read.
Write program code for the main program.
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The procedure WriteAllToFile() stores the content of TreeArray in a new text file with the filename Tree.txt . The file Tree.txt is not provided. 5 marks
Each node in TreeArray is stored on one line with a comma separating each value.
For example, the current contents of TreeArray are:
| Index | 0 | 1 | 2 |
|---|---|---|---|
0 |
–1 |
20 |
1 |
1 |
–1 |
30 |
–1 |
| … | |||
49 |
-1 |
-1 |
-1 |
After writing TreeArray to the text file, Tree.txt will contain:
–1,20,1
–1,30,–1
…
-1,-1,-1
Write program code for WriteAllToFile()
Include exception handling when writing to the file.
Save your program.
Copy and paste the program code into part 3(d) in the evidence document.
(e) (i) Amend the main program to call WriteAllToFile() 1 mark
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot that shows all of the content stored in the file Tree.txt
In this screenshot you need to make sure the filename is visible.
Save your program.
Copy and paste the screenshot(s) into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a)
Python TreeArray = [] for x in range(50): TreeArray.append([-1,-1,-1]) RootPointer = -1 FreeNode = 0
3(b)
if TreeArray[CurrentNode][0] == -1: TreeArray[CurrentNode][0] = FreeNode Placed = True else: CurrentNode = TreeArray[CurrentNode][0] else: if TreeArray[CurrentNode][2] == -1: TreeArray[CurrentNode][2] = FreeNode Placed = True else: CurrentNode = TreeArray[CurrentNode][2] FreeNode = FreeNode + 1 else: print("The tree is full")
3(c)
VB.NET Try Dim FileReader As New System.IO.StreamReader("TreeData.txt") While Not FileReader.EndOfStream AddNode(FileReader.ReadLine()) End While FileReader.Close() Catch ex As Exception Console.WriteLine("Cannot open file") End Try Python try: File= open("TreeData.txt") for Line in File: AddNode(int(Line.strip())) File.close() except: print("Error cannot open file")
3(d)
VB.NET Sub WriteAllToFile() Dim FileWriter As IO.StreamWriter = New IO.StreamWriter("Tree.txt", False) Dim Line As String Try For x = 0 To 49 Line = TreeArray(x, 0) & "," & TreeArray(x, 1) & "," & TreeArray(x, 2) FileWriter.WriteLine(Line) Next FileWriter.Close() Catch ex As Exception Console.WriteLine("Cannot open or write to file") End Try End Sub Python def WriteAllToFile(): try: File = open("Tree.txt","a+") for x in range(0, 50): Line = str(TreeArray[x][0]) + "," + str(TreeArray[x][1])+ "," + str(TreeArray[x][2]) + "\n" File.write(Line) File.close() except: print("Cannot write to file")
3(e)(i) [1 mark]
1 mark for calling WriteAllToFile() Example program code Java WriteAllToFile(); VB.NET WriteAllToFile() Python WriteAllToFile()
3(e)(ii) [1 mark]
1 mark for a screenshot that shows correct data stored, each node on a new line (in correct format). The screenshot must include the filename. e.g.
(a) A linked list of nodes is used to store an ordered list of integers. Each node consists of the data, a left pointer and a right pointer, for example:
Left pointer Data Right pointer
The linked list will be organised as a binary tree.
−1 is used to represent a null pointer.
Complete the binary tree, including null pointers, to show how the data will be organised after the following integers have been added:
6, 15, 41, 66 Root pointer 4 marks
(b) Describe what is meant by recursion. 2 marks
Show mark scheme
4(a) [4 marks]
One mark per mark point MP1 Any two nodes added correctly with correct data (6, 15, 41, 66) and arrows MP2 Remaining two nodes added with correct data (6, 15, 41, 66) and all nodes with connecting arrows starting from pointer boxes MP3 Correct null pointers (-1) added throughout MP4 … with no entries in other pointer boxes and all nodes correctly positioned and connected Root pointer Left pointer Data Right pointer 36 -1 40 12 -1 3 -1 15 -1 -1 41 -1 6 -1 -1 66 -1
4(b) [2 marks]
One mark per mark point MP1 A technique used to solve problems using a function/procedure/subroutine that calls itself (general case) MP2 … until the terminating condition / base case is achieved, when no further recursive calls are made
4(c) [1 mark]
One mark • Stack
(a) State the purpose of the A* and Dijkstra’s algorithms. 1 mark
(b) Outline the difference between the A* and Dijkstra’s algorithms. 2 marks
(c) Explain how unsupervised learning takes place in machine learning. 3 marks
Show mark scheme
10(a) [1 mark]
To find the path between two points on a graph using the algorithm.
10(b) [2 marks]
One mark per point ( Max 2 ) MP1 A* tries to find a better path (between two points) by using a heuristic function // A* finds the adjacent route with the shortest path and continues this until the destination is reached MP2 … Dijkstra’s just explores all possible routes. MP3 The heuristic function on the A* algorithm gives priority to nodes that are supposed to be better than others / less costly than others. MP4 Dijkstra’s algorithm cannot work with negative values/weights //A* algorithm can work with negative values/weights.
10(c) [3 marks]
One mark for each mark point ( Max 3 ) MP1 Unsupervised learning uses algorithms to analyse / cluster MP2 … unlabelled data sets MP3 They discover hidden patterns / data groupings / clusters without the need for human intervention. MP4 It is able to discover similarities and differences in data / information.
(a) An array is an Abstract Data Type (ADT). 1 mark
Identify two other ADTs.
1
2
(b) A 1D array DataArray holds up to 1000 elements of type integer and needs to be sorted in ascending order. 4 marks
Write the pseudocode for an insertion sort to sort the array into ascending order.
Use the identifiers from the table in your algorithm.
You do not need to declare any arrays or variables for this algorithm. You may assume this has already been done.
| Identifier | Data type | Description |
|---|---|---|
| Index | INTEGER | counter for outer loop |
| Position | INTEGER | counter for inner loop – insertion position |
| DataArray | INTEGER | 1D array to store up to 1000 integers |
| Value | INTEGER | value to insert |
The first line has been written for you.
FOR Index ← 2 to 1000
(c) Describe two ways in which the performance of a sort routine is affected by the data to be sorted. 2 marks
1
2
Show mark scheme
12(a) [1 mark]
One mark for any two correct ADTs ( Max 1 ) • Binary tree • Graph • Linked list • Queue • Stack
12(b) [4 marks]
One mark for each marking point ( Max 4 ) MP1 Temporary assignment of the element being ‘inserted’ before inner loop MP2 Appropriate inner loop MP3 Check if current content is > DataArray Value MP4 Moving data to adjacent element as required MP5 Appropriate updating of variable Position MP6 Re-insertion of the element outside the inner loop Example algorithm FOR Index 2 to 1000 Value DataArray[Index] Position Index – 1 IF DataArray[Position] > Value THEN WHILE Position >= 1 AND DataArray[Position] > Value DataArray[Position + 1] DataArray[Position] Position Position – 1 ENDWHILE DataArray[Position + 1] Value ENDIF NEXT Index
12(c) [2 marks]
One mark for each marking point MP1 The performance of a sorting routine should improve if the data is already partially sorted // The performance of a sorting routine is likely to be worse if the data is completely out of order MP2 The sort may take longer if the number of items to be sorted is larger // The sort may take less time if the number of items to be sorted is fewer.
A program stores data in a binary tree that is designed using Object‑Oriented Programming (OOP).
| e stores data in ascending numerical order, for example: | |
|---|---|
| 30 20 45 63 33 1 21 |
30 20 45 63 33 1 21 |
| 1 | 63 |
| The class Node stores data about the nodes. Node | |
|---|---|
Node |
Node |
NodeData : IntegerLeftNode : NodeRightNode : Node |
stores the node’s integer data stores the node that is stored to the left of the current node, or a null value if there is no node to the left stores the node that is stored to the right of the current node, or a null value if there is no node to the right |
Constructor()GetLeft()GetRight()GetData()SetLeft()SetRight() |
initialisesNodeData to its parameter value; initialisesLeftNode andRightNode to a null valuereturns LeftNodereturns RightNodereturns NodeData takes an object of type Node as a parameter and storesit in LeftNodetakes an object of type Node as a parameter and storesit in RightNode |
(a) (i) Write program code to declare the class Node and its constructor. 4 marks
Do not declare the other methods.
Use your programming language appropriate constructor.
If you are writing in Python, include attribute declarations using comments.
Save your program as Question3_J25 .
Copy and paste the program code into part 3(a)(i) in the evidence document.
(ii) Write program code for the three get methods. 3 marks
Save your program.
Copy and paste the program code into part 3(a)(ii) in the evidence document.
(iii) The method SetLeft() takes an object of type Node as a parameter. The method stores the parameter in the attribute LeftNode The method SetRight() takes an object of type Node as a parameter. The method stores the parameter in the attribute RightNode Write program code for SetLeft() and SetRight() Save your program. 3 marks
Copy and paste the program code into part 3(a)(iii) in the evidence document.
(b) Write the main program to declare five objects of type Node : 2 marks
Node 1 with the data
10Node 2 with the data
20Node 3 with the data
5Node 4 with the data
15Node 5 with the data
7
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
| (c) The class Tree stores the tree. Tree | |
|---|---|
Tree |
Tree |
FirstNode : Node |
stores the root node in the tree |
Constructor()GetRootNode()Insert() |
initialisesFirstNode to its parameter valuereturns the node stored in FirstNodestores its parameter node in the correct position in the tree |
(i) Write program code to declare the class Tree and its constructor. 2 marks
Do not declare the other methods.
Use your programming language appropriate constructor.
If you are writing in Python, include attribute declarations using comments.
Save your program.
Copy and paste the program code into part 3(c)(i) in the evidence document.
(ii) Write program code for GetRootNode() Save your program. 1 mark
Copy and paste the program code into part 3(c)(ii) in the evidence document.
(iii) The method Insert() takes a node as a parameter and then searches the tree to find the position to insert the new node by: 6 marks
checking whether the node’s data is less than or greater than the root node’s data
moving to the left node if the data is less than the root node’s data
moving to the right node if the data is greater than or equal to the root node’s data
repeating until the final position of the node is found and stores the node in that position.
Write program code for Insert()
Save your program.
Copy and paste the program code into part 3(c)(iii) in the evidence document.
(d) The recursive procedure OutputInOrder() outputs the data stored in the binary tree in ascending numerical order. 5 marks
The procedure takes a Node object as a parameter and then:
checks if the left node is null. If there is a left node, the function calls itself with the left node
outputs the data of the current node
checks if the right node is null. If there is a right node, the function calls itself with the right node.
Write program code for OutputInOrder()
Save your program.
Copy and paste the program code into part 3(d) in the evidence document. (e) (i) Write program code to extend the main program to: 3 marks
create a new object of type
Treewith the node containing the data 10 as the first nodeinsert the nodes with the values 20, 5, 15 and 7 into the tree in the order given
call
OutputInOrder()with the tree’s root node as a parameter.
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a)(i) [4 marks]
1 mark each • Class header (and end where appropriate) • Constructor header (and end where appropriate) with (min) one parameter (integer) within class • 3 attributes with correct data types • has parameter assigned, and are assigned null within constructor NodeData LeftNode RightNode
NodeData = pNodeData LeftNode = Nothing RightNode = Nothing
3(a)(ii) [3 marks]
1 mark each • 1 get method with no parameter … • … returning correct value • 2nd and 3rd correct get methods
3(a)(iii) [3 marks]
1 mark each • 1 set method taking parameter of type Node … • … assigning to correct attribute • 2nd correct set method
3(b) [2 marks]
1 mark each • Creating 1 instance of with a correct value and storing the node … Node • … remaining 4 correct
3(c)(i) [2 marks]
1 mark each • Class header (and end) no inheritance and constructor header (and end) taking 1 node parameter within class … Tree • … storing parameter in declared as a data type FirstNode Node FirstNode = pFirstNode FirstNode = pFirstNode;
3(c)(ii) [1 mark]
1 mark for • Get method header (and end) with no parameter, returning FirstNode
3(c)(iii) [6 marks]
1 mark each to max 6 • Insert method header (and end) taking 1 node parameter • If parameter < first node, checking if there is a left node … • … storing node in left node if it is null • If parameter >= first node, checking if there is a right node … • … storing node in right node if it is null • Looping until correct position is found // recursive calls
If NewNode.GetData() < CurrentNode.GetData() Then If CurrentNode.GetLeft() Is Nothing Then CurrentNode.SetLeft(NewNode) Return True Else CurrentNode = CurrentNode.GetLeft() End If
Else If CurrentNode.GetRight() Is Nothing Then CurrentNode.SetRight(NewNode) Return True Else CurrentNode = CurrentNode.GetRight() End If End If
3(d) [5 marks]
1 mark each • Procedure header (and end) taking node as parameter, that is recursive • Checking if left is null and recursive call if not null • Outputting node's data • Checking if right is null and recursive call if not null • Correct order
OutputInOrder(RootNode.GetLeft()) OutputInOrder(RootNode.GetRight())
3(e)(i) [3 marks]
1 mark each • Creation of object with the Node with value 10 as parameter Tree • Calling method for tree with the nodes for 20, 5, 15 and 7 in order Insert() • Calling with tree's root node as parameter OutputInOrder()
3(e)(ii) [1 mark]
Output of 5 7 10 15 20
A program sorts the data in the 1D array DataArray and searches DataArray for specific
values.
DataArray stores 14 integer values and is declared local to the main program.
(a) Write program code to create DataArray and initialise it with the following data values in the order they are written: 1 mark
0 3 4 56 67 44 43 32 31 345 45 6 54 1
Save your program as Question2_J25 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) The function InsertionSort() takes an array of integers as a parameter. The function sorts the data in the array into ascending numerical order using an insertion sort. The function returns the sorted array. 5 marks
Write program code for InsertionSort()
You must not use any inbuilt sorting functions for your programming language.
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The procedure OutputArray() takes an array of integers as a parameter. The procedure outputs each element in the array from the first element to the last element. The output is on one line with a space between each number. 2 marks
An example output is:
"0 3 4 56 67 44 43 32 31 345 45 6 54 1"
Write program code for OutputArray()
Save your program.
Copy and paste the program code into part 2(c) in the evidence document. (d) (i) The main program needs extending to: 2 marks
output the content of the unsorted array using
OutputArray()sort the array using
InsertionSort()output the content of the sorted array using
OutputArray()
Write program code to extend the main program.
Save your program.
Copy and paste the program code into part 2(d)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 2(d)(ii) in the evidence document.
(e) The function Search() performs a binary search to find ItemToFind in DataArray The function takes two parameters: 6 marks
DataArray, an array of integersItemToFind, an integer to find inDataArray
The function returns:
the index of
ItemToFindif it is inDataArray–1ifItemToFindis not inDataArray
Write program code for Search()
You must not use any inbuilt searching functions for your programming language.
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) (i) The main program needs extending to call Search() with the sorted array four times: 2 marks
the first time to find the index of the integer 0
the second time to find the index of the integer 345
the third time to find the index of the integer 67
the fourth time to find the index of the integer 2
If the integer is found in the array, output an appropriate message that includes the index. If the integer is not found, output that it was not found.
Write program code to extend the main program.
Save your program.
Copy and paste the program code into part 2(f)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 2(f)(ii) in the evidence document.
Show mark scheme
2(a) [1 mark]
1 mark for array declared with data values: 0 3 4 56 67 44 43 32 31 345 45 6 54 1
2(b) [5 marks]
1 mark each • header (and close) taking array as a parameter and returning (attempt at) sorted array InsertionSort() • Looping through/for each element • Extracting element and comparing to sorted list … • … moving elements in sorted list • … and inserting element in correct position (ascending order)
Return DataArray CurrentValue = DataArray(X) Y = X - 1 While Y >= 0 AndAlso CurrentValue < DataArray(Y) DataArray(Y + 1) = DataArray(Y) Y = Y - 1 End While DataArray(Y + 1) = CurrentValue
2(c) [2 marks]
1 mark each • header (and close) taking an array parameter and outputting the array contents … OutputArray() • … in correct format
If DataArray(X) <> -1 Then Output = Output & DataArray(X) & " " End If X = X + 1
2(d)(i) [2 marks]
1 mark each • Calling with array parameter and storing/using return array InsertionSort() • … calling with array parameter before and after OutputArray() InsertionSort()
2(d)(ii) [1 mark]
1 mark for output showing unsorted then sorted array e.g.
2(e) [6 marks]
1 mark each • header (and close) taking array and integer as parameters Search() • Looping/recursive calls until no elements left/Low<=High and returning –1 if not found • … calculating middle index and accessing this value • … comparison of array at middle value to integer parameter • … if they are equal return mid • … if array[mid] < parameter update low to middle + 1, if array[mid] > parameter update high to middle – 1 // recursive call with updated low and updated high
Middle = (High + Low) \ 2 If DataArray(Middle) < ItemToFind Then Low = Middle + 1 ElseIf DataArray(Middle) > ItemToFind Then High = Middle - 1 Else Return Middle End If
2(f)(i) [2 marks]
1 mark each • Calling with all four sets of values 0 345 67 2 Search() • … outputting 'not found' or index in appropriate message each time
2(f)(ii) [1 mark]
1 mark for output showing locations for first 3 and not found for 4th
A program stores data in a linked list that is designed using Object‑Oriented Programming (OOP).
The class Node stores data about the nodes.
| Node | |
|---|---|
TheData : IntegerNextNode : Node |
stores the integer data stores the next node in the linked list |
Constructor()GetData()GetNextNode()SetNextNode() |
initialisesTheData to its parameter value, initialisesNextNode to a null value returns TheDatareturns NextNodetakes an object of type Node as a parameter and stores it inNextNode |
(a) (i) Write program code to declare the class Node and its constructor. 4 marks
Do not declare the other methods.
Use your programming language appropriate constructor.
If you are writing in Python, include attribute declarations using comments.
Save your program as Question3_J25 .
Copy and paste the program code into part 3(a)(i) in the evidence document.
(ii) Write program code for the two get methods. 3 marks
Save your program.
Copy and paste the program code into part 3(a)(ii) in the evidence document.
(iii) The method SetNextNode() takes an object of type Node as a parameter. The method stores the parameter in the attribute NextNode Write program code for SetNextNode() Save your program. 2 marks
Copy and paste the program code into part 3(a)(iii) in the evidence document.
| The class LinkedList stores the linked list. LinkedList | |
|---|---|
LinkedList |
LinkedList |
HeadNode : Node |
stores the first node in the linked list |
Constructor()InsertNode()RemoveNode()Traverse() |
initialisesHeadNode to a null valuecreates a new node using its integer parameter. Sets this node as the new head node and updates NextNodefinds the first node that contains its integer parameter and removes this node from the linked list concatenates and returns the integer data in each node in the linked list |
(i) Write program code to declare the class LinkedList and its constructor.
Do not declare the other methods.
Use your programming language appropriate constructor.
If you are writing in Python, include attribute declarations using comments.
Save your program.
Copy and paste the program code into part 3(b)(i) in the evidence document.
(ii) The method InsertNode() : 2 marks 4 marks
takes an integer as a parameter
creates a new node with the parameter as the integer data
uses the new node’s method
SetNextNode()to store the currentHeadNodeas the next nodereplaces
HeadNodewith the current node.
Write program code for InsertNode()
Save your program.
Copy and paste the program code into part 3(b)(ii) in the evidence document.
(iii) The method Traverse() concatenates the integer data from the nodes in the linked list, starting with the node stored in HeadNode . The method returns the final string with each integer data separated with a space. 3 marks
Write program code for Traverse()
Save your program.
Copy and paste the program code into part 3(b)(iii) in the evidence document.
(iv) The method RemoveNode() takes an integer parameter to search for and remove from the linked list. 6 marks
The method first checks if the linked list is empty. If the linked list is empty the method
returns FALSE
If the linked list is not empty, the integer data in HeadNode is compared to the parameter.
If it matches the parameter, HeadNode is changed to store the next node.
If the parameter does not match, the nodes are followed until either:
the node with matching integer data is found. This node is removed, the appropriate nodes updated and
TRUEreturnedor
none of the nodes contain matching integer data to the parameter. No nodes are removed and
FALSEis returned.
Write program code for RemoveNode()
Save your program.
Copy and paste the program code into part 3(b)(iv) in the evidence document.
(c) (i) The main program creates a new LinkedList object and uses the appropriate method 3 marks
to insert five nodes with the following integer data values in the order given:
10 20 30 40 50
The main program then:
calls
Traverse()removes the node containing the integer data
30usingRemoveNode()calls
Traverse()
Write program code for the main program.
Save your program.
Copy and paste the program code into part 3(c)(i) in the evidence document.
(ii) Test your program. 2 marks
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(c)(ii) in the evidence document.
Show mark scheme
3(a)(i) [4 marks]
1 mark each • Class header (and end) Node • declared as Integer, declared as TheData NextNode Node • Constructor header (and end) taking (min) 1 parameter … • … storing parameter to within constructor and storing null value to TheData TheData = NodeData NextNode = Nothing
3(a)(ii) [3 marks]
1 mark each • 1 get method header (and close) taking no parameters … • … returning correct value (without overwriting) • 2nd correct get method
3(a)(iii) [2 marks]
1 mark each • method header (and close) taking 1 parameter (of type SetNextNode() • … storing parameter in NextNode
3(b)(i) [2 marks]
1 mark each • Class header (and close) and constructor header with no parameter (and close) … LinkedList • … declaring as type and storing null value in constructor HeadNode Node HeadNode = Nothing
3(b)(ii) [4 marks]
1 mark each • method header (and close) taking one (integer) parameter InsertNode() • Creating new instance of with the parameter as the argument Node • Calling for new node with as parameter SetNextNode() HeadNode • Replacing with new node HeadNode
3(b)(iii) [3 marks]
1 mark each • method header (and close) with no parameter and returns created string Traverse() • Starts at head node and follows nodes using until no nodes left … GetNextNode() • … concatenates the data from each node and formats correctly
ReturnValue = ReturnValue & CurrentNode.GetData() & " " CurrentNode = CurrentNode.GetNextNode()
3(b)(iv) [6 marks]
1 mark each to max 6 • method header (and close) taking (integer) parameter and returning Boolean in all cases RemoveNode() • Checking if head node is null and returning FALSE • Checking if head node equals parameter and returning if true … TRUE • … and updating to HeadNode HeadNode.GetNextNode() • Following nodes comparing data from each node to parameter … • ... if found updating next node and returning TRUE • … if end of list returning FALSE
Return False HeadNode = HeadNode.GetNextNode() Return True If ((CurrentNode).GetNextNode()).GetData() = DataToRemove Then CurrentNode.SetNextNode(CurrentNode.GetNextNode().GetNextNode()) Found = True Else CurrentNode = CurrentNode.GetNextNode() End If
3(c)(i) [3 marks]
1 mark each • Creating new object LinkedList • Calling five times with correct data in correct order InsertNode() • Calling and calling and store/output the return value, before RemoveNode(30) Traverse() after Full marks can be awarded to students who may have stored and/or outputted the return value from the function call.
3(c)(ii) [2 marks]
1 mark each • Output of linked list with 50 40 30 20 10 • Output of 2nd linked list with 50 40 20 10
The following diagram shows an ordered binary tree.
(a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer. 4 marks
–1 is used to represent a null pointer.
Complete this linked list to represent the given binary tree.
RootPtr
(b) A user-defined record structure is used to store the nodes of the linked list in part (a). 4 marks
Complete the diagram, using your answer for part (a).
| Index | LeftPtr | Data | RightPtr |
|---|---|---|---|
| 0 | Red | ||
| 1 | Green | ||
| 2 | Yellow | ||
| 3 | Blue | ||
| 4 | Orange | ||
| 5 | Indigo | ||
| 6 | Violet | ||
| 7 |
(c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer. 4 marks
The following pseudocode represents a function that searches for an element in the array of records BinTree. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found.
Complete the pseudocode for the function.
FUNCTION SearchTree(Item : STRING)
NowPtr
WHILE NowPtr <> -1
IF ______ THEN
NowPtr BinTree[NowPtr].LeftPtr
ELSE
IF BinTree[NowPtr].Data < Item THEN
ELSE
RETURN NowPtr
ENDIF
ENDIF
ENDWHILE
RETURN NowPtr
ENDFUNCTION
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 4) MP1 Four additional nodes with correct data values MP2 Correct null pointers in all added nodes (6) with no extra null pointers where the arrow points to the next node MP3 Correct arrows to represent pointers joining parent nodes to child nodes MP4 All nodes in correct order and no extra data added to pointers. RootPtr RightPtr LeftPtr Data Red Green Yellow Orange -1 Blue -1 -1 Indigo -1 -1 -1 Violet -1
11(b) [4 marks]
One mark per mark point ( Max 4) Red Green MP1 Correct and rows Yellow Blue MP2 Correct and rows Orange Indigo Violet MP3 Correct , and rows FreePtr MP4 Correct with blank row 7 RootPt RightPt Index LeftPtr Data r r 0 0 1 Red 2 1 3 Green 4 2 6 Yellow -1 3 -1 Blue -1 4 5 Orange -1 5 -1 Indigo -1 FreePt 6 -1 Violet -1 r 7 7
11(c) [4 marks]
One mark for any correct row ( Max 4 ) FUNCTION SearchTree(Item : STRING) RETURNS INTEGER NowPtr RootPtr WHILE NowPtr <> -1 IF BinTree[NowPtr].Data > Item THEN NowPtr BinTree[NowPtr].LeftPtr ELSE IF BinTree[NowPtr].Data < Item THEN NowPtr BinTree[NowPtr].RightPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NowPtr ENDFUNCTION
This binary tree shows an ordered list of integers.
(a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer. 4 marks
−1 is used to represent a null pointer.
Complete this linked list to represent the given binary tree organisation.
RootPtr
(b) A 2D array is used to store the nodes of the linked list in part (a). 4 marks
Complete the diagram using your answer for part (a).
| Index | LeftPtr | Data | RightPtr |
|---|---|---|---|
| 0 | 25 | ||
| 1 | 4 | ||
| 2 | 36 | ||
| 3 | 1 | ||
| 4 | 16 | ||
| 5 | 64 | ||
| 6 | 9 | ||
| 7 | 49 | ||
| 8 |
(c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer. 4 marks
The following pseudocode represents a function that searches for an element in the array of records LinkList. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found.
Complete the pseudocode for the function.
FUNCTION SearchList(Item : INTEGER)
NullPtr −1
______ RootPtr
WHILE NowPtr <> NullPtr
IF LinkList[NowPtr].Data < Item THEN
NowPtr LinkList[NowPtr].RightPtr
ELSE
IF ______ THEN
NowPtr
ELSE
RETURN NowPtr
ENDIF
ENDIF
ENDWHILE
RETURN NullPtr
ENDFUNCTION
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 4) MP1 Five additional nodes with correct data values MP2 Correct null pointers in all nodes (7) – no extra null pointers where the arrow points to the next node MP3 Correct arrows to represent pointers joining parent nodes to child nodes – must come from the correct left or right pointer not the middle MP4 All nodes in correct order and no additional data in left/right pointer boxes. RootPtr LeftPtr Data RightPtr 25 4 -1 36 -1 1 -1 16 -1 64 -1 49 -1 -1 9 -1
11(b) [4 marks]
First eight rows of table ( Max 3 ) Three marks for all eight correct rows Two marks for six or seven correct rows One mark for three, four or five correct rows Last row of table and FreePtr ( Max 1 ) FreePtr One mark for correct with last row of table completely blank RootPt RightP Index LeftPtr Data r tr 0 0 1 25 2 1 3 4 4 2 -1 36 5 3 -1 1 -1 4 6 16 -1 5 7 64 -1 FreePt 6 -1 9 -1 r 8 7 -1 49 -1 8
11(c) [4 marks]
One mark for any correct row ( Max 4 ) FUNCTION SearchList(Item : INTEGER) RETURNS INTEGER NullPtr -1 NowPtr RootPtr WHILE NowPtr <> NullPtr IF LinkList[NowPtr].Data < Item THEN NowPtr LinkList[NowPtr].RightPtr ELSE IF LinkList[NowPtr].Data
Item THEN NowPtr LinkList[NowPtr].LeftPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NullPtr ENDFUNCTION
The following diagram shows an ordered binary tree.
(a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer. 4 marks
–1 is used to represent a null pointer.
Complete this linked list to represent the given binary tree.
RootPtr
(b) A user-defined record structure is used to store the nodes of the linked list in part (a). 4 marks
Complete the diagram, using your answer for part (a).
| Index | LeftPtr | Data | RightPtr |
|---|---|---|---|
| 0 | Red | ||
| 1 | Green | ||
| 2 | Yellow | ||
| 3 | Blue | ||
| 4 | Orange | ||
| 5 | Indigo | ||
| 6 | Violet | ||
| 7 |
(c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer. 4 marks
The following pseudocode represents a function that searches for an element in the array of records BinTree. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found.
Complete the pseudocode for the function.
FUNCTION SearchTree(Item : STRING)
NowPtr
WHILE NowPtr <> -1
IF ______ THEN
NowPtr BinTree[NowPtr].LeftPtr
ELSE
IF BinTree[NowPtr].Data < Item THEN
ELSE
RETURN NowPtr
ENDIF
ENDIF
ENDWHILE
RETURN NowPtr
ENDFUNCTION
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 4) MP1 Four additional nodes with correct data values MP2 Correct null pointers in all added nodes (6) with no extra null pointers where the arrow points to the next node MP3 Correct arrows to represent pointers joining parent nodes to child nodes MP4 All nodes in correct order and no extra data added to pointers. RootPtr RightPtr LeftPtr Data Red Green Yellow Orange -1 Blue -1 -1 Indigo -1 -1 -1 Violet -1
11(b) [4 marks]
One mark per mark point ( Max 4) Red Green MP1 Correct and rows Yellow Blue MP2 Correct and rows Orange Indigo Violet MP3 Correct , and rows FreePtr MP4 Correct with blank row 7 RootPt RightPt Index LeftPtr Data r r 0 0 1 Red 2 1 3 Green 4 2 6 Yellow -1 3 -1 Blue -1 4 5 Orange -1 5 -1 Indigo -1 FreePt 6 -1 Violet -1 r 7 7
11(c) [4 marks]
One mark for any correct row ( Max 4 ) FUNCTION SearchTree(Item : STRING) RETURNS INTEGER NowPtr RootPtr WHILE NowPtr <> -1 IF BinTree[NowPtr].Data > Item THEN NowPtr BinTree[NowPtr].LeftPtr ELSE IF BinTree[NowPtr].Data < Item THEN NowPtr BinTree[NowPtr].RightPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NowPtr ENDFUNCTION
A linked list stores positive integer data in a 2D array. The first dimension of the array stores the integer data. The second dimension of the array stores the pointer to the next node in the linked list.
A linked list node with no data is initialised with the integer –1 . These nodes are linked together as
an empty list. A pointer of –1 identifies that node as the last node.
The linked list can store 20 nodes.
The global 2D array LinkedList stores the linked list.
LinkedList is initialised as an empty list. The data in each node is initialised to –1 . Each node’s
pointer stores the index of the next node. The last node stores the pointer value –1, which indicates
it is the last node.
The global variable FirstEmpty stores the index of the first element in the empty list. This is the
first node in the empty linked list when it is initialised, which is index 0 .
The global variable FirstNode stores the index of the first element in the linked list. There is no
data in the linked list when it is initialised, so FirstNode is initialised to –1 .
This diagram shows the content of the initialised array.
FirstEmpty = 0
FirstNode = –1
|Index|Data|Pointer|
|---|---|---|
|`0`|`-1`|`1`|
|`1`|`-1`|`2`|
|`2`|`-1`|`3`|
|`3`|`-1`|`4`|
|`4`|`-1`|`5`|
||||
|`19`|<br>`-1`|<br>`-1`|
(a) Write program code for the main program to declare and initialise LinkedList, FirstNode and FirstEmpty . 2 marks
Save your program as Question3_N24 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The procedure InsertData() takes five positive integers as input from the user and inserts these into the linked list. 6 marks
Each data item is inserted at the front of the linked list.
| The table shows the steps | to follow depending on the state of the linked list: |
|---|---|
| Linked list state | Steps |
| not full | insert the data in the index pointed to byFirstEmptychange the pointer to the index pointed to by FirstNodechange the values of FirstNode andFirstEmpty |
| full | end the procedure |
Any node that is at the end of the linked list has a pointer of –1 .
Write program code for InsertData() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The procedure OutputLinkedList() outputs the data in the linked list in order by following the pointers from FirstNode .
(i) Write program code for OutputLinkedList() . 2 marks
Save your program.
Copy and paste the program code into part 3(c)(i) in the evidence document.
(ii) Amend the main program to call InsertData() and then OutputLinkedList() . 1 mark
Save your program.
Copy and paste the program code into part 3(c)(ii) in the evidence document.
(iii) Test your program with the test data: 1 mark
5 1 2 3 8
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 3(c)(iii) in the evidence document.
(d) The procedure RemoveData() removes a node from the linked list.
The procedure takes the data item to be removed from the linked list as a parameter.
The procedure checks each node in the linked list, starting with the node FirstNode, until it
finds the node to be removed. This node is added to the empty list, and pointers are changed
as appropriate. The procedure only removes the first occurrence of the parameter.
Assume that the data item being removed is in the linked list.
(i) Write program code for RemoveData() . 5 marks
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Amend the main program to: 1 mark
call
RemoveData()with the parameter 5output the word
"After"call
OutputLinkedList().
Save your program.
Copy and paste the program code into part 3(d)(ii) in the evidence document.
(iii) Test your program with both sets of given test data: 1 mark
Test data set 1: 5 6 8 9 5
Test data set 2: 10 7 8 5 6
Take a screenshot of each output.
Save your program.
Copy and paste the screenshot(s) into part 3(d)(iii) in the evidence document.
Show mark scheme
3(a)
Python LinkedList = [] #global FirstNode = -1 FirstEmpty = 0 for x in range(0, 19): LinkedList.append([-1, x + 1]) LinkedList[19][0] = -1 LinkedList[19][1] = -1 Java private static Integer[][] LinkedList = new Integer[20][2]; private static Integer FirstNode; private static Integer FirstEmpty; public static void main(String args[]){ FirstNode = -1; FirstEmpty = 0; for(Integer X = 0; X < 19; X++){ LinkedList[X][0] = -1; LinkedList[X][1] = X + 1; } LinkedList[19][0] = -1; LinkedList[19][1] = -1; }
3(b)
Java public static void InsertData(){ Integer NewItem; Integer CurrentPointer = 0; Integer PreviousPointer = 0; Scanner scanner = new Scanner(System.in); Integer NextEmpty; for(Integer X = 0; X < 5; X++){ System.out.println("Enter the next number"); NewItem = Integer.parseInt(scanner.nextLine()); if(FirstEmpty == -1){ X = 5; }else{ NextEmpty = LinkedList[FirstEmpty][1]; LinkedList[FirstEmpty][0] = NewItem; LinkedList[FirstEmpty][1] = FirstNode; FirstNode = FirstEmpty; FirstEmpty = NextEmpty; } } }
3(c)(i)
Java public static void OutputLinkedList(){ Integer CurrentPointer = FirstNode; Boolean Flag = true; while(Flag){ System.out.println(LinkedList[CurrentPointer][0]); CurrentPointer = LinkedList[CurrentPointer][1]; if(CurrentPointer == -1){Flag = false;} } }
3(c)(ii) [1 mark]
1 mark for calling then InsertData() OutputLinkedList() Python InsertData() OutputLinkedList() VB.NET InsertData() OutputLinkedList() Java InsertData(); OutputLinkedList();
3(c)(iii) [1 mark]
1 mark for inputs of 5 1 2 3 8 and output of 8 3 2 1 5
3(d)(i)
Java public static void RemoveData(Integer ItemToRemove){ Integer CurrentPointer = 0; Integer PreviousNode = 0; Integer NewFirst = 0; if(LinkedList[FirstNode][0] == ItemToRemove){ NewFirst = LinkedList[FirstNode][1]; LinkedList[FirstNode][1] = FirstEmpty; FirstEmpty = FirstNode; FirstNode = NewFirst; }else{ if (FirstNode != -1){ CurrentPointer = FirstNode; PreviousNode = -1; while(ItemToRemove != LinkedList[CurrentPointer][0] && CurrentPointer != -1){ PreviousNode = CurrentPointer; CurrentPointer = LinkedList[CurrentPointer][1]; } if(ItemToRemove == LinkedList[CurrentPointer][0]){ LinkedList[PreviousNode][1] = LinkedList[CurrentPointer][1]; LinkedList[CurrentPointer][0] = -1; LinkedList[CurrentPointer][1] = FirstEmpty; FirstEmpty = CurrentPointer; } } } }
3(d)(ii)
Java public static void main(String args[]){ FirstNode = -1; FirstEmpty = 0; for(Integer X = 0; X < 20; X++){ LinkedList[X][0] = -1; LinkedList[X][1] = X + 1; } InsertData(); OutputLinkedList(); RemoveData(5); System.out.println("After"); OutputLinkedList(); }
3(d)(iii) [1 mark]
1 mark for input and output. Test data 1: Input 5 6 8 9 5 ‘After’ Output: 9 8 6 5 Test data 2: Input 10 7 8 5 6 “After” Output: 6 8 7 10
A linked list stores positive integer data in a 2D array. The first dimension of the array stores the integer data. The second dimension of the array stores the pointer to the next node in the linked list.
A linked list node with no data is initialised with the integer –1 . These nodes are linked together as
an empty list. A pointer of –1 identifies that node as the last node.
The linked list can store 20 nodes.
The global 2D array LinkedList stores the linked list.
LinkedList is initialised as an empty list. The data in each node is initialised to –1 . Each node’s
pointer stores the index of the next node. The last node stores the pointer value –1, which indicates
it is the last node.
The global variable FirstEmpty stores the index of the first element in the empty list. This is the
first node in the empty linked list when it is initialised, which is index 0 .
The global variable FirstNode stores the index of the first element in the linked list. There is no
data in the linked list when it is initialised, so FirstNode is initialised to –1 .
This diagram shows the content of the initialised array.
FirstEmpty = 0
FirstNode = –1
|Index|Data|Pointer|
|---|---|---|
|`0`|`-1`|`1`|
|`1`|`-1`|`2`|
|`2`|`-1`|`3`|
|`3`|`-1`|`4`|
|`4`|`-1`|`5`|
||||
|`19`|<br>`-1`|<br>`-1`|
(a) Write program code for the main program to declare and initialise LinkedList, FirstNode and FirstEmpty . 2 marks
Save your program as Question3_N24 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The procedure InsertData() takes five positive integers as input from the user and inserts these into the linked list. 6 marks
Each data item is inserted at the front of the linked list.
| The table shows the steps | to follow depending on the state of the linked list: |
|---|---|
| Linked list state | Steps |
| not full | insert the data in the index pointed to byFirstEmptychange the pointer to the index pointed to by FirstNodechange the values of FirstNode andFirstEmpty |
| full | end the procedure |
Any node that is at the end of the linked list has a pointer of –1 .
Write program code for InsertData() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The procedure OutputLinkedList() outputs the data in the linked list in order by following the pointers from FirstNode .
(i) Write program code for OutputLinkedList() . 2 marks
Save your program.
Copy and paste the program code into part 3(c)(i) in the evidence document.
(ii) Amend the main program to call InsertData() and then OutputLinkedList() . 1 mark
Save your program.
Copy and paste the program code into part 3(c)(ii) in the evidence document.
(iii) Test your program with the test data: 1 mark
5 1 2 3 8
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 3(c)(iii) in the evidence document.
(d) The procedure RemoveData() removes a node from the linked list.
The procedure takes the data item to be removed from the linked list as a parameter.
The procedure checks each node in the linked list, starting with the node FirstNode, until it
finds the node to be removed. This node is added to the empty list, and pointers are changed
as appropriate. The procedure only removes the first occurrence of the parameter.
Assume that the data item being removed is in the linked list.
(i) Write program code for RemoveData() . 5 marks
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Amend the main program to: 1 mark
call
RemoveData()with the parameter 5output the word
"After"call
OutputLinkedList().
Save your program.
Copy and paste the program code into part 3(d)(ii) in the evidence document.
(iii) Test your program with both sets of given test data: 1 mark
Test data set 1: 5 6 8 9 5
Test data set 2: 10 7 8 5 6
Take a screenshot of each output.
Save your program.
Copy and paste the screenshot(s) into part 3(d)(iii) in the evidence document.
Show mark scheme
3(a)
Python LinkedList = [] #global FirstNode = -1 FirstEmpty = 0 for x in range(0, 19): LinkedList.append([-1, x + 1]) LinkedList[19][0] = -1 LinkedList[19][1] = -1 Java private static Integer[][] LinkedList = new Integer[20][2]; private static Integer FirstNode; private static Integer FirstEmpty; public static void main(String args[]){ FirstNode = -1; FirstEmpty = 0; for(Integer X = 0; X < 19; X++){ LinkedList[X][0] = -1; LinkedList[X][1] = X + 1; } LinkedList[19][0] = -1; LinkedList[19][1] = -1; }
3(b)
Java public static void InsertData(){ Integer NewItem; Integer CurrentPointer = 0; Integer PreviousPointer = 0; Scanner scanner = new Scanner(System.in); Integer NextEmpty; for(Integer X = 0; X < 5; X++){ System.out.println("Enter the next number"); NewItem = Integer.parseInt(scanner.nextLine()); if(FirstEmpty == -1){ X = 5; }else{ NextEmpty = LinkedList[FirstEmpty][1]; LinkedList[FirstEmpty][0] = NewItem; LinkedList[FirstEmpty][1] = FirstNode; FirstNode = FirstEmpty; FirstEmpty = NextEmpty; } } }
3(c)(i)
Java public static void OutputLinkedList(){ Integer CurrentPointer = FirstNode; Boolean Flag = true; while(Flag){ System.out.println(LinkedList[CurrentPointer][0]); CurrentPointer = LinkedList[CurrentPointer][1]; if(CurrentPointer == -1){Flag = false;} } }
3(c)(ii) [1 mark]
1 mark for calling then InsertData() OutputLinkedList() Python InsertData() OutputLinkedList() VB.NET InsertData() OutputLinkedList() Java InsertData(); OutputLinkedList();
3(c)(iii) [1 mark]
1 mark for inputs of 5 1 2 3 8 and output of 8 3 2 1 5
3(d)(i)
Java public static void RemoveData(Integer ItemToRemove){ Integer CurrentPointer = 0; Integer PreviousNode = 0; Integer NewFirst = 0; if(LinkedList[FirstNode][0] == ItemToRemove){ NewFirst = LinkedList[FirstNode][1]; LinkedList[FirstNode][1] = FirstEmpty; FirstEmpty = FirstNode; FirstNode = NewFirst; }else{ if (FirstNode != -1){ CurrentPointer = FirstNode; PreviousNode = -1; while(ItemToRemove != LinkedList[CurrentPointer][0] && CurrentPointer != -1){ PreviousNode = CurrentPointer; CurrentPointer = LinkedList[CurrentPointer][1]; } if(ItemToRemove == LinkedList[CurrentPointer][0]){ LinkedList[PreviousNode][1] = LinkedList[CurrentPointer][1]; LinkedList[CurrentPointer][0] = -1; LinkedList[CurrentPointer][1] = FirstEmpty; FirstEmpty = CurrentPointer; } } } }
3(d)(ii)
Java public static void main(String args[]){ FirstNode = -1; FirstEmpty = 0; for(Integer X = 0; X < 20; X++){ LinkedList[X][0] = -1; LinkedList[X][1] = X + 1; } InsertData(); OutputLinkedList(); RemoveData(5); System.out.println("After"); OutputLinkedList(); }
3(d)(iii) [1 mark]
1 mark for input and output. Test data 1: Input 5 6 8 9 5 ‘After’ Output: 9 8 6 5 Test data 2: Input 10 7 8 5 6 “After” Output: 6 8 7 10
10 (a) State a condition that must be true for an array to be searchable for a binary search. 1 mark
(b) Complete the given pseudocode to find an item in a 1D array Names of type STRING using a binary search. 5 marks
DECLARE Names : ARRAY[1:100000] OF STRING
DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE CurrentItem : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList 1
# ←
EndOfList 100000
# ←
OUTPUT "Which name do you wish to find? "
INPUT ToFind
NotInList FALSE
# ←
WHILE ______ AND
CurrentItem (TopOfList + EndOfList) DIV 2
# ←
IF ______ THEN
Found TRUE
# ←
ELSE
IF TopOfList >= EndOfList THEN
ELSE
IF ToFind > Names[CurrentItem] THEN
ELSE
EndOfList CurrentItem – 1
# ←
ENDIF
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", CurrentItem, " in array"
ELSE
OUTPUT "Item not in array"
ENDIF
Show mark scheme
10(a) [1 mark]
mark The elements are sorted according to the compare function / in ascending / descending order.
10(b)
IF Found = TRUE THEN OUTPUT "Item found at position ", CurrentItem, " in array" OUTPUT "Item not in array"
10(c) [2 marks]
mark from Big O for a binary search is O(Log 2 n). Big O notation is used to indicate the time/space complexity of an algorithm. mark from The time taken to complete the search increases logarithmically as the number of search items increases linearly The time taken to complete the search increases linearly as the number of search items increases exponentially As the search field is repeatedly getting smaller, the number of comparisons made before the item is found, or the number of items runs out, is relatively small.
(a) Complete the pseudocode to find an item in a 1D array Widgets of type STRING, using a linear search. 4 marks
DECLARE Widgets : ARRAY[1:50000] OF STRING
DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE Count : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList 1
EndOfList 50000
OUTPUT "Enter the name of the item you wish to find "
INPUT ToFind
…………………………………………………………………………………………………………………………………
NotInList FALSE
Count TopOfList
WHILE …………………………………………………………… AND ………………………………………………………………………
IF ……………………………………………………………………………………………………………………………… THEN
Found TRUE
ENDIF
Count Count + 1
IF …………………………………………………………………………………………………………………………… THEN
NotInList TRUE
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", Count - 1, " in array"
ELSE
OUTPUT "Item not in array"
ENDIF
(b) Compare the methods used by the linear and binary search algorithms to find an item in an array. Refer to Big O notation in your answer. 4 marks
Show mark scheme
8(a) [4 marks]
mark for each correctly completed line ( Max 4 ) DECLARE Widgets : ARRAY[1:50000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE Count : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList 1 EndOfList 50000 OUTPUT "Enter the name of the item you wish to find " INPUT ToFind Found FALSE NotInList FALSE Count TopOfList WHILE Found = FALSE AND NotInList = FALSE // Count <= EndOfList IF ToFind = Widgets[Count] // Widgets[Count] = ToFind THEN Found TRUE ENDIF Count Count + 1 IF Found = FALSE AND Count > EndOfList THEN NotInList TRUE ENDIF ENDWHILE IF Found = TRUE THEN OUTPUT "Item found at position ", Count - 1, " in array" OUTPUT "Item not in array" ENDIF
8(b) [4 marks]
mark per mark point ( Max 3 ) Linear search sequentially checks each element of the array / list. … until the matching element is found, or the end of the array / list is reached. Binary search finds the mid-point of an array/list and determines which side contains the item to be found … it discards the half of the array/list not containing the search item // … it finds the position of a target value within an array / list by repeatedly halving the target search field. The binary search requires the elements to be sorted // The linear search does not require the elements to be sorted. The binary search will usually do many fewer comparisons of records/iterations against the target than a linear search before it finds its target. Linear search starts at the beginning of the array/list and binary search starts in the middle of the array/list. mark per mark point ( Max 2 ) Big O for binary search is O (Log 2 n) Big O for linear search is O (n) Big O notation is used to indicate the time / space complexity of an algorithm
10 (a) State a condition that must be true for an array to be searchable for a binary search. 1 mark
(b) Complete the given pseudocode to find an item in a 1D array Names of type STRING using a binary search. 5 marks
DECLARE Names : ARRAY[1:100000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE CurrentItem : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList ← 1 EndOfList ← 100000
OUTPUT "Which name do you wish to find? " INPUT ToFind
NotInList ← FALSE
WHILE ______ AND CurrentItem ← (TopOfList + EndOfList) DIV 2
IF ______ THEN Found ← TRUE ELSE IF TopOfList >= EndOfList THEN
ELSE IF ToFind > Names[CurrentItem] THEN
ELSE EndOfList ← CurrentItem – 1 ENDIF ENDIF ENDIF ENDWHILE IF Found = TRUE THEN OUTPUT "Item found at position ", CurrentItem, " in array" ELSE OUTPUT "Item not in array" ENDIF
Show mark scheme
10(a) [1 mark]
mark The elements are sorted according to the compare function / in ascending / descending order.
10(b)
IF Found = TRUE THEN OUTPUT "Item found at position ", CurrentItem, " in array" OUTPUT "Item not in array"
10(c) [2 marks]
mark from Big O for a binary search is O(Log 2 n). Big O notation is used to indicate the time/space complexity of an algorithm. mark from The time taken to complete the search increases logarithmically as the number of search items increases linearly The time taken to complete the search increases linearly as the number of search items increases exponentially As the search field is repeatedly getting smaller, the number of comparisons made before the item is found, or the number of items runs out, is relatively small.
A program needs to take integer numbers as input, sort the numbers and then search for a specific number.
(a) The integer numbers will be stored in the global 1D array, DataStored, with space for up to 20 integers. 1 mark
The global variable NumberItems stores the quantity of items the array contains.
Write program code to declare DataStored and NumberItems .
Save your program as Question1_J24 .
Copy and paste the program code into part 1(a) in the evidence document.
(b) The procedure Initialise() : 5 marks
prompts the user to input the quantity of numbers the user would like to enter
reads the input and validates it is between 1 and 20 (inclusive)
prompts the user to input each number and stores each number in
DataStored.
Write program code for Initialise() .
Save your program.
Copy and paste the program code into part 1(b) in the evidence document.
Show mark scheme
1(a) [1 mark]
1 mark for: Declaration of (global) array with identifier DataStored (Integer and 20 spaces) and NumberItems (Integer) public static Integer[] DataStored = new Integer[20]; public static Integer NumberItems= 0; VB.NET Dim DataStored(19) As Integer Dim NumberStored As Integer = 0 Python global DataStored #integer global NumberItems #Integer 20 items
1(b)
Python def Initialise(): global DataStored global NumberItems Valid = False while(Valid == False): NumberItems = int(input("How many numbers will you enter?")) #loop until < 20 if NumberItems > 0 and NumberItems< 21: Valid = True for Count in range(0, NumberItems): DataStored.append(int(input("Enter number")))
1(c)(i) [2 marks]
1 mark each: Storing 0 in NumberItems and then calling Initialise() Outputting all contents of array DataStored public static Integer NumberItems= 0; Initialise(); for(Integer X = 0; X < NumberItems; X++){ System.out.println(DataStored[X]); VB.NET NumberItems = 0 Initialise() For X = 0 To NumberItems - 1 Console.WriteLine(DataStored(X)) Python NumberItems = 0 Initialise() print(DataStored)
1(c)(ii) [2 marks]
1 mark each Output showing quantity entered twice (30 and 5) with first being invalid Array output 3 9 4 1 2
1(d)(i)
Python def BubbleSort(): global DataStored global NumberItems for Count in range(0, NumberItems): for Count2 in range(0, NumberItems-1): if DataStored[Count2] > DataStored[Count]: DataStored[Count2], DataStored[Count] = DataStored[Count], DataStored[Count2]
1(d)(ii) [1 mark]
1 mark for calling BubbleSort() and outputting array contents after VB.NET BubbleSort() For X = 0 To NumberStored - 1 Console.WriteLine(DataStored(X)) e.g. Java BubbleSort(); for(Integer X = 0; X < NumberItems; X++){ System.out.println(DataStored[X]); e.g. Python BubbleSort() print(DataStored)
1(d)(iii) [1 mark]
1 mark for screenshot showing the inputs and the values in the correct order
1(e)(i)
VB.NET Function BinarySearch(DataToFind) Dim First As Integer = 0 Dim Last As Integer = NumberItems Dim MidValue As Integer While (First <= Last) MidValue = (First + Last) / 2 If DataToFind = DataStored(MidValue) Then Return MidValue End If If DataToFind < DataStored(MidValue) Then Last = MidValue - 1 Else First = MidValue + 1 End If End While Return -1 End Function Python def BinarySearch(DataToFind): global DataStored global NumberItems First = 0 Last= NumberItems while(First <= Last): MidValue = int((First + Last) / 2) if DataToFind == DataStored[MidValue]: return MidValue if DataToFind < DataStored[MidValue]: Last = MidValue - 1 else: First = MidValue + 1 return -1
1(e)(ii) [3 marks]
1 mark each: Taking number as input … calling BinarySearch with input Outputting value returned Scanner scanner = new Scanner(System.in); System.out.println("Enter a number to find"); Integer Search = Integer.parseInt(scanner.nextLine()); System.out.println(BinarySearch(Search)); VB.NET Console.WriteLine("Enter a number to find") Dim Search As Integer = Console.ReadLine() Console.WriteLine(BinarySearch(Search)) Python Search = int(input("Enter a number to find")) print(BinarySearch(Search))
1(e)(iii) [2 marks]
1 mark for each test Test 1 – Accept found in index 16
A program reads data from the user and stores the data that is valid in a linear queue.
The queue is stored as a global 1D array, QueueData, of string values. The array needs space for
20 elements.
The global variable QueueHead stores the index of the first element in the queue.
The global variable QueueTail stores the index of the last element in the queue.
(a) The main program initialises all the elements in QueueData to a suitable null value, QueueHead to −1 and QueueTail to −1. 1 mark
Write program code for the main program.
Save your program as Question3_J24 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The function Enqueue() takes the data to insert into the queue as a parameter. 4 marks
If the queue is not full, it inserts the parameter in the queue, updates the appropriate pointer(s)
and returns TRUE . If the queue is full, it returns FALSE .
Write program code for Enqueue() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The function Dequeue() returns "false" if the queue is empty. If the queue is not empty, it returns the next item in the queue and updates the appropriate pointer(s). 3 marks
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The string values to be stored in the queue are 7 characters long. The first 6 characters are digits and the 7th character is a check digit. The check digit is calculated from the first 6 digits using this algorithm:
multiply the digits in position 0, position 2 and position 4 by 1
multiply the digits in position 1, position 3 and position 5 by 3
calculate the sum of the products (add together the results from all of the multiplications)
divide the sum of the products by 10 and round the result down to the nearest integer to get the check digit
if the check digit equals 10 then it is replaced with '
X'.
Example:
Data is 954123
| Character position | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Digit | 9 | 5 | 4 | 1 | 2 | 3 |
| Multiplier | 1 | 3 | 1 | 3 | 1 | 3 |
| Product | 9 | 15 | 4 |
3 | 2 | 9 |
Sum of products = 9 + 15 + 4 + 3 + 2 + 9 = 42
Divide sum of products by 10: 42 / 10 = 4 (rounded down)
The check digit = 4. This is inserted into character position 6.
The data including the check digit is: 9541234
A 7‑character string is valid if the 7th character matches the check digit for that data. For example, the data 9541235 is invalid because the 7th character (5) does not match the check digit for 954123.
(i) The subroutine StoreItems() takes ten 7‑character strings as input from the user and uses the check digit to validate each input. 6 marks
Each valid input has the check digit removed and is stored in the queue using
Enqueue() .
An appropriate message is output if the item is inserted. An appropriate message is
output if the queue is already full.
Invalid inputs are not stored in the queue.
The subroutine counts and outputs the number of invalid items that were entered.
StoreItems() can be a procedure or a function as appropriate.
Write program code for StoreItems() .
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Write program code to amend the main program to: 1 mark
call
StoreItems()call
Dequeue()output a suitable message if the queue was empty
output the returned value if the queue was not empty.
Save your program.
Copy and paste the program code into part 3(d)(ii) in the evidence document.
(iii) Test the program with the following inputs in the order given: 2 marks
999999X
1251484
5500212
0033585
9845788
6666666
3258746
8111022
7568557
0012353
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(d)(iii) in the evidence document.
Show mark scheme
3(a) [1 mark]
1 mark each QueueData as 1D (string) array initialised to 20 null values and QueueHead initialised to -1 , QueueTail initialised to -1 class Queue{ public static String[] QueueData = new String[20]; public static Integer QueueHead; public static Integer QueueTail; public static void main(String args[]){ for(Integer x = 0; x < 20; x++){ QueueData[x] = ""; } QueueHead = -1; QueueTail = -1; } VB.NET Dim QueueData(0 To 20) As String Dim QueueHead As Integer = -1 Dim QueueTail As Integer = -1 Sub Main(args As String()) For x = 0 To 19 QueueData(x) = "" Next End Sub Python global QueueData global QueueHead global QueueTail QueueData = [] for x in range(0, 20): QueueData.append("") QueueHead = -1 QueueTail = -1
3(b)
Python def Enqueue(DataToInsert): global QueueData global QueueHead global QueueTail if QueueTail == 19: return False elif QueueHead == -1: QueueHead = 0 QueueTail = QueueTail + 1 QueueData.append(DataToInsert) return True
3(c)
Python def Dequeue(): global QueueData global QueueHead global QueueTail if QueueHead < 0 or QueueHead > 20 or QueueHead > QueueTail: return False else: QueueHead = QueueHead + 1 return QueueData[QueueHead-1]
3(d)(i)
Python def StoreItems(): global QueueData global QueueHead global QueueTail Count = 0 for X in range(0, 10): Data = input("Enter data") Total= int(Data[0]) + int(Data[1]) * 3 + int(Data[2]) + int(Data[3]) * 3 + int(Data[4]) + int(Data[5]) * 3 Total = int(Total / 10) if((Total == 10 and Data[6] == "X") or (Total == int(Data[6]))): Result = Enqueue(Data[0:6]) if(Result == True): print("Inserted item") else: print("Queue full") else: Count = Count + 1 print("There were", Count,"Invalid items")
3(d)(ii)
Python QueueData = [] for x in range(0, 20): QueueData.append("") QueueHead = -1 QueueTail = -1 StoreItems() Value = Dequeue() if Value == False: print("No data items") else: print("Item code", Value)
3(d)(iii) [2 marks]
1 mark each Data input of 10 values and output a message saying there are 4 invalid items 999999 output
A binary tree stores data in ascending order. For example:
A computer program stores integers in a binary tree in ascending order. The program uses Object‑Oriented Programming (OOP).
The binary tree is stored as a 1D array of nodes. Each node contains a left pointer, a data value and a right pointer.
| The class Node stores the data about a node. | |
|---|---|
Node |
Node |
LeftPointer : INTEGERData : INTEGERRightPointer : INTEGER |
stores the index of the node to the left in the binary tree stores the node’s data stores the index of the node to the right in the binary tree |
Constructor()GetLeft()GetRight()GetData()SetLeft()SetRight()SetData() |
initialisesData to its parameter valueinitialises LeftPointer andRightPointer to −1returns the left pointer returns the right pointer returns the data value assigns the parameter to the left pointer assigns the parameter to the right pointer assigns the parameter to the data |
(a) (i) Write program code to declare the class Node and its constructor. 4 marks
Do not declare the other methods.
Use the appropriate constructor for your programming language.
If you are writing in Python, include attribute declarations using comments.
Save your program as Question2_J24 .
Copy and paste the program code into part 2(a)(i) in the evidence document.
(ii) The get methods GetLeft(), GetRight() and GetData() each return the relevant attribute. 3 marks
Write program code for the three get methods.
Save your program.
Copy and paste the program code into part 2(a)(ii) in the evidence document.
(iii) The set methods SetLeft(), SetRight() and SetData() each take a parameter and then store this in the relevant attribute. 3 marks
Write program code for the three set methods.
Save your program.
Copy and paste the program code into part 2(a)(iii) in the evidence document.
| The class TreeClass stores the data about the binary tree. | |
|---|---|
TreeClass |
TreeClass |
Tree[0:19] : NodeFirstNode : INTEGERNumberNodes : INTEGER |
an array of 20 elements of typeNodestores the index of the first node in the tree stores the quantity of nodes in the tree |
Constructor()InsertNode()OutputTree() |
initialisesFirstNode to −1 andNumberNodes to 0initialises each element in Tree to aNode object with thedata value of −1 takes a Node object as a parameter, inserts it in the arrayand updates the pointer for its parent node outputs the left pointer, data and right pointer of each node in Tree |
Nodes cannot be deleted from this tree.
(i) Write program code to declare the class TreeClass and its constructor. 4 marks
Do not declare the other methods.
Use the appropriate constructor for your programming language.
If you are writing in Python, include attribute declarations using comments.
Save your program.
Copy and paste the program code into part 2(b)(i) in the evidence document.
(ii) The method InsertNode() takes a Node object, NewNode, as a parameter and inserts it into the array Tree . 6 marks
InsertNode() first checks if the tree is empty.
If the tree is empty, InsertNode() :
stores
NewNodein the arrayTreeat indexNumberNodesincrements
NumberNodesstores 0 in
FirstNode.
If the tree is not empty, InsertNode() :
stores
NewNodein the arrayTreeat indexNumberNodesaccesses the data in the array
Treeat indexFirstNodeand compares it to the data inNewNoderepeatedly follows the pointers until the correct position for
NewNodeis foundonce the position is found,
InsertNode()sets the left or right pointer of its parent nodeincrements
NumberNodes.
Write program code for InsertNode() .
Save your program.
Copy and paste the program code into part 2(b)(ii) in the evidence document.
(iii) The method OutputTree() outputs the left pointer, the data and the right pointer for each node that has been inserted into the tree. The outputs are in the order they are saved in the array. 4 marks
If there are no nodes in the array, the procedure outputs ‘No nodes’.
Write program code for OutputTree() .
Save your program.
Copy and paste the program code into part 2(b)(iii) in the evidence document.
(c) (i) The main program declares an instance of TreeClass with the identifier TheTree . 1 mark
Write program code for the main program.
Save your program.
Copy and paste the program code into part 2(c)(i) in the evidence document.
(ii) The main program inserts the following integers into the binary tree in the order given: 4 marks
The main program then calls the method OutputTree() .
Write program code to amend the main program.
Save your program.
Copy and paste the program code into part 2(c)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 2(c)(iii) in the evidence document.
Show mark scheme
2(a)(i)
Python class Node(): def init (self, PData): self. LeftPointer = -1 #int self. Data = PData #int self. RightPointer = -1 #int
2(a)(ii)
def GetRight(self): return self. RightPointer def GetData(self): return self. Data
2(a)(iii)
self. RightPointer = NewRight def SetData(self, NewData): self. Data = NewData
2(b)(i)
For x = 0 To 19 Tree(x) = New Node(-1) Next End Sub End Class Python class TreeClass(): def init (self): self. Tree = [] #type node 20 spaces self. FirstNode = -1 #int self. NumberNodes = 0 #int for x in range(20): self. Tree.append(Node(-1))
2(b)(ii)
NodeAccess = self. Tree[NodeAccess].GetLeft() Direction = "left" elif NewNode.GetData() > self. Tree[NodeAccess].GetData(): NodeAccess = self. Tree[NodeAccess].GetRight() Direction = "right" if(Direction == "left"): self. Tree[Previous].SetLeft(self. NumberNodes) else: self. Tree[Previous].SetRight(self. NumberNodes) self. NumberNodes = self. NumberNodes + 1
2(b)(iii)
Python def OutputTree(self): if self. NumberNodes == 0: print("No nodes") else: for x in range(0, self. NumberNodes): print(self. Tree[x].GetLeft(), " ", self. Tree[x].GetData(), " ",self. Tree[x].GetRight())
2(c)(i) [1 mark]
1 mark for Instance of TreeClass created with identifier TheTree public static void main(String args[]){ TreeClass TheTree = new TreeClass(); VB.NET Sub Main(args As String()) Dim TheTree As TreeClass = New TreeClass() End Sub Python TheTree = TreeClass()
2(c)(ii)
Python TheTree = TreeClass() TheTree.InsertNode(Node(10)) TheTree.InsertNode(Node(11)) TheTree.InsertNode(Node(5)) TheTree.InsertNode(Node(1)) TheTree.InsertNode(Node(20)) TheTree.InsertNode(Node(7)) TheTree.InsertNode(Node(15)) TheTree.OutputTree()
2(c)(iii) [1 mark]
1 mark for correct output e.g.
A program sorts an array of integers and searches the array for a particular value.
(a) The array of integers, NumberArray, stores the following data in the order given: 1 mark
100 85 644 22 15 8 1
The array is declared and initialised local to the main program.
Write program code to declare and initialise the array.
Save your program as Question3_J24 .
Copy and paste the program code into part 3(a) in the evidence document. (b) (i) The following recursive pseudocode function sorts the array into ascending order using 4 marks an insertion sort and returns the sorted array.
DECLARE LastItem : INTEGER
DECLARE CheckItem : INTEGER
DECLARE LoopAgain : BOOLEAN
FUNCTION RecursiveInsertion(IntegerArray : ARRAY[] OF INTEGER,
NumberElements : INTEGER) RETURNS ARRAY[] OF INTEGER
IF NumberElements <= 1 THEN
RETURN IntegerArray
ELSE
CALL RecursiveInsertion(IntegerArray, NumberElements - 1)
LastItem IntegerArray[NumberElements - 1]
CheckItem NumberElements - 2
ENDIF
LoopAgain TRUE
IF CheckItem < 0 THEN
LoopAgain FALSE
ELSE
IF IntegerArray[CheckItem] < LastItem THEN
LoopAgain FALSE
ENDIF
ENDIF
WHILE LoopAgain
IntegerArray[CheckItem + 1] IntegerArray[CheckItem]
CheckItem CheckItem - 1
IF CheckItem < 0 THEN
LoopAgain FALSE
ELSE
IF IntegerArray[CheckItem] < LastItem THEN
LoopAgain FALSE
ENDIF
ENDIF
ENDWHILE
IntegerArray[CheckItem + 1] LastItem
RETURN IntegerArray
ENDFUNCTION
Write the program code for the pseudocode function RecursiveInsertion() .
Save your program.
Copy and paste the program code into part 3(b)(i) in the evidence document.
(ii) Amend the main program to: 2 marks
call
RecursiveInsertion()with the initialised arrayNumberArrayand the number of elements as parametersoutput the word ‘Recursive’
output the content of the returned array.
Save your program.
Copy and paste the program code into part 3(b)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(b)(iii) in the evidence document.
(c) The function RecursiveInsertion() can be changed to use iteration instead of recursion.
(i) Write program code for the function IterativeInsertion() to perform the same processes as RecursiveInsertion() but using iteration instead of recursion. 4 marks
Save your program.
Copy and paste the program code into part 3(c)(i) in the evidence document.
(ii) Write program code to amend the main program to also: 1 mark
call
IterativeInsertion()with the original initialised arrayNumberArrayoutput the word ‘iterative’
output the content of the returned array.
Save your program.
Copy and paste the program code into part 3(c)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(c)(iii) in the evidence document.
(d) The recursive function BinarySearch() takes the parameters:
IntegerArray- an array of integersFirst- the index of the first array elementLast- the index of the last array elementToFind- an integer to search for in the array.
The function uses recursion to perform a binary search for ToFind in IntegerArray .
The function returns the index where ToFind is stored or returns −1 if ToFind is not in the
array.
(i) Write program code for the recursive function BinarySearch() . 6 marks
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Write program code to amend the main program to: 2 marks
call
BinarySearch()with the sorted array and the integer 644 as the search valueoutput ‘Not found’ if 644 is not found in the array
output the index if 644 is found in the array.
Save your program.
Copy and paste the program code into part 3(d)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(d)(iii) in the evidence document.
Show mark scheme
3(a) [1 mark]
1 mark each NumberArray declared (in main) with the 7 correct values in order (integer) 100 85 644 22 15 8 1 public static void main(String args[]){ Integer[] NumberArray = new Integer[7]; NumberArray[0] = 100; NumberArray[1] = 85; NumberArray[2] = 644; NumberArray[3] = 22; NumberArray[4] = 15; NumberArray[5] = 8; NumberArray[6] = 1; VB.NET Sub Main(args As String()) Dim NumberArray(7) As Integer NumberArray(0) = 100 NumberArray(1) = 85 NumberArray(2) = 644 NumberArray(3) = 22 NumberArray(4) = 15 NumberArray(5) = 8 NumberArray(6) = 1 EndSub Python NumberArray = [100, 85, 644, 22, 15, 8, 1]
3(b)(i)
LoopAgain = False End If End While IntegerArray(CheckItem + 1) = LastItem Return IntegerArray End Function Python def RecursiveInsertion(IntegerArray, NumberElements): if NumberElements <= 1: return IntegerArray RecursiveInsertion(IntegerArray,NumberElements - 1) LastItem = IntegerArray[NumberElements - 1] CheckItem = NumberElements - 2 LoopAgain = True if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False while (LoopAgain): IntegerArray[CheckItem + 1] = IntegerArray[CheckItem] CheckItem = CheckItem - 1 if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False IntegerArray[CheckItem + 1] = LastItem return IntegerArray
3(b)(ii) [2 marks]
1 mark each Calling RecursiveInsertion() with array and number of elements (7 or length) Outputting ‘recursive’ and then each element in returned array Integer[] SortedArray = new Integer[7]; SortedArray = RecursiveInsertion(NumberArray, 7); System.out.println("Recursive"); for(Integer x = 0; x < 7; x++){ System.out.println(SortedArray[x]); VB.NET SortedArray = RecursiveInsertion(NumberArray, 7) Console.WriteLine("Recursive") For x = 0 To 6 Console.WriteLine(SortedArray(x)) Next x Python SortedArray = RecursiveInsertion(NumberArray, len(NumberArray)) print("Recursive", SortedArray)
3(b)(iii) [1 mark]
1 mark for screenshot with: Recursive
3(c)(i)
Python def IterativeInsertion(IntegerArray, NumberElements): while NumberElements > 0: LastItem = IntegerArray[NumberElements - 1] CheckItem = NumberElements - 2 LoopAgain = True if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False while(LoopAgain): IntegerArray[CheckItem + 1] = IntegerArray[CheckItem] CheckItem = CheckItem - 1 if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False IntegerArray[CheckItem + 1] = LastItem NumberElements = NumberElements - 1 return IntegerArray
3(c)(ii) [1 mark]
1 mark each Calling IterativeInsertion() with original unsorted array and outputting ‘iterative’ and the content of the returned array Integer[] Sorted2Array = new Integer[7]; Sorted2Array = IterativeInsertion(NumberArray, 7); System.out.println("iterative"); for(Integer x = 0; x < 7; x++){ System.out.println(Sorted2Array[x]); VB.NET Sorted2Array = IterativeInsertion(NumberArray, 7) Console.WriteLine("iterative") For x = 0 To 6 Console.WriteLine(Sorted2Array(x)) Next x Python Sorted2Array = IterativeInsertion(NumberArray, len(NumberArray)) print("iterative", Sorted2Array)
3(c)(iii) [1 mark]
1 mark for Recursive 1 8 15 22 85 100 644 Iterative 1 8 15 22 85 100 644
3(d)(i)
Return -1 Else Middle = (Last + First) \ 2 If IntegerArray(Middle) = ToFind Then Return Middle ElseIf IntegerArray(Middle) > ToFind Then Return BinarySearch(IntegerArray, First, Middle - 1, ToFind) Else Return BinarySearch(IntegerArray, Middle + 1, Last, ToFind) End If End If End Function Python def BinarySearch(IntegerArray, First, Last, ToFind): if First > Last: return -1 else: Middle = int((Last + First) / 2) if IntegerArray[Middle] == ToFind: return Middle elif IntegerArray[Middle] > ToFind: return BinarySearch(IntegerArray, First, Middle - 1, ToFind) else: return BinarySearch(IntegerArray, Middle + 1, Last, ToFind)
3(d)(ii) [2 marks]
1 mark each Calling BinarySearch function with sorted array, 0, 6/len(array)–1, 644 as parameters Checking return value and outputting ‘Not found’ if –1 and index otherwise Position = BinarySearch(Sorted2Array, 0, 6, 644); if(Position == -1){ System.out.println("Not found"); }else{ System.out.println(Position); VB.NET Position = BinarySearch(Sorted2Array, 0, 6, 644) If Position = -1 Then Console.WriteLine("Not found") Console.WriteLine(Position) End If Python Position = BinarySearch(Sorted2Array, 0, len(NumberArray)-1, 644) if Position == -1: print("Not found") else: print(Position)
3(d)(iii) [1 mark]
1 mark for screenshot showing found in index 6 e.g.
A program needs to take integer numbers as input, sort the numbers and then search for a specific number.
(a) The integer numbers will be stored in the global 1D array, DataStored, with space for up to 20 integers. 1 mark
The global variable NumberItems stores the quantity of items the array contains.
Write program code to declare DataStored and NumberItems .
Save your program as Question1_J24 .
Copy and paste the program code into part 1(a) in the evidence document.
(b) The procedure Initialise() : 5 marks
prompts the user to input the quantity of numbers the user would like to enter
reads the input and validates it is between 1 and 20 (inclusive)
prompts the user to input each number and stores each number in
DataStored.
Write program code for Initialise() .
Save your program.
Copy and paste the program code into part 1(b) in the evidence document.
Show mark scheme
1(a) [1 mark]
1 mark for: Declaration of (global) array with identifier DataStored (Integer and 20 spaces) and NumberItems (Integer) public static Integer[] DataStored = new Integer[20]; public static Integer NumberItems= 0; VB.NET Dim DataStored(19) As Integer Dim NumberStored As Integer = 0 Python global DataStored #integer global NumberItems #Integer 20 items
1(b)
Python def Initialise(): global DataStored global NumberItems Valid = False while(Valid == False): NumberItems = int(input("How many numbers will you enter?")) #loop until < 20 if NumberItems > 0 and NumberItems< 21: Valid = True for Count in range(0, NumberItems): DataStored.append(int(input("Enter number")))
1(c)(i) [2 marks]
1 mark each: Storing 0 in NumberItems and then calling Initialise() Outputting all contents of array DataStored public static Integer NumberItems= 0; Initialise(); for(Integer X = 0; X < NumberItems; X++){ System.out.println(DataStored[X]); VB.NET NumberItems = 0 Initialise() For X = 0 To NumberItems - 1 Console.WriteLine(DataStored(X)) Python NumberItems = 0 Initialise() print(DataStored)
1(c)(ii) [2 marks]
1 mark each Output showing quantity entered twice (30 and 5) with first being invalid Array output 3 9 4 1 2
1(d)(i)
Python def BubbleSort(): global DataStored global NumberItems for Count in range(0, NumberItems): for Count2 in range(0, NumberItems-1): if DataStored[Count2] > DataStored[Count]: DataStored[Count2], DataStored[Count] = DataStored[Count], DataStored[Count2]
1(d)(ii) [1 mark]
1 mark for calling BubbleSort() and outputting array contents after VB.NET BubbleSort() For X = 0 To NumberStored - 1 Console.WriteLine(DataStored(X)) e.g. Java BubbleSort(); for(Integer X = 0; X < NumberItems; X++){ System.out.println(DataStored[X]); e.g. Python BubbleSort() print(DataStored)
1(d)(iii) [1 mark]
1 mark for screenshot showing the inputs and the values in the correct order
1(e)(i)
VB.NET Function BinarySearch(DataToFind) Dim First As Integer = 0 Dim Last As Integer = NumberItems Dim MidValue As Integer While (First <= Last) MidValue = (First + Last) / 2 If DataToFind = DataStored(MidValue) Then Return MidValue End If If DataToFind < DataStored(MidValue) Then Last = MidValue - 1 Else First = MidValue + 1 End If End While Return -1 End Function Python def BinarySearch(DataToFind): global DataStored global NumberItems First = 0 Last= NumberItems while(First <= Last): MidValue = int((First + Last) / 2) if DataToFind == DataStored[MidValue]: return MidValue if DataToFind < DataStored[MidValue]: Last = MidValue - 1 else: First = MidValue + 1 return -1
1(e)(ii) [3 marks]
1 mark each: Taking number as input … calling BinarySearch with input Outputting value returned Scanner scanner = new Scanner(System.in); System.out.println("Enter a number to find"); Integer Search = Integer.parseInt(scanner.nextLine()); System.out.println(BinarySearch(Search)); VB.NET Console.WriteLine("Enter a number to find") Dim Search As Integer = Console.ReadLine() Console.WriteLine(BinarySearch(Search)) Python Search = int(input("Enter a number to find")) print(BinarySearch(Search))
1(e)(iii) [2 marks]
1 mark for each test Test 1 – Accept found in index 16
A program reads data from the user and stores the data that is valid in a linear queue.
The queue is stored as a global 1D array, QueueData, of string values. The array needs space for
20 elements.
The global variable QueueHead stores the index of the first element in the queue.
The global variable QueueTail stores the index of the last element in the queue.
(a) The main program initialises all the elements in QueueData to a suitable null value, QueueHead to −1 and QueueTail to −1. 1 mark
Write program code for the main program.
Save your program as Question3_J24 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The function Enqueue() takes the data to insert into the queue as a parameter. 4 marks
If the queue is not full, it inserts the parameter in the queue, updates the appropriate pointer(s)
and returns TRUE . If the queue is full, it returns FALSE .
Write program code for Enqueue() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The function Dequeue() returns "false" if the queue is empty. If the queue is not empty, it returns the next item in the queue and updates the appropriate pointer(s). 3 marks
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The string values to be stored in the queue are 7 characters long. The first 6 characters are digits and the 7th character is a check digit. The check digit is calculated from the first 6 digits using this algorithm:
multiply the digits in position 0, position 2 and position 4 by 1
multiply the digits in position 1, position 3 and position 5 by 3
calculate the sum of the products (add together the results from all of the multiplications)
divide the sum of the products by 10 and round the result down to the nearest integer to get the check digit
if the check digit equals 10 then it is replaced with '
X'.
Example:
Data is 954123
| Character position | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Digit | 9 | 5 | 4 | 1 | 2 | 3 |
| Multiplier | 1 | 3 | 1 | 3 | 1 | 3 |
| Product | 9 | 15 | 4 |
3 | 2 | 9 |
Sum of products = 9 + 15 + 4 + 3 + 2 + 9 = 42
Divide sum of products by 10: 42 / 10 = 4 (rounded down)
The check digit = 4. This is inserted into character position 6.
The data including the check digit is: 9541234
A 7‑character string is valid if the 7th character matches the check digit for that data. For example, the data 9541235 is invalid because the 7th character (5) does not match the check digit for 954123.
(i) The subroutine StoreItems() takes ten 7‑character strings as input from the user and uses the check digit to validate each input. 6 marks
Each valid input has the check digit removed and is stored in the queue using
Enqueue() .
An appropriate message is output if the item is inserted. An appropriate message is
output if the queue is already full.
Invalid inputs are not stored in the queue.
The subroutine counts and outputs the number of invalid items that were entered.
StoreItems() can be a procedure or a function as appropriate.
Write program code for StoreItems() .
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Write program code to amend the main program to: 1 mark
call
StoreItems()call
Dequeue()output a suitable message if the queue was empty
output the returned value if the queue was not empty.
Save your program.
Copy and paste the program code into part 3(d)(ii) in the evidence document.
(iii) Test the program with the following inputs in the order given: 2 marks
999999X
1251484
5500212
0033585
9845788
6666666
3258746
8111022
7568557
0012353
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(d)(iii) in the evidence document.
Show mark scheme
3(a) [1 mark]
1 mark each QueueData as 1D (string) array initialised to 20 null values and QueueHead initialised to -1 , QueueTail initialised to -1 class Queue{ public static String[] QueueData = new String[20]; public static Integer QueueHead; public static Integer QueueTail; public static void main(String args[]){ for(Integer x = 0; x < 20; x++){ QueueData[x] = ""; } QueueHead = -1; QueueTail = -1; } VB.NET Dim QueueData(0 To 20) As String Dim QueueHead As Integer = -1 Dim QueueTail As Integer = -1 Sub Main(args As String()) For x = 0 To 19 QueueData(x) = "" Next End Sub Python global QueueData global QueueHead global QueueTail QueueData = [] for x in range(0, 20): QueueData.append("") QueueHead = -1 QueueTail = -1
3(b)
Python def Enqueue(DataToInsert): global QueueData global QueueHead global QueueTail if QueueTail == 19: return False elif QueueHead == -1: QueueHead = 0 QueueTail = QueueTail + 1 QueueData.append(DataToInsert) return True
3(c)
Python def Dequeue(): global QueueData global QueueHead global QueueTail if QueueHead < 0 or QueueHead > 20 or QueueHead > QueueTail: return False else: QueueHead = QueueHead + 1 return QueueData[QueueHead-1]
3(d)(i)
Python def StoreItems(): global QueueData global QueueHead global QueueTail Count = 0 for X in range(0, 10): Data = input("Enter data") Total= int(Data[0]) + int(Data[1]) * 3 + int(Data[2]) + int(Data[3]) * 3 + int(Data[4]) + int(Data[5]) * 3 Total = int(Total / 10) if((Total == 10 and Data[6] == "X") or (Total == int(Data[6]))): Result = Enqueue(Data[0:6]) if(Result == True): print("Inserted item") else: print("Queue full") else: Count = Count + 1 print("There were", Count,"Invalid items")
3(d)(ii)
Python QueueData = [] for x in range(0, 20): QueueData.append("") QueueHead = -1 QueueTail = -1 StoreItems() Value = Dequeue() if Value == False: print("No data items") else: print("Item code", Value)
3(d)(iii) [2 marks]
1 mark each Data input of 10 values and output a message saying there are 4 invalid items 999999 output
A stack is to be set up using the information in the table.
| Identifier | Data type | Description |
|---|---|---|
BasePointer |
INTEGER |
points to the bottom of the stack |
TopPointer |
INTEGER |
points to the top of the stack |
Stack |
REAL |
1D array to implement the stack |
A constant, with identifier Capacity, limits the size of the stack to 25 items.
(a) Write the pseudocode for the required declarations. 3 marks
(b) Complete the pseudocode function Pop() to pop an item from Stack . 5 marks
// popping an item from the stack
FUNCTION Pop()
DECLARE Item : REAL
Item 0
______ BasePointer THEN
Item
TopPointer
ELSE
OUTPUT "The stack is empty – error"
ENDIF
ENDFUNCTION
Show mark scheme
10(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 Correct constant declaration MP2 Two correct variable declarations MP3 Correct array declaration Example answer: CONSTANT Capacity = 25 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:25] OF REAL
10(b) [5 marks]
One mark for each correctly completed line ( Max 5 ) // popping an item from the stack FUNCTION Pop() RETURNS REAL DECLARE Item : REAL Item 0 IF TopPointer >= BasePointer THEN Item Stack[TopPointer] TopPointer TopPointer – 1 ELSE OUTPUT "The stack is empty – error" ENDIF RETURN Item ENDFUNCTION
10(c) [2 marks]
One mark per mark point ( Max 2 ) MP1 A queue is a first in first out / FIFO data structure and a stack is a first in last out / FILO / LIFO data structure // Data is removed from a queue in the order it is received and removed from a stack in the reverse order to which it is received MP2 Both ADTs can vary in size / are of indeterminate length MP3 Data is popped and pushed (onto/from a stack) at the same end but it is enqueued and dequeued (to/from a queue) at different/opposite ends // a queue has two accessible ends and a stack has only one MP4 A stack has only one moveable pointer whereas a queue has two.
(b) Justify the use of a linked list instead of an array to implement a stack. 2 marks
(c) Explain how a compiler makes use of a stack when translating recursive programming code. 4 marks
Show mark scheme
9(a)(i) [2 marks]
Two marks for all five empty boxes correct One mark for any three or four empty boxes correct Identifier Data type Description BasePointer INTEGER Points to the bottom of the stack TopPointer INTEGER Points to the top of the stack Stack REAL List of decimal numbers stored in the stack
9(a)(ii) [5 marks]
One mark for each correctly completed line ( Max 5 ) CONSTANT MaxSize = 40 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:40] OF REAL // initialisation of stack PROCEDURE Initialise() BasePointer 1 TopPointer 0 ENDPROCEDURE // adding an item to the stack PROCEDURE Push(NewItem) IF TopPointer < MaxSize THEN TopPointer TopPointer + 1 Stack[TopPointer] NewItem ENDIF ENDPROCEDURE
9(b) [2 marks]
One mark for linked list and one mark for array ( Max 2 ) Linked list MP1 A linked list is a dynamic data structure / not restricted in size MP2 Has greater freedom to expand or contract by adding or removing nodes as necessary MP3 Allows more efficient editing using pointers (instead of moving the data). Array MP4 An array is a static data structure1 generally fixed in size MP5 When the array is full, the stack cannot be extended any further.
9(c) [4 marks]
One mark per mark point ( Max 1 ) MP1 The compiler must produce object code to One mark per mark point ( Max 3 ) MP2 …push return addresses / values of local variables onto a stack MP3 …with each recursive call // … to set up winding MP4 …pop return addresses / values of local variables off the stack … MP5 …after the base case is reached // … to implement unwinding.
A stack is to be set up using the information in the table.
| Identifier | Data type | Description |
|---|---|---|
BasePointer |
INTEGER |
points to the bottom of the stack |
TopPointer |
INTEGER |
points to the top of the stack |
Stack |
REAL |
1D array to implement the stack |
A constant, with identifier Capacity, limits the size of the stack to 25 items.
(a) Write the pseudocode for the required declarations. 3 marks
(b) Complete the pseudocode function Pop() to pop an item from Stack . 5 marks
// popping an item from the stack
FUNCTION Pop()
DECLARE Item : REAL
Item 0
______ BasePointer THEN
Item
TopPointer
ELSE
OUTPUT "The stack is empty – error"
ENDIF
ENDFUNCTION
Show mark scheme
10(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 Correct constant declaration MP2 Two correct variable declarations MP3 Correct array declaration Example answer: CONSTANT Capacity = 25 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:25] OF REAL
10(b) [5 marks]
One mark for each correctly completed line ( Max 5 ) // popping an item from the stack FUNCTION Pop() RETURNS REAL DECLARE Item : REAL Item 0 IF TopPointer >= BasePointer THEN Item Stack[TopPointer] TopPointer TopPointer – 1 ELSE OUTPUT "The stack is empty – error" ENDIF RETURN Item ENDFUNCTION
10(c) [2 marks]
One mark per mark point ( Max 2 ) MP1 A queue is a first in first out / FIFO data structure and a stack is a first in last out / FILO / LIFO data structure // Data is removed from a queue in the order it is received and removed from a stack in the reverse order to which it is received MP2 Both ADTs can vary in size / are of indeterminate length MP3 Data is popped and pushed (onto/from a stack) at the same end but it is enqueued and dequeued (to/from a queue) at different/opposite ends // a queue has two accessible ends and a stack has only one MP4 A stack has only one moveable pointer whereas a queue has two.
A linear queue is implemented using the 1D array, Queue . The index of the first element in the
array is 0.
(a) (i) Write program code to declare: 2 marks
Queue- a global array with space to store 50 IDs of type stringHeadPointer- a global variable to point to the first element in the queue, initialised to −1TailPointer- a global variable to point to the next available space in the queue, initialised to 0.
Save your program as Question2_N23 .
Copy and paste the program code into part 2(a)(i) in the evidence document.
(ii) The procedure Enqueue() takes a string parameter. 4 marks
If the queue is full, the procedure outputs a suitable message. If the queue is not full, the procedure inserts the parameter into the queue and updates the relevant pointer(s).
Write program code for Enqueue() .
Save your program.
Copy and paste the program code into part 2(a)(ii) in the evidence document.
(iii) The function Dequeue() checks if the queue is empty. 4 marks
If the queue is empty, the function outputs a suitable message and returns the string
"Empty" .
If the queue is not empty, the function returns the first element in the queue and updates
the relevant pointer(s).
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 2(a)(iii) in the evidence document.
(b) A shop sells computer games. Each game has a unique identifier (ID) of string data type. 6 marks
The text file QueueData.txt contains a list of game IDs.
The procedure ReadData() reads the data from the text file and inserts each item of data
into the array Queue .
Write program code for the procedure ReadData() .
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) Some game IDs appear in the text file more than once.
The program needs to total the number of times each game ID appears in the text file.
The record structure RecordData has the following fields:
ID- a string to store the game IDTotal- an integer to store the total number of times that game ID appears in the text file.
(i) Write program code to declare the record structure RecordData . 2 marks
If you are writing in Python, include attribute declarations as comments.
Save your program.
Copy and paste the program code into part 2(c)(i) in the evidence document.
(ii) The global 1D array Records stores up to 50 items of type RecordData . 2 marks
The global variable NumberRecords stores the number of records currently in the array
Records and is initialised to 0.
Write program code to declare Records and NumberRecords .
If you are writing in Python, include attribute declarations as comments.
Save your program.
Copy and paste the program code into part 2(c)(ii) in the evidence document.
(iii) The pseudocode algorithm for the procedure TotalData() : 5 marks
uses
Dequeue()to remove an ID from the queuechecks whether a
RecordDatawith the returned ID exists inRecordsincrements the total for that ID in the record if the ID already exists
creates a new record and stores it in
Recordsif the ID does not exist.
PROCEDURE TotalData()
DECLARE DataAccessed : STRING
DECLARE Flag : BOOLEAN
DataAccessed Dequeue()
# ←
Flag FALSE
# ←
IF NumberRecords = 0 THEN
Records[NumberRecords].ID DataAccessed
# ←
Records[NumberRecords].Total 1
# ←
Flag TRUE
# ←
NumberRecords NumberRecords + 1
# ←
ELSE
FOR X 0 TO NumberRecords - 1
# ←
IF Records[X].ID = DataAccessed THEN
Records[X].Total Records[X].Total + 1
# ←
Flag TRUE
# ←
ENDIF
NEXT X
ENDIF
IF Flag = FALSE THEN
Records[NumberRecords].ID DataAccessed
# ←
Records[NumberRecords].Total 1
# ←
NumberRecords NumberRecords + 1
# ←
ENDIF
ENDPROCEDURE
Write program code for the procedure TotalData() .
Save your program.
Copy and paste the program code into part 2(c)(iii) in the evidence document.
(d) The procedure OutputRecords() outputs the ID and total of each record in Records in the format: 1 mark
ID 1234 Total 4
Write program code for OutputRecords() .
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) The main program needs to:
call
ReadData()call
TotalData()for each element in the queuecall
OutputRecords().
(i) Write program code for the main program. 2 marks
Save your program.
Copy and paste the program code into part 2(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(e)(ii) in the evidence document.
Show mark scheme
2(a)(i) [2 marks]
One mark each • (Global) array with identifier with (minimum) 50 elements (of type string) Queue • (integer) initialised to 0, (integer) initialised to -1 TailPointer HeadPointer Example program code: Java public static String[] Queue = new String[50]; public static Integer HeadPointer = -1; public static Integer TailPointer = 0; VB.NET Dim Queue(50) As String Dim HeadPointer As Integer Dim TailPointer As Integer Sub Main(args As String()) HeadPointer = -1 TailPointer = 0 End Sub Python global Queue #string 50 elements global HeadPointer global TailPointer #main Queue = [] HeadPointer = -1 TailPointer = 0
2(a)(ii)
Python def Enqueue(Data): global TailPointer global HeadPointer global Queue if TailPointer == 50: print("Queue full") else: Queue.append(Data) TailPointer +=1 if HeadPointer == -1: HeadPointer = 0
2(a)(iii)
Python def Dequeue(): global Queue global HeadPointer if HeadPointer == -1 or HeadPointer == TailPointer: print("Queue empty") return "Empty" else: HeadPointer +=1 return Queue[HeadPointer - 1]
2(b)
DataReader.Close() Catch ex As Exception Console.WriteLine("No file") End Try End Sub Python def ReadData(): try: DataFile = open("QueueData.txt") for Line in DataFile: Enqueue(Line.strip()) DataFile.close() except IOError: print("No file")
2(c)(i)
self. ID = Value def GetID(self): return self. ID def SetTotal(self, Value): self. Total = Value def GetTotal(self): return self. Total
2(c)(ii) [2 marks]
One mark each • (global) 1D Array named of type Records RecordData • (global) declared as integer and initialised to 0 NumberRecords Example program code: Java public static RecordData[] Records = new RecordData[50]; public static Integer NumberRecords = 0; VB.NET Dim Records(49) As RecordData Dim NumberRecords As Integer Sub Main(args As String()) NumberRecords = 0 End Sub Python #main Records = [] #50 elements of type RecordData NumberRecords = 0
2(c)(iii)
Flag = True else: for X in range(0, NumberRecords): if(Records[X].GetID() == DataAccessed): Records[X].SetTotal(Records[X].GetTotal() + 1) Flag = True if Flag == False: Records.append(RecordData(DataAccessed, 1)) NumberRecords += 1
2(d) [1 mark]
One mark each • Looping through all array elements and outputting ID and total in correct format
System.out.println("ID ", Records[X].ID + " Total " + Records[X].Total); Console.WriteLine("ID " & Records(X).ID & " Total " & Records(X).Total) print("ID", Records[X].GetID(), " Total ", Records[X].GetTotal())
2(e)(i)
Python #main Queue = [] Records = [] HeadPointer = 0 TailPointer = 0 ReadData() NumberRecords = 0 while HeadPointer != TailPointer: TotalData() OutputRecords()
2(e)(ii) [1 mark]
One mark for screenshot e.g.
A program stores lower-case letters in two stacks.
One stack stores vowels (a, e, i, o, u) and one stack stores consonants (letters that are not vowels).
Each stack is implemented as a 1D array.
(a) (i) Write program code to declare two 1D global arrays: StackVowel and StackConsonant . 2 marks
Each array needs to store up to 100 letters. The index of the first element in each array is 0.
If you are writing in Python, include declarations using comments.
Save your program as Question1_N23 .
Copy and paste the program code into part 1(a)(i) in the evidence document.
(ii) The global variable VowelTop is a pointer that stores the index of the next free space in StackVowel . 1 mark
The global variable ConsonantTop is a pointer that stores the index of the next free
space in StackConsonant .
VowelTop and ConsonantTop are both initialised to 0.
Write program code to declare and initialise the two variables.
If you are writing in Python, include declarations using comments.
Save your program.
Copy and paste the program code into part 1(a)(ii) in the evidence document.
Show mark scheme
1(a)(i) [2 marks]
One mark each • Two arrays with correct identifiers of type string/character • Each has 100 elements Example program code: Java public static String[] StackVowel = new String[100]; public static String[] StackConsonant = new String[100]; VB.NET Dim StackVowel(0 To 99) As Char Dim StackConsonant(0 To 99) As Char Python StackVowel = [] #string 100 StackConsonant = [] #string 100
1(a)(ii) [1 mark]
One mark for • Declaring both variables as type integer global and initialised to 0 Example program code: Java public static Integer VowelTop = 0; public static Integer ConsonantTop = 0; VB.NET Dim VowelTop As Integer = 0 Dim ConsonantTop As Integer = 0 Python global VowelTop #integer global ConsonantTop #integer #main VowelTop = 0 ConsonantTop = 0
1(b)(i)
VB.NET Sub PushData(Letter As Char) If Letter = "a" Or Letter = "e" Or Letter = "i" Or Letter = "o" Or Letter = "u" Then If VowelTop = 100 Then Console.WriteLine("Vowel stack full") Else StackVowel(VowelTop) = Letter VowelTop += 1 End If Else If ConsonantTop = 100 Then Console.WriteLine("Consonant stack full") Else StackConsonant(ConsonantTop) = Letter ConsonantTop += 1 End If End If End Sub Python def PushData(Letter): global VowelTop global ConsonantTop if Letter == "a" or Letter == "e" or Letter == "i" or Letter == "o" or Letter == "u": if VowelTop == 100: print("Vowel stack full") else: StackVowel.append(Letter) VowelTop = VowelTop + 1 else: if ConsonantTop == 100: print("Consonant stack full") else: StackConsonant.append(Letter) ConsonantTop = ConsonantTop + 1
1(b)(ii)
Console.WriteLine("File not found") End Try End Sub Python def ReadData(): try: DataFile = open("StackData.txt") for Line in DataFile: PushData(Line.strip()) DataFile.close() except: print("File not found")
1(c)
global VowelTop global ConsonantTop if ConsonantTop - 1 >= 0: ConsonantTop = ConsonantTop - 1 DataToReturn = StackConsonant[ConsonantTop] del StackConsonant[-1] return DataToReturn else: return "No data"
1(d)(i)
DataAccessed = PopConsonant() if DataAccessed != "No data": Letters = Letters + DataAccessed Flag = True else: print("No consonants left") print(Letters)
1(d)(ii) [1 mark]
One mark showing input in order vowel, cons, cons, vowel, vowel. Output is then e.g.
A linear queue is implemented using the 1D array, Queue . The index of the first element in the
array is 0.
(a) (i) Write program code to declare: 2 marks
Queue- a global array with space to store 50 IDs of type stringHeadPointer- a global variable to point to the first element in the queue, initialised to −1TailPointer- a global variable to point to the next available space in the queue, initialised to 0.
Save your program as Question2_N23 .
Copy and paste the program code into part 2(a)(i) in the evidence document.
(ii) The procedure Enqueue() takes a string parameter. 4 marks
If the queue is full, the procedure outputs a suitable message. If the queue is not full, the procedure inserts the parameter into the queue and updates the relevant pointer(s).
Write program code for Enqueue() .
Save your program.
Copy and paste the program code into part 2(a)(ii) in the evidence document.
(iii) The function Dequeue() checks if the queue is empty. 4 marks
If the queue is empty, the function outputs a suitable message and returns the string
"Empty" .
If the queue is not empty, the function returns the first element in the queue and updates
the relevant pointer(s).
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 2(a)(iii) in the evidence document.
(b) A shop sells computer games. Each game has a unique identifier (ID) of string data type. 6 marks
The text file QueueData.txt contains a list of game IDs.
The procedure ReadData() reads the data from the text file and inserts each item of data
into the array Queue .
Write program code for the procedure ReadData() .
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) Some game IDs appear in the text file more than once.
The program needs to total the number of times each game ID appears in the text file.
The record structure RecordData has the following fields:
ID- a string to store the game IDTotal- an integer to store the total number of times that game ID appears in the text file.
(i) Write program code to declare the record structure RecordData . 2 marks
If you are writing in Python, include attribute declarations as comments.
Save your program.
Copy and paste the program code into part 2(c)(i) in the evidence document.
(ii) The global 1D array Records stores up to 50 items of type RecordData . 2 marks
The global variable NumberRecords stores the number of records currently in the array
Records and is initialised to 0.
Write program code to declare Records and NumberRecords .
If you are writing in Python, include attribute declarations as comments.
Save your program.
Copy and paste the program code into part 2(c)(ii) in the evidence document.
(iii) The pseudocode algorithm for the procedure TotalData() : 5 marks
uses
Dequeue()to remove an ID from the queuechecks whether a
RecordDatawith the returned ID exists inRecordsincrements the total for that ID in the record if the ID already exists
creates a new record and stores it in
Recordsif the ID does not exist.
PROCEDURE TotalData()
DECLARE DataAccessed : STRING
DECLARE Flag : BOOLEAN
DataAccessed Dequeue()
# ←
Flag FALSE
# ←
IF NumberRecords = 0 THEN
Records[NumberRecords].ID DataAccessed
# ←
Records[NumberRecords].Total 1
# ←
Flag TRUE
# ←
NumberRecords NumberRecords + 1
# ←
ELSE
FOR X 0 TO NumberRecords - 1
# ←
IF Records[X].ID = DataAccessed THEN
Records[X].Total Records[X].Total + 1
# ←
Flag TRUE
# ←
ENDIF
NEXT X
ENDIF
IF Flag = FALSE THEN
Records[NumberRecords].ID DataAccessed
# ←
Records[NumberRecords].Total 1
# ←
NumberRecords NumberRecords + 1
# ←
ENDIF
ENDPROCEDURE
Write program code for the procedure TotalData() .
Save your program.
Copy and paste the program code into part 2(c)(iii) in the evidence document.
(d) The procedure OutputRecords() outputs the ID and total of each record in Records in the format: 1 mark
ID 1234 Total 4
Write program code for OutputRecords() .
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) The main program needs to:
call
ReadData()call
TotalData()for each element in the queuecall
OutputRecords().
(i) Write program code for the main program. 2 marks
Save your program.
Copy and paste the program code into part 2(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(e)(ii) in the evidence document.
Show mark scheme
2(a)(i) [2 marks]
One mark each • (Global) array with identifier with (minimum) 50 elements (of type string) Queue • (integer) initialised to 0, (integer) initialised to -1 TailPointer HeadPointer Example program code: Java public static String[] Queue = new String[50]; public static Integer HeadPointer = -1; public static Integer TailPointer = 0; VB.NET Dim Queue(50) As String Dim HeadPointer As Integer Dim TailPointer As Integer Sub Main(args As String()) HeadPointer = -1 TailPointer = 0 End Sub Python global Queue #string 50 elements global HeadPointer global TailPointer #main Queue = [] HeadPointer = -1 TailPointer = 0
2(a)(ii)
Python def Enqueue(Data): global TailPointer global HeadPointer global Queue if TailPointer == 50: print("Queue full") else: Queue.append(Data) TailPointer +=1 if HeadPointer == -1: HeadPointer = 0
2(a)(iii)
Python def Dequeue(): global Queue global HeadPointer if HeadPointer == -1 or HeadPointer == TailPointer: print("Queue empty") return "Empty" else: HeadPointer +=1 return Queue[HeadPointer - 1]
2(b)
DataReader.Close() Catch ex As Exception Console.WriteLine("No file") End Try End Sub Python def ReadData(): try: DataFile = open("QueueData.txt") for Line in DataFile: Enqueue(Line.strip()) DataFile.close() except IOError: print("No file")
2(c)(i)
self. ID = Value def GetID(self): return self. ID def SetTotal(self, Value): self. Total = Value def GetTotal(self): return self. Total
2(c)(ii) [2 marks]
One mark each • (global) 1D Array named of type Records RecordData • (global) declared as integer and initialised to 0 NumberRecords Example program code: Java public static RecordData[] Records = new RecordData[50]; public static Integer NumberRecords = 0; VB.NET Dim Records(49) As RecordData Dim NumberRecords As Integer Sub Main(args As String()) NumberRecords = 0 End Sub Python #main Records = [] #50 elements of type RecordData NumberRecords = 0
2(c)(iii)
Flag = True else: for X in range(0, NumberRecords): if(Records[X].GetID() == DataAccessed): Records[X].SetTotal(Records[X].GetTotal() + 1) Flag = True if Flag == False: Records.append(RecordData(DataAccessed, 1)) NumberRecords += 1
2(d) [1 mark]
One mark each • Looping through all array elements and outputting ID and total in correct format
System.out.println("ID ", Records[X].ID + " Total " + Records[X].Total); Console.WriteLine("ID " & Records(X).ID & " Total " & Records(X).Total) print("ID", Records[X].GetID(), " Total ", Records[X].GetTotal())
2(e)(i)
Python #main Queue = [] Records = [] HeadPointer = 0 TailPointer = 0 ReadData() NumberRecords = 0 while HeadPointer != TailPointer: TotalData() OutputRecords()
2(e)(ii) [1 mark]
One mark for screenshot e.g.
(a) Draw one line from each machine learning category to its most appropriate description. 4 marks
Machine learning category Description
simulates the data-processing capabilities of the human brain to make decisions
Supervised learning
Reinforcement learning
Deep learning
Unsupervised learning
enables learning by mapping an input to an output based on example input– output pairs
enables information related to errors produced by the neural network to be transmitted
enables learning in an interactive environment by trial and error using its own experiences
enables learning by allowing the process to discover patterns on its own that were previously undetected
(b) Describe the purpose of both the A* algorithm and Dijkstra’s algorithm. 2 marks
Show mark scheme
2(a)
One mark for each correct line connecting a machine learning technique to its most appropriate description ( Max 4 ). Machine learning category Description simulates the data processing capabilities of the human brain to make decisions Supervised learning enables learning by mapping an input to an output based on example input- output pairs Reinforcement learning enables information related to errors produced by the neural network to be transmitted Deep learning enables learning in an interactive environment by trial and error using its own experiences Unsupervised learning enables learning by allowing the process to discover patterns on its own that were previously undetected
2(b) [2 marks]
One mark per mark point ( Max 2 ) to find the optimal / shortest / most cost-effective route … between two nodes in a … based on distance / cost / time.
(b) Complete the following pseudocode for the function Dequeue to remove the front item from the queue. 4 marks
FUNCTION Dequeue RETURNS STRING
DECLARE Item : STRING
______ > 0 THEN
Item ←
IF Length = 0 THEN
CALL Initialise // reset the pointers
ELSE
IF FrontPointer > MaxSize THEN
______ ← 1
ENDIF
ENDIF
ELSE
OUTPUT "The print queue was empty – error!"
Item ← ""
ENDIF
RETURN Item
ENDFUNCTION
(c) Explain how a new element can be added to the queue if it is implemented using two stacks. 4 marks 2 marks
12 (a) Describe what is meant by recursion.
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 3 ) correctly defined constant correctly defined array three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize - 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER
11(b) [4 marks]
One mark for each correctly completed line ( Max 4 ) FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length
0 THEN Item Queue[FrontPointer] FrontPointer FrontPointer + 1 Length Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer 1 ENDIF ENDIF ELSE OUTPUT " The print queue was empty – error " Item "" ENDIF RETURN Item ENDFUNCTION
11(c)
One mark per mark point ( Max 4 ) MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1.
(b) Complete the Karnaugh map (K‑map) for the given truth table. 2 marks
AB
CD
(c) Draw loop(s) around appropriate group(s) in the K‑map to produce an optimal sum‑of‑products. 2 marks
(d) Write the Boolean logic expression from your answer to part (c) as a simplified sum‑of‑products. 2 marks
Z =
(e) Use Boolean algebra to give your answer to part (d) in its simplest form. 1 mark
Z = [1]
10 (a) State one category of machine learning.
(b) Calculate the path that takes the shortest time to travel from the Begin node to the End node, using the A* algorithm. 5 marks 2 marks
Show your working in the table provided.
The first two rows have already been completed.
| Start node | Destination node |
Cost from start node (g) |
Heuristic (h) |
Total (f = g + h) |
|---|---|---|---|---|
| Begin | Begin | 0 | 12 | 12 |
| Begin | A | 5 | 8 | 13 |
Final path 11 (a) The pseudocode shown represents a queue Abstract Data Type (ADT) with procedures for initialisation and to add new items. It is incomplete.
CONSTANT MaxLength = 50
DECLARE FrontPointer : INTEGER
DECLARE RearPointer : INTEGER
DECLARE Length : INTEGER
DECLARE Queue : ARRAY[0 : MaxLength – 1] OF STRING
// initialisation of queue
PROCEDURE Initialise
FrontPointer ‑1
______ 0
ENDPROCEDURE
// adding a new item to the queue
PROCEDURE Enqueue(NewItem : STRING)
IF ______ THEN
RearPointer
IF RearPointer > MaxLength – 1 THEN
RearPointer 0
ENDIF
Length Length + 1
ENDIF
ENDPROCEDURE
| (i) Study the pseudoc | code and insert th | he identifiers to complete this table. |
|---|---|---|
| Identifier | Data type | Description |
STRING |
An array to store the contents of the queue. | |
INTEGER |
Points to the last item of the queue. | |
INTEGER |
Indicates the number of items in the queue. | |
INTEGER |
Points to the first item of the queue. |
(ii) Complete the given pseudocode. [5]
(b) Explain the reasons why a queue ADT works better than a stack ADT in organising print jobs. 3 marks
Show mark scheme
11(a)(i) [5 marks]
One mark for every two correct identifiers (Max 2) Identifier Data type Description Queue STRING An array to store the contents of the queue. RearPointer INTEGER Points to the last term of the queue. Length INTEGER Indicates the number of items in the queue. FrontPointer INTEGER Points to the first term of the queue.
11(a)(ii)
One mark for each correctly completed line ( Max 5 ) CONSTANT MaxLength = 50 DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER DECLARE Queue : ARRAY[0:MaxLength – 1] OF STRING // Initialisation of queue PROCEDURE Initialise FrontPointer -1 RearPointer -1 Length 0 ENDPROCEDURE // Adding a new item to the queue PROCEDURE Enqueue(NewItem : STRING) IF Length < MaxLength THEN // IF Length <= MaxLength - 1 THEN RearPointer RearPointer + 1 IF RearPointer > MaxLength – 1 THEN RearPointer 0 ENDIF Queue[RearPointer] NewItem Length Length + 1 ENDIF ENDPROCEDURE
11(b) [3 marks]
One mark per mark point ( Max 3 ) Print jobs are expected to be actioned by the printer in the order they are received … because the printer queue is a queue, the first job to be sent to the printer would be the first job printed. If the printer queue was on a stack, the first job the printer received would not be printed until all the other jobs have been printed.
(a) Draw one line from each machine learning category to its most appropriate description. 4 marks
Machine learning category Description
simulates the data-processing capabilities of the human brain to make decisions
Supervised learning
Reinforcement learning
Deep learning
Unsupervised learning
enables learning by mapping an input to an output based on example input– output pairs
enables information related to errors produced by the neural network to be transmitted
enables learning in an interactive environment by trial and error using its own experiences
enables learning by allowing the process to discover patterns on its own that were previously undetected
(b) Describe the purpose of both the A* algorithm and Dijkstra’s algorithm. 2 marks
Show mark scheme
2(a)
One mark for each correct line connecting a machine learning technique to its most appropriate description ( Max 4 ). Machine learning category Description simulates the data processing capabilities of the human brain to make decisions Supervised learning enables learning by mapping an input to an output based on example input- output pairs Reinforcement learning enables information related to errors produced by the neural network to be transmitted Deep learning enables learning in an interactive environment by trial and error using its own experiences Unsupervised learning enables learning by allowing the process to discover patterns on its own that were previously undetected
2(b) [2 marks]
One mark per mark point ( Max 2 ) to find the optimal / shortest / most cost-effective route … between two nodes in a … based on distance / cost / time.
(b) Complete the following pseudocode for the function Dequeue to remove the front item from the queue. 4 marks
FUNCTION Dequeue RETURNS STRING
DECLARE Item : STRING
______ > 0 THEN
Item ←
IF Length = 0 THEN
CALL Initialise // reset the pointers
ELSE
IF FrontPointer > MaxSize THEN
______ ← 1
ENDIF
ENDIF
ELSE
OUTPUT "The print queue was empty – error!"
Item ← ""
ENDIF
RETURN Item
ENDFUNCTION
(c) Explain how a new element can be added to the queue if it is implemented using two stacks. 4 marks 2 marks
12 (a) Describe what is meant by recursion.
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 3 ) correctly defined constant correctly defined array three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize - 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER
11(b) [4 marks]
One mark for each correctly completed line ( Max 4 ) FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length
0 THEN Item Queue[FrontPointer] FrontPointer FrontPointer + 1 Length Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer 1 ENDIF ENDIF ELSE OUTPUT " The print queue was empty – error " Item "" ENDIF RETURN Item ENDFUNCTION
11(c)
One mark per mark point ( Max 4 ) MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1.
A program implements two stacks using 1D arrays. One stack stores the names of colours. One stack stores the names of animals.
(a) The program contains the following global arrays and variables: 3 marks
1D array
Animalto store the names of up to 20 animals.1D array
Colourto store the names of up to 10 colours.AnimalTopPointerto point to the next free space in the arrayAnimal, initialised to 0.ColourTopPointerto point to the next free space in the arrayColour, initialised to 0.
Write program code to declare the global arrays and variables.
Save your program as Question3_J2023 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) (i) Study the pseudocode function PushAnimal() : 3 marks
FUNCTION PushAnimal(DataToPush : STRING) RETURNS BOOLEAN
IF AnimalTopPointer = 20 THEN
RETURN FALSE
ELSE
Animal[AnimalTopPointer] DataToPush
AnimalTopPointer AnimalTopPointer + 1
RETURN TRUE
ENDIF
ENDFUNCTION
Write program code for the function PushAnimal()
Save your program.
Copy and paste the program code into part 3(b)(i) in the evidence document.
(ii) Study the pseudocode function PopAnimal() : 3 marks
FUNCTION PopAnimal() RETURNS STRING
DECLARE ReturnData : STRING
IF AnimalTopPointer = 0 THEN
RETURN ""
ELSE
ReturnData Animal[AnimalTopPointer - 1]
AnimalTopPointer AnimalTopPointer - 1
RETURN ReturnData
ENDIF
ENDFUNCTION
Write program code to declare the function PopAnimal()
Save your program.
Copy and paste the program code into part 3(b)(ii) in the evidence document.
(iii) The procedure ReadData() : 5 marks
reads the animal names from the file
AnimalData.txtuses
PushAnimal()to insert each name onto the stackuses appropriate exception handling if the file does not exist.
Write program code for the procedure ReadData()
Save your program.
Copy and paste the program code into part 3(b)(iii) in the evidence document.
(iv) The function PushColour() performs the same actions as PushAnimal() but inserts an item into Colour . 2 marks
The function PopColour() performs the same actions as PopAnimal() but removes
the next item from Colour .
Write program code for the functions PushColour() and PopColour()
Save your program.
Copy and paste the program code into part 3(b)(iv) in the evidence document.
(v) Amend the procedure ReadData() so that it also:
reads the colours from the text file
ColourData.txtuses
PushColour()to insert each colour onto the stackuses appropriate exception handling if the file does not exist.
Save your program.
Copy and paste the program code into part 3(b)(v) in the evidence document.
(c) The procedure OutputItem() : 2 marks
pops the next item from both
AnimalandColouroutputs the colour and animal on one line, for example
"black horse"
If there is no data in Colour :
the animal is pushed back onto
Animal"No colour"is output.
If there is no data in Animal :
the colour is pushed back onto
Colour"No animal"is output.
Write program code for the procedure OutputItem()
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The main program: 5 marks
calls the procedure
ReadData()calls
OutputItem()four times.
(i) Write program code for the main program. 1 mark
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 3(d)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark each (Global) Animal array (with 20 string elements) (Global) Colour array (with 10 string elements) (Global) AnimalTopPointer and ColourTopPointer initialised to 0 Example program code: public static String[] Animal = new String[20]; public static String[] Colour = new String[10]; public static Integer AnimalTopPointer = 0; public static Integer ColourTopPointer = 0; VB.NET Dim Animal(0 to 19) As String Dim Colour(0 to 9) As String Dim AnimalTopPointer As Integer = 0 Dim ColourTopPointer As Integer = 0 Python Animal = [] #20 elements Colour = [] #10 elements global AnimalTopPointer global ColourTopPointer AnimalTopPointer = 0 ColourTopPointer = 0
3(b)(i)
else: Animal.append(DataToPush) AnimalTopPointer +=1 return True
3(b)(ii)
Python def PopAnimal(): global AnimalTopPointer global ColourTopPointer if AnimalTopPointer == 0: return "" else: ReturnData = Animal[AnimalTopPointer - 1] AnimalTopPointer -=1 return ReturnData
3(b)(iii)
Python def ReadData(): try: global AnimalTopPointer global ColourTopPointer AnimalFile = open("AnimalData.txt", 'r') for Line in AnimalFile: PushAnimal(Line) AnimalFile.close() except IOError: print("Could not find file")
3(b)(iv)
End Function Function PopColour() Dim ReturnData As String If ColourTopPointer = 0 Then Return "" Else ReturnData = Colour(ColourTopPointer - 1) ColourTopPointer = ColourTopPointer - 1 Return ReturnData End If End Function Python def PushColour(DataToPush): global AnimalTopPointer global ColourTopPointer if ColourTopPointer == 10: return False else: Colour.append(DataToPush) ColourTopPointer +=1 return True def PopColour(): global AnimalTopPointer global ColourTopPointer if ColourTopPointer == 0: return "" else: ReturnData = Colour[ColourTopPointer - 1] ColourTopPointer -=1 return ReturnData
3(b)(v)
Loop AnimalFileReader.Close() Dim ColourFile As String = "ColourData.txt" Dim ColourFileReader As New System.IO.StreamReader(ColourFile) Do Until ColourFileReader.EndOfStream PushColour(ColourFileReader.ReadLine()) Loop ColourFileReader.Close() Catch ex As Exception Console.WriteLine("Invalid file") End Try End Sub Python def ReadData(): try: global AnimalTopPointer global ColourTopPointer AnimalFile = open("AnimalData.txt", 'r') for Line in AnimalFile: PushAnimal(Line) AnimalFile.close() ColourFile = open("ColourData.txt", 'r') for Line in ColourFile: PushColour(Line) ColourFile.close() except IOError: print("Could not find file")
3(c)
Else If Animalreturned = "" Then Console.WriteLine("No animal") PushColour(ColourReturned) Else Console.WriteLine("A " & ColourReturned & " " & Animalreturned) End If End If End Sub Python def OutputItem(): global AnimalTopPointer global ColourTopPointer ColourReturned = PopColour() AnimalReturned = PopAnimal() if ColourReturned == "": print("No colour") PushAnimal(AnimalReturned) else: if AnimalReturned == "": print("No animal") PushColour(ColourReturned) else: print(ColourReturned, AnimalReturned)
3(d)(i) [1 mark]
1 mark for Calling ReadData() and calling OutputItem() 4 times Example program code: public static void main(String args[]){ ReadData(); OutputItem(); OutputItem(); OutputItem(); OutputItem(); VB.NET Sub Main() ReadData() OutputItem() OutputItem() OutputItem() OutputItem() End Sub Python ReadData() OutputItem() OutputItem() OutputItem() OutputItem()
3(d)(ii) [1 mark]
1 mark for output
A business sells a single product. Customers can purchase one or more of this product.
Each sale has an ID and a quantity, for example "ABC" and 2
The business needs a program to store the data about the sales in a circular queue data structure.
(a) Write program code to declare a record structure, SaleData, to store the data about each sale. 2 marks
Save your program as Question2_J2023 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) Write program code to: 4 marks
declare a global array,
CircularQueue, of 5 items to store the sale recordsdeclare the global pointers
HeadandTaildeclare the global variable
NumberOfItemsinitialise all elements of the array
CircularQueueto an empty record, where the ID is null ("") and quantity is-1initialise
Head,TailandNumberOfItemsto0
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The function Enqueue() : 6 marks
takes a new record as a parameter
inserts the record in the circular queue at the element pointed to by
Tailupdates pointers and other variables as required
returns −1 if the circular queue is full
returns
1if the record is stored successfully.
Write program code for the function Enqueue() .
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The function Dequeue() : 6 marks
returns a null or empty record if the circular queue is empty
returns the first record in the queue if the circular queue is not empty
updates pointers and other variables as required.
Write program code for the function Dequeue() .
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) The procedure EnterRecord() : 5 marks
takes an ID and quantity as input and creates a sale record
uses
Enqueue()to insert the record in the circular queueoutputs
"Full"if the record was not inserted in the circular queueoutputs
"Stored"if the record was inserted in the circular queue.
Write program code for the procedure EnterRecord() .
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) The following sale records need to be entered into the program:
| ID | Quantity |
|---|---|
| ADF | 10 |
| OOP | 1 |
| BXW | 5 |
| XXZ | 22 |
| HQR | 6 |
| LLP | 3 |
(i) Amend the main program to: 4 marks
use
EnterRecord()to input the six records in the tableuse
Dequeue()to remove one recordoutput either the ID and quantity of the removed record, or an error message if the circular queue is empty
use
EnterRecord()to input the record with the ID "LLP" for a second timeoutput the ID and quantity for all the records currently stored in the array
CircularQueue.
Write program code to perform these tasks.
Save your program.
Copy and paste the program code into part 2(f)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(f)(ii) in the evidence document.
Show mark scheme
2(a) [2 marks]
1 mark each Record declaration named SaleData // class declaration (and end) named SaleData … SaleID declared as string, Quantity as integer in record // if a class then a constructor assigning attributes SaleID and Quantity Example Program code: class SaleData{ private String SaleId; private Integer Quantity; public SaleData(String SaleIDP, Integer Quantityp){ SaleId = SaleIDP; Quantity = Quantityp; } VB.NET Structure SaleData Public SaleID As String Public Quantity As Integer End Structure Python class SaleData: def init(self, SaleIDp, Quantityp): self.SaleID = SaleIDp #string self.Quantity = Quantityp #integer
2(b)
Python CircularQueue = [] #SaleData, 5 items global NumberOfItems #int global Head #int global Tail #int #main NumberOfItems = 0 Head = 0 Tail = 0 for x in range(0, 5): CircularQueue.append((SaleData("",-1)))
2(c)
Else Tail += 1 End If NumberOfItems += 1 Return 1 End If End Function Python def Enqueue(RecordToAdd): global NumberOfItems #int global Head #int global Tail #int if(NumberOfItems == 5): return -1 else: CircularQueue[Tail] = RecordToAdd if(Tail == 4): Tail = 0 else: Tail +=1 NumberOfItems +=1 return 1
2(d)
Else Head += 1 End If End If Return RecordRemoved End Function Python def Dequeue(): global NumberOfItems #int global Head #int global Tail #int RecordRemoved = SaleData("", -1) if not(NumberOfItems == 0): RecordRemoved = CircularQueue[Head] NumberOfItems -=1 if Head == 4: Head = 0 else: Head +=1 return RecordRemoved
2(e)
Python def EnterRecord(): ID = input("Enter ID") QuantityP = input("Enter quantity") Record = SaleData(ID, QuantityP) if Enqueue(Record) == -1: print("Full") else: print("Stored")
2(f)(i)
EnterRecord() EnterRecord() Dim ReturnValue As SaleData = new SaleData ReturnValue = Dequeue() If (ReturnValue.SaleID = "") Then Console.WriteLine("No items") Console.WriteLine(ReturnValue.SaleID & " " & ReturnValue.Quantity) End If EnterRecord() For x = 0 To 4 Console.WriteLine(CircularQueue(x).SaleID & " " & CircularQueue(x).Quantity) Python EnterRecord() EnterRecord() EnterRecord() EnterRecord() EnterRecord() EnterRecord() ReturnValue = Dequeue() if ReturnValue.SaleID == "": print("No items") else: print(ReturnValue.SaleID, " ", ReturnValue.Quantity) EnterRecord() for x in range(0, 5): print(CircularQueue[x].SaleID, " ", CircularQueue[x].Quantity)
2(f)(ii) [1 mark]
1 mark for screenshot showing: Data for 6 records input 5 messages stating (e.g.) stored and 1 message stating (e.g.) full 1 output of ADF 10 (dequeued) Repeat successful input of LLP 3 Output of the 5 records
A program implements two stacks using 1D arrays. One stack stores the names of colours. One stack stores the names of animals.
(a) The program contains the following global arrays and variables: 3 marks
1D array
Animalto store the names of up to 20 animals.1D array
Colourto store the names of up to 10 colours.AnimalTopPointerto point to the next free space in the arrayAnimal, initialised to 0.ColourTopPointerto point to the next free space in the arrayColour, initialised to 0.
Write program code to declare the global arrays and variables.
Save your program as Question3_J2023 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) (i) Study the pseudocode function PushAnimal() : 3 marks
FUNCTION PushAnimal(DataToPush : STRING) RETURNS BOOLEAN
IF AnimalTopPointer = 20 THEN
RETURN FALSE
ELSE
Animal[AnimalTopPointer] DataToPush
AnimalTopPointer AnimalTopPointer + 1
RETURN TRUE
ENDIF
ENDFUNCTION
Write program code for the function PushAnimal()
Save your program.
Copy and paste the program code into part 3(b)(i) in the evidence document.
(ii) Study the pseudocode function PopAnimal() : 3 marks
FUNCTION PopAnimal() RETURNS STRING
DECLARE ReturnData : STRING
IF AnimalTopPointer = 0 THEN
RETURN ""
ELSE
ReturnData Animal[AnimalTopPointer - 1]
AnimalTopPointer AnimalTopPointer - 1
RETURN ReturnData
ENDIF
ENDFUNCTION
Write program code to declare the function PopAnimal()
Save your program.
Copy and paste the program code into part 3(b)(ii) in the evidence document.
(iii) The procedure ReadData() : 5 marks
reads the animal names from the file
AnimalData.txtuses
PushAnimal()to insert each name onto the stackuses appropriate exception handling if the file does not exist.
Write program code for the procedure ReadData()
Save your program.
Copy and paste the program code into part 3(b)(iii) in the evidence document.
(iv) The function PushColour() performs the same actions as PushAnimal() but inserts an item into Colour . 2 marks
The function PopColour() performs the same actions as PopAnimal() but removes
the next item from Colour .
Write program code for the functions PushColour() and PopColour()
Save your program.
Copy and paste the program code into part 3(b)(iv) in the evidence document.
(v) Amend the procedure ReadData() so that it also:
reads the colours from the text file
ColourData.txtuses
PushColour()to insert each colour onto the stackuses appropriate exception handling if the file does not exist.
Save your program.
Copy and paste the program code into part 3(b)(v) in the evidence document.
(c) The procedure OutputItem() : 2 marks
pops the next item from both
AnimalandColouroutputs the colour and animal on one line, for example
"black horse"
If there is no data in Colour :
the animal is pushed back onto
Animal"No colour"is output.
If there is no data in Animal :
the colour is pushed back onto
Colour"No animal"is output.
Write program code for the procedure OutputItem()
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The main program: 5 marks
calls the procedure
ReadData()calls
OutputItem()four times.
(i) Write program code for the main program. 1 mark
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 3(d)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark each (Global) Animal array (with 20 string elements) (Global) Colour array (with 10 string elements) (Global) AnimalTopPointer and ColourTopPointer initialised to 0 Example program code: public static String[] Animal = new String[20]; public static String[] Colour = new String[10]; public static Integer AnimalTopPointer = 0; public static Integer ColourTopPointer = 0; VB.NET Dim Animal(0 to 19) As String Dim Colour(0 to 9) As String Dim AnimalTopPointer As Integer = 0 Dim ColourTopPointer As Integer = 0 Python Animal = [] #20 elements Colour = [] #10 elements global AnimalTopPointer global ColourTopPointer AnimalTopPointer = 0 ColourTopPointer = 0
3(b)(i)
else: Animal.append(DataToPush) AnimalTopPointer +=1 return True
3(b)(ii)
Python def PopAnimal(): global AnimalTopPointer global ColourTopPointer if AnimalTopPointer == 0: return "" else: ReturnData = Animal[AnimalTopPointer - 1] AnimalTopPointer -=1 return ReturnData
3(b)(iii)
Python def ReadData(): try: global AnimalTopPointer global ColourTopPointer AnimalFile = open("AnimalData.txt", 'r') for Line in AnimalFile: PushAnimal(Line) AnimalFile.close() except IOError: print("Could not find file")
3(b)(iv)
End Function Function PopColour() Dim ReturnData As String If ColourTopPointer = 0 Then Return "" Else ReturnData = Colour(ColourTopPointer - 1) ColourTopPointer = ColourTopPointer - 1 Return ReturnData End If End Function Python def PushColour(DataToPush): global AnimalTopPointer global ColourTopPointer if ColourTopPointer == 10: return False else: Colour.append(DataToPush) ColourTopPointer +=1 return True def PopColour(): global AnimalTopPointer global ColourTopPointer if ColourTopPointer == 0: return "" else: ReturnData = Colour[ColourTopPointer - 1] ColourTopPointer -=1 return ReturnData
3(b)(v)
Loop AnimalFileReader.Close() Dim ColourFile As String = "ColourData.txt" Dim ColourFileReader As New System.IO.StreamReader(ColourFile) Do Until ColourFileReader.EndOfStream PushColour(ColourFileReader.ReadLine()) Loop ColourFileReader.Close() Catch ex As Exception Console.WriteLine("Invalid file") End Try End Sub Python def ReadData(): try: global AnimalTopPointer global ColourTopPointer AnimalFile = open("AnimalData.txt", 'r') for Line in AnimalFile: PushAnimal(Line) AnimalFile.close() ColourFile = open("ColourData.txt", 'r') for Line in ColourFile: PushColour(Line) ColourFile.close() except IOError: print("Could not find file")
3(c)
Else If Animalreturned = "" Then Console.WriteLine("No animal") PushColour(ColourReturned) Else Console.WriteLine("A " & ColourReturned & " " & Animalreturned) End If End If End Sub Python def OutputItem(): global AnimalTopPointer global ColourTopPointer ColourReturned = PopColour() AnimalReturned = PopAnimal() if ColourReturned == "": print("No colour") PushAnimal(AnimalReturned) else: if AnimalReturned == "": print("No animal") PushColour(ColourReturned) else: print(ColourReturned, AnimalReturned)
3(d)(i) [1 mark]
1 mark for Calling ReadData() and calling OutputItem() 4 times Example program code: public static void main(String args[]){ ReadData(); OutputItem(); OutputItem(); OutputItem(); OutputItem(); VB.NET Sub Main() ReadData() OutputItem() OutputItem() OutputItem() OutputItem() End Sub Python ReadData() OutputItem() OutputItem() OutputItem() OutputItem()
3(d)(ii) [1 mark]
1 mark for output
11 (a) Define these Object-Oriented Programming (OOP) terms:
Instance
Inheritance
Polymorphism 3 marks
(b) In OOP, a class contains attributes and methods. 5 marks
Complete the pseudocode for the class Car to enable objects to be created. The class needs
to include:
string attributes to store the make, model, body type and fuel type
an integer attribute to store the number of cars of that type built.
The attributes must be available only through the methods of the class.
CLASS
PRIVATE Make : STRING
PRIVATE
PUBLIC PROCEDURE New(CarMake : STRING, ______ ,
______ )
Make
←
Model
←
BodyType CarBodyType
# ←
Fuel ""
# ←
NumberBuilt 0
# ←
ENDPROCEDURE
GetFuel()
GetNumberBuilt()
Show mark scheme
10(a) [2 marks]
Two marks for all five rows correct One mark for four rows correct Statement RISC ✓ uses a smaller instruction set ✓ uses single-cycle instructions and limited addressing modes uses fewer general-purpose registers uses both hardwired and micro coded control unit uses a system where cache is split between data and ✓ instructions
10(b) [4 marks]
One mark for each correct point ( Max 4 ) • Instructions are divided into subtasks / 5 stages • … Instruction fetch / IF, Instruction decode / ID, operand fetch / OF, opcode/instruction execute IE, result store / write back result / WB • Each subtask is completed during one clock cycle • No two instructions can execute their same stage at the same clock cycle • The second instruction begins in the second clock cycle, while the first instruction has moved on to its second subtask. • The third instruction begins in the third clock cycle while the first and second instructions move on to their second and third subtasks, respectively, etc.
Show mark scheme
10(a) [3 marks]
One mark for each correct OOP term definition • Encapsulation – putting properties and methods inside a class // ensures sensitive data is hidden from users by hiding values of a structured data object inside a class. • Getter – method that is used to return the value of a property. • Setter – method that is used to update the value of a property.
10(b) [3 marks]
One mark for each point • properties correct • setters correct • getters correct SubstituteTeacher SubName : STRING Telephone : STRING InSchool : BOOLEAN SetSubName(StaffName : STRING) SetTelephone(Tel : STRING) SetInSchool(Present : BOOLEAN) GetSubName() GetTelephone() GetInSchool()
11 (a) Define these Object-Oriented Programming (OOP) terms:
Instance
Inheritance
Polymorphism 3 marks
(b) In OOP, a class contains attributes and methods. 5 marks
Complete the pseudocode for the class Car to enable objects to be created. The class needs
to include:
string attributes to store the make, model, body type and fuel type
an integer attribute to store the number of cars of that type built.
The attributes must be available only through the methods of the class.
CLASS
PRIVATE Make : STRING
PRIVATE
PUBLIC PROCEDURE New(CarMake : STRING, ______ ,
______ )
Make
←
Model
←
BodyType CarBodyType
# ←
Fuel ""
# ←
NumberBuilt 0
# ←
ENDPROCEDURE
GetFuel()
GetNumberBuilt()
Show mark scheme
10(a) [2 marks]
Two marks for all five rows correct One mark for four rows correct Statement RISC ✓ uses a smaller instruction set ✓ uses single-cycle instructions and limited addressing modes uses fewer general-purpose registers uses both hardwired and micro coded control unit uses a system where cache is split between data and ✓ instructions
10(b) [4 marks]
One mark for each correct point ( Max 4 ) • Instructions are divided into subtasks / 5 stages • … Instruction fetch / IF, Instruction decode / ID, operand fetch / OF, opcode/instruction execute IE, result store / write back result / WB • Each subtask is completed during one clock cycle • No two instructions can execute their same stage at the same clock cycle • The second instruction begins in the second clock cycle, while the first instruction has moved on to its second subtask. • The third instruction begins in the third clock cycle while the first and second instructions move on to their second and third subtasks, respectively, etc.
A computer program is being developed that uses a set of cards. The program is written using object-oriented programming.
| The program has two classes: Card and Hand. The methods and attributes of these classes are shown: | |
|---|---|
Card |
Card |
Number : INTEGERColour : STRING |
stores the card number from 1 to 5 inclusive stores the card colour: red, blue or yellow |
Constructor()GetNumber()GetColour() |
takes a number and colour as parameters and sets the private values to these parameters returns the card number returns the card colour |
| GetNumber() GetColour() returns the card number returns the card colour | |
|---|---|
Hand |
Hand |
Cards : ARRAY[0:9] OF CardFirstCard : INTEGERNumberCards : INTEGER |
1D array of typeCardstores the position of the first card in the hand stores the number of cards in the hand |
Constructor()GetCard() |
takes five card objects as parameters, assigns each card to the array Cards[], initialisesFirstCard to 0and NumberCards to 5takes an index as a parameter and returns the card at that index in the array |
(a) (i) Write program code to declare the class Card, its attributes and constructor. 5 marks
Do not write program code for the get methods.
Use your programming language appropriate constructor.
All attributes must be private. If you are writing in Python, include attribute declarations using comments.
Save your program as Question2_N22 .
Copy and paste the program code into part 2(a)(i) in the evidence document.
(ii) Write program code for the class methods GetNumber() and GetColour() . 3 marks
Save your program.
Copy and paste the program code into part 2(a)(ii) in the evidence document.
(iii) The program is tested with the following cards: 2 marks
| Number | Colour |
|---|---|
| 1 | red |
| 2 | red |
| 3 | red |
| 4 | red |
| 5 | red |
| 1 | blue |
| 2 | blue |
| 3 | blue |
| 4 | blue |
| 5 | blue |
| 1 | yellow |
| 2 | yellow |
| 3 | yellow |
| 4 | yellow |
| 5 | yellow |
Write program code to declare each of these cards as a variable of type Card in the
main program.
Save your program.
Copy and paste the program code into part 2(a)(iii) in the evidence document.
(b) (i) Write program code to declare the class Hand, its attributes and constructor. 6 marks
Do not write the get methods.
Use your programming language appropriate constructor.
All attributes must be private. If you are writing in Python, include attribute declarations using comments.
Save your program.
Copy and paste the program code into part 2(b)(i) in the evidence document.
(ii) The get method GetCard() takes an index as a parameter and returns the card stored at that index in the array. 2 marks
Write program code for the method GetCard() .
Save your program.
Copy and paste the program code into part 2(b)(ii) in the evidence document.
(iii) Two players are declared with 5 cards each. 2 marks
Player 1 has the cards: 1 red, 2 red, 3 red, 4 red, 1 yellow. Player 2 has the cards: 2 yellow, 3 yellow, 4 yellow, 5 yellow, 1 blue.
Write program code to declare player 1 and player 2 as objects of type Hand, with the
cards indicated.
Save your program.
Copy and paste the program code into part 2(b)(iii) in the evidence document.
(c) The function CalculateValue() takes a player’s hand as a parameter and returns a score calculated using the following rules:
If a card is red, 5 points are added to the player’s score.
If a card is blue, 10 points are added to the player’s score.
If a card is yellow, 15 points are added to the player’s score.
The number of each card in the hand is added to the player’s score.
(i) Write program code for the function CalculateValue() . 6 marks
Assume that there are only 5 cards in the player’s hand in this function.
Save your program.
Copy and paste the program code into part 2(c)(i) in the evidence document.
(ii) Amend the main program by writing program code to use the function CalculateValue() for each of the two players. The player with the highest score wins. 4 marks
Output an appropriate message to identify the winning player, or if the game was a draw (both players have the same number of points).
Save your program.
Copy and paste the program code into part 2(c)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 2(c)(iii) in the evidence document.
Show mark scheme
2(a)(i)
Java class Card{ private Integer Number; private String Colour; public Card(Integer Number1, String Colourp){ Number = Number1; Colour = Colourp; }} VB.NET Class Card Private Number As Integer Private Colour As String Sub New(Number1, Colourp) Number = Number1 Colour = Colourp End Sub End Class
2(a)(ii) [3 marks]
1 mark per point: • 1 get method as function (and end where appropriate) with no parameters… • …returning the value • 2nd correct get method Example program code: Python def GetNumber(self): return self.__Number def GetColour(self): return self.__Colour Java public Integer GetNumber(){ return Number; } public String GetColour(){ return Colour; } VB.NET Function GetNumber() Return Number End Function Function GetColour() Return Colour End Function
2(a)(iii)
VB.NET Dim OneRed As New Card (1, "red") Dim TwoRed As New Card(2, "red") Dim ThreeRed As New Card(3, "red") Dim FourRed As New Card(4, "red") Dim FiveRed As New Card(5, "red") Dim OneBlue As New Card(1, "blue") Dim TwoBlue As New Card(2, "blue") Dim ThreeBlue As New Card(3, "blue") Dim FourBlue As New Card(4, "blue") Dim FiveBlue As New Card(5, "blue") Dim OneYellow As New Card(1, "yellow") Dim TwoYellow As New Card(2, "yellow") Dim ThreeYellow As New Card(3, "yellow") Dim FourYellow As New Card(4, "yellow") Dim FiveYellow As New Card(5, "yellow")
2(b)(i)
Java class Hand{ private Card[] Cards = new Card[10]; private Integer FirstCard; private Integer NumberCards; public Hand(CARD Card1, CARD Card2, CARD Card3, CARD Card4, CARD Card5){ Cards[0] = Card1; Cards[1] = Card2; Cards[2] = Card3; Cards[3] = Card4; Cards[4] = Card5; FirstCard = 0; NumberCards = 5; } } VB.NET class Hand Private Cards(9) As Card Private FirstCard As Integer Private NumberCards As Integer Sub New(Card1, Card2, Card3, Card4, Card5) Cards(0) = Card1 Cards(1) = Card2 Cards(2) = Card3 Cards(3) = Card4 Cards(4) = Card5 FirstCard = 0 NumberCards = 5 End Sub End Class
2(b)(ii) [2 marks]
1 mark per point: • function header (and end where appropriate) taking (integer) GetCard() parameter • returning the card at parameter index in array Example program code: Python def GetCard(self, Position): return self.__Cards[Position] Java public Card GetCard(Integer Position){ return Cards[Position]; } VB.NET Function GetCard(Position) Return Cards(Position) End Function
2(b)(iii) [2 marks]
1 mark per point: • 2 variables (player 1 and player 2) of type Hand • using constructor and sending the correct variables as parameters Example program code: Python Player1 = Hand(OneRed, TwoRed, ThreeRed, FourRed, OneYellow) Player2 = Hand(TwoYellow, ThreeYellow, FourYellow, FiveYellow, OneBlue) Java Hand Player1 = new Hand(OneRed, TwoRed, ThreeRed, FourRed, OneYellow); Hand Player2 = new Hand(TwoYellow, ThreeYellow, FourYellow, FiveYellow, OneBlue); VB.NET Dim Player1 As New Hand(OneRed, TwoRed, ThreeRed, FourRed, OneYellow) Dim Player2 As New Hand(TwoYellow, ThreeYellow, FourYellow, FiveYellow, OneBlue)
2(c)(i)
Java public static Integer CalculateValue(Hand Player){ Integer Score = 0; String Colour; Card CardGot; for(Integer X = 0; X<5; X++){ CardGot = Player.GetCard(X); Score = Score + CardGot.GetNumber(); Colour = CardGot.GetColour(); if(Colour == "red"){ Score = Score + 5; }else if(Colour == "blue"){ Score = Score + 10; } else { Score = Score + 15; }}return Score;} VB.NET Function CalculateValue(Player As Hand) Dim Score As Integer = 0 Dim Colour As String Dim CardGot As Card For Count = 0 To 4 CardGot = Player.GetCard(Count) Score = Score + CardGot.GetNumber() Colour = CardGot.GetColour() If Colour = "red" Then Score = Score + 5 ElseIf Colour = "blue" Then Score = Score + 10 Else Score = Score + 15 End If Next Return Score End Function
2(c)(ii) [4 marks]
1 mark per point: • One function call of ) for each player … CalculateValue( • …sending the player's hand as parameter • Comparing return values and outputting the player with the highest score in an appropriate message … • … or if there was a draw in appropriate message Example program code: Python Player1score = CalculateValue(Player1) Player2score = CalculateValue(Player2) if Player1score > Player2score: print("Player 1 wins") elif Player1score < Player2score: print("Player 2 wins") else: print("It's a draw") Java Integer Player1score = CalculateValue(Player1); Integer Player2score = CalculateValue(Player2); if(Player1score > Player2score){ System.out.println("Player 1 wins"); }else if(Player2score > Player1score){ System.out.println("Player2 wins"); } else { System.out.println("It's a draw"); } VB.NET Dim Player1score As Integer Dim Player2score As Integer Player1score = CalculateValue(Player1) Player2score = CalculateValue(Player2) If Player1score > Player2score Then Console.WriteLine("Player 1 wins") ElseIf Player1score < Player2score Then Console.WriteLine("Player 2 wins") Else Console.WriteLine("It's a draw") End If
2(c)(iii) [1 mark]
Output showing player 2 wins, for example:
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: 3 marks
declare the global 2D array
ArrayNodesinitialise all 3 integer values to
–1for each node.
Save your program as Question3_N22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The binary tree stores the following values: 2 marks
| Left pointer | Data | Right pointer |
|---|---|---|
| 1 | 20 | 5 |
| 2 | 15 | –1 |
| –1 | 3 | 3 |
| –1 | 9 | 4 |
| –1 | 10 | –1 |
| –1 | 58 | –1 |
| –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.
(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. 5 marks
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.
(d) A post order traversal performs the following operation: 7 marks
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
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. (e) (i) Amend the main program by writing program code to: 3 marks
call the function
SearchValue()to find the position of the number 15 in the treeuse the result from
SearchValue()to output either the index of the value if found, or an appropriate message to state that the value was not foundcall the procedure
PostOrder().
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark per point: • 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)
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)
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) [7 marks]
1 mark per point ( Max 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) [3 marks]
1 mark per point: • calling with 15 and as a parameter … SearchValue() rootPointer • … if return value
-1 output returned index and if return value = -1 output not found Both as appropriate messages • Calling with as a PostOrder() ArrayNodes[RootPointer] 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) [1 mark]
Screenshot with result as shown, for example:
A computer game is being developed. The game has 10 different characters that are all active in the game.
Part of the game is being written using object-oriented programming.
| The class Character stores data about the characters. Each character has a name and the x coordinate and y coordinate of their current position. Character | |
|---|---|
Character |
Character |
Name : STRINGXCoordinate : INTEGERYCoordinate : INTEGER |
stores the name of the character stores the x coordinate stores the y coordinate |
Constructor()GetName()GetX()GetY()ChangePosition() |
initialisesName, XCoordinate andYCoordinate from thevalues passed as parameters returns the name of the character returns the x coordinate of the character returns the y coordinate of the character takes XChange as an integer parameter and adds it to thex coordinate takes YChange as an integer parameter and adds it to they coordinate |
(a) Write program code to declare the class Character and its constructor. Do not write program code for the other methods. 4 marks
Use your programming language appropriate constructor.
All attributes must be private. If you are writing in Python, include attribute declarations using comments.
Save your program as Question2_N22 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) Write program code for the three get methods for the class Character . 3 marks
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) Write program code for the method ChangePosition() . 2 marks
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The main program has a 1D array of characters. Each character is stored as an object of type Character . 7 marks
The game has a maximum of 10 characters. The character names, x coordinates and y
coordinates are stored in the file Characters.txt in the order:
name
x coordinate
y coordinate.
For example, the first character in the file is named Amal, with the x coordinate 0 and the y coordinate 2.
Amend the main program by writing program code to:
declare the array
read in all 10 characters from
Characters.txtstore each character as an object in the array.
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) The main program needs to read in a character’s name from the user, search for the character in the array and store the index of its position. It repeats until the user enters a name that exists in the array. 5 marks
Amend the main program by writing program code to perform this task.
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) The user will enter a letter to identify the direction the chosen character from part 2(e) should move. 7 marks
If ‘A’ is input, the character moves left (x coordinate minus 1).
If ‘W’ is input, the character moves up (y coordinate plus 1).
If ‘S’ is input, the character moves down (y coordinate minus 1).
If ‘D’ is input, the character moves right (x coordinate plus 1).
Amend the main program by writing program code to:
take a letter as input until it is a valid move (A, W, S or D)
change the position of the character using the appropriate method.
Save your program.
Copy and paste the program code into part 2(f) in the evidence document. (g) (i) When a change to a character’s position has been made, the program needs to output 2 marks the character’s name and the new x and y coordinates of the character, in the format:
Qui has changed coordinates to X = 83 and Y = 0
Amend the main program by writing program code to perform these tasks.
Save your program.
Copy and paste the program code into part 2(g)(i) in the evidence document.
(ii) Test your program by inputting the following four items of data in the order given: 1 mark
THOMAS
qui
Take a screenshot of the output.
Copy and paste the screenshot into part 2(g)(ii) in the evidence document.
Show mark scheme
2(a) [4 marks]
1 mark per point: • Class declaration (and end where appropriate) for Character • Declaring the 3 private attributes with appropriate data types; as Name string, as integer, as integer xCoordinate yCoordinate • Constructor method (and end where appropriate) taking 3 parameters … • …assigning parameters to all 3 attributes Example program code: Java class Character{ private String Name; private Integer XCoordinate; private Integer YCoordinate; public Character(String Namep, Integer XCoord, Integer YCoord){ Name = Namep; XCoordinate = XCoord; YCoordinate = YCoord; }} Python class Character: #private Name as string #private XCoordinate as integer #private YCoordinate as integer def init(self, Namep, Xcoord, Ycoord): self.__Name = Namep self.__XCoordiante = Xcoord self.__YCoordinate = Ycoord VB.NET Class Character Private Name As String Private XCoordinate As Integer Private YCoordinate As Integer Sub New(Namep, Xcoord, Ycoord) Name = Namep XCoordinate = Xcoord YCoordinate = Ycoord End Sub End Class
2(b) [3 marks]
1 mark per point: • 1 get method header (and end where appropriate) with no parameters… • …returning correct value • 2nd and 3rd correct get methods Example program code: Java public String GetName(){ return Name;} public Integer GetX(){ return XCoordinate;} public Integer GetY(){ return YCoordinate;} Python def GetName(self): return self.__Name def GetX(self): return self.__XCoordinate def GetY(self): return self.__YCoordinate VB.NET Function GetName() Return Name End Function Function GetX() Return XCoordinate End Function Function GetY() Return YCoordinate End Function
2(c) [2 marks]
1 mark per point: • method header (and end where appropriate) taking 2 (integer) parameters • adding both parameters to existing x and y coordinate values Example program code: Java public void ChangePosition(Integer XChange, Integer YChange){ XCoordinate = XCoordinate + XChange; YCoordinate = YCoordinate + YChange; } Python def ChangePosition(self, XChange, YChange): self.__XCoordinate = self.__XCoordinate + XChange self.__YCoordinate = self.__YCoordinate + YChange VB.NET Sub changePosition(XChange, YChange) XCoordinate = XCoordinate + XChange YCoordinate = YCoordinate + YChange End Sub
2(d)
VB.NET Sub Main() Dim Characters(0 To 9) As Character Dim TextFile As String = "Characters.txt" Try Dim FileReader As New System.IO.StreamReader(TextFile) For X = 0 To 10 Name = FileReader.ReadLine() Xcoord = FileReader.ReadLine() Ycoord = FileReader.ReadLine() Characters(X) = New Character(Name, Xcoord, Ycoord) Next FileReader.Close() Catch ex As Exception Console.WriteLine("File not found") End Try end sub
2(e)
Java Integer Position = -1; String CharacterName = ""; Scanner scanner = new Scanner(System.in); String Temp = ""; while(Position == -1){ System.out.println("Enter the Character to move"); CharacterName = scanner.nextLine(); for(Integer Count = 0; Count < 10; Count++){ Temp = Characters[Count].GetName(); Temp = Temp.toLowerCase(); if(Temp.equals(CharacterName.toLowerCase())){ Position = Count; } }}
2(f)
Dim IsValid As Boolean = False Dim Move As String While IsValid <> True Console.WriteLine("Enter A for left, W for up, S for down or D for right") Move = Console.ReadLine() If Move.ToUpper = "A" Then Characters(Position).ChangePosition(-1, 0) IsValid = True ElseIf Move.ToUpper = "W" Then Characters(Position).ChangePosition(0, 1) IsValid = True ElseIf Move.ToUpper = "S" Then Characters(Position).ChangePosition(0, -1) IsValid = True ElseIf Move.ToUpper = "D" Then Characters(Position).ChangePosition(1, 0) IsValid = True End If End While
2(g)(i) [2 marks]
1 mark per point: • Outputting given message including name, x and y position • …all using appropriate get methods Example program code: Java System.out.println(CharacterName + " has changed coordinates to X = " + Characters[Position].GetX() + " Y = " + Characters[Position].GetY()); Python print(CharacterName, " has changed coordinate to X = ", str(Characters[Position].GetX()), " Y = ", str(Characters[Position].GetY())) VB.NET Console.WriteLine(CharacterName & " has changed coordinates to X = " & Characters(Position).GetX & " Y = " & Characters(Position).GetY())
2(g)(ii) [1 mark]
1 mark for correct result, for example:
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. 3 marks
Write program code to:
declare the global array
Queuedeclare 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.
(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. 6 marks
Write program code for the function Enqueue() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The main program uses the Enqueue() function to store the numbers 1 to 20 (inclusive) 4 marks
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.
(d) The following iterative pseudocode function calculates the total of all the values stored in the queue. 6 marks
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.
(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. 1 mark
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark per point: • 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) [6 marks]
1 mark per point: • 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) [4 marks]
1 mark per point: • Looping 20 times • … using with each number 1 to 20 in ascending numerical Enqueue() 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) [6 marks]
1 mark per point: • 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]
1 mark for calling function and outputting return value. 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]
1 mark for screenshot showing 210, for example:
A computer program is being developed that uses a set of cards. The program is written using object-oriented programming.
| The program has two classes: Card and Hand. The methods and attributes of these classes are shown: | |
|---|---|
Card |
Card |
Number : INTEGERColour : STRING |
stores the card number from 1 to 5 inclusive stores the card colour: red, blue or yellow |
Constructor()GetNumber()GetColour() |
takes a number and colour as parameters and sets the private values to these parameters returns the card number returns the card colour |
| GetNumber() GetColour() returns the card number returns the card colour | |
|---|---|
Hand |
Hand |
Cards : ARRAY[0:9] OF CardFirstCard : INTEGERNumberCards : INTEGER |
1D array of typeCardstores the position of the first card in the hand stores the number of cards in the hand |
Constructor()GetCard() |
takes five card objects as parameters, assigns each card to the array Cards[], initialisesFirstCard to 0and NumberCards to 5takes an index as a parameter and returns the card at that index in the array |
(a) (i) Write program code to declare the class Card, its attributes and constructor. 5 marks
Do not write program code for the get methods.
Use your programming language appropriate constructor.
All attributes must be private. If you are writing in Python, include attribute declarations using comments.
Save your program as Question2_N22 .
Copy and paste the program code into part 2(a)(i) in the evidence document.
(ii) Write program code for the class methods GetNumber() and GetColour() . 3 marks
Save your program.
Copy and paste the program code into part 2(a)(ii) in the evidence document.
(iii) The program is tested with the following cards: 2 marks
| Number | Colour |
|---|---|
| 1 | red |
| 2 | red |
| 3 | red |
| 4 | red |
| 5 | red |
| 1 | blue |
| 2 | blue |
| 3 | blue |
| 4 | blue |
| 5 | blue |
| 1 | yellow |
| 2 | yellow |
| 3 | yellow |
| 4 | yellow |
| 5 | yellow |
Write program code to declare each of these cards as a variable of type Card in the
main program.
Save your program.
Copy and paste the program code into part 2(a)(iii) in the evidence document.
(b) (i) Write program code to declare the class Hand, its attributes and constructor. 6 marks
Do not write the get methods.
Use your programming language appropriate constructor.
All attributes must be private. If you are writing in Python, include attribute declarations using comments.
Save your program.
Copy and paste the program code into part 2(b)(i) in the evidence document.
(ii) The get method GetCard() takes an index as a parameter and returns the card stored at that index in the array. 2 marks
Write program code for the method GetCard() .
Save your program.
Copy and paste the program code into part 2(b)(ii) in the evidence document.
(iii) Two players are declared with 5 cards each. 2 marks
Player 1 has the cards: 1 red, 2 red, 3 red, 4 red, 1 yellow. Player 2 has the cards: 2 yellow, 3 yellow, 4 yellow, 5 yellow, 1 blue.
Write program code to declare player 1 and player 2 as objects of type Hand, with the
cards indicated.
Save your program.
Copy and paste the program code into part 2(b)(iii) in the evidence document.
(c) The function CalculateValue() takes a player’s hand as a parameter and returns a score calculated using the following rules:
If a card is red, 5 points are added to the player’s score.
If a card is blue, 10 points are added to the player’s score.
If a card is yellow, 15 points are added to the player’s score.
The number of each card in the hand is added to the player’s score.
(i) Write program code for the function CalculateValue() . 6 marks
Assume that there are only 5 cards in the player’s hand in this function.
Save your program.
Copy and paste the program code into part 2(c)(i) in the evidence document.
(ii) Amend the main program by writing program code to use the function CalculateValue() for each of the two players. The player with the highest score wins. 4 marks
Output an appropriate message to identify the winning player, or if the game was a draw (both players have the same number of points).
Save your program.
Copy and paste the program code into part 2(c)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 2(c)(iii) in the evidence document.
Show mark scheme
2(a)(i)
Java class Card{ private Integer Number; private String Colour; public Card(Integer Number1, String Colourp){ Number = Number1; Colour = Colourp; }} VB.NET Class Card Private Number As Integer Private Colour As String Sub New(Number1, Colourp) Number = Number1 Colour = Colourp End Sub End Class
2(a)(ii) [3 marks]
1 mark per point: • 1 get method as function (and end where appropriate) with no parameters… • …returning the value • 2nd correct get method Example program code: Python def GetNumber(self): return self.__Number def GetColour(self): return self.__Colour Java public Integer GetNumber(){ return Number; } public String GetColour(){ return Colour; } VB.NET Function GetNumber() Return Number End Function Function GetColour() Return Colour End Function
2(a)(iii)
VB.NET Dim OneRed As New Card (1, "red") Dim TwoRed As New Card(2, "red") Dim ThreeRed As New Card(3, "red") Dim FourRed As New Card(4, "red") Dim FiveRed As New Card(5, "red") Dim OneBlue As New Card(1, "blue") Dim TwoBlue As New Card(2, "blue") Dim ThreeBlue As New Card(3, "blue") Dim FourBlue As New Card(4, "blue") Dim FiveBlue As New Card(5, "blue") Dim OneYellow As New Card(1, "yellow") Dim TwoYellow As New Card(2, "yellow") Dim ThreeYellow As New Card(3, "yellow") Dim FourYellow As New Card(4, "yellow") Dim FiveYellow As New Card(5, "yellow")
2(b)(i)
Java class Hand{ private Card[] Cards = new Card[10]; private Integer FirstCard; private Integer NumberCards; public Hand(CARD Card1, CARD Card2, CARD Card3, CARD Card4, CARD Card5){ Cards[0] = Card1; Cards[1] = Card2; Cards[2] = Card3; Cards[3] = Card4; Cards[4] = Card5; FirstCard = 0; NumberCards = 5; } } VB.NET class Hand Private Cards(9) As Card Private FirstCard As Integer Private NumberCards As Integer Sub New(Card1, Card2, Card3, Card4, Card5) Cards(0) = Card1 Cards(1) = Card2 Cards(2) = Card3 Cards(3) = Card4 Cards(4) = Card5 FirstCard = 0 NumberCards = 5 End Sub End Class
2(b)(ii) [2 marks]
1 mark per point: • function header (and end where appropriate) taking (integer) GetCard() parameter • returning the card at parameter index in array Example program code: Python def GetCard(self, Position): return self.__Cards[Position] Java public Card GetCard(Integer Position){ return Cards[Position]; } VB.NET Function GetCard(Position) Return Cards(Position) End Function
2(b)(iii) [2 marks]
1 mark per point: • 2 variables (player 1 and player 2) of type Hand • using constructor and sending the correct variables as parameters Example program code: Python Player1 = Hand(OneRed, TwoRed, ThreeRed, FourRed, OneYellow) Player2 = Hand(TwoYellow, ThreeYellow, FourYellow, FiveYellow, OneBlue) Java Hand Player1 = new Hand(OneRed, TwoRed, ThreeRed, FourRed, OneYellow); Hand Player2 = new Hand(TwoYellow, ThreeYellow, FourYellow, FiveYellow, OneBlue); VB.NET Dim Player1 As New Hand(OneRed, TwoRed, ThreeRed, FourRed, OneYellow) Dim Player2 As New Hand(TwoYellow, ThreeYellow, FourYellow, FiveYellow, OneBlue)
2(c)(i)
Java public static Integer CalculateValue(Hand Player){ Integer Score = 0; String Colour; Card CardGot; for(Integer X = 0; X<5; X++){ CardGot = Player.GetCard(X); Score = Score + CardGot.GetNumber(); Colour = CardGot.GetColour(); if(Colour == "red"){ Score = Score + 5; }else if(Colour == "blue"){ Score = Score + 10; } else { Score = Score + 15; }}return Score;} VB.NET Function CalculateValue(Player As Hand) Dim Score As Integer = 0 Dim Colour As String Dim CardGot As Card For Count = 0 To 4 CardGot = Player.GetCard(Count) Score = Score + CardGot.GetNumber() Colour = CardGot.GetColour() If Colour = "red" Then Score = Score + 5 ElseIf Colour = "blue" Then Score = Score + 10 Else Score = Score + 15 End If Next Return Score End Function
2(c)(ii) [4 marks]
1 mark per point: • One function call of ) for each player … CalculateValue( • …sending the player's hand as parameter • Comparing return values and outputting the player with the highest score in an appropriate message … • … or if there was a draw in appropriate message Example program code: Python Player1score = CalculateValue(Player1) Player2score = CalculateValue(Player2) if Player1score > Player2score: print("Player 1 wins") elif Player1score < Player2score: print("Player 2 wins") else: print("It's a draw") Java Integer Player1score = CalculateValue(Player1); Integer Player2score = CalculateValue(Player2); if(Player1score > Player2score){ System.out.println("Player 1 wins"); }else if(Player2score > Player1score){ System.out.println("Player2 wins"); } else { System.out.println("It's a draw"); } VB.NET Dim Player1score As Integer Dim Player2score As Integer Player1score = CalculateValue(Player1) Player2score = CalculateValue(Player2) If Player1score > Player2score Then Console.WriteLine("Player 1 wins") ElseIf Player1score < Player2score Then Console.WriteLine("Player 2 wins") Else Console.WriteLine("It's a draw") End If
2(c)(iii) [1 mark]
Output showing player 2 wins, for example:
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: 3 marks
declare the global 2D array
ArrayNodesinitialise all 3 integer values to
–1for each node.
Save your program as Question3_N22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The binary tree stores the following values: 2 marks
| Left pointer | Data | Right pointer |
|---|---|---|
| 1 | 20 | 5 |
| 2 | 15 | –1 |
| –1 | 3 | 3 |
| –1 | 9 | 4 |
| –1 | 10 | –1 |
| –1 | 58 | –1 |
| –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.
(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. 5 marks
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.
(d) A post order traversal performs the following operation: 7 marks
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
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. (e) (i) Amend the main program by writing program code to: 3 marks
call the function
SearchValue()to find the position of the number 15 in the treeuse the result from
SearchValue()to output either the index of the value if found, or an appropriate message to state that the value was not foundcall the procedure
PostOrder().
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark per point: • 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)
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)
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) [7 marks]
1 mark per point ( Max 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) [3 marks]
1 mark per point: • calling with 15 and as a parameter … SearchValue() rootPointer • … if return value
-1 output returned index and if return value = -1 output not found Both as appropriate messages • Calling with as a PostOrder() ArrayNodes[RootPointer] 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) [1 mark]
Screenshot with result as shown, for example:
(c) State two other uses of a stack. 2 marks
1
2
Show mark scheme
9(a) [3 marks]
LDM #500 : Immediate 500 LDD 500 : Direct 100 LDI 500 : Indirect 20
9(b) [7 marks]
Instruction Label Opcode Operand LDM #20 STO Twenty LDI Y ADD Twenty STO Z Twenty: #20 Y: Z: mark for LDM #20 seen mark for storing 20 at any address mark for labelling that address e.g. Twenty away from the program code mark for labelling addresses away from the program code as Y and Z mark for correct use of LDI Y mark for correct use of STO Z mark for correct use of ADD with labelled address
State the reasons for including exception handling routines when writing a program.
Include an example of an exception in your answer. 4 marks
Show mark scheme
9 [4 marks]
To trap (some) runtime errors To prevent a program halting unexpectedly To produce meaningful error messages for these errors Example divide by zero // end of file // file not found
(c) State two other uses of a stack. 2 marks
1
2
Show mark scheme
9(a) [3 marks]
LDM #500 : Immediate 500 LDD 500 : Direct 100 LDI 500 : Indirect 20
9(b) [7 marks]
Instruction Label Opcode Operand LDM #20 STO Twenty LDI Y ADD Twenty STO Z Twenty: #20 Y: Z: mark for LDM #20 seen mark for storing 20 at any address mark for labelling that address e.g. Twenty away from the program code mark for labelling addresses away from the program code as Y and Z mark for correct use of LDI Y mark for correct use of STO Z mark for correct use of ADD with labelled address
A computer game is being developed using object-oriented programming.
| One element of the game is a balloon. This is designed as the class Balloon. The class has the following attributes and methods. Balloon | |
|---|---|
Balloon |
Balloon |
Health : INTEGERColour : STRINGDefenceItem : STRING |
The health of the balloon The colour of the balloon The item the balloon uses to defend itself |
Constructor()ChangeHealth()GetDefenceItem()CheckHealth() |
Initialises the defence item and colour using the parameters Initialises health to 100 Takes the change as a parameter and adds this to the health Returns the defence item of the object If the health is 0 or less, it returns TRUE, otherwise itreturns FALSE |
(a) The constructor takes the name of the defence item and the balloon’s colour as parameters and sets these to the attributes. The health is initialised to 100 . 5 marks
Write program code to declare the class Balloon and its constructor. Do not write any other
methods.
Use your language appropriate constructor.
All attributes should be private. If you are writing in Python include attribute declarations using comments.
Save your program as Question2_J2022 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) The get method GetDefenceItem() returns the defence item of the object. 2 marks
Amend your program code to include the get method GetDefenceItem() .
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The object’s method ChangeHealth() takes an integer number as a parameter and adds this to the health attribute of the object. 2 marks
Amend your program code to include the method ChangeHealth() .
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The object’s method CheckHealth() returns TRUE if the health of the object is 0 or less (no health remaining) and returns FALSE otherwise (health remaining). 2 marks
Amend your program code to include the method CheckHealth() .
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) Amend the main program to: 3 marks
take as input a defence item and colour from the user
create a new balloon with the identifier
Balloon1using the data input.
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) The function Defend() : 8 marks
takes a balloon object as a parameter
takes as input the strength of an opponent from the user
uses the
ChangeHealth()method to subtract the strength input from the object’s healthoutputs the defence item of the balloon
checks the health of the object and outputs an appropriate message if it has no health remaining, or if it has health remaining
returns the amended balloon object.
Write program code to declare the function Defend() .
Save your program.
Copy and paste the program code into part 2(f) in the evidence document.
(g) (i) Amend the main program to call the function Defend() . 2 marks
Save your program.
Copy and paste the program code into part 2(g)(i) in the evidence document.
(ii) Test your program using the following inputs: 1 mark
balloon defence method
"Shield"balloon colour
"Red"strength of opponent
50
Take a screenshot to show the output.
Copy and paste the screenshot into part 2(g)(ii) in the evidence document.
Show mark scheme
2(a)
VB.NET Class balloon Private Health As Integer Private Colour As String Private DefenceItem As String Public Sub New(PDefenceItem, PColour) Health = 100 Colour = PColour DefenceItem = PDefenceItem End Sub End Class
2(b) [2 marks]
1 mark per mark point get header and close with no parameter … … returning defence item attribute Example program code: public String GetDefenceItem(){ return DefenceItem; Python def GetDefenceItem(self): return self.__DefenceItem VB.NET Public Function GetDefenceItem() Return DefenceItem End Function
2(c) [2 marks]
1 mark per mark point procedure header and close taking 1 parameter … … adding parameter value to health attribute Example program code: public void ChangeHealth(Integer Change){ Health = Health + Change; Python def ChangeHealth(self, Change): self.__Health = self.__Health + Change VB.NET Public Sub ChangeHealth(Change) Health = Health + Change End Sub
2(d) [2 marks]
1 mark per mark point method header and close and checking if health attribute is <= 0 Returning TRUE if health attribute <= 0 and returning FALSE otherwise Example program code: public Boolean CheckHealth(){ if(Health <= 0){ return true; }else{ return false; Python def CheckHealth(self): if self.__Health <= 0: return True else: return False VB.NET Function CheckHealth() If Health <= 0 Then Return True Else Return False End If End Function
2(e) [3 marks]
1 mark per mark point take as input defence method and colour (2 strings) instantiating new balloon object with identifier Balloon1 … … with both input values as parameters Example program code: public static void main(String[] args){ Scanner scanner = new Scanner(System.in); System.out.println("Enter balloon defence method"); String Method = scanner.nextLine(); System.out.println("Enter the balloon colour"); String Colour = scanner.nextLine(); Balloon Balloon1 = new Balloon(Method, Colour); Python Method = input("Enter balloon defence method ") Colour = input("Enter the balloon colour ") Balloon1 = Balloon(Method, Colour) VB.NET Sub Main() Console.WriteLine("Enter balloon defence method") Dim Method As String = Console.ReadLine Console.WriteLine("Enter the balloons colour") Dim Colour As String = Console.ReadLine Dim Balloon1 As Balloon = New Balloon(Method, Colour) End Sub
2(f)
Python def Defend(MyBalloon): Strength = int(input("Enter the strength of opponent")) MyBalloon.VhangeHealth(-Strength) print("You defended with ", str(MyBalloon.GetDefenceItem())) if(MyBalloon.CheckHealth() == True): print("Defence failed") else: print("Defence succeeded") return MyBalloon VB.NET Function Defend(MyBalloon) Console.WriteLine("Enter the strength of opponent") Dim Strength As Integer = Console.ReadLine MyBalloon.ChangeHealth(-Strength) Console.WriteLine("You defended with " & MyBalloon.GetDefenceItem) If (MyBalloon.CheckHealth() = True) Then Console.WriteLine("Defence failed") Else Console.WriteLine("Defence succeeded") End If Return MyBalloon End Function
2(g)(i) [2 marks]
1 mark each calling Defend with balloon object … … and stores return value over object Example program code: Balloon1 = Defend(Balloon1); Python Balloon1 = Defend(Balloon1) VB.NET Balloon1 = Defend(Balloon1)
2(g)(ii) [1 mark]
1 mark for screenshot with: Shield, Red and 50 input Output stating their defence item was Shield Output says health is not 0 (in some manner)
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. 2 marks
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.
(b) The function Enqueue is written in pseudocode. The function adds DataToAdd to the queue. 7 marks
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.
(c) The function Dequeue() returns "FALSE" if the queue is empty, or it returns the next data item in the queue. 6 marks
Write program code for the function Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document. (d) (i) Amend the main program to: 5 marks
take as input 11 string values from the user
use the
Enqueue()function to add each element to the queueoutput 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.
(ii) Test your program with the input data: 1 mark
"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.
Show mark scheme
3(a) [2 marks]
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: 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
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
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
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)) Console.WriteLine("Successful") Else Console.WriteLine("Unsuccessful") End If Console.WriteLine(Dequeue) Console.WriteLine(Dequeue)
3(d)(ii) [1 mark]
1 mark for showing inputs and outputs: A – J input and successful. K input and unsuccessful. Output: A, B
A 2D array stores data entered by a user.
(a) The main program declares a 2D array of 10 by 10 integer elements. 4 marks
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.
(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. 5 marks
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.
(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. 3 marks
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.
(iii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 2(b)(iii) in the evidence document.
(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() . 8 marks
Save your program.
Copy and paste the program code into part 2(c)(i) in the evidence document.
(ii) In the main program, test the function BinarySearch() twice, outputting the returned value each time. 2 marks
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.
Show mark scheme
2(a)
import java.util.Scanner; import java.util.Random; 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);} } }
2(b)(i)
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; } }
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);
2(b)(iii) [1 mark]
1 mark for output showing array unsorted and then sorted on 1 of the dimensions
2(c)(i)
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 ; }
2(c)(ii) [2 marks]
1 mark per mark point screenshot outputting the index when Number is found screenshot outputting –1 with a Number not found
A programmer is designing a computer game that uses a set of cards.
Each card has a number and a colour. The cards are saved in the text file CardValues.txt
| The program has a class named Card. The class has the following attributes and methods. Card | |
|---|---|
Card |
Card |
| Number : INTEGER Colour : STRING |
The number of the card The colour of the card |
| Constructor() GetNumber() GetColour() |
Takes two values as parameters and sets them to the private attributes Returns the number of the card Returns the colour of the card |
(a) The constructor takes the number and colour of the card as parameters and sets them to the private attributes. 5 marks
Write program code to declare the class Card and its constructor. Do not write any other methods.
Use your programming language appropriate constructor.
All attributes should be private. If you are writing in Python, include attribute declarations using comments.
Save your program as Question3_J22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The two get methods return the associated attribute. 3 marks
Write program code for the get methods GetNumber() and GetColour() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The text file CardValues.txt stores the data for 30 cards, in the order: number, colour. 7 marks
For example, the first card in the text file:
1 is the number
red is the colour.
A 1D array of type Card is declared to store all the cards read in from CardValues.txt
Write the main program to:
declare an array of type Card with 30 elements
read in the data for the 30 cards from CardValues.txt and assign each to the array.
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The program needs to allow all players (maximum of 5) to select 4 cards from the 30 available. 6 marks
A card can only be selected once, so the program needs to record which cards have already been selected.
The function, ChooseCard() :
takes as input an integer to represent an array index from 1 to 30
validates that the value is between 1 and 30 inclusive
checks if the card is available (it has not already been selected)
loops until an available card is selected
returns the index of the card if it is available.
Amend the program to store which cards have already been selected and write program code for the function ChooseCard() .
Save your program.
Copy and paste the program code into part 3(d) in the evidence document.
(e) The main program needs to allow one player to select all their 4 cards.
(i) Amend the main program to: 5 marks
create an array, Player1, for player 1 of type Card
ask player 1 to input 4 integers using the function from part 3(d)
store the cards in Player1
output the number and colour of the 4 cards in Player1 .
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program with the following test data: 1 mark
Test 1: 1 5 9 10
Test 2: 2 2 3 4 4 5
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a)
import java.util.Scanner; import java.io.*; class Card{ private Integer Number; private String Colour; public Card(Integer pNumber, String pColour){ Number = pNumber; Colour = pColour; public static void main(String args[]){
3(b) [3 marks]
1 mark per mark point 1 get method header (and close where appropriate) with no parameter … … returning attribute 2nd correct get method Example program code: VB.NET Function GetNumber() Return Number End Function Function GetColour() Return Colour End Function Python def GetNumber(self): return self.__Number def GetColour(self): return self.__Colour public Integer GetNumber(){ return Number; } public String GetColour(){ return Colour; }
3(c)
catch(FileNotFoundException ex){ System.out.println("No file found"); } catch(IOException ex){ System.out.println("No file found"); }
3(d)
public static Boolean[] NumbersChosen = new Boolean[30]; public Integer chooseCard (){ Boolean flagContinue = true; Integer CardSelected = -1; while(flagContinue){ System.out.println("Select a Card from 1 to 30"); Scanner scanner = new Scanner(System.in); CardSelected = Integer.parseInt(scanner.nextLine()); if(CardSelected < 1 || CardSelected > 30){ System.out.println("Number must be between 1 and 30"); }else if(NumbersChosen[CardSelected - 1]){ System.out.println("Already taken"); }else{ System.out.println("Valid"); flagContinue = false; } } NumbersChosen[CardSelected - 1] = true; return CardSelected - 1;
3(e)(i)
Card[] Player1 = new Card[5]; for(Integer x = 0; x < 5; x++){ Player1[x] = CardArray[ChooseCard()]; for(Integer x = 0; x < 5; x++){ System.out.println(Player1[x].GetColour()); System.out.println(Player1[x].GetNumber());
3(e)(ii)
Test 2 e.g.
A computer game is being developed using object-oriented programming.
| One element of the game is a balloon. This is designed as the class Balloon. The class has the following attributes and methods. Balloon | |
|---|---|
Balloon |
Balloon |
Health : INTEGERColour : STRINGDefenceItem : STRING |
The health of the balloon The colour of the balloon The item the balloon uses to defend itself |
Constructor()ChangeHealth()GetDefenceItem()CheckHealth() |
Initialises the defence item and colour using the parameters Initialises health to 100 Takes the change as a parameter and adds this to the health Returns the defence item of the object If the health is 0 or less, it returns TRUE, otherwise itreturns FALSE |
(a) The constructor takes the name of the defence item and the balloon’s colour as parameters and sets these to the attributes. The health is initialised to 100 . 5 marks
Write program code to declare the class Balloon and its constructor. Do not write any other
methods.
Use your language appropriate constructor.
All attributes should be private. If you are writing in Python include attribute declarations using comments.
Save your program as Question2_J2022 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) The get method GetDefenceItem() returns the defence item of the object. 2 marks
Amend your program code to include the get method GetDefenceItem() .
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The object’s method ChangeHealth() takes an integer number as a parameter and adds this to the health attribute of the object. 2 marks
Amend your program code to include the method ChangeHealth() .
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The object’s method CheckHealth() returns TRUE if the health of the object is 0 or less (no health remaining) and returns FALSE otherwise (health remaining). 2 marks
Amend your program code to include the method CheckHealth() .
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) Amend the main program to: 3 marks
take as input a defence item and colour from the user
create a new balloon with the identifier
Balloon1using the data input.
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) The function Defend() : 8 marks
takes a balloon object as a parameter
takes as input the strength of an opponent from the user
uses the
ChangeHealth()method to subtract the strength input from the object’s healthoutputs the defence item of the balloon
checks the health of the object and outputs an appropriate message if it has no health remaining, or if it has health remaining
returns the amended balloon object.
Write program code to declare the function Defend() .
Save your program.
Copy and paste the program code into part 2(f) in the evidence document.
(g) (i) Amend the main program to call the function Defend() . 2 marks
Save your program.
Copy and paste the program code into part 2(g)(i) in the evidence document.
(ii) Test your program using the following inputs: 1 mark
balloon defence method
"Shield"balloon colour
"Red"strength of opponent
50
Take a screenshot to show the output.
Copy and paste the screenshot into part 2(g)(ii) in the evidence document.
Show mark scheme
2(a)
VB.NET Class balloon Private Health As Integer Private Colour As String Private DefenceItem As String Public Sub New(PDefenceItem, PColour) Health = 100 Colour = PColour DefenceItem = PDefenceItem End Sub End Class
2(b) [2 marks]
1 mark per mark point get header and close with no parameter … … returning defence item attribute Example program code: public String GetDefenceItem(){ return DefenceItem; Python def GetDefenceItem(self): return self.__DefenceItem VB.NET Public Function GetDefenceItem() Return DefenceItem End Function
2(c) [2 marks]
1 mark per mark point procedure header and close taking 1 parameter … … adding parameter value to health attribute Example program code: public void ChangeHealth(Integer Change){ Health = Health + Change; Python def ChangeHealth(self, Change): self.__Health = self.__Health + Change VB.NET Public Sub ChangeHealth(Change) Health = Health + Change End Sub
2(d) [2 marks]
1 mark per mark point method header and close and checking if health attribute is <= 0 Returning TRUE if health attribute <= 0 and returning FALSE otherwise Example program code: public Boolean CheckHealth(){ if(Health <= 0){ return true; }else{ return false; Python def CheckHealth(self): if self.__Health <= 0: return True else: return False VB.NET Function CheckHealth() If Health <= 0 Then Return True Else Return False End If End Function
2(e) [3 marks]
1 mark per mark point take as input defence method and colour (2 strings) instantiating new balloon object with identifier Balloon1 … … with both input values as parameters Example program code: public static void main(String[] args){ Scanner scanner = new Scanner(System.in); System.out.println("Enter balloon defence method"); String Method = scanner.nextLine(); System.out.println("Enter the balloon colour"); String Colour = scanner.nextLine(); Balloon Balloon1 = new Balloon(Method, Colour); Python Method = input("Enter balloon defence method ") Colour = input("Enter the balloon colour ") Balloon1 = Balloon(Method, Colour) VB.NET Sub Main() Console.WriteLine("Enter balloon defence method") Dim Method As String = Console.ReadLine Console.WriteLine("Enter the balloons colour") Dim Colour As String = Console.ReadLine Dim Balloon1 As Balloon = New Balloon(Method, Colour) End Sub
2(f)
Python def Defend(MyBalloon): Strength = int(input("Enter the strength of opponent")) MyBalloon.VhangeHealth(-Strength) print("You defended with ", str(MyBalloon.GetDefenceItem())) if(MyBalloon.CheckHealth() == True): print("Defence failed") else: print("Defence succeeded") return MyBalloon VB.NET Function Defend(MyBalloon) Console.WriteLine("Enter the strength of opponent") Dim Strength As Integer = Console.ReadLine MyBalloon.ChangeHealth(-Strength) Console.WriteLine("You defended with " & MyBalloon.GetDefenceItem) If (MyBalloon.CheckHealth() = True) Then Console.WriteLine("Defence failed") Else Console.WriteLine("Defence succeeded") End If Return MyBalloon End Function
2(g)(i) [2 marks]
1 mark each calling Defend with balloon object … … and stores return value over object Example program code: Balloon1 = Defend(Balloon1); Python Balloon1 = Defend(Balloon1) VB.NET Balloon1 = Defend(Balloon1)
2(g)(ii) [1 mark]
1 mark for screenshot with: Shield, Red and 50 input Output stating their defence item was Shield Output says health is not 0 (in some manner)
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. 2 marks
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.
(b) The function Enqueue is written in pseudocode. The function adds DataToAdd to the queue. 7 marks
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.
(c) The function Dequeue() returns "FALSE" if the queue is empty, or it returns the next data item in the queue. 6 marks
Write program code for the function Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document. (d) (i) Amend the main program to: 5 marks
take as input 11 string values from the user
use the
Enqueue()function to add each element to the queueoutput 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.
(ii) Test your program with the input data: 1 mark
"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.
Show mark scheme
3(a) [2 marks]
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: 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
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
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
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)) Console.WriteLine("Successful") Else Console.WriteLine("Unsuccessful") End If Console.WriteLine(Dequeue) Console.WriteLine(Dequeue)
3(d)(ii) [1 mark]
1 mark for showing inputs and outputs: A – J input and successful. K input and unsuccessful. Output: A, B
(a) The diagram shown represents an artificial neural network.
Layer 1 Hidden Layer 2
Layer 3
(i) State the reason for having multiple hidden layers in an artificial neural network. 1 mark
(ii) Explain how artificial neural networks enable machine learning. 4 marks
(b) Find the shortest path between the Home and School nodes using the A* algorithm. 5 marks 3 marks
Show your working in the table provided.
The first two rows in the table have been completed.
| Node | Cost from Home node (g) | Heuristic (h) | Total (f = g + h) |
|---|---|---|---|
| Home | 0 | 14 | 14 |
| A | 1 | 10 | 11 |
Final path 10 (a) State three essential features of recursion .
1
2
3
(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion. 3 marks
(c) Identify two ADTs other than a stack. 2 marks
1
2
(d) The function StackFull() checks whether a stack is full. 5 marks
The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.
FUNCTION StackFull() RETURNS BOOLEAN
IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
An algorithm AddInteger is required to add a new integer data element to a stack.
The stack is implemented as an array ArrayStack .
The function AddInteger() calls StackFull() and returns an appropriate message.
Complete the pseudocode for the function AddInteger() .
FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING
ENDFUNCTION
Show mark scheme
9(a)(i) [1 mark]
One mark for correct statement (Max 1) Enables deep learning to take place • Where the problem you are trying to solve has a higher level of • complexity it requires more layers to solve To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. •
9(a)(ii) [4 marks]
One mark for each correct marking point (Max 4) Artificial neural networks are intended to replicate the way human brains • work Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where • characteristics are extracted / outputs are calculated … this process of training / learning is repeated many times to achieve • optimum outputs // reinforcement learning takes place Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have • been made.
9(b) [5 marks]
One mark for each correct calculation as follows (Max 4) Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) • One mark for correct path (Max 1) : Home School • Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home School
Show mark scheme
10(a) [3 marks]
One mark for each correct marking point (Max 3) Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case • Unwinding can occur once the base case is reached.
10(b) [2 marks]
One mark for each correct marking point (Max 3) A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding • … to maintain the required order.
10(c) [5 marks]
One mark for each marking point (Max 2) Linked List • Queue • Binary Tree
10(d)
One mark for each marking point (Max 5) Checking if stack is full / empty using • IF … THEN … (ELSE) … ENDIF … correctly using function • StackFull() suitable message if stack is full • RETURN message if space available on stack • RETURN Incrementing pointer if space available • TopOfStack Assigning new data using correct variable • NewInteger … to correct the array element in array. • ArrayStack[] Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE ← TopOfStack TopOfStack + 1 ← ArrayStack[TopOfStack] NewInteger RETURN "Item added" ENDIF ENDFUNCTION
(a) The diagram shown represents an artificial neural network.
Layer 1 Hidden Layer 2
Layer 3
(i) State the reason for having multiple hidden layers in an artificial neural network. 1 mark
(ii) Explain how artificial neural networks enable machine learning. 4 marks
(b) Find the shortest path between the Home and School nodes using the A* algorithm. 5 marks 3 marks
Show your working in the table provided.
The first two rows in the table have been completed.
| Node | Cost from Home node (g) | Heuristic (h) | Total (f = g + h) |
|---|---|---|---|
| Home | 0 | 14 | 14 |
| A | 1 | 10 | 11 |
Final path 10 (a) State three essential features of recursion .
1
2
3
(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion. 3 marks
(c) Identify two ADTs other than a stack. 2 marks
1
2
(d) The function StackFull() checks whether a stack is full. 5 marks
The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.
FUNCTION StackFull() RETURNS BOOLEAN
IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
An algorithm AddInteger is required to add a new integer data element to a stack.
The stack is implemented as an array ArrayStack .
The function AddInteger() calls StackFull() and returns an appropriate message.
Complete the pseudocode for the function AddInteger() .
FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING
ENDFUNCTION
Show mark scheme
9(a)(i) [1 mark]
One mark for correct statement (Max 1) Enables deep learning to take place • Where the problem you are trying to solve has a higher level of • complexity it requires more layers to solve To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. •
9(a)(ii) [4 marks]
One mark for each correct marking point (Max 4) Artificial neural networks are intended to replicate the way human brains • work Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where • characteristics are extracted / outputs are calculated … this process of training / learning is repeated many times to achieve • optimum outputs // reinforcement learning takes place Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have • been made.
9(b) [5 marks]
One mark for each correct calculation as follows (Max 4) Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) • One mark for correct path (Max 1) : Home School • Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home School
Show mark scheme
10(a) [3 marks]
One mark for each correct marking point (Max 3) Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case • Unwinding can occur once the base case is reached.
10(b) [2 marks]
One mark for each correct marking point (Max 3) A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding • … to maintain the required order.
10(c) [5 marks]
One mark for each marking point (Max 2) Linked List • Queue • Binary Tree
10(d)
One mark for each marking point (Max 5) Checking if stack is full / empty using • IF … THEN … (ELSE) … ENDIF … correctly using function • StackFull() suitable message if stack is full • RETURN message if space available on stack • RETURN Incrementing pointer if space available • TopOfStack Assigning new data using correct variable • NewInteger … to correct the array element in array. • ArrayStack[] Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE ← TopOfStack TopOfStack + 1 ← ArrayStack[TopOfStack] NewInteger RETURN "Item added" ENDIF ENDFUNCTION
An ordered binary tree stores integer data in ascending numerical order.
The data for the binary tree is stored in a 2D array with the following structure:
| LeftPointer [0] | Data [1] | RightPointer [2] |
|---|---|---|
1 |
10 |
2 |
-1 |
5 |
-1 |
-1 |
16 |
-1 |
Each row in the table represents one node on the tree.
The number -1 represents a null pointer.
(a) The 2D array, ArrayNodes, is declared with space for 20 nodes. 4 marks
Each node has a left pointer, data and right pointer.
The program also initialises the:
RootPointerto-1(null); this points to the first node in the binary treeFreeNodeto0; this points to the first empty node in the array.
Write program code to declare ArrayNodes, RootPointer and FreeNode in the main
program.
If you are writing in Python programming language, include attribute declarations using comments.
Save your program as question 3 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The procedure AddNode() adds a new node to the array ArrayNodes . 8 marks
The procedure needs to:
take the array, root pointer and free node pointer as parameters
ask the user to enter the data and read this in
add the node to the root pointer if the tree is empty
otherwise, follow the pointers to find the position for the data item to be added
store the data in the location and update all pointers.
There are six incomplete statements in the following pseudocode for the procedure AddNode() .
PROCEDURE AddNode(BYREF ArrayNodes[] : ARRAY OF INTEGER,
BYREF RootPointer : INTEGER, BYREF FreeNode : INTEGER)
OUTPUT "Enter the data"
INPUT NodeData
IF FreeNode <= 19 THEN
ArrayNodes[FreeNode, 0] -1
# ←
ArrayNodes[FreeNode, 1] ………………………………………
# ←
ArrayNodes[FreeNode, 2] -1
# ←
IF RootPointer = ……………………………………… THEN
RootPointer 0
# ←
ELSE
Placed FALSE
# ←
CurrentNode RootPointer
# ←
WHILE Placed = FALSE
IF NodeData < ArrayNodes[CurrentNode, 1] THEN
IF ArrayNodes[CurrentNode, 0] = -1 THEN
ArrayNodes[CurrentNode, 0] ………………………………………
# ←
Placed TRUE
# ←
ELSE
……………………………………… ArrayNodes[CurrentNode, 0]
# ←
ENDIF
ELSE
IF ArrayNodes[CurrentNode, 2] = -1 THEN
ArrayNodes[CurrentNode, 2] FreeNode
# ←
Placed ………………………………………
# ←
ELSE
CurrentNode ArrayNodes[CurrentNode, 2]
# ←
ENDIF
ENDIF
ENDWHILE
ENDIF
FreeNode ……………………………………… + 1
# ←
ELSE
OUTPUT("Tree is full")
ENDIF
ENDPROCEDURE
Write program code for the procedure AddNode() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The procedure PrintAll() outputs the data in each element in ArrayNodes, in the order they are stored in the array. 4 marks
Each element is printed in a row in the order:
LeftPointer Data RightPointer
For example:
1 20 -1
-1 10 -1
Write program code for the procedure PrintAll() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The main program should loop 10 times, each time calling the procedure AddNode() . It should then call the procedure PrintAll() .
(i) Edit the main program to perform the actions described. 3 marks
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Test the program by entering the data: 1 mark
Take a screenshot to show the output after the given data are entered.
Copy and paste the screenshot into part 3(d)(ii) in the evidence document.
(e) An in-order tree traversal visits the left node, then the root (and outputs this), then visits the right node.
(i) Write a recursive procedure, InOrder(), to perform an in-order traversal on the tree held in ArrayNodes . 7 marks
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test the procedure InOrder() with the same data entered in part (d)(ii) . 1 mark
Take a screenshot to show the output after entering the data.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [8 marks]
1 mark per bullet point Declaring array named of type integer • ArrayNodes …with 20 by 3 elements • declared as integer and assigned -1 • RootPointer declared as integer and assigned 0 • FreeNode Example program code: Python ArrayNodes=[[0 for X in range(3)] for Y in range(20)] RootPointer = -1 FreeNode = 0 VB.NET Sub Main() Dim ArrayNodes(19, 2) As Integer Dim RootPointer As Integer = -1 Dim FreeNode As Integer = 0 End Sub Java public static Integer[][] ArrayNodes = new Integer[20][3]; public static Integer RootPointer = -1; public static Integer FreeNode = 0;
3(b) [4 marks]
Java public static void AddNode(){ System.out.println("Enter the Data"); Integer NodeData; Scanner in = new Scanner(System.in); NodeData = in.nextInt(); if(FreeNode <= 19){ ArrayNodes[FreeNode][0] = -1; ArrayNodes[FreeNode][1] = NodeData; ArrayNodes[FreeNode][2] = -1; if (RootPointer == -1){ RootPointer = 0; }else{ Boolean Placed = false; Integer CurrentNode = RootPointer; while(Placed == false){ if (NodeData < ArrayNodes[CurrentNode][1]){ if (ArrayNodes[CurrentNode][0] == -1){ ArrayNodes[CurrentNode][0] = FreeNode; Placed = true; }else{ CurrentNode = ArrayNodes[CurrentNode][0]; } }else{ if (ArrayNodes[CurrentNode][2] == -1){ ArrayNodes[CurrentNode][2] = FreeNode; Placed = true; }else{ CurrentNode = ArrayNodes[CurrentNode][2]; } } } } FreeNode = FreeNode + 1; }else{ System.out.println("Tree is full"); } }
3(c) [3 marks]
1 mark per bullet point procedure header (and end, take array as parameter) • Loops through all array elements // loops 20 times • Prints data in index 0, 1, 2 in each array element… • … in the correct order and format (spaces between) • Example program code: Python def PrintAll(ArrayNodes): for X in range(0, 20): print(str(ArrayNodes[X][0]), " ", str(ArrayNodes[X][1]), " ", str(ArrayNodes[X][2])) VB.NET Sub PrintAll(ByRef ArrayNodes) For X = 0 To 19 Console.WriteLine(ArrayNodes(X, 0) & " " & ArrayNodes(X,
- & " " & ArrayNodes(X, 2)) Next End Sub Java public static void PrintAll(){ for(int X = 0; X < 20; X++){ System.out.println(ArrayNodes[X][0] + " " + ArrayNodes[X][1] + " " + ArrayNodes[X][2]); } }
3(d)(i) [1 mark]
1 mark per bullet point looping 10 times • calling 10 times (check parameters in 3b) • AddNode calling outside of loop (check parameters in 3c) • PrintAll Example program code: Python for X in range(0,10): ArrayNodes, RootPointer, FreeNode = AddNode(ArrayNodes,RootPointer,FreeNode) PrintAll(ArrayNodes) VB.NET For X = 0 To 9 AddNode(ArrayNodes, RootPointer, FreeNode) Next printall(ArrayNodes) Java for (int X = 0; X < 10; X++){ AddNode(); } PrintAll();
3(d)(ii) [7 marks]
1 mark for screenshot showing the following output: 1 10 2 9 5 3 4 15 6 5 8 8 7 12 −1 −1 6 −1 −1 20 −1 −1 11 −1 −1 9 −1 −1 4 −1
3(e)(i) [1 mark]
1 mark per bullet point procedure name taking a parameter (for current node being • InOrder accessed) Checking if left Node is empty (−1) • ….(if not) calling procedure recursively with [Current Node][0] as parameter • outputting the [Current Node][1] • checking if right Node is empty (−1) • …(if not) calling procedure recursively with [Current Node][2] as a parameter • Order is correct, left, root, right • Example program code: Python def InOrder(ArrayNodes, RootNode): if ArrayNodes[RootNode][0] != -1: InOrder(ArrayNodes, ArrayNodes[RootNode][0]) print(str(ArrayNodes[RootNode][1])) if ArrayNodes[RootNode][2] != -1: InOrder(ArrayNodes, ArrayNodes[RootNode][2]) VB.NET Sub InOrder(ArrayNodes, RootNode) If ArrayNodes(RootNode, 0) <> -1 Then InOrder(ArrayNodes, ArrayNodes(RootNode, 0)) End If Console.WriteLine(ArrayNodes(RootNode, 1)) If ArrayNodes(RootNode, 2) <> -1 Then InOrder(ArrayNodes, ArrayNodes(RootNode, 2)) End If End Sub Java public static void InOrder(Integer Root){ if (ArrayNodes[Root][0] != -1){ InOrder(ArrayNodes[Root][0]); } System.out.println(ArrayNodes[Root][1]); if(ArrayNodes[Root][2] != -1){ InOrder(ArrayNodes[Root][2]); } }
3(e)(ii)
1 mark showing output:
An ordered binary tree stores integer data in ascending numerical order.
The data for the binary tree is stored in a 2D array with the following structure:
| LeftPointer [0] | Data [1] | RightPointer [2] |
|---|---|---|
1 |
10 |
2 |
-1 |
5 |
-1 |
-1 |
16 |
-1 |
Each row in the table represents one node on the tree.
The number -1 represents a null pointer.
(a) The 2D array, ArrayNodes, is declared with space for 20 nodes. 4 marks
Each node has a left pointer, data and right pointer.
The program also initialises the:
RootPointerto-1(null); this points to the first node in the binary treeFreeNodeto0; this points to the first empty node in the array.
Write program code to declare ArrayNodes, RootPointer and FreeNode in the main
program.
If you are writing in Python programming language, include attribute declarations using comments.
Save your program as question 3 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The procedure AddNode() adds a new node to the array ArrayNodes . 8 marks
The procedure needs to:
take the array, root pointer and free node pointer as parameters
ask the user to enter the data and read this in
add the node to the root pointer if the tree is empty
otherwise, follow the pointers to find the position for the data item to be added
store the data in the location and update all pointers.
There are six incomplete statements in the following pseudocode for the procedure AddNode() .
PROCEDURE AddNode(BYREF ArrayNodes[] : ARRAY OF INTEGER,
BYREF RootPointer : INTEGER, BYREF FreeNode : INTEGER)
OUTPUT "Enter the data"
INPUT NodeData
IF FreeNode <= 19 THEN
ArrayNodes[FreeNode, 0] -1
# ←
ArrayNodes[FreeNode, 1] ………………………………………
# ←
ArrayNodes[FreeNode, 2] -1
# ←
IF RootPointer = ……………………………………… THEN
RootPointer 0
# ←
ELSE
Placed FALSE
# ←
CurrentNode RootPointer
# ←
WHILE Placed = FALSE
IF NodeData < ArrayNodes[CurrentNode, 1] THEN
IF ArrayNodes[CurrentNode, 0] = -1 THEN
ArrayNodes[CurrentNode, 0] ………………………………………
# ←
Placed TRUE
# ←
ELSE
……………………………………… ArrayNodes[CurrentNode, 0]
# ←
ENDIF
ELSE
IF ArrayNodes[CurrentNode, 2] = -1 THEN
ArrayNodes[CurrentNode, 2] FreeNode
# ←
Placed ………………………………………
# ←
ELSE
CurrentNode ArrayNodes[CurrentNode, 2]
# ←
ENDIF
ENDIF
ENDWHILE
ENDIF
FreeNode ……………………………………… + 1
# ←
ELSE
OUTPUT "Tree is full"
ENDIF
ENDPROCEDURE
Write program code for the procedure AddNode() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The procedure PrintAll() outputs the data in each element in ArrayNodes, in the order they are stored in the array. 4 marks
Each element is printed in a row in the order:
LeftPointer Data RightPointer
For example:
1 20 -1
-1 10 -1
Write program code for the procedure PrintAll() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The main program should loop 10 times, each time calling the procedure AddNode() . It should then call the procedure PrintAll() .
(i) Edit the main program to perform the actions described. 3 marks
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Test the program by entering the data: 1 mark
Take a screenshot to show the output after the given data are entered.
Copy and paste the screenshot into part 3(d)(ii) in the evidence document.
(e) An in-order tree traversal visits the left node, then the root (and outputs this), then visits the right node.
(i) Write a recursive procedure, InOrder(), to perform an in-order traversal on the tree held in ArrayNodes . 7 marks
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test the procedure InOrder() with the same data entered in part (d)(ii) . 1 mark
Take a screenshot to show the output after entering the data.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [8 marks]
1 mark per bullet point Declaring array named of type integer • ArrayNodes …with 20 by 3 elements • declared as integer and assigned -1 • RootPointer declared as integer and assigned 0 • FreeNode Example program code: Python ArrayNodes=[[0 for X in range(3)] for Y in range(20)] RootPointer = -1 FreeNode = 0 VB.NET Sub Main() Dim ArrayNodes(19, 2) As Integer Dim RootPointer As Integer = -1 Dim FreeNode As Integer = 0 End Sub Java public static Integer[][] ArrayNodes = new Integer[20][3]; public static Integer RootPointer = -1; public static Integer FreeNode = 0;
3(b) [4 marks]
Java public static void AddNode(){ System.out.println("Enter the Data"); Integer NodeData; Scanner in = new Scanner(System.in); NodeData = in.nextInt(); if(FreeNode <= 19){ ArrayNodes[FreeNode][0] = -1; ArrayNodes[FreeNode][1] = NodeData; ArrayNodes[FreeNode][2] = -1; if (RootPointer == -1){ RootPointer = 0; }else{ Boolean Placed = false; Integer CurrentNode = RootPointer; while(Placed == false){ if (NodeData < ArrayNodes[CurrentNode][1]){ if (ArrayNodes[CurrentNode][0] == -1){ ArrayNodes[CurrentNode][0] = FreeNode; Placed = true; }else{ CurrentNode = ArrayNodes[CurrentNode][0]; } }else{ if (ArrayNodes[CurrentNode][2] == -1){ ArrayNodes[CurrentNode][2] = FreeNode; Placed = true; }else{ CurrentNode = ArrayNodes[CurrentNode][2]; } } } } FreeNode = FreeNode + 1; }else{ System.out.println("Tree is full"); } }
3(c) [3 marks]
1 mark per bullet point procedure header (and end, take array as parameter) • Loops through all array elements // loops 20 times • Prints data in index 0, 1, 2 in each array element… • … in the correct order and format (spaces between) • Example program code: Python def PrintAll(ArrayNodes): for X in range(0, 20): print(str(ArrayNodes[X][0]), " ", str(ArrayNodes[X][1]), " ", str(ArrayNodes[X][2])) VB.NET Sub PrintAll(ByRef ArrayNodes) For X = 0 To 19 Console.WriteLine(ArrayNodes(X, 0) & " " & ArrayNodes(X,
- & " " & ArrayNodes(X, 2)) Next End Sub Java public static void PrintAll(){ for(int X = 0; X < 20; X++){ System.out.println(ArrayNodes[X][0] + " " + ArrayNodes[X][1] + " " + ArrayNodes[X][2]); } }
3(d)(i) [1 mark]
1 mark per bullet point looping 10 times • calling 10 times (check parameters in 3b) • AddNode calling outside of loop (check parameters in 3c) • PrintAll Example program code: Python for X in range(0,10): ArrayNodes, RootPointer, FreeNode = AddNode(ArrayNodes,RootPointer,FreeNode) PrintAll(ArrayNodes) VB.NET For X = 0 To 9 AddNode(ArrayNodes, RootPointer, FreeNode) Next printall(ArrayNodes) Java for (int X = 0; X < 10; X++){ AddNode(); } PrintAll();
3(d)(ii) [7 marks]
1 mark for screenshot showing the following output: 1 10 2 9 5 3 4 15 6 5 8 8 7 12 −1 −1 6 −1 −1 20 −1 −1 11 −1 −1 9 −1 −1 4 −1
3(e)(i) [1 mark]
1 mark per bullet point procedure name taking a parameter (for current node being • InOrder accessed) Checking if left Node is empty (−1) • ….(if not) calling procedure recursively with [Current Node][0] as parameter • outputting the [Current Node][1] • checking if right Node is empty (−1) • …(if not) calling procedure recursively with [Current Node][2] as a parameter • Order is correct, left, root, right • Example program code: Python def InOrder(ArrayNodes, RootNode): if ArrayNodes[RootNode][0] != -1: InOrder(ArrayNodes, ArrayNodes[RootNode][0]) print(str(ArrayNodes[RootNode][1])) if ArrayNodes[RootNode][2] != -1: InOrder(ArrayNodes, ArrayNodes[RootNode][2]) VB.NET Sub InOrder(ArrayNodes, RootNode) If ArrayNodes(RootNode, 0) <> -1 Then InOrder(ArrayNodes, ArrayNodes(RootNode, 0)) End If Console.WriteLine(ArrayNodes(RootNode, 1)) If ArrayNodes(RootNode, 2) <> -1 Then InOrder(ArrayNodes, ArrayNodes(RootNode, 2)) End If End Sub Java public static void InOrder(Integer Root){ if (ArrayNodes[Root][0] != -1){ InOrder(ArrayNodes[Root][0]); } System.out.println(ArrayNodes[Root][1]); if(ArrayNodes[Root][2] != -1){ InOrder(ArrayNodes[Root][2]); } }
3(e)(ii)
1 mark showing output:
(a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. 5 marks
Show your working and write your answers in the table provided.
Working
| Answers | |||||
|---|---|---|---|---|---|
| Town 1 | Town 2 | Town 3 | Town 4 | Town 5 | Town 6 |
Show mark scheme
5(a) [5 marks]
Working (Max 3) May be seen on diagram Initialisation: setting Base to 0 • … and the rest of the towns to • ∞ Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ • May be seen in working section of paper Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least • one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8
5(b) [3 marks]
One mark for each correct marking point (Max 3) Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide • relationships between nodes AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression • methods
(a) State two factors that may affect the performance of a sorting algorithm. 2 marks
(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a onedimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. 6 marks
…
…
YearSize 249
Flag TRUE
# ←
WHILE Flag = TRUE
Flag FALSE
# ←
|hown.||
|---|---|
|**Name**|**Name**|
|**1**|**2**|
|Smithfield|Tom|
|Johnson|Jane|
|||
|Peters|Jade|
|Allen|John|
FOR Student 1 TO YearSize - 1
# ←
IF Score[Student] < Score[Student + 1] THEN
Temp1 Score[Student]
# ←
Temp2 Name[Student,1]
# ←
Temp3 Name[Student,2]
# ←
Score[Student] Score[Student + 1]
# ←
Name[Student,1] Name[Student + 1,1]
# ←
Name[Student,2] Name[Student + 1,2]
# ←
Score[Student + 1] Temp1
# ←
Name[Student + 1,1] Temp2
# ←
Name[Student + 1,2] Temp3
# ←
Flag TRUE
# ←
ENDIF
NEXT Student
ENDWHILE
Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.
Show mark scheme
8(a) [6 marks]
One mark for each correct marking point (Max 2) The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm •
8(b) [2 marks]
One mark for each marking point (max 6) MP1 Use of loop to cycle through the whole year group FOR MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of loop with correct exit clause WHILE MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm ← YearSize 249 ← FOR Student 2 to YearSize ← Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Counter Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 ← Score[Counter] Score[Counter - 1] ← Name[Counter,1] Name[Counter - 1,1] ← Name[Counter,2] Name[Counter - 1,2] ← Counter Counter – 1 ENDWHILE ← Score[Counter] Temp1 ← Name[Counter,1] Temp2 ← Name[Counter,2] Temp3 NEXT Student
(a) Describe what is meant by an imperative (procedural) programming language. 2 marks 2 marks
(b) Describe what is meant by a declarative programming language. 4 marks
| (c) Identify the programming paradigm for eac | ch of these program code examples. |
|---|---|
| Program code example | Programming paradigm |
male(john).female(ethel).parent(john, ethel). |
|
FOR Counter = 1 TO 20 X = X * CounterNEXT Counter |
|
Start: LDD Counter INC ACC STO Counter |
|
public class Vehicle{ private speed; public Vehicle() { speed = 0; }} |
Show mark scheme
9(a)
One mark for each correct marking point (Max 2) Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to • perform … in the order written / given • … each line of code changes something in the program run. •
9(b) [2 marks]
One mark for each correct marking point (Max 2) Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a • mathematical style
9(c) [4 marks]
One mark for each correct programming paradigm (Max 4) Program code example Programming paradigm male(john). Declarative female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 Procedural / imperative X = X * Counter NEXT Counter Start: LDD Counter Low-level / assembly INC ACC STO Counter public class Vehicle { private speed; public Vehicle() Object oriented / (OOP) { speed = 0; } }
(a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. 5 marks
Show your working and write your answers in the table provided.
Working
| Answers | |||||
|---|---|---|---|---|---|
| Town 1 | Town 2 | Town 3 | Town 4 | Town 5 | Town 6 |
Show mark scheme
5(a) [5 marks]
Working (Max 3) May be seen on diagram Initialisation: setting Base to 0 • … and the rest of the towns to • ∞ Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ • May be seen in working section of paper Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least • one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8
5(b) [3 marks]
One mark for each correct marking point (Max 3) Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide • relationships between nodes AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression • methods
(a) State two factors that may affect the performance of a sorting algorithm. 2 marks
(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a onedimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. 6 marks
…
…
YearSize 249
Flag TRUE
# ←
WHILE Flag = TRUE
Flag FALSE
# ←
|hown.||
|---|---|
|**Name**|**Name**|
|**1**|**2**|
|Smithfield|Tom|
|Johnson|Jane|
|||
|Peters|Jade|
|Allen|John|
FOR Student 1 TO YearSize - 1
# ←
IF Score[Student] < Score[Student + 1] THEN
Temp1 Score[Student]
# ←
Temp2 Name[Student,1]
# ←
Temp3 Name[Student,2]
# ←
Score[Student] Score[Student + 1]
# ←
Name[Student,1] Name[Student + 1,1]
# ←
Name[Student,2] Name[Student + 1,2]
# ←
Score[Student + 1] Temp1
# ←
Name[Student + 1,1] Temp2
# ←
Name[Student + 1,2] Temp3
# ←
Flag TRUE
# ←
ENDIF
NEXT Student
ENDWHILE
Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.
Show mark scheme
8(a) [6 marks]
One mark for each correct marking point (Max 2) The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm •
8(b) [2 marks]
One mark for each marking point (max 6) MP1 Use of loop to cycle through the whole year group FOR MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of loop with correct exit clause WHILE MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm ← YearSize 249 ← FOR Student 2 to YearSize ← Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Counter Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 ← Score[Counter] Score[Counter - 1] ← Name[Counter,1] Name[Counter - 1,1] ← Name[Counter,2] Name[Counter - 1,2] ← Counter Counter – 1 ENDWHILE ← Score[Counter] Temp1 ← Name[Counter,1] Temp2 ← Name[Counter,2] Temp3 NEXT Student
(a) Describe what is meant by an imperative (procedural) programming language. 2 marks 2 marks
(b) Describe what is meant by a declarative programming language. 4 marks
| (c) Identify the programming paradigm for eac | ch of these program code examples. |
|---|---|
| Program code example | Programming paradigm |
male(john).female(ethel).parent(john, ethel). |
|
FOR Counter = 1 TO 20 X = X * CounterNEXT Counter |
|
Start: LDD Counter INC ACC STO Counter |
|
public class Vehicle{ private speed; public Vehicle() { speed = 0; }} |
Show mark scheme
9(a)
One mark for each correct marking point (Max 2) Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to • perform … in the order written / given • … each line of code changes something in the program run. •
9(b) [2 marks]
One mark for each correct marking point (Max 2) Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a • mathematical style
9(c) [4 marks]
One mark for each correct programming paradigm (Max 4) Program code example Programming paradigm male(john). Declarative female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 Procedural / imperative X = X * Counter NEXT Counter Start: LDD Counter Low-level / assembly INC ACC STO Counter public class Vehicle { private speed; public Vehicle() Object oriented / (OOP) { speed = 0; } }
(a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. 5 marks
Show your working and write your answers in the table provided.
Working
| Answers | |||||
|---|---|---|---|---|---|
| Town 1 | Town 2 | Town 3 | Town 4 | Town 5 | Town 6 |
Show mark scheme
5(a) [5 marks]
Working (Max 3) May be seen on diagram Initialisation: setting Base to 0 • … and the rest of the towns to • ∞ Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ • May be seen in working section of paper Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least • one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8
5(b) [3 marks]
One mark for each correct marking point (Max 3) Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide • relationships between nodes AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression • methods
(a) State two factors that may affect the performance of a sorting algorithm. 2 marks
(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a onedimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. 6 marks
…
…
YearSize 249
Flag TRUE
# ←
WHILE Flag = TRUE
Flag FALSE
# ←
|hown.||
|---|---|
|**Name**|**Name**|
|**1**|**2**|
|Smithfield|Tom|
|Johnson|Jane|
|||
|Peters|Jade|
|Allen|John|
FOR Student 1 TO YearSize - 1
# ←
IF Score[Student] < Score[Student + 1] THEN
Temp1 Score[Student]
# ←
Temp2 Name[Student,1]
# ←
Temp3 Name[Student,2]
# ←
Score[Student] Score[Student + 1]
# ←
Name[Student,1] Name[Student + 1,1]
# ←
Name[Student,2] Name[Student + 1,2]
# ←
Score[Student + 1] Temp1
# ←
Name[Student + 1,1] Temp2
# ←
Name[Student + 1,2] Temp3
# ←
Flag TRUE
# ←
ENDIF
NEXT Student
ENDWHILE
Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.
Show mark scheme
8(a) [6 marks]
One mark for each correct marking point (Max 2) The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm •
8(b) [2 marks]
One mark for each marking point (max 6) MP1 Use of loop to cycle through the whole year group FOR MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of loop with correct exit clause WHILE MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm ← YearSize 249 ← FOR Student 2 to YearSize ← Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Counter Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 ← Score[Counter] Score[Counter - 1] ← Name[Counter,1] Name[Counter - 1,1] ← Name[Counter,2] Name[Counter - 1,2] ← Counter Counter – 1 ENDWHILE ← Score[Counter] Temp1 ← Name[Counter,1] Temp2 ← Name[Counter,2] Temp3 NEXT Student
(a) Describe what is meant by an imperative (procedural) programming language. 2 marks 2 marks
(b) Describe what is meant by a declarative programming language. 4 marks
| (c) Identify the programming paradigm for eac | ch of these program code examples. |
|---|---|
| Program code example | Programming paradigm |
male(john).female(ethel).parent(john, ethel). |
|
FOR Counter = 1 TO 20 X = X * CounterNEXT Counter |
|
Start: LDD Counter INC ACC STO Counter |
|
public class Vehicle{ private speed; public Vehicle() { speed = 0; }} |
Show mark scheme
9(a)
One mark for each correct marking point (Max 2) Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to • perform … in the order written / given • … each line of code changes something in the program run. •
9(b) [2 marks]
One mark for each correct marking point (Max 2) Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a • mathematical style
9(c) [4 marks]
One mark for each correct programming paradigm (Max 4) Program code example Programming paradigm male(john). Declarative female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 Procedural / imperative X = X * Counter NEXT Counter Start: LDD Counter Low-level / assembly INC ACC STO Counter public class Vehicle { private speed; public Vehicle() Object oriented / (OOP) { speed = 0; } }
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: 2 marks
declare the global 1D array,
arrayData, with ten elementsinitialise
arrayDatain 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.
(b) (i) A function, linearSearch(), takes an integer as a parameter and performs a linear 6 marks
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.
(ii) Edit the main program to: 4 marks
allow the user to input an integer value
pass the value to
linearSearch()as the parameteroutput 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.
(iii) Test your program with one value that is in the array and one value that is not in the array. 2 marks
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.
(c) The following bubble sort pseudocode algorithm sorts the data in theArray into descending numerical order. There are five incomplete statements. 6 marks
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.
Show mark scheme
2(a)
arrayData[7] = 15; arrayData[8] = 21; arrayData[9] = 8;
2(b)(i)
Python def linearSearch(searchValue): for x in range(0, 10): if arrayData[x] == searchValue: return True return False public static Boolean linearSearch(Integer searchValue){ for (int x = 0; x < 10; x++){ if(arrayData[x] == searchValue){ return true; } return false;
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") 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"); }
2(b)(iii) [2 marks]
1 mark for screenshot showing input and output for number found 1 mark for screenshot showing input and output for number not found
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 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 ; } } }
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: 2 marks
declare the global 1D array,
arrayData, with ten elementsinitialise
arrayDatain 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.
(b) (i) A function, linearSearch(), takes an integer as a parameter and performs a linear 6 marks
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.
(ii) Edit the main program to: 4 marks
allow the user to input an integer value
pass the value to
linearSearch()as the parameteroutput 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.
(iii) Test your program with one value that is in the array and one value that is not in the array. 2 marks
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.
(c) The following bubble sort pseudocode algorithm sorts the data in theArray into descending numerical order. There are five incomplete statements. 6 marks
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.
Show mark scheme
2(a)
arrayData[7] = 15; arrayData[8] = 21; arrayData[9] = 8;
2(b)(i)
Python def linearSearch(searchValue): for x in range(0, 10): if arrayData[x] == searchValue: return True return False public static Boolean linearSearch(Integer searchValue){ for (int x = 0; x < 10; x++){ if(arrayData[x] == searchValue){ return true; } return false;
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") 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"); }
2(b)(iii) [2 marks]
1 mark for screenshot showing input and output for number found 1 mark for screenshot showing input and output for number not found
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 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 ; } } }
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: 2 marks
declare the global 1D array,
arrayData, with ten elementsinitialise
arrayDatain 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.
(b) (i) A function, linearSearch(), takes an integer as a parameter and performs a linear 6 marks
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.
(ii) Edit the main program to: 4 marks
allow the user to input an integer value
pass the value to
linearSearch()as the parameteroutput 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.
(iii) Test your program with one value that is in the array and one value that is not in the array. 2 marks
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.
(c) The following bubble sort pseudocode algorithm sorts the data in theArray into descending numerical order. There are five incomplete statements. 6 marks
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.
Show mark scheme
2(a)
arrayData[7] = 15; arrayData[8] = 21; arrayData[9] = 8;
2(b)(i)
Python def linearSearch(searchValue): for x in range(0, 10): if arrayData[x] == searchValue: return True return False public static Boolean linearSearch(Integer searchValue){ for (int x = 0; x < 10; x++){ if(arrayData[x] == searchValue){ return true; } return false;
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") 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"); }
2(b)(iii) [2 marks]
1 mark for screenshot showing input and output for number found 1 mark for screenshot showing input and output for number not found
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 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 ; } } }