Answer ALL Questions in This Section

S.5/Grad. Exam/ CS/ Paper I/ P.12

Section A (40 marks)

Answer ALL questions in this section.

1. (a) (i) Explain why must a high-level language program be translated before it can be run?

______

(2 marks)

(ii) State ONE difference between the translation method used by a compiler and that used by an interpreter.

______

(2 marks)

(b) Usually, we buy software that has been compiled into executable machine-code format instead of original high-level language format. Give TWO reasons why software is sold in executable machine-code format.

______

(4 marks)

(a) The library of ABC school uses a computer system to keep track the borrowing and returning of the books. Each student should use student card to borrow a book. There is bar code in each of the student card. Files are used to store the student’s information and borrowing records. The librarian uses a bar code scanner to read the bar code. The information in these files is accessed immediately after the bar code is read by the scanner.

(i) What should be the information stored in the bar code of each student card?

______

(1 mark)

(ii) Suggest ONE suitable file organization for the file. Give ONE reason for your answer.

______

(2 marks)

(b) To store the information, two data files, STUDENT and TRANSACTION are maintained. The structures of the STUDENT file and the TRANSACTION file are shown below:

File / Field name / Description
STUDENT / STUDID / identity card number of the student
NAME / name of the student
CLASS / class of the student
DOB / date of birth
File / Field name / Description
TRANSACTION / TITLE / name of the book borrowed
DATE_OUT / date on which book is borrowed.
DATE_IN / date on which book is returned.

(i) Suggest ONE key field for the file STUDENT. Give a reason.

______

(2 mark)

(ii) For any THREE of the above fields, suggest ONE method of validation.

______

(3 marks)

3. Peter uses a word processor to prepare an invitation card to be sent to all of his friends. Before typing the contents of the card, Peter chooses a page layout as shown below.

There is a 3 cm gap between the edges of the page and the shaded region. The text is to be displayed within the shaded region.

(a) Write down all the necessary page set-up settings that Peter marks.

______

(2 marks)

(b) Why is it advisable to fix the page set-up before typing and formatting the contents of a document?

______

(2 marks)

In order to keep track of his academic performance, Peter uses spreadsheet software to store his examination results of Chinese, English and Mathematics for the past 5 years. And Peter has also used other spreadsheet features to process the above data.

(i) update information more efficiently.

______

(2 mark)

(ii) present information more clearly.

______

(2 mark)

4. A computer uses 8-bit binary codes to represent characters and integers. The method of representation is given by the following three rules:

type bit

8 / 7 / 6 / 5 / 4 / 3 / 2 / 1

Rule 1: When the type bit is 1, the code represents a character, when the type bit is 0, the code

represents an integer.

Rule 2: Characters are represented in ASCII code using bits 1 to 7.

Rule 3: Integers are represented by two’s complement using bits 1 to 7.

(a) Write down the character or integer represented by the following bit patterns:

(i) 00001111

______

(ii) 11100000

______

(iii) 01111010

______

(3 marks)

(b) Write down the bit pattern of

(i) the character “H”

______

(ii) the integer 30

______

(iii) the integer –11

______

(3 marks)

______

(2 marks)

5. Study the following assembly language program. All numbers are in hexadecimals.

Memory Address / Memory Content / Meaning
200 / INP / Input data from input device to accumulator
204 / SUB 500 / Subtract from accumulator the contents of address 500 and store the result in accumulator.
208 / JPN 214 / Branch to address 214 if the contents of accumulator are less than zero.
20C / JPZ 21C / Branch to address 21C if the contents of accumulator are equal to zero.
210 / BRN 204 / Branch unconditionally to address 204
214 / OUT 508 / Output the contents of address 508
218 / BRN 220 / Branch unconditionally to address 220
21C / OUT 504 / Output the contents of address 504
220 / DEC 50C / Decrease the contents of address 50C by 1.
224 / LDA 50C / Load the contents of address 50C to accumulator.
228 / JMP 200 / Branch to address 200 if the contents of accumulator are greater than zero.
22C / STP / Stop the program.

Suppose the initial content of address 500, 504, 508, 50C are C, 1, 0, 5 respectively. The input sequence is {1A, 18, 2C, 15, 24}

(a) Complete the following table to show the contents of address 50C, the output value and the contents of accumulator immediately after the execution of the instruction at address 220 for each pass. Give your answers in DENARY.

Contents of address 50C / Output Value / Contents of Accumulator
1st pass / 4 / 0
2nd pass
3rd pass
4th pass
5th pass

(4 marks)

(b) What is the function of the number stored in address 50C?

______

(2 marks)

______

(2 marks)

END OF SECTION A

Section B (40 marks)

Answer ALL questions in this section.

6. Kenneth writes a program to calculate the numbers of digits, upper-case letters, lower-case letters and other characters in a sentence respectively.

The program should have output on the VDU as follows (the data behind each colon is input from the keyboard by the user, whereas the other items are output by the program):

Sample output 1:

Input a sentence : Here are 10 apples. They cost $15.

Number of digits = 4

Number of upper-case letters = 2

Number of lower-case letters = 19

Number of other characters = 9

Sample output 2:

Input a sentence : Hey! What are you doing?

Number of digits = 0

Number of upper-case letters = 2

Number of lower-case letters = 16

Number of other characters = 6

Kenneth’s program is as follows:

Line Number

Program statement

