Free until 14 Nov · 80% off for the first 100 · Pricing

Computer Science 9618/42 October/November 2021: question paper and mark scheme

Cambridge AS & A Level Computer Science (9618), Paper 4 Practical, October/November 2021. Read both free below, or download them. Done the paper? Get it marked by AI against this mark scheme.

9618_w21_qp_429618_w21_ms_429618/42/O/N/21

Paper
Paper 4 Practical
Total marks
75
Time
2 hours 30 minutes
Code on the paper
9618/42/O/N/21
9618_w21_ms_42.pdf

9618/42 mark scheme, question by question

Each question as it's printed, and the mark scheme's points for it, as text. Diagrams, tables and graphs are in the PDFs above.

Question 117 marks

Question

Study the following pseudocode for a recursive function. FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER IF X < Y THEN OUTPUT X + Y RETURN (Unknown(X + 1, Y) * 2) ELSE IF X = Y THEN RETURN 1 ELSE OUTPUT X + Y RETURN (Unknown(X - 1, Y) DIV 2) ENDIF ENDIF ENDFUNCTION The operator DIV returns the integer value after division e.g. 13 DIV 2 would give 6 (a) Write program code to declare the function Unknown(). Save your program as question 1. Copy and paste the program code into part 1(a) in the evidence document. [3] (b) The main program needs to run all three of the following function calls and output the result of each call: Unknown(10, 15) Unknown(10, 10) Unknown(15, 10) (i) For each of the three function calls, the main program needs to: • output the value of the two parameters • call the function with those parameters • output the return value. Write the program code for the main program. Save your program. Copy and paste the program code into part 1(b)(i) in the evidence document. [3] (ii) Take a screenshot to show the output from part (b)(i). Copy and paste the screenshot into part 1(b)(ii) in the evidence document. [2] (c) Rewrite the function Unknown() as an iterative function, IterativeUnknown(). Save your program. Copy and paste the program code into part 1(c) in the evidence document. [7] (d) The iterative function needs to be called three times with the same parameters as in part (b). (i) For each of the three function calls, the main program needs to: • output the value of the two parameters • call the iterative function with those parameters • output the return value. Amend the main program to perform these tasks. Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [1] (ii) Take one or more screenshots to show the output of both functions for each set of parameters. Copy and paste the screenshot(s) into part 1(d)(ii) in the evidence document. [1]

Mark scheme

