Cambridge A Level Computer Science 9618 — 2022 Oct/Nov Paper 2 · Variant 2

1 (a) A programmer is developing an algorithm to solve a problem. Part of the algorithm would be appropriate to implement as a subroutine (a procedure or a function). (i) State two reasons why the programmer may decide to use a subroutine. 1 ........................................................................................................................................ ........................................................................................................................................... 2 ........................................................................................................................................ ........................................................................................................................................... [2] (ii) A procedure header is shown in pseudocode: PROCEDURE MyProc(Count : INTEGER, Message : STRING) Give the correct term for the identifiers Count and Message and explain their use. Term .................................................................................................................................. Use .................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... [2] (b) The algorithm in part (a) is part of a program that will be sold to the public. All the software errors that were identified during in-house testing have been corrected. Identify and describe the additional test stage that may be carried out before the program is sold to the public. Test stage ................................................................................................................................. Description ................................................................................................................................ ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [4] (c) Part of an identifier table is shown: Variable Type Example value FlagDay DATE 23/04/2004 CharList STRING "ABCDEF" Count INTEGER 29 Complete the table by evaluating each expression using the example values. Expression Evaluation MID(CharList, MONTH(FlagDay), 1) INT(Count / LENGTH(CharList)) (Count >= 29) AND (DAY(FlagDay) > 23) [3]

Mark scheme: Question Answer Marks 1(a)(i) One mark for each point (Max 2): 2 • When a task which is repeated / reused / performed in several places • When a part of an algorithm performs a specific task • Reduces complexity of program / program is simplified // subroutine already available • Testing / debugging / maintenance is easier 1(a)(ii) One mark for each part: 2 Term: Parameter(s) Use: to pass values / arguments to the procedure 1(b) One mark for test stage, one mark for each description point 4 (Max 3 for Description) Test stage: Beta testing Description: 1 Testing carried out by a small group of (potential) users 2 Users will check that the software works as required / works in the real world / does not contain errors 3 Users will feedback problems / suggestions for improvement 4 Problems / suggestions identified are addressed (before the program is sold) 1(c) One mark per row: 3 Expression Evaluation MID(CharList, MONTH(FlagDay), 1) 'D' INT(Count / LENGTH(CharList)) 4 (Count >= 99) AND (DAY(FlagDay) > 23) FALSE

More questions on Structured Programming

2 (a) An algorithm will process data from a test taken by a group of students. The algorithm will prompt and input the name and test mark for each of the 35 students. The algorithm will add the names of all the students with a test mark of less than 20 to an existing text file Support_List.txt, which already contains data from other group tests. (i) Describe the steps that the algorithm should perform. Do not include pseudocode statements in your answer. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [5] (ii) Explain why it may be better to store the names of the students in a file rather than in an array. ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [1] (iii) Explain why WRITE mode cannot be used in the answer to part 2(a)(i). ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [1] (b) Examine the following state-transition diagram. Input-A Output-X Input-B Output-W Input-BSTART S1 S2 S3 Input-A Input-A Input-B S4 Input-A Output-W Complete the table to show the inputs, outputs and next states. Input Output Next state S1 Input-A S2 Output-W Output-W [4]

Mark scheme: 2(a)(i) One mark per step (or equivalent): 5 1 Open file in APPEND mode (and subsequent Close) 2 Prompt and Input a student name and mark 3 If mark greater than or equal to 20 jump to step 5 4 Write only the name to the file 5 Repeat from Step 2 for 35 times / the number of students 2(a)(ii) Data in a file is saved after the computer is switched off / stored 1 permanently // no need to re-enter the data when the program is re-run 2(a)(iii) Example answer: 1 So that existing file data is not overwritten. 2(b) 4 One mark per row (row 2 to 5): Input Output Next state S1 Input-A Output-X S2 Input-A (none) S2 Input-B Output-W S3 Input-A Output-W S4

More questions on Files

3 A stack is used in a program to store string data which needs to be accessed in several modules. (a) A stack is an example of an Abstract Data Type (ADT). Identify one other example of an ADT and describe its main features. Example .................................................................................................................................... Features ................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (b) Explain how the stack can be implemented using an array. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [5] (c) A second stack is used in the program. The diagram below shows the initial state of this stack. Value X is at the top of the stack and was the last item added. Upper-case letters are used to represent different data values. Stack operations are performed in three groups as follows: Group 1: PUSH D PUSH E Group 2: POP POP POP Group 3: PUSH A PUSH B POP PUSH C Complete the diagram to show the state of the stack after each group of operations has been performed. Include the current stack pointer (SP) after each group. Memory Initial After After After location state Group 1 Group 2 Group 3 957 956 955 954 953 X ←SP 952 Y 951 Z 950 P [5]

Mark scheme: 3(a) One mark for name, Max two for features (Max 3 in total) 3 Name: Queue Features: 1 Each queue element contains one data item 2 A Pointer to the front / start of the queue 3 A Pointer to the back / end of the queue 4 Data is added at back / end and removed from front / start // works on a FIFO basis 5 May be circular ALTERNATIVE: Name: Linked List Features: 1 Each node contains data and a pointer to the next node 2 A Pointer to the start of the list 3 Last node in the list has a null pointer 4 Data may be added / removed by manipulating pointers (not moving data) 5 Nodes are traversed in a specific sequence 6 Unused nodes are stored on a free list // a free-list pointer to the Free List 3(b) One mark per point (Max 5): 5 1 Declare a (1D) array of data type STRING 2 The number of elements in that array corresponds to the size of the required stack 3 Declare an integer / variable for StackPointer 4. Declare an integer / variable for the size of the stack // for the max value of StackPointer 5 Use the StackPointer as an index to the array 6 Pointers and variables initialised to indicate empty stack 7 Store each item on the stack as one array element / Each stack item maps to one array element 8 Attempt to describe Push and Pop operations 9 Push and Pop routines need to check for full or empty conditions 3(c) One mark for each: 5 1 Data 'After Group 1' (as shown, including blank cells) 2 Data 'After Group 2' (as shown, including blank cells) 3 Data 'After Group 3' (as shown, including blank cells) 4 SP 'After Group 1' pointing to location 955 5 Final two SPs pointing to locations 952 and 954

More questions on Introduction to Abstract Data Types (ADT)

4 The program flowchart represents a simple algorithm. START INPUT UserID Set Average to GetAverage(UserID) Set Total to 0 Set Index to 4 Add 1 to Index YES Is Index < 7 ? NO Set Last to SameMonth[Index] NO Is Average Add Last to Total ? > Last YES Add Average to Total Update(UserID, Total) END (a) Write the equivalent pseudocode for the algorithm represented by the flowchart. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [6] (b) Give the name of the iterative construct in the flowchart. ............................................................................................................................................. [1]

Mark scheme: 4(a) One mark per point: 6 1 Input UserID and use of GetAverage()and assignment 2 Initialisation of Total to zero and Index to 4 3 Conditional loop with Index from 4 to 6 4 Assignment of Last from element SameMonth[Index] in a loop 5 Structure: IF...THEN...ELSE...ENDIF in a loop 6 Correct assignments and final call to Update()after the loop INPUT UserID Average  GetAverage(UserID) Total  0 Index  4 WHILE Index < 7 // REPEAT Last  SameMonth[Index] IF Average > Last THEN Total  Total + Average ELSE Total  Total + Last ENDIF Index  Index + 1 ENDWHILE // UNTIL Index = 7 CALL Update(UserID, Total) Alternative solution using FOR loop: One mark per point FOR loop solution: 1 Input UserID and use of GetAverage()and assignment 2 Initialisation of Total to zero 3 loop Index from 4 to 6 4 Assignment of Last from array SameMonth in a loop 5 Comparison IF...THEN...ELSE...ENDIF in a loop 6 Appropriate assignments in a loop AND final call to Update()after the loop INPUT UserID Average  GetAverage(UserID) Total  0 FOR Index  4 TO 6 Last  SameMonth[Index] IF Average > Last THEN Total  Total + Average ELSE Total  Total + Last ENDIF NEXT Index CALL Update(UserID, Total) 4(b) Pre-condition (loop) / count-controlled (loop) 1

More questions on Constructs

