Cambridge International Examinations
Cambridge International Advanced Subsidiary and Advanced Level
COMPUTER SCIENCE 9608/04
Paper 4 Further Problem-solving and Programming Skills For Examination from 2015
SPECIMEN PAPER
2 hours
Candidates answer on the Question Paper.
No Additional Materials are required.
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.
Answer all questions.
No marks will be awarded for using brand names for software packages or hardware.
No calculators allowed.
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.
This document consists of 15 printed pages and 1 blank page.
© UCLES 2012 [Turn over
, 2
Throughout the paper you will be asked to write either pseudocode or program code.
Complete the statement to say which high-level programming language you will use.
Programming language used: ............................................
1 (a) Complete the algorithm, written in pseudocode, for a binary search.
The data being searched is stored in the array SearchData[63]. The item of data being
searched is stored in the variable SearchItem.
X 0
Low 1
High ………………………………………
WHILE (High>=Low) AND (…………………………………………………)
Middle INT((High + Low)/2)
IF SearchData[Middle] = SearchItem
THEN
X Middle
ELSE
IF SearchData[Middle] < SearchItem
THEN
Low Middle + 1
ELSE
IF SearchData[Middle] > SearchItem
THEN
……………………………………………………………………
ENDIF
ENDIF
ENDIF
ENDWHILE [3]
(b) (i) The binary search only works if the data in the array being searched is:
[1]
(ii) The maximum number of comparisons that are required to find an item which is present
in the array SearchData is:
[1]
(iii) At the end of the algorithm, the variable X contains:
either the value which indicates
or the value which indicates [4]
© UCLES 2012 9608/04/SP/15
, 3
(c) You will change the binary search algorithm to a recursive algorithm and write the equivalent
program code in the form of a procedure. Name the recursive procedure BinarySearch.
Use these variables.
Variable Data Type Description
SearchData ARRAY[63] : INTEGER global array
SearchItem INTEGER global variable
X INTEGER global variable
Low INTEGER parameter
High INTEGER parameter
Middle INTEGER local variable
Write program code for the recursive procedure BinarySearch.
[5]
(d) Write the initial call to the recursive procedure.
[1]
© UCLES 2012 9608/04/SP/15 [Turn over
Cambridge International Advanced Subsidiary and Advanced Level
COMPUTER SCIENCE 9608/04
Paper 4 Further Problem-solving and Programming Skills For Examination from 2015
SPECIMEN PAPER
2 hours
Candidates answer on the Question Paper.
No Additional Materials are required.
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.
Answer all questions.
No marks will be awarded for using brand names for software packages or hardware.
No calculators allowed.
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.
This document consists of 15 printed pages and 1 blank page.
© UCLES 2012 [Turn over
, 2
Throughout the paper you will be asked to write either pseudocode or program code.
Complete the statement to say which high-level programming language you will use.
Programming language used: ............................................
1 (a) Complete the algorithm, written in pseudocode, for a binary search.
The data being searched is stored in the array SearchData[63]. The item of data being
searched is stored in the variable SearchItem.
X 0
Low 1
High ………………………………………
WHILE (High>=Low) AND (…………………………………………………)
Middle INT((High + Low)/2)
IF SearchData[Middle] = SearchItem
THEN
X Middle
ELSE
IF SearchData[Middle] < SearchItem
THEN
Low Middle + 1
ELSE
IF SearchData[Middle] > SearchItem
THEN
……………………………………………………………………
ENDIF
ENDIF
ENDIF
ENDWHILE [3]
(b) (i) The binary search only works if the data in the array being searched is:
[1]
(ii) The maximum number of comparisons that are required to find an item which is present
in the array SearchData is:
[1]
(iii) At the end of the algorithm, the variable X contains:
either the value which indicates
or the value which indicates [4]
© UCLES 2012 9608/04/SP/15
, 3
(c) You will change the binary search algorithm to a recursive algorithm and write the equivalent
program code in the form of a procedure. Name the recursive procedure BinarySearch.
Use these variables.
Variable Data Type Description
SearchData ARRAY[63] : INTEGER global array
SearchItem INTEGER global variable
X INTEGER global variable
Low INTEGER parameter
High INTEGER parameter
Middle INTEGER local variable
Write program code for the recursive procedure BinarySearch.
[5]
(d) Write the initial call to the recursive procedure.
[1]
© UCLES 2012 9608/04/SP/15 [Turn over