1(a) 1 mark per bullet point 3 • function with correct name and parameters • correct Div operator (or equivalent) used • code matches pseudocode Example program code: Python def Unknown(X, Y): if X < Y: print(str(X + Y)) return Unknown(X + 1, Y) * 2 elif X == Y: return 1 else: print(str(X + Y)) return int(Unknown(X - 1, Y) / 2) VB.NET Function Unknown(X, Y) If X < Y Then Console.WriteLine(X + Y) Return Unknown(X + 1, Y) * 2 ElseIf X = Y Then Return 1 Else Console.WriteLine(X + Y) Return Unknown(X - 1, Y) \ 2 End If End Function Java public static Integer Unknown(Integer X, Integer Y){ if(X < Y){ System.out.println(X+Y); return Unknown(X + 1, Y) * 2; }else if(X == Y){ return 1; }else{ System.out.println(X + Y); Integer ReturnValue = Unknown(X-1,Y) / 2; return ReturnValue; } } 1(b)(i) 1 mark per bullet point 3 • Suitable output identifying parameters for each call • All three correct function calls … • …outputting the return value for each call Example program code: Python print("10 and 15") print(str(Unknown(10, 15))) print("10 and 10") print(str(Unknown(10, 10))) print("15 and 10") print(str(Unknown(15, 10))) VB.NET Console.WriteLine("10 and 15") Console.WriteLine(Unknown(10, 15)) Console.WriteLine("10, 10") Console.WriteLine(Unknown(10, 10)) Console.WriteLine("15, 10") Console.WriteLine(Unknown(15, 10)) Java public static void main(String[] args){ System.out.println("10 and 15"); System.out.println(Unknown(10,15)); System.out.println("10 and 10"); System.out.println(Unknown(10, 10)); System.out.println("15 and 10"); System.out.println(Unknown(15, 10)); } 1(b)(ii) 1 mark for 1 function with correct output 2 1 mark for remaining 2 function calls with correct output For example: 10 and 15 25 26 27 28 29 32 10 and 10 1 15 and 10 25 24 23 22 21 0 1(c) 1 mark per bullet point 7 • Iterative function, taking 2 parameters • Starting with return value (Total) as 1 • Looping while X <> Y // might be 1 loop or two separate // returning when X = Y // looping until X==Y • Within each loop, outputting (X+Y) correctly when X<Y and Y<X • Each time X < Y, Total * 2 and X++ • Each time Y < X Total DIV 2 and X-- • Returning the Total after correct calculations Example program code: Python def IterativeUnknown(X,Y): Total = 1 while X != Y: print(str(X + Y)) if X < Y: X = X + 1 Total = Total * 2 else: X = X - 1 Total = int(Total / 2) return Total VB.NET Function IterativeUnknown(X, Y) Dim Total As Integer = 1 While X <> Y Console.WriteLine(X + Y) If X < Y Then X = X + 1 Total = Total * 2 Else X = X - 1 Total = Total \ 2 End If End While Return Total End Function 1(c) Java public static Integer IterativeUnknown(Integer X, Integer Y){ Integer Total = 1; while (X != Y){ System.out.println(X+Y); if(X<Y){ X = X + 1; Total = Total * 2; }else{ X = X - 1; Total = Total / 2; } } return Total; } 1(d)(i) Calling function 3 times with correct Data and outputting 1 Example program code: Python print("10 and 15") print(str(IterativeUnknown(10, 15))) print("10 and 10") print(str(IterativeUnknown(10, 10))) print("15 and 10") print(str(IterativeUnknown(15, 10))) VB.NET Console.WriteLine("10 and 15") Console.WriteLine(IterativeUnknown(10, 15)) Console.WriteLine("10, 10") Console.WriteLine(IterativeUnknown(10, 10)) Console.WriteLine("15, 10") Console.WriteLine(IterativeUnknown(15, 10)) Java System.out.println("10 and 15"); System.out.println(IterativeUnknown(10, 15)); System.out.println("10 and 10"); System.out.println(IterativeUnknown(10, 10)); System.out.println("15 and 10"); System.out.println(IterativeUnknown(15, 10)); 1(d)(ii) 1 mark for screenshot showing correct output for both functions 1

Question 230 marks

Question

