2000 Ce Cs Paper Ii C Version

2000-CE COMP STUD

Candidate Number

PAPER I (SECT B & C)

Centre Number HONG KONG EXAMINATION AND ASSESSMENT AUTHORITY HONG KONG CERTIFICATE OF EDUCATION EXAMINATION 2000

Seat Number

COMPUTER STUDIES PAPER 2 Question-Answer Book 11:15 am – 1:15 pm (2 hours) This paper must be answered in English Marker’s Use Only Marker No.

Examiner’s Use Only Examiner No.

Q.1 Instructions: 1.

Write your Candidate Number, Centre Number and Seat Number in the spaces provided.

2.

Answer all questions.

3.

Write your answers in the spaces provided in this question-answer book.

4.

Supplementary answer sheets will be supplied upon request. Write your Candidate Number on each sheet and fasten them with string inside this book.

Q.2 Q.3 Q.4 Q.4

0

1

2

3

4

0

1

Total

Checker’s Use Only Checker No. Total

2000-CE-COMP STUD 1B & C-1 (C Version)

2

3

4

1.

(a)

Tai Ming writes a program to accept two character strings and output a message to say if the second character string is part of the first one. The program should produce the output below on the VDU. (In this output, all the data following a colon is entered through the keyboard by the user. All other items are output from the program.) Enter Enter Enter Enter Enter Enter Enter Enter

the the the the the the the the

length of character character character character character character character

character string 1 : 7 1 of string 1 : s 2 of string 1 : i 3 of string 1 : x 4 of string 1 : t 5 of string 1 : e 6 of string 1 : e 7 of string 1 : n

Enter the length of character string 2 : 4 Enter the character 1 of string 2 : t Enter the character 2 of string 2 : e Enter the character 3 of string 2 : e Enter the character 4 of string 2 : n String 2 is a part of string 1.

2000-CE-COMP STUD 1B & C-2 (C Version)

Tai Ming’s program is shown below: Line Number 10 20 30

Program Statement #include <stdio.h> #define true 1 #define false 0