5 Examine the following pseudocode. IF A = TRUE THEN IF B = TRUE THEN IF C = TRUE THEN CALL Sub1() ELSE CALL Sub2() ENDIF ENDIF ELSE IF B = TRUE THEN IF C = TRUE THEN CALL Sub4() ELSE CALL Sub3() ENDIF ELSE IF C = FALSE THEN CALL Sub3() ELSE CALL Sub4() ENDIF ENDIF ENDIF A programmer wants to re-write the pseudocode as four separate IF...THEN...ENDIF statements, each containing a single CALL statement. This involves writing a single, simplified logic expression as the condition in each statement. Write the amended pseudocode. 1 ....................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... 2 ....................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... 3 ....................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... 4 ....................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... [4]

Mark scheme: 5 One mark per IF...THEN...ENDIF clause: 4 1 IF A AND B AND C THEN CALL Sub1() ENDIF 2 IF (A AND B) AND NOT C THEN CALL Sub2() ENDIF 3 IF (NOT A) AND (NOT C) THEN CALL Sub3() ENDIF 4 IF (NOT A) AND C THEN CALL Sub4() ENDIF

6 (a) The factorial of an integer number is the product of all the integers from that number down to 1. In general, the factorial of n is n × (n−1) × ... × 2 × 1 For example, the factorial of 5 is 5 × 4 × 3 × 2 × 1 = 120 In this question, n will be referred to as the BaseNumber. A function FindBaseNumber() will: • be called with a positive, non-zero integer value as a parameter • return BaseNumber if the parameter value is the factorial of the BaseNumber • return −1 if the parameter value is not a factorial. For example: Parameter value Value returned 120 5 12 −1 6 3 1 1 FindBaseNumber(12) will return −1 because 12 is not a factorial. You may use the rest of this page for rough working. Write pseudocode for the function FindBaseNumber(). ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [7] (b) A program is written to allow a user to input a sequence of values to be checked using the function FindBaseNumber(). The user will input one value at a time. The variable used to store the user input has to be of type string because the user will input ‘End’ to end the program. Valid input will be converted to an integer and passed to FindBaseNumber() and the return value will be output. Complete the table by giving four invalid strings that may be used to test distinct aspects of the required validation. Give the reason for your choice in each case. Input Reason for choice ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... ...................................................................................................... [4]

Mark scheme: 6(a) Example by repeated multiplication: 7 Mark as follows (multiplication solution), (Max 7): 1 Function heading and ending including parameter and return type 2 Declaration and initialisation of local Num 3 Any conditional loop 4 Conditional loop until ThisValue found or Try out of range 5 Multiply Try by Num in a loop 6 Compare Try with ThisValue and set termination if the same in a loop 7 Increment Num and repeat in a loop 8 Attempt to Return Num if ThisValue is a factorial or -1 otherwise FUNCTION FindBaseNumber(ThisValue : INTEGER) RETURNS INTEGER DECLARE Num, Try : INTEGER DECLARE Found : BOOLEAN Num  0 Found  FALSE Try  1 WHILE Try <= ThisValue AND Found = FALSE Num  Num + 1 Try  Try * Num IF Try = ThisValue THEN //BaseNumber found Found  TRUE ENDIF ENDWHILE IF Found = TRUE THEN RETURN Num ELSE RETURN -1 ENDIF ENDFUNCTION 6(a) Alternative FOR LOOP solution. Mark as follows: 1 Function heading and ending including parameter and return type 2 Declaration of local Integer value for Num and Try 3 Count-controlled Loop from 1 to ThisValue 4 Multiply Try by Num in a loop 5 Compare Try with ThisValue in a loop 6 ...Immediate return of Num if they are the same in a loop 7 Return –1 if ThisValue not found after loop FUNCTION FindBaseNumber(ThisValue : INTEGER) RETURNS INTEGER DECLARE Num, Try : INTEGER Try  1 FOR Num  1 TO ThisValue Try  Try * Num IF Try = ThisValue THEN //BaseNumber found RETURN Num ENDIF NEXT Num RETURN -1 ENDFUNCTION 6(b) One mark per row. 4 Examples of invalid strings: 1 Non-numeric but not "End" // contains space or other non-numeric characters 2 Real number 3 Integer value out of range (i.e. <= 0) 4 Empty string 5 Correct word but wrong case e.g. "end" rather than "End" Input Reason for choice "Aardvark" Non-numeric (and not "End") "27.3" Numeric but not an integer "-3" // "0" A non-positive integer "" An empty string