A program, written using object-oriented programming, stores pictures as objects. The program stores the dimensions of the picture (width and height), the colour of the frame (e.g. black), and a description of the picture (e.g. flowers). The class has the following attributes and methods. Picture Description : STRING // stores a description of the picture Width : INTEGER // stores the width e.g. 30 Height : INTEGER // stores the height e.g. 40 FrameColour : STRING // stores the colour e.g. black Constructor() // takes all four values as parameters and sets them to the private attributes GetDescription() // returns the description of the picture GetHeight() // returns the height GetWidth() // returns the width GetColour() // returns the frame colour SetDescription() // takes the new description as a parameter and writes the value to description (a) The constructor takes the picture description, frame colour, height, and width as parameters and sets these to the private attributes. Write the program code to declare the class Picture 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 programming language, include attribute declarations using comments. Save your program as question 2. Copy and paste the program code into part 2(a) in the evidence document. [5] (b) The four get methods return the associated attribute, for example, GetDescription() returns the description of the picture. Write the four get methods. Save your program. Copy and paste the program code into part 2(b) in the evidence document. [3] (c) The method SetDescription() takes a new description as a parameter, and writes this value to the appropriate attribute. Write the method SetDescription(). Save your program. Copy and paste the program code into part 2(c) in the evidence document. [2] (d) Write program code to declare an array of type Picture with 100 elements. Save your program. Copy and paste the program code into part 2(d) in the evidence document. [1] (e) The text file Pictures.txt stores the data for the pictures in the order: description, width, height, colour. For example, for the first picture in the text file: Flowers is the description 45 is the width 50 is the height black is the frame colour. The data read into the program from the text file is stored in an array of type Picture. The main program and the function will need to access the array data. The function ReadData(): • opens the file Pictures.txt • reads the data from the file • creates a new object of type Picture for each picture • writes each object to the array • raises an exception if the file cannot be found • counts and returns the number of pictures in the array. Write program code for the function ReadData(). Save your program. Copy and paste the program code into part 2(e) in the evidence document. [8] (f) The main program calls the function ReadData(). Write the main program. Save your program. Copy and paste the program code into part 2(f) in the evidence document. [2] (g) The main program needs to ask the user to input their requirements for a picture. The user will enter the colour of the frame, the maximum width, and the maximum height of the picture. The program will then search the array of pictures, and output the picture description, the width, and the height of any picture that meets the user’s requirements. The program should allow the user to input the colour in any case (e.g. Silver, silver, or SILVER), and still output the correct results. Edit the main program to perform the described actions. Save your program. Copy and paste the program code into part 2(g) in the evidence document. [7] (h) Test your program by inputting the following search criteria: • BLACK, 100, 100 • silver, 25, 25 Take screenshots to show the output for both search criteria. Copy and paste the screenshots into part 2(h) in the evidence document. [2]

Mark scheme

