Computer Science 9618/21 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) An algorithm includes a number of complex calculations. A programmer is writing a program to implement the algorithm and decides to use library routines to provide part of the solution.
State three possible benefits of using library routines in the development of the program.
1 ……
2 ……
3 ……
[3]
(b) The following pseudocode is part of a program that stores names and test marks for use in other parts of the program.
DECLARE Name1, Name2, Name3 : STRING
DECLARE Mark1, Mark2, Mark3 : INTEGER
INPUT Name1
INPUT Mark1
INPUT Name2
INPUT Mark2
INPUT Name3
INPUT Mark3
(i) The pseudocode needs to be changed to allow for data to be stored for up to 30 students.
Explain why it would be good practice to use arrays to store the data.
…… [3]
(ii) The following pseudocode statement includes array references:
OUTPUT "Student ", Name[Count], " scored ", Mark[Count]
State the purpose of the variable Count and give its data type.
Purpose ……
Data type ……
[2]
(c) The pseudocode statements in the following table may contain errors.
State the error in each case or write ‘NO ERROR’ if the statement contains no error.
Assume that any variables used are of the correct type for the given function.
Statement Error
IF EMPTY ← "" THEN
Status ← IS_NUM(-23.4)
X ← STR_TO_NUM("37") + 5
Y ← STR_TO_NUM("37" + "5")
[4]
Mark scheme
1(a) One mark per point: 3
1 They are tried and tested so free from errors
2 They perform a function that you may not be able to program yourself
(for example encryption)
3 They are readily available / speed up development time
1(b)(i) One mark per point: 3
1 Algorithm to process / search / organise the data is easier to implement
// Values may be accessed via a loop-controlled variable / iterated
through using index
2 Makes the program easier to design / code / test / understand
3 Multiple instances referenced via a single identifier / so fewer identifiers
needed // Easier to amend the program when the number of students
increases
1(b)(ii) One mark per point: 2
Purpose: It identifies / references an individual array element // provides the
index to the array
Data type: Integer
1(c) One mark per row: 4
Statement Error
IF EMPTY ← "" THEN Should be "=" not ←
Status ← IS_NUM(-23.4) Parameter should be a string (or
char) // should not be a real
X ← STR_TO_NUM("37") + 5 NO ERROR
Y ← STR_TO_NUM("37" + "5") Wrong operator – should be & or
Parameter is not a string
A system is being developed to help manage a car hire business. A customer may hire a car for a number of days.
An abstract model needs to be produced.
(a) Explain the process of abstraction and state four items of data that should be stored each time a car is hired.
Explanation ……
Item 1 ……
Item 2 ……
Item 3 ……
Item 4 ……
[3]
(b) Identify two operations that would be required to process the car hire data.
Operation 1 ……
Operation 2 ……
[2]
Mark scheme
2(a) One mark for Explanation: 3
• Abstraction is used to filter out information / data that is not necessary
for the task
Or the opposite:
• To keep only information / data that is necessary for the task
One mark for each TWO data items (not dependent on 'Explanation'):
Items include:
• Car details: ID, Car Registration, car type etc
• Customer details: ID, name, address, licence details etc
• Start date (of hire)
• Return date / Number of days (of hire)
• Cost of hire
2(b) One mark for each (Max 2) 2
Examples include:
1 Input customer details
2 Input car details
3 Input payment details
4 Create hire / start hire
5 Return car / end hire
6 Change / check car status (hired / available / written-off)
7 Cancel hire
8 Process payment / calculate hire cost
A 1D array Data of type integer contains 200 elements. Each element has a unique value.
An algorithm is required to search for the largest value and output it.
Describe the steps that the algorithm should perform.
Do not include pseudocode statements in your answer.
…… [5]
Mark scheme
3 One mark per point (Max 5): 5
1 Declare a variable / an integer Max
2 Assign value of first / any element to Max
3 Set up a loop to repeat 200 times / from start to end of array
4 Use the loop counter as the array index
5 If value of current element is greater than Max...
6 ...then assign value to Max
7 After the loop, Output Max
(a) The following diagram shows an Abstract Data Type (ADT) representation of an ordered linked list. The data item stored in each node is a single character. The data will be accessed in alphabetical order.
The symbol Ø represents a null pointer.
Start pointer
'C' 'J' 'L' Ø
(i) Nodes with data 'A' and 'K' are added to the linked list. Nodes with data 'J' and 'L' are deleted.
After the changes, the data items still need to be accessed in alphabetical order.
Complete the diagram to show the new state of the linked list.
Start pointer
'C' 'J' 'L'
[4]
(ii) The original data could have been stored in a 1D array in which each element stores a character.
For example:
'C' 'J' 'L'
Explain the advantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array.
…… [2]
(iii) Explain the disadvantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array.
…… [2]
(b) A program will store data using a linked list like the one shown in part (a).
Explain how the linked list can be implemented.
…… [4]
Mark scheme
4(a)(i) One mark for each: 4
1 Data A and K stored in new / existing nodes
2 Start pointer points to Node A
3 Node A points to Node C and Node C points to Node K
4 Node K contains Null Pointer
4(a)(ii) One mark per point: 2
1 Pointers determine the ordering of data // only the pointers need to be
changed when data changed
2 Easier to add / delete data (to maintain correct sequence) in a linked list
// description of moving data to maintain correct sequence when array
used
4(a)(iii) One mark per point: 2
1 Need to store pointers as well as data
2 More complex (to setup / implement)
4(b) One mark per point (Max 4): 4
1 Declare two (1D) arrays
2 One for data, one for pointers
3 Elements from same index represent one node
4 Declare an integer / variable for StartPointer // explain its use
5 Define appropriate value for null pointer // explain its use
6 Declare an integer / variable for FreeList pointer // explain its use
7 Routines are needed to add / delete / search
Alternative MP1, 2 and 3 for record-based implementation:
1 Define a record type with fields for data and pointer
2 Declare one (1D) array
3 ...of the defined record type
A program uses two 1D arrays of type integer. Array1 contains 600 elements and Array2 contains 200 elements.
Array1 contains sample values read from a sensor. The sensor always takes three consecutive samples and all of these values are stored in Array1.
A procedure Summarise() will calculate the average of three consecutive values from Array1 and write the result to Array2. This will be repeated for all values in Array1.
The diagram below illustrates the process for the first six entries in Array1.
}
Array1 Array2 Comment
10 15 average of first three values
20 41 average of next three values
}
15
40
41
42
Write pseudocode for the procedure Summarise().
…… [5]
Mark scheme
5 Mark as follows (Max 5): 5
1 Procedure heading and ending and declaration of both indexes
2 Loop to process all elements from Array1
3 Sum (any) three consecutive values from Array1 and divide by 3
in a loop
4 Convert result to Integer
5 Assign value to correct element of Array2 in a loop
6 Increment Array2 index in a loop
PROCEDURE Summarise()
DECLARE Value : REAL
DECLARE IxA, IxB : INTEGER // Index variables
IxB ← 1
FOR IxA ← 1 TO 598 STEP 3
Value ← Array1[IxA] + Array1[IxA + 1] + Array1[IxA + 2]
Value ← Value / 3
Array2[IxB] ← INT(Value)
IxB ← IxB + 1
NEXT IxA
ENDPROCEDURE
The following pseudocode algorithm attempts to check whether a string is a valid email address.
FUNCTION IsValid(InString : STRING) RETURNS BOOLEAN
DECLARE Index, Dots, Ats, Others : INTEGER
DECLARE NextChar : CHAR
DECLARE Valid : BOOLEAN
Index ← 1
Dots ←0
Ats 0←
Others ← 0
Valid ← TRUE
REPEAT
NextChar ←
MID(InString, Index, 1)
CASE OF NextChar
'.' : Dots Dots + 1 ←
'@' : Ats Ats + 1 ←
IF Ats > 1 THEN
Valid FALSE ←
ENDIF
OTHERWISE : Others Others + 1 ←
ENDCASE
IF Dots > 1 AND Ats = 0 THEN
Valid FALSE ←
ELSE
Index ←
Index + 1
ENDIF
UNTIL Index > LENGTH(InString) OR Valid = FALSE
IF NOT (Dots >= 1 AND Ats = 1 AND Others > 8) THEN
Valid FALSE ←
ENDIF
RETURN Valid
ENDFUNCTION
(a) Part of the validation is implemented by the line:
IF NOT (Dots >= 1 AND Ats = 1 AND Others > 8) THEN
State the values that would result in the condition evaluating to TRUE.
…… [1]
(b) (i) Complete the trace table by dry running the function when it is called as follows:
Result ← IsValid("Liz.123@big@net")
Index NextChar Dots Ats Others Valid
[5]
(ii) State the value returned when IsValid() is called using the expression shown in part (b)(i).
…… [1]
Mark scheme
6(a) One mark for any part correct (accept equivalent wording) (Max 1): 1
• Condition evaluates to TRUE if bracket contents evaluate to FALSE:
• Bracket contents evaluate to FALSE if:
• Dots: zero / less than one
or
• Ats: not equal to one
or
• Others: less than nine
6(b)(i) One mark for each area as outlined: 5
Index NextChar Dots Ats Others Valid
0 0 0 TRUE
1 'L' 1
2 'i' 2
3 'z' 3
4 '.' 1
5 '1' 4
6 '2' 5
7 '3' 6
8 '@' 1
9 'b' 7
10 'i' 8
11 'g' 9
12 '@' 2 FALSE
6(b)(ii) FALSE 1
A simple arithmetic expression is stored as a string in the format:
<Value1><Operator><Value2>
An operator character is one of the following: '+' '−' '*' '/'
Example arithmetic expression strings:
"803+1904"
"34/7"
(a) A procedure Calculate() will:
• take an arithmetic expression string as a parameter
• evaluate the expression
• output the result.
Assume:
• the string contains only numeric digits and a single operator character
• Value1 and Value2 represent integer values
• Value1 and Value2 are unsigned (they will not be preceded by ' + ' or ' − ').
(i) Write pseudocode for the procedure Calculate().
…… [7]
(ii) Calculate() is changed to a function that returns the value of the evaluated expression.
Write the header for the function in pseudocode.
…… [1]
(b) A string representing an arithmetic expression could be in the correct format but be impossible to evaluate.
Give an example of a correctly formatted string and explain why evaluation would be impossible.
Example string ……
Explanation ……
[2]
Mark scheme
7(a)(i) One mark per point (Max 7) as follows: 7
1 Declaration of local variables for Par1 Par2 and Par3
2 Loop to end of (parameter) string // until operator is found
3 Extract a character in a loop...
4 Attempt at extraction of three parts of expression using substring
functions
5 Completely correct extraction of all three parts of expression
6. Convert string to Integer using STR_TO_NUM(<something
sensible>)
7 Attempt to interpret at least two operators (Par2): + - * /
8 Corresponding correct calculation (all operators) and final Output of
result
PROCEDURE Calculate(Expression : STRING)
DECLARE Val1, Val2, Index : INTEGER
DECLARE Result : REAL
DECLARE Par1, Par2, Par3 : STRING
CONSTANT PLUS = '+'
CONSTANT MINUS = '-'
CONSTANT MULTIPLY = '*'
CONSTANT DIVIDE = '/'
FOR Index ← 1 TO LENGTH(Expression) //search for
operator
ThisChar ← MID(Expression, Index, 1)
IF IS_NUM(ThisChar) = FALSE THEN
Par1 ← LEFT(Expression, Index – 1)
Par2 ← ThisChar
Par3 ← RIGHT(Expression, LENGTH(Expression) –
Index)
ENDIF
NEXT Index
Val1 ← STR_TO_NUM(Par1)
Val2 ← STR_TO_NUM(Par3)
CASE OF Par2
PLUS : Result ← Val1 + Val2
MINUS : Result ← Val1 - Val2
MULTIPLY : Result ← Val1 * Val2
DIVIDE : Result ← Val1 / Val2
ENDCASE
OUTPUT Result
ENDPROCEDURE
7(a)(ii) FUNCTION Calculate(Expression : STRING) RETURNS REAL 1
7(b) Example string: "23/0" (Any divide by zero example) 2
Reason: The result is infinity / cannot be represented / is undefined // will
cause the program to crash
A teacher is designing a program to perform simple syntax checks on programs written by students. Student programs are submitted as text files, which are known as project files.
A project file may contain blank lines.
The teacher has defined the first program module as follows:
Module Description
• takes the name of an existing project file as a parameter of type string
CheckFile()
• returns TRUE if the file is valid (it contains at least 10 non-blank lines), otherwise returns FALSE
(a) Write pseudocode for module CheckFile().
…… [7]
Further modules are defined as follows:
Module Description
• takes a line from a project file as a parameter of type string
CheckLine() • returns zero if the line is blank or contains no syntax error, otherwise returns an error number as an integer
• takes two parameters:
○ the name of a project file as a string
○ the maximum number of errors as an integer
• uses CheckFile() to test the project file. Outputs an error
CountErrors() message and ends if the project file is not valid
• calls CheckLine() for each line in the project file
• counts the number of errors
• outputs the number of errors or a warning message if the maximum number of errors is exceeded
(b) CountErrors() is called to check the project file Jim01Prog.txt and to stop if more than
20 errors are found.
Write the pseudocode statement for this call.
…… [2]
(c) Write pseudocode for module CountErrors(). Assume CheckFile() and CheckLine() have been written and can be used in your solution.
…… [8]
(d) Module CheckLine() includes a check for syntax errors.
Two examples of syntax error that cannot be detected from examining a single line are those involving selection and iteration.
Give two other examples.
1 ……
2 ……
[2]
Mark scheme
8(a) One mark for each point (Max 7) as follows: 7
1 Function heading and ending including parameter and return type
2 Declaration and initialisation of local Integer for Count
3 OPEN in READ mode and CLOSE
4 Conditional loop until EOF()
5 Read a line in a loop
6 If non-blank, increment count in a loop
7 Terminate loop when 10 non-blank lines have been read
8 Return Boolean in both cases
FUNCTION CheckFile(Thisfile : STRING) RETURNS BOOLEAN
DECLARE Valid : BOOLEAN
DECLARE ThisLine : STRING
DECLARE Count : INTEGER
Count ← 0
Valid ← FALSE
OPEN ThisFile FOR READ
WHILE NOT EOF(ThisFile) AND Valid = FALSE
READFILE ThisFile, ThisLine
IF ThisLine <> "" THEN
Count ← Count + 1
IF Count > 9 THEN
Valid ← TRUE
ENDIF
ENDIF
ENDWHILE
CLOSEFILE ThisFile
RETURN Valid
ENDFUNCTION
8(b) CALL CountErrors("Jim01Prog.txt", 20) 2
One mark for each:
1 Module name, at least one parameter in brackets and one parameter
correct
2 Completely correct statement
8(c) Mark as follows: 8
1 Procedure heading and ending including parameters
2 Declaration and initialisation of local Integer value for ErrCount
3 Use of CheckFile(), output message and terminate if it returns
FALSE
4 Conditional loop until EOF()
5 ...or ErrCount > MaxErrors
6 Read line and use as parameter to CheckLine()in a loop
7 Test return value and increment ErrCount if non-zero in a loop
8 Output either message once only as appropriate
PROCEDURE CountErrors(ThisFile : STRING, MaxErrors :
INTEGER)
DECLARE ErrCount, ThisError : INTEGER
DECLARE ThisLine : STRING
ErrCount ← 0
IF CheckFile(ThisFile) = FALSE THEN
OUTPUT "That program file is not valid"
ELSE
OPEN ThisFile FOR READ
REPEAT
READFILE, ThisFile, ThisLine
ThisError ← CheckLine(ThisLine)
IF ThisError <> 0 THEN
ErrCount ← ErrCount + 1
ENDIF
UNTIL ErrCount > MaxErrors OR EOF(ThisFile)
IF EOF(ThisFile) = FALSE THEN
OUTPUT "Check terminated – too many errors"
ELSE
OUTPUT "There were ", ErrCount, " errors."
ENDIF
CLOSEFILE ThisFile
ENDIF
ENDPROCEDURE
8(d) One mark for each (Max 2): 2
Examples:
1 Incorrect block structure. Missing keyword denoting part of block (for
example ENDPROCEDURE, ENDFUNCTION, ENDTYPE)
2 Data type errors, for example, assigning an integer value to a string
3 Identifier used before it is declared
4 Incorrect parameter use
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/21 October/November 2022 mark scheme?+
On this page, free: the mark scheme for AS & A Level Computer Science 9618/21, October/November 2022 (9618_w22_ms_21), and the question paper (9618_w22_qp_21), to read or download, with each question's marking points written out underneath.
How many marks is 9618/21 out of?+
Computer Science 9618/21 for October/November 2022 is out of 75 marks, with 2 hours to answer it.
Can I get my 9618/21 answers marked?+
Yes. Upload your answers to 9618/21/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.