Please stick the barcode label h&

2019-DSE
ICT
PAPER 2D

HONG KONG EXAMINATIONS AND ASSESSMENT AUTHORITY

Candidate Number
HONG KONG DIPLOMA OF SECONDARY EDUCATION EXAMINATION 2019

INFORMATION AND COMMUNICATION TECHNOLOGY

PAPER 2D
Software Development
Question-Answer Book

11:15 am -12:45 pm (1 hour 30 minutes)

This paper must be answered in English

INSTRUCTIONS

(1) After the announcement of the start of the

examination, you should first write your Candidate
Number in the space provided on Page 1 and stick
barcode labels in the spaces provided on Pages 1, 3, 5
and 7.

(2) ANSWER ALL QUESTIONS. Write your answers in

the spaces provided in this Question-Answer book.
Do not write in the margins. Answers written in the
margins will not be marked.

(3) Supplementary answer sheets will be supplied on

request. Write your candidate number, mark the
question number box and stick a barcode label on
each sheet, and fasten them with string INSIDE this
book.

(4) No extra time will be given to candidates for sticking on

the barcode labels or filling in the question number
boxes after the ‘Time is up’ announcement.

2019-DSE-ICT2D-1 63 nm
*A2OOE02o
 Answer all questions.

1. Peter uses stacks to manage boxes. Each box stores some apples. In the following example, a stack
contains 3 boxes with 10, 20 and 30 apples.

30
20
10 <- Bottom of the stack

Below are the operations on the stacks:

Operation Description
Push (S, k) Push a box with k apples into stack S.
Pop(S) Remove a box from stack S and return the number of apples in the box.
Empty(S) Return TRUE if stack S has no boxes in it; otherwise, return FALSE.

(a) (i) Initially there is an empty stack A. Write down the final content of A after executing the following -o
-oQJ
JZ
pseudocode.
cd
£ E
<D
Push(A, 10) <L>
JO
Push(A, 20)
C TMP <- Pop (A) c
if Empty (A) then Push(A, 30) gc/i
c a
’S)
‘5b cd
£ E
E <D
<i>
S c
c
a c
GJ
E Bottom of A .E
£
C/5 (2 marks)
Q
O
* £
3 (ii) Initially there is an empty stack B. Write down the final content of B after executing the following
3
pseudocode.

Push(B, 10)
Push(B, 20)
Push (B, 30)
Push(B, Pop(B)+Pop(B))

<- Bottom of B
(2 marks)

Answers written in the margins will not be marked.

64
2019-DSE-ICT 2D-2
 Please stick the barcode label he

I
I

(b) Initially there is a non-empty stack A and an empty stack B, as shown below:

30
20
15
5 <- Bottom of A <r Bottom of B ■

Write down the final content of A and B after executing the following pseudocode.

7 TMP <• 0
while not Empty (A) do
1 TMP <" TMP + Pop (A)
if TMP > 30 then
Push(B, 30)
I TMP TMP - 30
Push(B, TMP)
=

1
I
I
<
Bottom of A <- Bottom of B
I

(3 marks)
a

Answers written in the margins will not be marked.

05
20I9-DSIMCT2D-3
 (c) Initially there is a non-empty stack X and an empty stack Y. REV (X, Y) is a subprogram for moving
all the boxes in stack X to stack Y, where the boxes in Y are in reverse order. An example is shown
below:

40 10
30 20
20 30
10 <- Bottom of X <- Bottom of Y Bottom of X 40 Bottom of Y
i j I j
I i
Initial content Final content

Complete the pseudocode for REV (X, Y) below.

REV(X,Y)

■u -u
Q
<D

* C3
£ O
o
O
c C

£
(3 marks) V)
C

i ’e?
£
£ <u
<D
-C •S
G c
C c
o OJ

a
£
go
<D <u
£ cz:
C
< <

Answers written in the margins will not be marked.

66
2019-DSE-ICT 2D-4
 Please stick the barcode label tr-

ci feinally there is a non-empty stack A and an empty stack B.

4C|

!
. 9$ j

I 40

X texes

3 Bottom <- Bottom 13 Bottom Bottom

of A of B of A of B
i j I j
i I
Initial content Final content

*! 1: is found that the apples in the bottom N boxes in A are rotten. Write the pseudocode for removing
±e tenom N boxes and keeping the remaining boxes in the original order in A with the use of
f REV(X,Y).

i -1
?
i

i
<