2(a) 1 mark per bullet point 5 • class declared (with appropriate close) with identifier Picture • correct attribute declarations with Data types (Description, Frame colour = string, Width, Height = integer.) • …as private • correct constructor (with appropriate close) with four parameters… • …parameters assigned to attributes Example program code: Python class Picture: def __init__(self, DescriptionP, WidthSizeP, HeightSizeP, FrameColourP): self.__Description = DescriptionP # string self.__Width = int(WidthSizeP) #integer self.__Height = int(HeightSizeP) #integer self.__FrameColour = FrameColourP #string Java class Picture{ private String Description; private Integer Width; private Integer Height; private String FrameColour; public Picture(String DescriptionP, Integer WidthP, Integer HeightP, String FrameColourP){ Description = DescriptionP; Width = WidthP; Height = HeightP; FrameColour = FrameColourP; } } 2(a) VB.NET Class Picture Private Description As String Private Width As Integer Private Height As Integer Private FrameColour As String Public Sub New(DescriptionP, WidthP, HeightP,FrameColourP) Description = DescriptionP Width = WidthP Height = HeightP FrameColour = FrameColourP End Sub End Class 2(b) 1 mark per bullet point 3 • 1 Get method taking no parameter… • …returning correct attribute • remaining 3 correct methods Example program code: Python def GetDescription(self): return self.__Description def GetWidth(self): return self.__Width def GetHeight(self): return self.__Height def GetColour(self): return self.__FrameColour Java public String GetDescription(){ return Description; } public Integer GetWidth(){ return Width; } public Integer GetHeight(){ return Height; } public String GetFrameColour(){ return FrameColour; } VB.NET Function GetDescription() Return Description End Function Function GetWidth() Return Width End Function Function GetHeight() Return Height End Function Function GetFrameColour() Return FrameColour End Function 2(c) 1 mark per bullet point 2 • Set method (procedure) taking parameter (no return) … • …assigning parameter to correct attribute Example program code: Python def SetDescription(self, DescriptionP): self.__Description = DescriptionP Java public void SetDescription(String DescriptionP){ Description = DescriptionP; } VB.NET Public Sub SetDescription(DescriptionP) Description = DescriptionP End Sub 2(d) 1 mark for declaring array of type Picture with 100 elements 1 Example program code: Python PictureArray = [] for i in range(100): PictureArray.append(Picture("",0,0,"")) Java public static void main(String[] args){ Picture[] PictureArray = new Picture[100];} VB.NET Dim PictureArray(0 to 99) As Picture 2(e) 1 mark per bullet point: 8 • Exception with opening the file inside... • ..appropriate catch and output 1 mark per bullet point to Max 7 • Function/procedure declared with correct name (and close, passing array by reference or global array declared) • opening Pictures.txt for Read • looping until EOF / or equivalent • …reading each set of 4 lines from the file within loop • creating object of type Picture • …with Description, Width, Height, Frame colour from File as parameters • ..adding to next array element/appending • closing the File (in an appropriate place) • counts and returns number of pictures in array Example program code: Python def ReadData(PictureArray): Filename = "Pictures.txt" Counter = 0 try: File = open(Filename,"r") Description = (File.readline()).strip().lower() while(Description != ""): Width = int((File.readline()).strip()) Height = int((File.readline()).strip()) Frame = ((File.readline()).strip()).lower() PictureArray[Counter] = Picture(Description, Width, Height, Frame) Description =((File.readline()).strip()).lower() Counter = Counter + 1 File.close() except IOError: print("Could not find File") return Counter, PictureArray 2(e) VB.NET Function ReadData(ByRef PictureArray, ByRef NumberPictures) As Integer Dim Counter As Integer = 0 Try Dim Filename As String = "Pictures.txt" Dim FileReader As New System.IO.StreamReader(Filename) Dim Description, FrameColour As String Dim Height, Width As Integer While FileReader.Peek <> -1 Description = FileReader.ReadLine() Width = FileReader.ReadLine() Height = FileReader.ReadLine() FrameColour = FileReader.ReadLine() PictureArray(NumberPictures) = New Picture(Description, Width, Height, FrameColour) NumberPictures = NumberPictures + 1 Counter = Counter + 1 End While FileReader.Close() Catch ex As Exception Console.WriteLine("Invalid File") End Try Return Counter End Function 2(e) Java public static Integer ReadData(Picture[] PictureArray){ String Filename = "Pictures.txt"; String DataRead; String Description; String Width; String Height; String FrameColour; Integer NumberPictures = 0; try{ FileReader f = new FileReader(Filename); BufferedReader Reader = new BufferedReader(f); DataRead = Reader.readLine(); while(DataRead != null){ Description = DataRead; Width = Reader.readLine(); Height = Reader.readLine(); FrameColour = Reader.readLine(); PictureArray[NumberPictures] = new Picture(Description, Integer.parseInt(Width), Integer.parseInt(Height), FrameColour); NumberPictures++; DataRead = Reader.readLine(); } Reader.close(); } catch(FileNotFoundException ex){ System.out.println("No File found"); } catch(IOException ex){ System.out.println("No File found"); } return NumberPictures; } 2(f) 1 mark per bullet point 2 • calling function ReadData() … • …store/use the Number of elements returned/by reference based on answer to part 2e Example program code: Python NumberPicturesInArray, PictureArray = ReadData(PictureArray) Java Integer NumberPicturesInArray = ReadData(PictureArray); VB.NET Dim NumberPicturesInArray As Integer = ReadData() 2(g) 1 mark per bullet point to Max 7 7 • taking as input all three values (colour, width, height) • … converting colour to lowercase // uppercase • looping through array … • …using returned value from part 2(f) as max index • …within loop, checking if Array[index].FrameColour matches input • …and checking if Array[index].FrameWidth <= input Width • …and checking if Array[index].FrameHeight <= input Height • …all using Get methods • outputting the Picture Description, Width and Height for all/any matching Pictures Example program code: Python FrameColour = input("Input the Frame colour ").lower() MaxWidth = int(input("Input the Maximum Width ")) MaxHeight = int(input("Input the Maximum Height ")) print("Matches Frames shown") for Z in range(0, NumberPicturesInArray): if PictureArray[Z].GetColour() == FrameColour: if(PictureArray[Z].GetWidth() <= MaxWidth): if (PictureArray[Z].GetHeight() <= MaxHeight): print(PictureArray[Z].GetDescription(), " " , str(PictureArray[Z].GetWidth()), " ", str(PictureArray[Z].GetHeight())) VB.NET Sub Main() Dim PictureArray(0 To 99) As Picture Dim NumberPictures As Integer = 0 Dim FrameColour As String Dim MaxWidth, MaxHeight As Integer ReadData(PictureArray, NumberPictures) Console.WriteLine("Input the Frame colour") FrameColour = (Console.ReadLine()).ToLower() Console.WriteLine("Input the Maximum Width") MaxWidth = Console.ReadLine() Console.WriteLine("Input the Maximum Height") MaxHeight = Console.ReadLine() Console.WriteLine("Matching Frames shown") For X = 0 To NumberPictures - 1 If PictureArray(X).GetFrameColour() = FrameColour And PictureArray(X).GetWidth <= MaxWidth And PictureArray(X).GetHeight <= MaxHeight Then 2(g) Console.WriteLine(PictureArray(X).GetDescription() & " " & PictureArray(X).GetWidth() & " " & PictureArray(X).GetHeight) End If Next Console.ReadLine() End Sub Java public static void main(String[] args){ Picture[] PictureArray = new Picture[100]; Integer NumberPicturesInArray = ReadData(PictureArray); Scanner scanner = new Scanner(System.in); System.out.println("Enter the Frame colour"); String FrameColour = scanner.nextLine(); System.out.println("Enter the Maximum Width"); Integer MaxWidth = Integer.parseInt(scanner.nextLine()); System.out.println("Enter the Maximum Height"); Integer MaxHeight = Integer.parseInt(scanner.nextLine()); FrameColour = FrameColour.toLowerCase(); for(int X = 0; X < NumberPicturesInArray; X++){ if(PictureArray[X].GetFrameColour().equals(FrameColour) && PictureArray[X].GetWidth() <= MaxWidth && PictureArray[X].GetHeight() <= MaxHeight){ System.out.println(PictureArray[X].GetDescription() + " " + PictureArray[X].GetWidth() + " " + PictureArray[X].GetHeight()); } } } 2(h) 1 mark for screenshot showing output for BLACK, 100, 100 2 1 mark for showing no outputs for silver, 25, 25 Input the Frame colour BLACK Input the Maximum Width 100 Input the Maximum Height 100 Matches Frames shown flowers 45 50 people 20 20 landscape 30 45 landscape 25 37 people 50 40 Input the Frame colour silver Input the Maximum Width 25 Input the Maximum Height 25 Matches Frames shown

