Soft Desigh and Development Engineer Examintion(Afternoon, part 2)

Chia sẻ: Tran Le Kim Yen Tran Le Kim Yen | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

50
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

There is a database in which data additions, changes, and deletions occur at a certain low frequency. The interval between backups has been increased to twice the current level for backing the database onto magnetic tape.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Soft Desigh and Development Engineer Examintion(Afternoon, part 2)

MINISTRY OF SCIENCE AND TECHNOLOGY BỘ KHOA HỌC VÀ CÔNG NGHỆ HOÀ LẠC HIGH TECH PARK BAN QUẢN LÝ MANAGEMENT BOARD KHU CÔNG NGHỆ CAO HOÀ LẠC VIETNAM IT EXAMINATION AND TRUNG TÂM SÁT HẠCH CÔNG NGHỆ TRAINING SUPPORT CENTER (VITEC) THÔNG TIN VÀ HỖ TRỢ ĐÀO TẠO (VITEC) SOFTWARE SÁT HẠCH DESIGN AND DEVELOPMENT KỸ SƯ ENGINEER THIẾT KẾ VÀ PHÁT TRIỂN EXAMINATION PHẦN MỀM 26th January 2003 Ngày 26 tháng 1 năm 2003 Afternoon I I Phần thi buổi chiều I I Do not open the exam booklet until Không mở đề thi trước khi được instructed to do so. phép. Inquiries about the exam questions Các thắc mắc về câu hỏi thi sẽ will not be answered. không được trả lời
2003 VITEC Software Design and Development Engineer Examination (Afternoon, Part 2) Questions must be answered in accordance with the following: Question Nos. Q1 Question Selection All Sub-Questions are compulsory Examination Time 15:30-16:30 (60 minutes) Instructions: 1. Use an HB pencil. If you need to change an answer, erase your previous answer completely and neatly. Wipe away any eraser debris. 2. Mark your examinee information and test answers in accordance with the instructions below. Your test will not be graded if you do not mark properly. Do not mark or write on the answer sheet outside of the prescribed places. (1)Examinee Number Write your examinee number in the space provided, and mark the appropriate space below each digit. (2)Date of Birth Write your date of birth (in numbers) exactly as it is printed on your examination admission card, and mark the appropriate space below each digit. (3)Write each answer in the space specified for that question. Answer can be written in English or Vietnamese. (4)Write your answers clearly and neatly. Answers that are difficult to read will receive a lower score. 3. After the test, you may take this question booklet home with you. Do not open the exam booklet until instructed to do so. Inquiries about the exam questions will not be answered.
2003 VITEC Class II Information Technology Engineer Examination - Afternoon Sát hạch Kĩ sư Thiết kế và Phát triển phần mềm (Buổi chiều - Phần 2) Các câu hỏi phải được trả lời tuân theo điều sau: Số hiệu câu hỏi Q1 Câu hỏi lựa chọn Tất cả các câu hỏi con đều bắt buộc Thời gian sát hạch 15:30 ~ 16:30 (120 phút) Hướng dẫn: 1. Dùng bút chì HB. Nếu bạn cần đổi câu trả lời, hãy xoá hết câu trả lời trước. Phủi sạch bụi tẩy trên giấy. 2. Đánh dấu thông tin sát hạch và câu trả lời sát hạch của bạn theo hướng dẫn dưới đây. Bài sát hạch của bạn sẽ không được chấm nếu bạn không đánh dấu đúng. Đừng đánh dấu hay viết lên tờ giấy trả lời bên ngoài chỗ đã qui định. (1) Số hiệu thí sinh Hãy viết số hiệu thí sinh ở chỗ đã cho, và đánh dấu vào chỗ thích hợp dưới mỗi chữ số. (2) Ngày sinh Hãy viết ngày sinh của bạn (theo số) đích xác như nó được in trong phiếu dự thi, và đánh dấu vào chỗ thích hợp dưới mỗi chữ số. (3) Hãy viết câu trả lời tại vị trí được dành cho câu hỏi đó. Câu trả lời có thể viết bằng tiếng Anh hoặc tiếng Việt. (4) Hãy trả lời một cách rõ ràng và gãy gọn. Những câu trả lời khó đọc sẽ bị điểm thấp. 3. Cuối giờ thi, bạn có thể giữ lại bộ đề thi này. Không mở tập giấy thi chừng nào chưa được hướng dẫn làm như vậy. Mọi việc hỏi thêm về các câu hỏi sát hạch sẽ không được trả lời.
2003 VITEC Class II Information Technology Engineer Examination - Afternoon Sát hạch Kĩ sư Thiết kế và Phát triển phần mềm (Buổi chiều - Phần 2) Các câu hỏi phải được trả lời tuân theo điều sau: Số hiệu câu hỏi Q1 Câu hỏi lựa chọn Tất cả các câu hỏi con đều bắt buộc Thời gian sát hạch 15:30 ~ 16:30 (120 phút) Hướng dẫn: 1. Dùng bút chì HB. Nếu bạn cần đổi câu trả lời, hãy xoá hết câu trả lời trước. Phủi sạch bụi tẩy trên giấy. 2. Đánh dấu thông tin sát hạch và câu trả lời sát hạch của bạn theo hướng dẫn dưới đây. Bài sát hạch của bạn sẽ không được chấm nếu bạn không đánh dấu đúng. Đừng đánh dấu hay viết lên tờ giấy trả lời bên ngoài chỗ đã qui định. (1) Số hiệu thí sinh Hãy viết số hiệu thí sinh ở chỗ đã cho, và đánh dấu vào chỗ thích hợp dưới mỗi chữ số. (2) Ngày sinh Hãy viết ngày sinh của bạn (theo số) đích xác như nó được in trong phiếu dự thi, và đánh dấu vào chỗ thích hợp dưới mỗi chữ số. (3) Hãy viết câu trả lời tại vị trí được dành cho câu hỏi đó. Câu trả lời có thể viết bằng tiếng Anh hoặc tiếng Việt. (4) Hãy trả lời một cách rõ ràng và gãy gọn. Những câu trả lời khó đọc sẽ bị điểm thấp. 3. Cuối giờ thi, bạn có thể giữ lại bộ đề thi này. Không mở tập giấy thi chừng nào chưa được hướng dẫn làm như vậy. Mọi việc hỏi thêm về các câu hỏi sát hạch sẽ không được trả lời.
2003 VITEC Software Design and Development Engineer Examination (Afternoon, Part 2) Questions must be answered in accordance with the following: Q1 Question Nos. Question Selection All Sub-Questions are compulsory Examination Time 15:30-16:30 (60 minutes) Instructions: 1. Use an HB pencil. If you need to change an answer, erase your previous answer completely and neatly. Wipe away any eraser debris. 2. Mark your examinee information and test answers in accordance with the instructions below. Your test will not be graded if you do not mark properly. Do not mark on white on the answer sheet outside of the prescribed places. (1)Examinee Number Write your examinee number in the space provided, and mark the appropriate space below each digit. (2)Date of Birth Write your date of birth (in numbers) exactly as it is printed on your examination admission card, and mark the appropriate space below each digit. (3)Write each answer in the space specified for that question. (4)Write your answers clearly and neatly. Answers that are difficult to read will receive a lower score. 3. After the test, you may take this question booklet home with you. Do not open the exam booklet until instructed to do so. Inquiries about the exam questions will not be answered. 1
Q1. Read the following text regarding the creation of a game program, then answer Sub- Questions 1 through 4. A decision was made to create a number guessing game program in which a person (hereinafter referred to as the “player”) competes with a computer. The rules of the game are as follows. (1) The competitors (player and program) each select a four-digit number consisting of four different numerals. In this example, this four-digit number is called the correct answer. The first digit in the correct answer (most significant digit) may be 0. (2) Competitors take turns trying to guess each other ’s correct answer, and the first one to guess correctly wins. If both competitors guess correctly in the same number of tries, then they tie. (3) When a competitor receives the other competitor ’s guess, it is compared with the receiving competitor ’s own correct answer, and a response is sent to the other competitor consisting of the number of hits, hit, or numerals which are correct in both numerical value and digit position; as well as the number of misses, miss, or numerals which are contained in the correct answer, but have incorrect digit positions. For example, if the correct answer is 1357 and the other competitor guesses 5310, then the response consists of one hit (hit) and two misses (miss). An overview of the number guessing game program is presented below. 1. The program determines a correct answer using random numbers. 2. The following are repeated until one of the competitors guesses the other ’s correct answer. 2-1. Comparison against correct answer The program receives the player ’s guess, compares it against the correct answer, and returns the numbers of hits, hit and misses, miss. 2-2. Guessing process 2-2-1. The program determines the next guess based on the hit and miss it has so far received, then sends that guess to the player. 2-2-2. The program receives the hit and miss calculated by the player. Below, the variables defined in the function are local variables, and the function’s arguments are passed by value unless otherwise specified. The array subscripts start at 0, and array elements are designated as 0th, 1st, 2nd, etc. Figure 1 shows the function for determining the correct answer. With this function, numbers 0 through 9 are randomly generated one at a time, and an array tab consisting of ten elements is used to obtain a four-digit number with no duplicate numerals. “random” 2
is a function for randomly generating natural numbers, and “%” is a modulus operator. The array tab is used as follows. The initial value of all elements is 0. If the tab[a] value remains at the initial value 0 for a randomly generated single- digit number a, then a is a number appearing for the first time, and 1 is inserted in tab[a]. If the value of tab[a] is 1, then the value is not changed. function set_answer () int tab[10], n, i, a Set all tab elements to 0 n=0 for (i = 1 to 4) repeat a = random() % 10 until(tab[a] = 0) tab[a] = 1 n= a endfor return n endfunction Fig. 1 “set_answer” Function The algorithm for calculating hit and miss will now be considered. First, the similarity of two four-digit numbers x and y is defined as follows, using the hit and miss of the two numbers: similarity(x, y) = hit * 10 + miss The set of the similarity values and the (hit, miss) values has a one-to-one correspondence, so the similarity is used within the program instead of the hit and miss. Similarity calculation is used when the player ’s guess is compared with the correct answer, and when the program is determining its own guess. This calculation is done frequently, so a highly efficient execution method will now be considered. In order to improve execution efficiency, before similarity is calculated during the game, one of the numbers to be compared is translated into a form called an array expression. In this translation process, if the subject number is d4d3d2d1, then i is stored in the dith element of the array, and 0 is stored in the other elements. Figure 2 shows the 3
function for translating the number y into an array expression. “pos” is an array which comprises ten elements and is called by reference. function make_pos(y, pos) int i, m Set all pos elements to 0 for(i = 1 to 4) m = y % 10 y = y / 10 pos[ ]=i b endfor endfunction Fig. 2 “make_pos” Function When the array expression (pos) for the number y is used, similarity(x, y) can be determined using the “sim” function in Figure 3. 4
function sim(x, pos) int hit, miss, i, p hit = 0 miss = 0 for(i = 1 to 4) p = x % 10 x = x / 10 if( ) c if( ) hit = hit + 1 d else miss = miss + 1 endif endif endfor return hit * 10 + miss endfunction Fig. 3 “sim” Function The guessing algorithm will now be considered. If all four-digit numbers consisting of four different numerals are generated, the set of generated numbers will necessarily contain the correct answer. Therefore, these numbers are generated in advance and inserted in the “nums” array. The algorithm for selecting a guess value in order to guess the player ’s correct answer is as follows. Numbers are taken from “nums” sequentially, and a number which is not inconsistent with the similarity information obtained thus far is used as the next guess. For example, consider a case in which the third guess is to be selected. Assume that the similarity values of the correct answer and the previous two guesses were as follows: Guess similarity First 1234 12 Second 1345 02 In this case, assume that the next number taken from “nums” is 2304. A calculation is performed to determine whether 2304 is suitable as the next guess, with the following results: similarity(2304, 1234) = 12,similarity(2304, 1345) = 11. These results show that 2304 is inconsistent with the second result, so it is not suitable as the next guess. 5
Now assume that the next number taken from “nums” is 0432. A calculation is performed to determine whether 0432 is suitable as the next guess, with the following results: similarity(0432, 1234) = 12,similarity(0432, 1345) = 02. These results show that 0432 is not inconsistent with the previous results, so it is used as the next guess. When these considerations are put together, the function for determining the kth guess is as shown in Figure 4. In this case, the “nums” array is an array containing correct answer candidates; guess[i-1] is the array expression for the ith guess; and log[i-1] is the similarity value between the ith guess and the correct answer. “index” is a subscript specifying a position before which the correct answer does not exist in the “nums” elements. The initial value for “index” is –1. function make_guess(k) int j index = index + 1 // Infinite loop for() j=0 while(j < k – 1 and sim(nums[index], guess[j]) = log[j]) e endwhile if(j < k - 1) f else return nums[index] endif endfor endfunction Fig. 4 “make_guess” Function 6
When all of the above-mentioned functions are used, the number guessing game program is as shown in Figure 5. “nums”, “guess”, “log” and “index” are global variables. int log[M], guess[M][10], nums[N], index // M and N are array sizes main() char r In “nums”, insert all four-digit numbers comprising four different numerals // Repeat game for() () play write “Continue game? Y/N” read r // Player selects to end game if(r = “N” ) exit endif endfor endmain function play() int ans, pos_a[10], i, r, g, hit, miss, guess_person ans = set_answer() make_pos(ans, pos_a) index = -1 i=1 // Repeat until correct for() // Read player ’s guess read guess_person r = sim(guess_person, pos_a) // Calculate similarity // Display results write r / 10, r % 10 // Calculate i th guess (i) g = make_guess // Display guess write g // Read guess results read hit, miss if(hit = 4 or r = 40) // Was guess correct? break endif // Record results log[i-1] = 10 * hit + miss // Record guess make_pos(g, guess[i-1]) i=i+1 endfor // Player wins if( ) g write “You win” // Computer wins elseif( ) h write “I win” else // Tie write “It’s a tie” endif endfunction Fig. 5 Number Guessing Game Program 7
Sub-Question 1 In the program in Figure 5, what is the minimum size N of the “nums” array? Sub-Question 2 Insert appropriate words in blanks through in Figs. 1 through 5. a h Sub-Question 3 After the player plays the game for a while, the program stops responding. An investigation of the issue showed that it occurred because the player ’s hit or miss response value was incorrect, so the program could not find a candidate which would be the correct answer. Changes need to be made so that in such cases, “make_guess” returns a value of –1. What type of judgment should be added to the “make_guess” function in Fig. 4? Answer in 4 words or less. Sub-Question 4 In the algorithm of the program in Figure 5, the computer always repeats the same guesses every time, even when the player plays against the computer repeatedly. For this reason, it becomes possible for the player to find numbers that are difficult for the computer to guess. In order to avoid this, the program should use a different sequence of guesses each time. In order to use a different guessing sequence each time, a certain operation should be performed on the “nums” array value immediately before “play” is called from “main”. Describe this operation in 4 words or less. 8
[Memo] 9
[Memo] 10
2003 VITEC Software Design and Development Engineer Examination (Afternoon, Part 2) Questions must be answered in accordance with the following: Question Nos. Q1 Question Selection All Sub-Questions are compulsory Examination Time 15:30-16:30 (60 minutes) Instructions: 1. Use an HB pencil. If you need to change an answer, erase your previous answer completely and neatly. Wipe away any eraser debris. 2. Mark your examinee information and test answers in accordance with the instructions below. Your test will not be graded if you do not mark properly. Do not mark on white on the answer sheet outside of the prescribed places. (1) Examinee Number Write your examinee number in the space provided, and mark the appropriate space below each digit. (2) Date of Birth Write your date of birth (in numbers) exactly as it is printed on your examination admission card, and mark the appropriate space below each digit. (3) Write each answer in the space specified for that question. (4) Write your answers clearly and neatly. Answers that are difficult to read will receive a lower score. 3. After the test, you may take this question booklet home with you. Do not open the exam booklet until instructed to do so. Inquiries about the exam questions will not be answered. 1
Q1. Hãy đọc đoạn văn sau đây về việc viết một chương trình trò chơi, sau đó trả lời các câu hỏi con từ 1 đến 4. Người ta quyết định thực hiện một chương trình trò chơi đoán số trong đó một người (từ đây gọi là “người chơi”) thi đấu với một máy tính. Luật của trò chơi như sau: (1) Mỗi bên đấu thủ (người chơi và chương trình) chọn một số có 4 chữ số, mỗi chữ số đều khác nhau. Trong ví dụ này, số 4 chữ số này gọi là đáp án đúng. Chữ số đầu tiên trong đáp án đúng (chữ số có nghĩa nhất) có thể bằng 0. (2) Các đấu thủ đến lượt chơi sẽ đoán đáp án đúng của bên kia, và bên nào đoán đúng trước là bên thắng. Nếu cả hai đấu thủ đoán đúng sau cùng số lần đoán, thì hoà. (3) Khi một đấu thủ nhận câu đoán của bên kia, nó so sánh câu đoán với đáp án của mình, và trả lại đối phương số điểm đoán đúng, hit, tức là số chữ số đoán đúng cả về giá trị và vị trí, cũng như số điểm đoán sai, tức là số chữ số có trong đáp án nhưng lại sai về vị trí. Ví dụ, nếu đáp án là 1357 và số đoán là 5310, thì trả lời là một đúng (hit) và 2 sai (miss). Tổng quan về chương trình đoán số được trình bày dưới đây. 1. Chương trình tự đặt ra một đáp án đúng sử dụng các số ngẫu nhiên. 2. Các thủ tục sau lặp đi lặp lại cho đến khi một đấu thủ đoán được đáp án của đối phương. 2-1. So sánh với đáp án đúng Chương trình nhận phỏng đoán của người chơi, so sánh nó với đáp án đúng, và trả lại số đúng, hit và số sai, miss. 2-2. Quy trình đoán 2-2-1. Chương trình đoán tiếp dựa trên số hit và miss đã nhận được cho đến lúc đó, sau đó gửi phỏng đoán cho người chơi. 2-2-2. Chương trình nhận lại số hit và miss do người chơi tính. Dưới đây, các biến định nghĩa trong hàm là các biến cục bộ, và tham số của hàm được truyền theo giá trị trừ khi được nói khác. Chỉ số mảng bắt đầu từ 0, và các phần tử mạng được chỉ ra là phần tử thứ 0, thứ 1, thứ 2, v.v. Hình 1 biểu diễn hàm dùng để xác định đáp án đúng. Với hàm này, các số từ 0 đến 9 được sinh ngẫu nhiên từng số mỗi lần, và một mảng tab chứa 10 phần tử được dùng để thu được một số có 4 chữ số không có chữ số trùng nhau. “random” là hàm dùng để sinh ngẫu nhiên một số tự nhiên, và “%” là phép chia lấy phần dư. Mảng tab được dùng như sau: 2
Giá trị khởi tạo của tất cả các phần tử bằng 0. Nếu giá trị tab[a] vẫn còn là giá trị khởi đầu 0 cho một số a có 1 chữ số được sinh ngẫu nhiên, thì a là số xuất hiện lần đầu, và 1 được thêm vào tab[a]. Nếu giá trị của tab[a] là 1, thì giá trị này không thay đổi. function set_answer () int tab[10], n, i, a Set all tab elements to 0 n=0 for (i = 1 to 4) repeat a = random() % 10 until(tab[a] = 0) tab[a] = 1 a n= endfor return n endfunction Hình 1 Hàm “set_answer” Thuật toán để tính hit và miss bây giờ sẽ được xét tới. Đầu tiên, hàm similarity cho hai số có 4 chữ số x và y được định nghĩa như sau, sử dụng hit và miss của hai số: similarity(x, y) = hit * 10 + miss Tập các giá trị của similarity và các giá trị (hit, miss) có tương ứng 1-1, nên similarity được dùng trong chương trình thay cho hit và miss. Việc tính similarity được dùng khi phỏng đoán của người chơi được so sánh với đáp án đúng, và khi chương trình xác định phỏng đoán của nó. Việc tính toán này được thực hiện thường xuyên, nên một phương pháp thực hiện hiệu quả cao sẽ được đề cập sau đây. Để cải thiện hiệu quả thực hiện, trước khi tính similarity trong trò chơi, một trong các số đem so sánh sẽ được biến đổi thành một dạng gọi là biểu thức mảng. Trong quá trình biến đổi này, nếu số đem biến đổi là d4d3d2d1, thì i được lưu vào phần tử thứ i (ký hiệu di) của mảng, và 0 được lưu vào các phần tử khác. Hình 2 biểu diễn hàm dùng để biến đổi số y sang biểu thức mảng. “pos” là một mảng gồm có 10 phần tử và được gọi theo tham chiếu. 3
function make_pos(y, pos) int i, m Set all pos elements to 0 for(i = 1 to 4) m = y % 10 y = y / 10 b pos[ ]=i endfor endfunction Hình 2 Hàm “make_pos” Khi biểu thức mảng (pos) cho số y được sử dụng, giá trị similarity(x, y) có thể được xác định nhờ hàm “sim” trong hình 3. 4