(4 marks/

t * nez incrementing REV, Peter uses break points for debugging. Describe how break points can help
r -rite a program.

-
(2 marks >

Answo n -.ut will not be marked.

67
 2. Mr Wong plans to write a score processing program. He uses an array Score to store N students’ scores.
The scores are sorted in descending order. In the following example, the first seven scores are shown.

Index 1 2 3 4 5 6 7
Score 91 83 72 67 67 67 48

A subprogram QueryByScore (SC) returns the number of students whose scores are equal to SC.

(a) Referring to the example above, what is the return value of QueryByScore (67) ?
(1 mark)

Mr Wong uses the following pseudocode for QueryByScore (SC) :

QueryByScore(SC)
i <- BinSearch (SC)
if i <> -1 then
a <- goLeft(i)
b <- goRight(i)
return b a + 1
else return 0
•u <D
Q
^4
where BinSearch (SC) returns a value k for Score[k] = SC using the binary search strategy,
CJ or returns -1 if not found, E
£ goLeft(i) returns the smallest value j for Score[j] = Score [i], and Q
o -O
x>
goRight(i) returns the largest value j for Score[j] = Score [i].
c a

(b) (i) Write the pseudocode for BinSearch (SC). £

C/J
G
c
‘Eb ‘Sb

£ E
Q -G
G
C a
G
a
Q
O

£
12
o
Q
£ £
oc
C
c
< <

(5 marks)

Answers written in the margins will not be marked.

68
2019-DSE-ICT 2D-6
 Please stick the barcode label he

The pseudocode for goLeft(i) is

goLeft(i)
j i
while (j > 1) and (Score(j-1] Score(i]) do
j j-1
return j

(ii) Write the pseudocode for goRight (i).

i
•c

rz

o
(3 marks)
o
c
(c) Mr Wong considers using a linked list instead of an array to store students’ scores in descending order.
An example is shown below.
» Score 91 Score 83 Score 2

r
■s
next next next null

(i) Mr Wong finds that it is more difficult to implement goLeft than goRight. Why?
.E

I
I
I
(2 marks)

(ii) Can BinSearch be implemented with the linked list efficiently? Explain briefly.

(1 mark)

(iii) Assume that a new top score will be added. Do you agree that it is more efficient to use the linked
list instead of the array? Explain briefly.

(2 marks)
Answers written in the margins will not be marked.

69
2019-DSE-ICT2D-7
 3. The system development team of a company redevelops its employee management system. There is some
discussion during the system development.

(a) (i) The system development will include five development phases, shown below. In which
development phase does each of the following discussions take place?

Phase 1: Systems analysis

Phase 2: Systems design
Phase 3: Systems implementation
Phase 4: Systems conversion and maintenance
Phase 5: Systems documentation
Development phase
(1,2, 3, 4 or 5)
Discussion 1
Greg: Referring to the Gantt chart, I’ll start to write some subprograms next
month. Can I have the data flow diagrams?
Eva: I’m working on the data flow diagrams based on the collected user
requirements. I’ll email them to you next week._____________________
Discussion 2
Eva: The new system has been in use for three months. What have you found?
Clara: Some reports generated by the old system and the new system are
"O
X5
<y
inconsistent.__________________________________________________
Discussion 3 c8
GJ
E Tom: I hope that the new system can keep track of the updated employee s
Q
CJ
-O records. Please design a system with multiple user accounts and X)

implement it after the summer. a

c
Eva: Noted. Til incorporate your requirement into the design.
* (3 marks) JV)
V) C
C
'Eb 'Eb
C3
(ii) Who is the system analyst in the system development team? Justify your answer. gj

E E
O
Q
.£ -5
c a
c
a cj
Q

§
VO £
o
<5
(2 marks) £
£ C/J
co c
C
< (iii) Give two benefits of using a Gantt chart for system development. <

(2 marks)

(iv) Referring to Discussion 2, what strategy has been used to change the old system into the new
system?

(1 mark)

Answers written in the margins will not be marked.

70
2019-DSE-ICT 2D-8
 i Discussion 4 i
- Greg: What testing will we do?
Eva: \Vc will conduct unit testing, system testing and acceptance testing.

(b) (i) After unit testing is completed, why should system testing be conducted?

(1 mark I
(ii) After system testing is completed, why should acceptance testing be conducted?

1 (1 mark.)
f
' piscussion.5 ‘ ' i
a
Greg: In the system, there are a number of subprograms. I suggest using a procedural programming
language for the implementation. s

I
il
Eu Xo. we should use an object-oriented programming

(c) (i) (h\t an advantage ofGregs suggestion over Eva’s.

language to implement the svctPm

E
*

* (1 mark)

<
I .G:ve ar. adxir.^ge of Eva ’s suggestion over Greg’s.

(1 mark.
I m Vsai.a linkers and loaders are involved in compiling an object-oriented program. What are the
c: Arerces between them?

(2 marks >

-qfkss wrtaar * sbe will not be nwi keJ.

’I
 4. A grid with 5x6 cells is used to overlay a map showing an island and an ocean, as shown below:

2 5 6

2 0 5,
R
3 0 0 2 9 2

2 3 2

5 0

In each cell, there is a number representing the number of people (in thousands) living in that area. A TJ
•o Q
two-dimensional array R is defined and R [ i, j ] stores the number of people in the corresponding cell.
c3
c5 e
E Peter and Mary plan to build a squared WiFi zone to cover the island. A WiFi zone with K * K cells can be
<u X)
♦—» represented by Z (i, j , K), where (i, j ] is the top left comer of the WiFi zone on the map.
c
c

£
(a) Suppose that there is a WiFi zone with 2x2 cells.
c/j

'I
Vi

'I (i) What is the number of people in Z (1,2,2) indicated by the bold square in the grid above? CQ
E
£ Q
x:
.G

g (1 mark) G

e
a
o
S
c (ii) The WiFi zone is relocated to serve the maximum number of people on the map. *C
‘C
£ £
2 (1) The WiFi zone is Z( , 2). Q
Q
£ £
VI
(1 mark) vi
a
< <
(2) How many people are living in the WiFi zone?
(1 mark)

Answers written in the margins will not be marked.

72
2019-DSE-ICT 2D-10
 *

mnTiT- -M B <r7~ “

the number of people living in the WiFi zone I

Peter x ' “S .« ' tetum
2 I 1 f . X)

(b) (i> :K ky <. be,ow-

1 :no A > V

<
I
I inc ?o
A frc» I to do
I me *0 i.—

b fiA’n 1 to I do
line <*0
S..T V 5UH1 * R( ]
I .me SO

I inc b0.
(4 marks)

(ii) Peter finds that SamR Axs not work properly if part of the WiFi zone lies outside the map, for
example. 2 (1,5,3) •

l\ 5 6

0
=
£
2 0
R
2 2 0

5 1 0 1 1
5 i
__ I
1

<
Rewrite Line 50 in (b/i) to solve the problem. Assume that the number of people living outside
the grid is zero.

|
■

(2 marks)

a-zTten in the margins will not he iwnF.cd

71
2( uOS£4CT2I>-H
 There is another array S such that S [ i, j ] stores the number of people living in the rectangular area from
R [ 1, 1 ] to R [ i, j ]. For example,

\j 1 2 3 4 5 6 2 3
i\
1 0 1 3 5 7 8 0
2 0 2 7 16 23 25
S 2 0
3 0 2 27 36 38 R
3 0 0 2 2
4 1 5 16 38 50 54

5 2 7 19 41 54

S[2,3] = R[l,l] + R[l,2] + R[l,3] + R[2,1] + R[2,2] + R[2,3] = 7

<□

C3
£
£ u
u JD
(c) What is the value in S [ 3Z 3] ?
a
c (1 mark)
£
V)
c
Instead of summing up all R terms, Mary calculates S[i,j ] by using its adjacent S values.
I -Su?
’eh c3
c3 £
£ Q
u (d) Complete the following formula for S [ 5 f 6 ]. X
X
c
.£ c
a Q
o
•—»
S[5,6] = R[5,6] + S[5,5] + S[4Z 6] - S[ 1 II "C
'I (2 marks) £
I i2
u
5 £
I
c
I c
<
<

Answers written in the margins will not be marked.

74
2019-DSE-ICT 2D-12
 , i, j, h m remtn . .......... "< tbe W1Fi zone
- ■ - Z-

i
—or ija» tx y- fcrxnula for aiculntinn 7. { ‘ t 7} in Suh*'/,

(2 marks)

' ■r i px. i 4 -sr* .zzgt z riber of cell#, why in Mary’s method fSurrS; better than Peter’s
'"C'.x'.C :.

z
(2 marks)
I
'£
I

i END OF RAPER
z
i

z\
&

'i <■

Answers written in the margins will not be marked.

75
2019-DSE-ICT2D-I3
=

Marking Schemes

This document was prepared for markers’ reference. It should not be regarded as a set of model answers.
Candidates and teachers who were not involved in the marking process are advised to interpret its content
with care.

General Notes on Marking

1. Teachers are strongly advised to conduct their own internal standardisation procedures using the marking
scheme before the actual marking begins. After standardisation, teachers should adhere to the marking
scheme to ensure a uniform standard of marking within the school.

2. The marking scheme may not exhaust all possible answers for each question. Teachers should exercise their
professional discretion and judgment in accepting alternative answers that are not in the marking scheme, but
are correct and well- reasoned.

3. The following symbols are used:

X This symbol indicates a wrong or unacceptable answer.

Shaded words, figures or ideas are not essential for the candidate to be awarded the point.

/ A single slash indicates an acceptable alternative within an answer.

+ A plus sign indicates that there are two pieces of information and the second part will be
awarded points only when the first part is correct.

4. In questions asking for a specified number of reasons or examples etc. and a candidate gives more than the
required number, the extra answers should not be marked. For instance, in a question asking candidates to
provide two examples, and if a candidate gives three answers, only the first two should be marked.

76
 Mary then develops a subprogram SumS (i, j , K) to return the number of people living in the WiFi zone
Z(i,j,K) by using S.

(e) Complete the following formula for calculating Z (3, 4 z 2) in SumS.

Z(3,4,2) = S[4,5] - S(4,3] - S[2,5] + S[ ]

(2 marks)

(f) For a grid with a very large number of cells, why is Mary’s method (Sums) better than Peter’s
method (SumR)?

•o
o
(2 marks)
s
Q
X
j
c

c/s | END OF PAPER

E
o

c
c
y1
I
U I
£
ou I
£z
C
<

I
a
|
I

Answers written in the margins will not be marked.

2019-DSE-ICT2D-13 75