Cambridge Assessment International Education
Cambridge International Advanced Subsidiary and Advanced Level
* 4 6 5 8 9 5 0 5 8 1 *
COMPUTER SCIENCE 9608/41
Paper 4 Further Problem-solving and Programming Skills May/June 2019
2 hours
Candidates answer on the Question Paper.
No Additional Materials are required.
No calculators allowed.
READ THESE INSTRUCTIONS FIRST
Write your centre number, candidate number and name in the spaces at the top of this page.
Write in dark blue or black pen.
You may use an HB pencil for any diagrams, graphs or rough working.
Do not use staples, paper clips, glue or correction fluid.
DO NOT WRITE IN ANY BARCODES.
Answer all questions.
No marks will be awarded for using brand names of software packages or hardware.
At the end of the examination, fasten all your work securely together.
The number of marks is given in brackets [ ] at the end of each question or part question.
The maximum number of marks is 75.
This document consists of 18 printed pages and 2 blank pages.
DC (PQ) 180360
© UCLES 2019 [Turn over
, 2
1 (a) A stack contains the values 'red', 'blue', 'green' and 'yellow'.
yellow Top of stack
green
blue
red
(i) Show the contents of the stack in part(a) after the following operations.
POP()
PUSH('purple')
PUSH('orange')
[1]
© UCLES 2019 9608/41/M/J/19
, 3
(ii) Show the contents of the stack from part(a)(i) after these further operations.
POP()
POP()
PUSH('brown')
POP()
PUSH('black')
[1]
(b) A queue is an alternative Abstract Data Type (ADT).
Describe a queue.
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
............................................................................................................................................. [3]
© UCLES 2019 9608/41/M/J/19 [Turn over
, 4
2 A computer games club wants to run a competition. The club needs a system to store the scores
achieved in the competition.
A selection of score data is as follows:
99, 125, 121, 97, 109, 95, 135, 149
(a) A linked list of nodes will be used to store the data. Each node consists of the data, a left
pointer and a right pointer. The linked list will be organised as a binary tree.
(i) Complete the binary tree to show how the score data above will be organised.
RootPointer
The symbol ∅ represents a null pointer.
LeftPointer RightPointer
99
97 ∅ 125
121
[5]
© UCLES 2019 9608/41/M/J/19
Cambridge International Advanced Subsidiary and Advanced Level
* 4 6 5 8 9 5 0 5 8 1 *
COMPUTER SCIENCE 9608/41
Paper 4 Further Problem-solving and Programming Skills May/June 2019
2 hours
Candidates answer on the Question Paper.
No Additional Materials are required.
No calculators allowed.
READ THESE INSTRUCTIONS FIRST
Write your centre number, candidate number and name in the spaces at the top of this page.
Write in dark blue or black pen.
You may use an HB pencil for any diagrams, graphs or rough working.
Do not use staples, paper clips, glue or correction fluid.
DO NOT WRITE IN ANY BARCODES.
Answer all questions.
No marks will be awarded for using brand names of software packages or hardware.
At the end of the examination, fasten all your work securely together.
The number of marks is given in brackets [ ] at the end of each question or part question.
The maximum number of marks is 75.
This document consists of 18 printed pages and 2 blank pages.
DC (PQ) 180360
© UCLES 2019 [Turn over
, 2
1 (a) A stack contains the values 'red', 'blue', 'green' and 'yellow'.
yellow Top of stack
green
blue
red
(i) Show the contents of the stack in part(a) after the following operations.
POP()
PUSH('purple')
PUSH('orange')
[1]
© UCLES 2019 9608/41/M/J/19
, 3
(ii) Show the contents of the stack from part(a)(i) after these further operations.
POP()
POP()
PUSH('brown')
POP()
PUSH('black')
[1]
(b) A queue is an alternative Abstract Data Type (ADT).
Describe a queue.
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
............................................................................................................................................. [3]
© UCLES 2019 9608/41/M/J/19 [Turn over
, 4
2 A computer games club wants to run a competition. The club needs a system to store the scores
achieved in the competition.
A selection of score data is as follows:
99, 125, 121, 97, 109, 95, 135, 149
(a) A linked list of nodes will be used to store the data. Each node consists of the data, a left
pointer and a right pointer. The linked list will be organised as a binary tree.
(i) Complete the binary tree to show how the score data above will be organised.
RootPointer
The symbol ∅ represents a null pointer.
LeftPointer RightPointer
99
97 ∅ 125
121
[5]
© UCLES 2019 9608/41/M/J/19
