2015-DSE Please stick the barcode label îu
ICT
PAPER 2D
HONG KONG EXAMINATIONS AND ASSESSMENT AUTHORITY Candidate Number
HONG KONG DIPLOMA OF SECONDARY EDUCATION EXAMINATION 2015 Pascal
Programming C
Language Used
INFORMATION AND COMMUNICATION TECHNOLOGY (Please tick one) ViSUûll BäSÏC
PAPER 2D Java
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 and 5.
(2) Tick the appropriate box for the programming language
used. No marks will be awarded if you tick either more
than one box or no boxes.
(3) 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.
(4) 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.
(5) 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.
2015-DSE-ICT 2D—1 65
•• A Z O O E O Z
Answer all questions.
1. fiunc ( a , b ) is a function with two positive integer inputs a and b, where a k b. It returns the integral part
of ( a=b ) . For example,
June 6, 2 ) returns 3 and fray.c ( 7 , 3 returns 2.
(a) (i) What will Fc u n ( 14 , 3 ) return?
(ii) moct ( a , b ) is a function that returns the remainder of ( a-b ). Complete the pseudocode of
June ( a , b ) below.
Func(a, b)
c € mod(a, b)
return b
(3 marks)
The following algorithm ALG 4 processes a Boolean array B with indices from 1 to n.
ALG1
Step l: for k from 1 to n do Step 2
Step 2: B ( kC) True
Answers written In the margins will nnt be
Answers written in the margins will not be
Step3: B(1) {- False
Step 4: for i from 1 to n do Steps 5 to 7
Step 5: if B [ i ) = True then do Steps 6 to 7
Step 6: for j from 2 to Func (n, i )
Step 7: B(i j ] T- Vals e
(b) Suppose n = 10. Dry run ALG1. Use F’ and ‘T’ to denote ‘Fat se’ and ‘True’ respectively in
the following tables.
(i) Fill in the content of B after the first pass and second pass of the loop in Step 4.
marked.
marked.
After first pass ,
B[1] B[2] B[3] B 4) B [ 5) B [ 6] B[7] B 8] B[9j B ( 1 0) '
After second pass
B[1] B 2] B 3] B[4] B[5) B[6] B[7] B(8] B 9] BI10]
(ii) Fill in the final content of B.
B[1) B [2 ) B[3] B[4] B [ 5) B [ 6) B { 7) B[8] B[9j B[10]
Answers written in the margins will not be marked.
2015-DSE-ICT 2D-2 66
Please stick the barcode label
here.
(iii) How many times will the statement in Step 7 be executed?
(iv) What is the pwpose of ALG 1?
(6 marks)
(c) (i) It is suggested that Step 4 should be changed to
‘for i from 2 to n do Steps 5 to 7’
Will this change affect the final content of B? Justify your answer.
Answers written in the margins will not be
(ii) It is suggested that changing Step 4 to
¿; ‘for i from 1 to Tuna (n, 2 } do Steps 5 to 7’
can improve the algorithm. Do you agree? Justify your answer.
marked.
(iii) ALG1 will be executed many times. Should it be implemented in a compiled language or an
interpreted language? Explain briefly.
(6 marks)
Answers written in the margins will not be
marked.
2015-DSE-ICT 2D—3 67
*p John is a project manager. He develops a vehicle repair system. The development work involves four
major tasks. The duration and dependencies of the tasks are shown below:
Duration (week) Task(s) that it de ends on
Task 1 3 Task 2
Task 2 4
Task 3 3 Task 1 and Task 4
Task 4 6
Task 5 3 Task 4
(a) (i) Complete the Gantt chart of the project below.
' I
(ii) Suppose that John spends more money to reduce the duration of Task 1, Task 2 and Task 3 by
1 week each. What is the duration of the new critical path of the project?
(5 marks) I
(b) (i) Task 2 is part of the requirements analysis stage. Give two common activities that John can do to
@ collect the requirements when doing Task 2. ’J
(ii) Task 1 is part of the implementation stage. After completing Task 1, what documents will be
prepared? Give one example and explain its use briefly.
(4 marks)
Answers written in the margins will not be
marked.
2015-DSE-ICT 2D—4 6
8
Please stick the barcode label here.
(c) John selects a programming language for the system development based on the following criteria.
Briefly describe the criteria and theé benefits for system development.
(i) Modularity
(ii) Portability
Answers written in the margins will not be marked.
Ans. wors written in ›tol margins will not h o»i
(iii) Utility libraries and development tools
(6 marks)
(d) When compiling the program code of the system, a linker is used. What is the purpose of the linker?
arked.
(2 marks)
Answers written in the margins will not be
marked.
2015-DSE-ICT 2D-5 69
3. Tony is developing a yearly school calendar system. There are events, El, E2, etc. marked in the
calendar using 1-52 and 1-7 to denote the weeks and the days respectively, as shown in the example
below. Assume that there is only one event at most each day.
Day
2 5 6 7
Week
1 El E3
2
3 E2
4
52 E88
(x, y) represents Day y in Week x in the calendar. Tony wants to use an array M so that M [x, y] stores
the name of the event on (x , y) . N [x, y) stores 0 if there is no event on that day.
lne wlll mol be marked.
(a) Referring to the example above, complete the following table to illustrate the content of H.
Answers written in the margins will not be
Array element Content
M[l,5) E3
M[3,2)
M{3,3]
A its were written In
(2 marks)
thei i›agr
Tony decides to use three global arrays name, x and y to store the information on the events in the
calendar in chronological order, as shown in the example below. marked.
i name[i] i x[i] i y[i]
1 E1 1 1 1 1
2 E3 2 1 2 5
3 E4 3 3 3 2
4 E2 4 3 4 6
Answers written in the margins will not be
marked.
2015-DSE-ICT 2D—6 70
(b) Tony writes a subprogram Lname (p, q) that returns the name of the event on Day q in Week p. It
returns 0 if there is no event on that day.
(i) Suppose that n stores the total number of events. Complete the pseudocode of Lname below.
Lr.ame(p,q)
event €
for i from l to n do
if x [ i ) = p ) and (y (i ] = q do
(the third line)
event {-
return eve at
(ii) Suppose n = 4. When Lname ( 2, 3 } is called, how many times will the statement on the third line
be executed?
(iii) Compared with JH in (a), give one advantage and one disadvantage of using the three arrays to
store information on the events.
Answers written in the margins will not be marked.
Advantage:
Anewera wrlksnk i the mza slsn will not ba
Disadvantage:
(5 marks)
Tony writes a subprogram order (x1, yl , x2, y2) that returns TRUE only when (x , y1) is earlier than
(x2, y2 ) in the calendar; otherwise, it returns 2ALSE.
(c) Complete the following pseudocode of order.
order(xl, yl, x2, y2)
if ( x1/x2 ) return TRUE
else if ( x1/x2 ) return
else if ( y1<y2 } return TRUE
else return
(2 marks)
Answers written in the margins will not be
marked.
2015-DSE-ICT 2H—7 71
Tony writes another subprogram shi?t l a , b 1 that shifts all the entries with indices between a and b
backward by one position in each of the three arrays. For example, name [b+ l ] stores the value in name
[b] , name [b] stores the value in r.erre o- i ] , and so on. Finally, name [ a+ 1 ] stores the value in name
(a] ; the corresponding entries in x and y will shift too. Assume that there are n events in the calendar.
i name{i] y[i]
1 El 1
E3 2 5
n E88 n 52 n 4
Tony wants to store a new event in the three arrays in chronological order where the event name and its date are stored in
Ne WName and ( Newx, Newy} respectively. There are two subprograms order and s hi It available:
Pascal version Function order(x1, yl, x2, y2 : integer) boolean
Procedure shift(a, b : in:eger)
C and Java version int order(int x1, int yl, int x2, int y2)
void shift(int a, int b)
VöualBxscverson Function order(xl As Integer, yl As Integer,
“_ x2 As Integer, y2 As Integer) As Boolean
Sub shift(a As Integer, b As Integer)
Answers written in the margins will not be
written in tho mnrgln9 will
(d) Write a subprogram Ins era Event in Pascal, C, Visual Basic or Java that stores the information on
the new event in the calendar in chronological order using the binary search technique.
swexr
A\l
marked.
(5 marks)
Answers written in the margins will not be
marked.
2015-DSE-IC’F 2D—8 72
4. Mary wants to de›'e1op an online storage system so that customers can store text files in centralised
servers and retrieve them later. In order to minimise the demands on storage capacity, all files w'ill be
compressed before stow_•e.
(a) The flow’ of daia in the online storage system is shown below:
Text file (2’
Compressed
COmpressed text file
Text file
text file
(1) (3) Compressed (5)
text file
Text flle
Compressed
Text file
File ID
text file File ID
(4)
Match the following items:
Answers written in the margins will not be
A. File storage module D. Compression and decompression module
B. File database E. File ID verification rnodule
C. File retrieval module
F. Customers
(3)
marked.
(4)
(5)
(5 marks)
Answers written in the margins will not be
marked.
2015-DSE-ICT 2D—9 73
There are many words in the text files. Mar›,' considers using 16-bit fixed-length binary sequences or
variable-length binary sequences to encode the words. Each variable-length binary sequence has only
one ‘1’. An example is shown below:
Word Fixed-length binary sequence , 'variable-length binary sequence
pen 00 0 00 00 0 0 0 000 0 0 0 !
a 000000000000GG† l
man 0 0 00 0 0 0 fi 0 0 0 0 0 01 S 001
ha oo o oo o ooco c ceo i i
Peter 0000000000000ï 00 C0O0l
is 0 0 0 0 0 0 0 0 0 0 0 0 01 01 000001
and 0 0 0 00 0 0 0 00 0 0 011 0 0000001
(b) (i) Give an advantage of using fixed-length binary sequences.
(ii) Give an advantage of using variable-length binary sequences.
nut bo
Answers written in the margins will not be
(2 marks)
Mary decides to use variable-length binary sequences.
(c) According to the table above, ‘Peter has a pen’ will be encrided as
‘0 0 0 010 0010 11
(i) Encode ‘Peter is a man’.
marked.
(ii) Decode ‘0 1 0 010 0 0 00 010 11’.
(2 marks)
Answers written in the margins will not be
marked.
2015-DSE-ICT 2WI0 74
(d) Mary writes a function DEC t s c ) that returns the words in a look-up table for variable-length
binary sequences, as shown in the example below.
Variable-length binary sequence Word
1 pen
0 01 man
0o0l has
00 001 Peter
0000 01 is
0 00 00 01 and
Assume that a character array B with length n stores the encoded binary sequences for a text file.
Write a pseudocode to decode the sequences and display the text with the use of DEC.
Answers written in the margins will not be marked.
(5 marks)
END OF PAPER
Answers written in the margins will not be marked.
2015-DSE-ICT 2D— 75
11
