Computer Science 9618/22 October/November 2022: question paper and mark scheme
Cambridge AS & A Level Computer Science (9618), Paper 2 Problem Solving & Programming, October/November 2022. Read both free below, or download them. Done the paper? Get it marked by AI against this mark scheme.
(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
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
(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-B
START
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) One mark per row (row 2 to 5): 4
Input Output Next state
S1
Input-A Output-X S2
Input-A (none) S2
Input-B Output-W S3
Input-A Output-W S4
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
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]
Is Average NO
> Last ? Add Last to Total
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
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
(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
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]
(c) Two 1D arrays were described at the beginning of the question. 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 two arrays will be replaced by a single array. A user-defined data type (record structure) has been declared as follows:
TYPE ErrorRec
DECLARE ErrCode : STRING
DECLARE ErrText : STRING
ENDTYPE
(i) State the error in the record declaration.
…… [1]
(ii) State two benefits of using the single array of the user-defined data type.
1 ……
2 ……
[2]
(iii) Write the declaration for the single array in pseudocode.
…… [1]
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
Checked your answers against these? Let AI mark the whole paper, on your own working.
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.
Where can I find the 9618/22 October/November 2022 mark scheme?+
On this page, free: the mark scheme for AS & A Level Computer Science 9618/22, October/November 2022 (9618_w22_ms_22), and the question paper (9618_w22_qp_22), to read or download, with each question's marking points written out underneath.
How many marks is 9618/22 out of?+
Computer Science 9618/22 for October/November 2022 is out of 75 marks, with 2 hours to answer it.
Can I get my 9618/22 answers marked?+
Yes. Upload your answers to 9618/22/O/N/22 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.