Question 334 marks

Question

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 Data RightPointer Index [0] [1] [2] [0] 1 10 2 [1] -1 5 -1 [2] -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. Each node has a left pointer, data and right pointer. The program also initialises the: • RootPointer to -1 (null); this points to the first node in the binary tree • FreeNode to 0; 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. [4] (b) The procedure AddNode() adds a new node to the array ArrayNodes. 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 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 ← ELSE CurrentNode ← ArrayNodes[CurrentNode, 2] ENDIF ENDIF ENDWHILE ENDIF FreeNode ← 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. [8] (c) The procedure PrintAll() outputs the data in each element in ArrayNodes, in the order they are stored in the array. 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. [4] (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. Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document. [3] (ii) Test the program by entering the data: 10 5 15 8 12 6 20 11 9 4 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. [1] (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. Save your program. Copy and paste the program code into part 3(e)(i) in the evidence document. [7] (ii) Test the procedure InOrder() with the same data entered in part (d)(ii). 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. [1]

Mark scheme

3(a) 1 mark per bullet point 4 • Declaring array named ArrayNodes of type integer • …with 20 by 3 elements • RootPointer declared as integer and assigned -1 • FreeNode declared as integer and assigned 0 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) 1 mark for each completed statement to Max 6 8 1 mark per bullet point • Function/procedure declaration either : taking parameters by reference returning the three amended values (Python) using global instead • remainder of function/procedure matches the pseudocode Example program code: Python def AddNode(ArrayNodes, RootPointer, FreeNode): NodeData = int(input("Enter the Data")) if FreeNode <= 19: ArrayNodes[FreeNode][0] = -1 ArrayNodes[FreeNode][1] = NodeData ArrayNodes[FreeNode][2] = -1 if RootPointer == -1: # Add to start RootPointer = 0 else: Placed = False 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: print("Tree is full") return ArrayNodes, RootPointer, FreeNode 3(b) VB.NET Sub AddNode(ByRef ArrayNodes, ByRef RootPointer, ByRef FreeNode) Console.WriteLine("Enter the Data") Dim NodeData As Integer = Console.ReadLine If FreeNode <= 19 Then ArrayNodes(FreeNode, 0) = -1 ArrayNodes(FreeNode, 1) = NodeData ArrayNodes(FreeNode, 2) = -1 If RootPointer = -1 Then RootPointer = 0 Else Dim Placed As Boolean = False Dim CurrentNode As Integer = RootPointer While Placed = False If NodeData < ArrayNodes(CurrentNode, 1) Then If ArrayNodes(CurrentNode, 0) = -1 Then ArrayNodes(CurrentNode, 0) = FreeNode Placed = True Else CurrentNode = ArrayNodes(CurrentNode, 0) End If Else If ArrayNodes(CurrentNode, 2) = -1 Then ArrayNodes(CurrentNode, 2) = FreeNode Placed = True Else CurrentNode = ArrayNodes(CurrentNode, 2) End If End If End While Endif FreeNode = FreeNode + 1 Else Console.WriteLine("Tree is full") End If End Sub 3(b) 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) 1 mark per bullet point 4 • 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, 1) & " " & 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 per bullet point 3 • looping 10 times • calling AddNode 10 times (check parameters in 3b) • calling PrintAll outside of loop (check parameters in 3c) 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) 1 mark for screenshot showing the following output: 1 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 per bullet point 7 • procedure name InOrder taking a parameter (for current node being 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: 1 4 5 6 8 9 10 11 12 15 20

Checked your answers against these? Let AI mark the whole paper, on your own working.

Mark my 9618/42

How this paper is marked

Examiners follow the generic marking principles at the front of the scheme, then each question's points: method (M), accuracy (A) and independent (B) marks, error carried forward where the scheme allows it, and positive marking, so you're credited for what you got right.

Check your answers against it

Done this paper? Upload your script and CIE Buddy's AI marker marks it question by question against this exact scheme, puts the ticks on your own working and says what each lost mark needed.

9618/42 in other series

Find another Computer Science paper

Every AS & A Level Computer Science mark scheme

Question papers and mark schemes © Cambridge University Press & Assessment. CIE Buddy is independent and not connected to Cambridge.

9618/42 questions

Where can I find the 9618/42 October/November 2021 mark scheme?

On this page, free: the mark scheme for AS & A Level Computer Science 9618/42, October/November 2021 (9618_w21_ms_42), and the question paper (9618_w21_qp_42), to read or download, with each question's marking points written out underneath.

How many marks is 9618/42 out of?

Computer Science 9618/42 for October/November 2021 is out of 75 marks, with 2 hours 30 minutes to answer it.

Can I get my 9618/42 answers marked?

Yes. Upload your answers to 9618/42/O/N/21 as a PDF or photos, and CIE Buddy marks every question against this paper's official mark scheme, using Cambridge's marking rules. You get your score, each lost mark explained on your own script, and the topics to revise. It's a guide, not an official Cambridge grade.