int main() 40 { 50 char pat1[2][10]; 60 int size1, size2, i, j; 70 int match; 80 90 printf("Enter the length of character string 1 : "); 100 scanf("%d", &size1); 110 for ( i = 0; i < size2; i++ ) 120 { 130 printf("Enter the character %d of string 1 : ", i + 1); 140 scanf(" %c", &(pat1[0][i])); 150 } 160 printf("\n"); 170 printf("Enter the length of character string 2 : "); 180 scanf("%d", &size2); 190 for ( i = 0; i < size2; i++ ) 200 { 210 printf("Enter the character %d of string 2 : ", i + 1); 220 scanf(" %c", &(pat1[0][i])); 230 } 240 i = 1; 250 match == false; 260 while ( match && (i + size2 <= size1) ) 270 { 280 for ( j = 0; j < size2; j++ ) 290 if ( pat1[0][I - j] != pat1[1][j] ) 300 match = false; 310 i--; 320 } 330 if ( match == true ) 340 printf("String 2 is a part of string 1.\n); 350 else 360 printf("String 2 is NOT a part of string 1.\n"); 370 } 380 However, there are several mistakes after line 80 in the program. Fill in the following table to show the location of each mistake and its correction. Line Number

Corrected Statement

(12 marks)

2000-CE-COMP STUD 1B & C-3 (C Version)

(b)

A small grocery store sells only 5 types of items: A, B, C, D and E which can be grouped into 3 different categories. A, B, and C belong to category 1, D belongs to category 2, and E belongs to category 3. When a customer checks out at the counter, a program in the cashier’s computer is executed to calculate the total number of purchased items for a customer as well as the subtotals for the 3 categories. The algorithm of the computer program is shown below. Step 1:

Declare the following integer variables: totalsum, i, qty, complete. Declare a character variable pitem. Declare a one-dimensional integer array subtotal of size 3. Step 2: Initialize totalsum to be 0; complete to be false and all elements in subtotal array to be 0. Step 3: As long as complete is false, do steps 4 – 9 again. Step 4: Read an item type into pitem. Step 5: If pitem equals ‘Q’, then assign true to complete; otherwise Step 6: Read in the quantity of the item type purchased into qty. Step 7: Do Step 6 again when the input value of qty is not between 1 and 10 inclusively. Step 8: Increase the corresponding element in subtotal by qty according to the category of pitem. Step 9: Increase the value of totalsum by qty. Step 10: Display totalsum and the subtotal array. Convert the algorithm into a C program.

2000-CE-COMP STUD 1B & C-4 (C Version)

(13 marks)

2000-CE-COMP STUD 1B & C-5 (C Version)

2.

The following C program reads a set of character strings, stores them in an array, and uses another integer array to sort and reference these character strings afterwards. Line numbers are added to the program listing for reference only. Line Number 100 110 120 130 140 150 160

int slist[40]; char varray[40][80]; char sitem[80]; int minv, size1;

170 180 190 200 210 220 230 240

void PrtOrdSeq(int pos) { while ( pos != -1 ) { printf("%s\n", varray[pos]); pos = slist[pos]; } }

300 310

int P1(char sitem[], int nextstr) ……

500 510

int P2(char sitem[], int i, int nextstr) ……

700 710 720

int main() { int i; for ( i = 0; i < 40; i++ ) slist[i] = -1; size1 = 0; do { printf("Enter character string %d :", size1 + 1); scanf("%s", sitem); if ( strcmp(sitem, "quit") != 0 ) size1 = P2(sitem, size1, minv); } while ( strcmp(sitem, "quit") != 0 ); PrtOrdSeq(minv); return 0;

730 740 750 760 770 780 790 800 810 820 830 840 850

(a)

Program Statement #include <stdio.h> #define true 1 #define false 0

}

(i)

What is the variable used for counting the number of inputted character strings?

(ii)

Rewrite lines 760 - 820 by completing the following program segment: printf("Enter character string %d :", size1 + 1); scanf("%s", sitem); while ( {

)

} (6 marks)

2000-CE-COMP STUD 1B & C-6 (C Version)

(b)

In the program, the array slist is used to reference and order the strings stored in the array varray. An index in slist corresponds to a character string stored in varray. The value stored in an element of slist represents where to find the next character string after the element in varray. If the value equals -1, there is no next character string afterwards. Examples of the first 4 elements in varray and first 4 elements in slist after inputting 4 character strings are shown below: varray [0] boy

[1] cat

[2] apple

[3] flower

slist [0] [1] [2] [3] 1 3 0 -1 In the above example, the alphabetical order of the four character strings represented by slist is ‘apple, ‘boy’, ‘cat’ and ‘flower’. The index of slist[2] corresponds to the third element of varray (varray[2]) which stores ‘apple’. The next character string is located by first taking the value stored in slist[2], which is 0; and it represents the position of ‘boy’ in varray (varray[0]). Similarly, the next character string after ‘boy’ is located by slist[0]. The function P1 is given below: int P1(char sitem[], int nextstr) { int before; int done_flag; done_flag = false; do { before = nextstr; nextstr = slist[before]; if ( nextstr == -1 ) done_flag = true; else if ( strcmp(sitem, varray[nextstr]) < 0 ) done_flag = true; } while ( !done_flag ); } (i)

return before;

Complete the following table by dry-running P1. Case

(ii)

Values passed to the function

1

sitem = “bus” and nextstr = 2

2

sitem = “archie” and nextstr = 2

3

sitem = “dog” and nextstr = 1

Value of before just before exiting the function

What is the purpose of P1?

(8 marks)

2000-CE-COMP STUD 1B & C-7 (C Version)

(c)

The function P2 is given below: int P2(char sitem[], int i, int nextstr) { int curstr, newpos; newpos = i; strcpy(varray[newpos], sitem); if ( i == 0 ) minv = 0; else { if ( strcmp(sitem, varray[minv]) <= 0 ) { slist[newpos] = minv; minv = newpos; } else { curstr = P1(sitem, nextstr); if ( slist[curstr] != -1 ) slist[newpos] = slist[curstr]; slist[curstr] = newpos; } } return i + 1; } (i)

Complete the following table by dry-running P2. Case

(ii)

Values passed to the function

1

sitem = “bus”, i = 4 and nextstr = 2

2

sitem = “come”, i = 5 and nextstr = 0

Value of slist[i] just before exiting the function

What is the purpose of P2?

(6 marks)

2000-CE-COMP STUD 1B & C-8 (C Version)

(d)

Assume that the program is now run from the beginning and the user inputs the following character strings sequentially into the program: Peter Sang Sue Black Peter Ho John June quit (i)

Complete the following table with the value of MINV immediately before executing line 820. sitem value before executing line 820 Peter Sang

Value of minv 0

Sue Black Peter Ho John June (ii)

Write the output of the program after execution.

(5 marks)

2000-CE-COMP STUD 1B & C-9 (C Version)

3.

Wai-chu writes a computer game using a C program. The specifications of the game are as follows. I.

The game is played by 2 players.

II.

The game uses a table of size n  n (i.e. a table with n rows and n columns) where n is an integer whose value is between 2 and 8 inclusively. Each cell in the table is referenced by a row number and a column number.

III.

At the beginning of the game, the computer asks a player to input n, and then it creates a table of size n  n. The value of each cell in the table is an integer randomly generated between 1 and 9 inclusively. For example, if n entered by a player is 3, the computer will create a table of size 3  3 as below: row 1 row 2 row 3

IV.

column 1 5 2 1

column 2 6 1 4

column 3 3 7 9

Each of the two players chooses any one of the cells in the table in turn. After a player has chosen a cell, the content of the table is updated according to the following rules. Rule A: In all cases, if the value in a cell is 0, it will remain 0. Rule B: The value in the chosen cell will decrease by 1. Rule C: The value(s) in the cell(s) of the same row will decrease by 1. Rule D: The value(s) in the cell(s) of the same column will decrease by 1. For example: If player 1 chooses the cell referenced by row 2 and column 1, the values in the cells of the table will be updated as follows. column 1 column 2 column 3 4 6 3 row 1 1 0 6 row 2 0 4 9 row 3 If player 2 chooses the cell referenced by row 1 and column 2, the values in the cells of the table will be updated as follows. row 1 row 2 row 3

V.

column 1 3 1 0

column 2 5 0 3

column 3 2 6 9

At the end of each turn, if ANY of the following 3 conditions is satisfied, the player of that turn wins, and the game ends. Condition 1: Condition 2: Condition 3:

The sum of the values in any row is 0. The sum of the values in any column is 0. The sum of the values in any diagonal is 0.

2000-CE-COMP STUD 1B & C-10 (C Version)

The following shows a sample output of the game. (In this output, all the data following a colon is entered through the keyboard by the user. All other items are output from the program.) Enter the size of the table: 3 A 3 x 3 table is generated The values of the cells in the table are > 5 6 3 2 1 7 1 4 9 Turn > Player 1 Please enter the row number: 2 Please enter the column number: 1 The values of the cells in the table are > 4 6 3 1 0 6 0 4 9 Turn > Player 2 Please enter the row number: 1 Please enter the column number: 2 The values of the cells in the table are > 3 5 2 1 0 6 0 3 9 Turn > Player 1 Please enter the row number: 1 Please enter the column number: 1 The values of the cells in the table are > 2 4 1 0 0 6 0 3 9 Turn > Player 2 Please enter the row number: 1 Please enter the column number: 3 The values of the cells in the table are > 1 3 0 0 0 5 0 3 8 Player 2 wins the game.

2000-CE-COMP STUD 1B & C-11 (C Version)

The declaration and the main body of the program have already been written by Wai-chu. Some functions and procedures are missing. Part of the program is as follows. #include <stdio.h> #define true 1 #define false 0 int square[8][8]; int turn, row_chosen, column_chosen, n; ……….. ……….. int main() { printf("Enter the size of the table: "); scanf("%d", &n); init(square); printf("A %d x %d table is generated\n", n, n); show(square); turn = 2; while ( !endgame(square) ) { if ( turn == 1 ) turn = 2; else turn = 1; printf("\n"); printf("Turn > Player %d\n", turn); get_data(); process(square, row_chosen - 1, column_chosen - 1); show(square); } printf("\n"); printf("Player %d wins the game.\n", turn); } Identifiers square turn row_chosen column_chosen n

Description 2-dimensional array used to store the values of the cells in the table variable used to store player number of the current turn variable used to store row number variable used to store column number variable used to store the size of the table

2000-CE-COMP STUD 1B & C-12 (C Version)

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

The procedure init is used to assign random integers to the n  n table. Complete the procedure init by filling in the missing parts in the following program segment. void init( { int r, c;

)

srand(time(NULL)); for ( r = 0; r < n; r++ ) for ( c = 0; c < n; c++ ) square[r][c] =

;

} (2 marks) (b)

Write the procedure get_data to get the row and column number entered by the players without data validation. void get_data() {

} (2 marks)

2000-CE-COMP STUD 1B & C-13 (C Version)

(c)

Write the procedure show to display the contents of the table. void show(int square[8][8]) { int r, c;

} (3 marks) (d)

Write the procedure process to implement all the rules mentioned in the specification of the game. void process(int square[8][8], int row, int column) { int r, c;

} (5 marks)

2000-CE-COMP STUD 1B & C-14 (C Version)

(e)

(i)

Write a function sumrow that returns the sum of a row. int sumrow(int square[8][8], int r) { int c, sum;

} (ii)

Write a function sumcolumn that returns the sum of a row. int sumcolumn(int square[8][8], int c) { int r, sum;

} (iii)

Write a function sumdiagonal1 that returns the sum of a diagonal from upper left corner to lower right corner. int sumdiagonal1(int square[8][8]) { int point, sum;

}

2000-CE-COMP STUD 1B & C-15 (C Version)

(iv)

Write a function sumdiagonal2 that returns the sum of a diagonal from upper right corner to lower left corner. int sumdiagonal2(int square[8][8]) { int point, sum;

} (7 marks) (f)

Using the 4 functions in part(e), write a function endgame that returns a true value if any one of the 3 conditions mentioned in specification V is satisfied, otherwise, returns a false value. int endgame(int square[8][8]) { int r, c, flag;

} (6 marks)

2000-CE-COMP STUD 1B & C-16 (C Version)

4.

(Note: In this question, a maximum of 4 marks will be awarded for effective communication.) Fat Roberto’s is a popular Italian restaurant. The owner of the restaurant, Mr Roberto Celini, feels that the business is growing so fast that the kitchen and t he dining room are getting out of control. Customers have been complaining that the food quality and service are deteriorating. Mr Cellini decides to hire a consulting firm to review the operations of the restaurant. The consulting firm has conducted a survey of customers, the kitchen staff, the waiters and the manager of the restaurant. The observations below are some of the most common problems cited in the survey. Observations made by customers • Orders are cancelled because waiting time is too long. • Food is cold when delivered to the table. • The bill is wrong. • Customers are not informed when particular food items are sold out. Observations made by waiters • Different order slips must be used for entrées (main courses), beverages (drinks), appetizers, and desserts. • Orders must be written in Italian for the Italian chef. • Kitchen staff do not inform waiters when particular food items are sold out. • Workloads of waiters is not fairly distributed. Observations made by kitchen staff • Some raw materials are frequently over-stocked while others are under-stocked or rotten when needed. • Cooked food is left in the kitchen for a long time. By the time the food is delivered to the table, it has turned cold. • Order slips were difficult to read or wrong. • Orders are written for particular food items that are already sold out. Observations made by the manager • The record of the stock level of raw materials is not kept accurately. • Waiters spend too much time writing orders and traveling back and forth from the kitchen. Thus, less time is spent on serving the customers in the dining room. The consulting firm has proposed to computerize the operations. Several networked computer terminals will be installed in the kitchen, in the dining room, at the cashier counter and in the store-room. The computer system will connect the kitchen, dining room, cashier counter and store-room to form an integrated information system. (a)

What essential data items should be included in a food order slip produced by the proposed system?

(4 marks) (b)

The consultant suggests using a touch screen monitor as the input device instead of a keyboard and mouse. Give TWO advantages of this suggestion.

(2 marks)

2000-CE-COMP STUD 1B & C-17 (C Version)

(c)

The availability of some food and beverages is restricted to certain time of periods and quantities. Briefly describe the steps which the system will have to perform in order for a customers’ order to be processed correctly.

(4 marks) (d)

The consultant suggests waiters should use a personal identification number (PIN) to access the system. However, the manager feels that using a PIN is not secure enough. Suggest TWO alternatives and give reasons to support your suggestions.

(4 marks) (e)

The manager wants to have a monthly sales analysis and inventory planning report. What essential information should be included in the report?

(3 marks) (f)

Briefly describe the steps which the system will have to perform to produce a customer’s bill.

(4 marks)

END OF PAPER

2000-CE-COMP STUD 1B & C-18 (C Version)

A Partial Character List for ASCII Character 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I

ASCII 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

Character J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c

ASCII 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

Character d e f g h I j k l m n o p q r s t u v w x y z { | }

ASCII 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

List of Operators and Reserved Words (C) #include, +, -, *, /, ++, --, +=, -=, *=, /=, %=, ==, %, >, <, =, >=, <=, !=, &&, ||, !, sqrt, rand, abs, strcat, strncat, strlen, atoi, strcpy, strncpy, const, void, return, int, float, char, \0, strcmp, strncmp, true, false, FILE, main, /*…*/, if…else, for, while, do…while, switch…case…break, break, continue, scanf, printf (%d, %f, %c, %s), \n, \t, fopen, getc, fgets, putc, fputs, EOF, fclose

2000-CE-COMP STUD 1B & C-19 (C Version)