10 / program Q1;
20 / var s, ss: string;
30 / i, DigCnt, UpCnt, LowCnt, OtherCnt : integer;
40 / begin
50 / writeln(‘Input a sentence : ‘);
60 / readln(s);
70 / for i := 1 to length(‘s’) do
80 / begin
90 / ss := copy(s, 1, i);
100 / if (ss >=’ 0’) and (ss <= ‘9’)
110 / then DigCnt := DigCnt + 1;
130 / else if (ss >= ‘A’) and (ss <= ‘Z’) then
140 / UpCnt := UpCnt + 1
150 / else (ss >= ‘a’) and (ss <= ‘z’)
170 / then LowCnt := LowCnt + 1
180 / else
190 / OtherCnt := i + 1;
200 / end;
210 / writeln(“Number of digits = ‘, DigCnt);
220 / write(‘Number of lower-case letters = ‘, UpCnt);
230 / writeln(‘Number of upper-case letters = ‘, LowCnt);
240 / writeln(‘Number of other characters = ‘, OtherCnt)
250 / end.

However, there are several mistakes after line 40 in the program. Fill in the following table to show the location of each mistake and its correction.

Line Number /

Corrected Statement

(10 marks)

7. Below is an algorithm of binary search.

Step 1: / Declare List to be an one-dimensional integer array of size 100.
Step 2: / Declare First, Last, Mid and Target to be integer variables, and Found to be Boolean variable
Step 3: / Read a number into variable Target
Step 4: / Assign 1 to be variable First.
Step 5: / Assign the size of the list to variable Last
Step 6: / Assign the value false to variable Found
Step 7: / While First <= Last and not Found
Assign (First + Last) div 2 to variable Middle
If contents in the middle of the list is equal to Target
Then assign the value true to variable Found
Else if Target < contents of middle element
Then assign Middle + 1 to variable First
Else assign Middle – 1 to variable Last
Step 8: / If Found is true
Then display the Target’s location
Else display the Target not found

Convert the algorithm into a Pascal program segment.

(10 marks)

8. The program below provides an encoding procedure Encode for an English word and a corresponding decoding procedure Decode to decode the encoded English word. Some program statements of the Decode procedure are missing.

Line Number

/ Program Statement
100 / program CODE (input, output);
110 / const M = 5;
120 / D = 21;
130 / N = 26;
140 / A = 65;
150 / var ENG, SEC: string;
160 / procedure Encode (C: string; var P: string);
170 / var Ch, Tmp: char;
180 / Len, Count, Asc: integer;
190 / begin
200 / P := ‘’;
210 / Len := length(C)
220 / for Count := 1 to Len do
230 / begin
240 / Ch := C[Count];
250 / Asc := ord(Ch) – A;
260 / Asc := (M*Asc) mod N;
270 / Tmp := chr(Asc + A);
280 / P := P + Tmp;
290 / End
300 / end;
310 / procedure Decode ( Missing statement );
320 / var Ch, Tmp: char;
330 / Len, Count, Asc: integer;
340 / begin
350 / C := ‘’;
Missing statements
800 / end;
810 / begin
820 / writeln(‘Please type an English word:’);
830 / readln(ENG);
840 / Encode(ENG, SEC);
850 / writeln(‘The resulting secret word is: ‘, SEC);
860 / writeln(‘Please type a secret word:’);
870 / readln(SEC);
880 / Decode(SEC, ENG);
890 / writeln(‘The decoded English word is: ‘, ENG);
900 / end.

You are not allowed to add any new variable in answering the question.

(a) (i) If the program segment from lines 820 to 850 is executed and the string variable ENG stores ‘EXAM’ as input, complete the following:

After executing the FOR loop when Count = 1, Ch = ______, Tmp = ______, P = ______

After executing the FOR loop when Count = 2, Ch = ______, Tmp = ______, P = ______

After executing the FOR loop when Count = 3, Ch = ______, Tmp = ______, P = ______

After executing the FOR loop when Count = 4, Ch = ______, Tmp = ______, P = ______

In line 850, SEC = ______

(ii) The encoding and the decoding formulae in the program are P = (5 X C) mod 26 and C = (21 X P) mod 26 respectively where P and C are integers from 0 to 25. By using these two formulae, complete the procedure Decode to decode the string stored in the variable SEC generated by the procedure Encode.

Procedure Decode ( ______);

var Ch, Tmp : char;

Len, Count, Asc : integer;

begin

C := ‘’;

end;

(iii) Write down the output of the variable ENG if the above procedure Decode is applied to the string stored in the variable SEC in (a)(i) and the decoding formula is changed to C = (20 X P) mod 26.

(8 marks)

(b) If this program is going to handle only small case letters (a .. z), one statement in the program should be changed. Write down the line number and the amended statement.

(2 marks)

9. In an examination, there are three different grades: grade A, grade B and grade C.

Mrs Smith is going to write a Pascal program to perform the following tasks:

Task A: Initialize the numbers of grade A, grade B and grade C’s received. Prompt for the input of a grade. If the grade input is ‘A’, ‘B’ or ‘C’, increase the corresponding number of grades by 1; otherwise, neglect the grade input. The procedure goes on until a ‘Z’ is input as a grade.

The input is case insensitive. In other words, both upper case and lower case should be acceptable.

Task B: Display the counting result in the following format:

Grade A : ***

Grade B : *****

Grade C : *

In the result, an asterisk (*) represents one count.

The following shows a sample output of the program. (In this output, all the data following a colon is input by the user through the keyboard. All other items are output from the program.)

Input a grade (or Z to stop): A

Input a grade (or Z to stop): a

Input a grade (or Z to stop): C

Input a grade (or Z to stop): a

Input a grade (or Z to stop): b

Input a grade (or Z to stop): C

Input a grade (or Z to stop): B

Input a grade (or Z to stop): b

Input a grade (or Z to stop): G

Input a grade (or Z to stop): A

Input a grade (or Z to stop): f

Input a grade (or Z to stop): Z

Grade A : ****

Grade B : ***

Grade C : **

Mrs Smith has already written the declaration and the main body of the program. Some procedures are missing. Part of the program is as follows: