Q1.
The plan below shows the layout of the Mass Transit Railway (MTR) in Hong Kong. The
maintenance depot is at Mong Kok.
All the trains operate the same cycle (sequence) of journeys, given by the algorithm
below. The algorithm is intended to ensure that:
1. trains are serviced as soon as possible after covering 135 km, and
2. each train will have travelled in both directions along each track at least once in the
cycle.
The algorithm relates to three arrays called station, journey and km. The contents of
these arrays are shown below.
Subscript Station
0 Mong Kok depot (MK)
1 Tsuen Wan (TW)
2 Quarry Bay (QB)
3 Sheung Wan (SW)
4 Chai Wan (CW)
5 Hong Kong Central (HK)
Page 1 of 12
Subscript Journey
0 3
1 4
2 3
3 1
4 5
5 2
6 3
The 6 × 6 two-dimensional array km, representing the distance between stations (in
kilometres), contains
The proposed algorithm is:
org:=0
last := 1
dest:= 3
maintain := FALSE
start := station[org]
finish := station[dest]
totalkm := km [org, dest]
org := dest
while(TRUE)
n := 0
repeat
n := n + 1
if (maintain = TRUE) then
n := last
totalkm := 0
maintain := FALSE
endif
Page 2 of 12
dest := journey [n]
if (totalkm > 135) then
dest := 0
last := n
maintain := TRUE
endif
start := station[org]
finish := station[dest]
totalkm := totalkm + km[org, dest]
org := dest
until n >= 6
endwhile
(a) What is the effect of the instructions while(TRUE) and endwhile?
(1)
(b) For each of the variables maintain and n, state with a reason what data type it
should be.
(4)
(c) Copy and complete the trace table below, for one iteration of the outer (while ....
endwhile) loop.
(8)
(d) An objective of the algorithm is that each train has travelled in both directions along
every track at least once in the cycle. Using your trace table, state, with reasons,
whether this objective has been achieved.
(2)
(Total 15 marks)
Q2.
(a) An example of an iteration in Pascal is:
FOR x : = 1 TO 10 DO writeln (‘Hello’);
In a high level programming language you are familiar with, using the correct syntax,
give an example of:
Page 3 of 12
(i) declaration;
(2)
(ii) assignment;
(1)
(iii) selection.
(2)
(b) A one-dimensional array q contains the following characters:
(i) Dry run the following algorithm, recording your results in the diagram.
FOR pointer ← 1 to 5
s[pointer] ← q[pointer]
END FOR
pointer1 ← 1
pointer2 ← 5
REPEAT
q[pointerl] ←s[pointer2]
pointer1 ← pointer1 + 1
pointer2 ←
pointer2 – 1
UNTIL pointer2 = 0
(10)
(ii) What is the purpose of the above algorithm?
Page 4 of 12
(1)
(Total 16 marks)
Q3.
The operating system of a computer network includes the following functions and
procedures:
OpenScreen( ComputerName, Channel )
where ComputerName is a character string identifying a computer on the network, and
Channel is an integer identifying a communication channel.
This function opens a communication channel to the screen of the computer specified,and
returns an integer, which is 0 if the function is successful, otherwise it returns one of
various error codes.
SendCharacter( Char, Channel, x, y )
where Char is a character, Channel identifies the communication channel, and the integer
variables x and y are screen coordinates. This procedure sends a character to the screen
of the other computer using the communication channel. It does not return a value.
CloseScreen( Channel ) closes the specified communication channel. It does not return a
value.
InputText( Buffer ) accepts a string of characters from the keyboard, terminated by a
carriage return (character code 13), and stores it in Buffer. It does not return a value.
A computer on the network is running a program, designed to enable the user to send
messages to another computer user. Part of the program uses the following algorithm:
Array of characters: Msg[50]
Integer: Count, Err, Col, Row
Character: Ch
InputText ( Msg ) // uses carriage return, code 13, as
terminator
Count := 0
Err := OpenScreen( “Admin_Computer”, 10 )
if ( Err = 0 ) then
Col := 1
Row := 12
Ch := “A”
while ( Ch does not contain the code 13 ) do
Ch := Msg[ Count ]
SendCharacter( Ch, 10, Col, Row )
Count := Count + 1
Col := Col + 1
endwhile
CloseScreen( 10 )
else
case ( Err ) of
when 1: print( “Specified computer is offline
or does not exist” )
when 2: print( “Cannot output - network interface
problem” )
when 3: print( “The network is down” )
endcase
endif
Page 5 of 12
(a) What is meant by the term parameters? Illustrate your answer by using examples of
the use of parameters from the algorithm above.
(3)
(b) What is the benefit to the programmer of using parameters?
(2)
(c) How would the array Msg be stored?
(1)
(d) Describe in detail the operation of the while ... endwhile section of the algorithm.
(4)
(e) What is the effect of the case ¼ of ¼ endcase section of the algorithm?
(2)
(f) The algorithm does not impose any limit on the length of the string the user inputs.
What might happen if a string 60 characters long were entered?
(1)
(Total 13 marks)
Page 6 of 12
Mark schemes
Q1.
(a) Causes process to repeat indefinitely
NOT repeats until maintain is TRUE
1
(b) Maintain has two values, TRUE / FALSE (1), => must be Boolean (1) n is used
as an array subscript (1) => must be integer (1) or n is used as a loop control
and can never be non-integer within the algorithm (1) => integer (1)
NOT numeric - too vague
4
(c) See table for model solution 1 mark each indicated section completed
correctly, including follow–through (7x1); additional 1 mark for correctly
modifying n downwards in penultimate section If candidates go completely
wrong but clearly deserve some credit marks can be awarded on the following
criteria, up to a maximum of 2 marks for correct sequence of loop repetitions,
including the change from 6 to 5 then 6 - i.e. the column for n, including
correct exit 2 marks for correct completion of the sequence of stations, ie the
org, dest, start, finish columns
2 marks for correct completion of totalkm column, i.e. correct lookups and
totalling 2 marks for correctly executing inner if branches, i.e. setting maintain
and resetting totalkm in correct places. Total 8 marks for all-correct trace
follow-through marks should be awarded where appropriate
8
(d) 2 marks for diagram, or explanation, showing that the journeys indicated
above cover all routes in both directions marks can be awarded for any
reasoned answer (indicating achievement or not) providing it is consistent with
the candidate’s trace table Note: the sequence is MK -> SW -> CW -> SW ->
TW -> HK -> MK -> QB -> SW etc., which does cover all lines in both
directions. Strictly speaking, whether the objective is achieved depends
whether journeys to/from MK depot are passenger-carrying / revenue-earning
or not. Either interpretation is acceptable - the marks are awarded for the
explanation.
n org dest last start finish totalkm maintain Remarks
0 3 1
FALSE
MK
SW
15
Page 7 of 12
0
Given
4 if ignored
SW if ignored
CW
+27 =
42
4 N<6 so rpt
1 mark
3 if ignored
CW if ignored
SW
+27 =
69
3 N<6 so rpt
1 mark
1 if ignored
SW if ignored
TW
+37=106
1 N<6 so rpt
1 mark
5 if ignored
Page 8 of 12
TW if ignored
HK
+34=140
5 N<6 so rpt
1 mark
2 if ignored
0 >140 so if
executed
True
HK
MK
+12=152
0 N<6 so rpt
1 mark
6 TRUE so if
executed
False
if ignored
MK
QB
+28 =
28
2 N<6 so rpt
Page 9 of 12
1 mark
3 if ignored
QB if ignored
SW
+43 =
71
N = 6 so
stop
repeat
loop
end while
1 mark
2
[15]
Q2.
(a) (i) VAR/CONST/TYPE/DIM/FUNCTION/PROCEDURE/LABEL
Or similar, name and type;; keyword and name;;
2
(ii) Eg x:=5 / y ← y – 1
1
(iii) Example of IF / CASE / SWITCH statement
(1 mark for keyword, 1 mark for selection criteria)
2
(b) (i)
Page 10 of 12
1 mark for each correct entry
10
(ii) Algorithm: reverse content of array
R re-arrange
1
[16]
Q3.
(a) Information passed to / from a function or procedure to define the values it is
to use - e.g. in calling OPENSCREEN, the values “Admin Computer” and 10
[actual or real parameters] are to be used as the values of COMPUTERNAME
and CHANNEL [formal parameters or placeholders]
3
(b) Enables same function to be used in a number of contexts, enables “black-
box” programming, or enables different programmers to work on various
modules
Accept: saves memory by not using global variables, or prevents inadvertent
modification of variables in a procedure
2
(c) As a series of contiguous / consecutive memory locations
1
(d) Extract a character from the MSG array, at the position indicated by COUNT
Call the SENDCHARACTER function, passing it CH and other data Increment
COUNT and COL
Repeat the process as long as CH does not have the value 13 [4 important
points are: repetition, what condition determines whether to repeat (examine
current value of CH variable), if condition is true what happens (execute block
to endwhile), effect of instructions in loop (next character in sequence sent to
other computer and screen coordinates adjusted)]
4
(e) Prints one of the specified messages, depending on the value of ERR
2
Page 11 of 12
(f) Would be too long for the MSG array and so might overwrite other data or
code
Accept: data truncated, interpreter produces runtime error (array bounds
exceeded), compiler error causes program build to abort
1
[13]
Page 12 of 12