More questions on Algorithms

7 A teacher is designing a program to perform simple syntax checks on programs written by students. Two global 1D arrays are used to store the syntax error data. Both arrays contain 500 elements. • Array ErrCode contains integer values that represent an error number in the range 1 to 800. • Array ErrText contains string values that represent an error description. The following diagram shows an example of the arrays. Index ErrCode ErrText 1 10 "Invalid identifier name" 2 20 "Bracket mismatch" 3 50 "Undeclared variable" 4 60 "Type mismatch in assignment" … 500 999 <Undefined> Note: • There may be less than 500 error numbers so corresponding elements in both arrays may be unused. Unused elements in ErrCode have the value 999. The value of unused elements in ErrText is undefined. • Values in the ErrCode array are stored in ascending order but not all values may be present, for example, there may be no error code 31. The teacher has defined two program modules as follows: Module Description • takes two parameters as integers: ○ a line number in the student’s program ○ an error number • searches for the error number in the ErrCode array: OutputError() ○ if found, outputs the corresponding error description and the line number, for example: "Bracket mismatch on line 34" ○ if not found, outputs the line number and a warning, for example: "Unknown error on line 34" SortArrays() sorts the arrays into ascending order of ErrCode (a) Write efficient pseudocode for module OutputError(). ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [6] (b) Write an efficient bubble sort algorithm in pseudocode for module SortArrays(). ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [8]

Mark scheme: 7(a) One mark per point (Max 6): 6 1 Procedure heading and ending including parameters 2 Conditional loop containing incrementing Index... 3 ...terminating when ErrNum found 4 ...terminating when ErrCode[Index] > ErrNum (i.e. ErrNum not found) 5 ... OR after element 500 tested 6 Test if found and OUTPUT 'Found' message 7 ...otherwise OUTPUT 'Not Found' message PROCEDURE OutputError(LineNum, ErrNum : INTEGER) DECLARE Index : INTEGER Index  0 // Search until ErrNum found OR not present OR end of array REPEAT Index  Index + 1 UNTIL ErrCode[Index] >= ErrNum OR Index = 500 IF ErrCode[Index] = ErrNum THEN OUTPUT ErrText[Index], " on line ", LineNum //Found ELSE OUTPUT "Unknown error on line ", LineNum //Not found ENDIF ENDPROCEURE 7(b) One mark per point (Max 8): 8 1 Procedure heading and ending as shown 2 Conditional loop correctly terminated 3 An inner loop 4 Correct range for inner loop 5 Comparison (element J with J+1) in a loop 6 Swap elements in both arrays in a loop 7 'No-Swap' mechanism: • Conditional outer loop including flag reset • Flag set in inner loop to indicate swap 8 Efficiency (this scenario): terminate inner loop when ErrCode = 999 9 Reducing Boundary in the outer loop PROCEDURE SortArrays() DECLARE TempInt, J, Boundary : INTEGER DECLARE TempStr : STRING DECLARE NoSwaps : BOOLEAN Boundary  499 REPEAT NoSwaps  TRUE FOR J  1 TO Boundary IF ErrCode[J]> ErrCode[J+1] THEN //first swap ErrCode elements TempInt  ErrCode[J] ErrCode[J]  ErrCode[J+1] ErrCode[J+1]  TempInt //now swap corresponding ErrText elements TempStr  ErrText[J] ErrText[J]  ErrText[J+1] ErrText[J+1]  TempStr NoSwaps  FALSE ENDIF NEXT J Boundary  Boundary - 1 UNTIL NoSwaps = TRUE ENDPROCEDURE 7(c)(i) ErrCode should be an INTEGER // ErrCode should not be a STRING 1 7(c)(ii) Benefits include: 2 1 Array of records can store mixed data types / multiple data types under a single identifer 2 Tighter / closer association between ErrCode and ErrText // simpler code as fields may be referenced together // values cannot get out of step as with two arrays 3 Program easier to design / write / debug / test / maintain / understand One mark per point Note: Max 2 marks 7(c)(iii) DECLARE Error : ARRAY[1:500] OF ErrorRec 1

More questions on Algorithms