課程名稱︰高等程式設計 課程性質︰選修 課程教師：劉邦鋒 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰2013.06.18 考試時限（分鐘）： 試題 : Advanced Computer Programming 2013 Final Examination National Taiwan University 06/18/2013 NOTE: You need to finish the writing part before doing the programming part. Writing Part: (1) Polymorphism (10%) ˙ Describe the principle and purpose of polymorphism. Please use a complete example in C++ to illustrate your points. (5%) ˙ Please describe the mechanisms in C++ that make polymorphism possible. The key words include virtual functions, class hierarchy, and pointers/references. (5%) (2) Accessing Data Member (10%) Describe the difference between private, protected, and public data members in C++. You should focus on the purpose of these different mechanisms, and how to achieve the purpose with these data access methods. Please give a complete example for each of them in C++, and illustrate your points. (3) Template Programming (10%) Describe the purpose of template programming. You should focus on the template mechanism, and how the mechanism achieves the purpose. Please give a complete example in C++ to illustrate your points. (4) Operator Overloading (10%) Describe the purpose of operator overloading. Give a complete example of operator overloading in C++, and explain why operator overloading can achieve these purposes. (5) Dynamic Programming (10%) ˙ What are the three principles of dynamic programming? Please use an example to illustrate these principles. (7%) ˙ What is the major difference between dynamic programming and exhaustive search? (3%) Programming Part: (1) Scheduler (10%) We want to schedule many courses into a classroom. Each course has a starting time and an ending time. The classroom can be used at any time, but it can only accommodate one course at a time. If two courses overlap then we cannot select them both. Now please write a program that selects as many courses as possible. (1.1) Input The first line of the input is the number of test cases T. Each test case starts with a line consisting of the number of courses C. The i-th of the following line has two integers, the starting time S_i and the ending time E_i. (1.2) Output The output consists of T lines. The i-th line has the maximum number of courses that can be selected in the i-th test case. (1.3) Technical Specification ˙ 1 ≦ T ≦ 50 ˙ 1 ≦ C ≦ 10^5 ˙ 0 ≦ S_i, E_i ≦ 2^32 (32-bit unsigned integer) (1.4) Sample Input 2 3 3 6 2 4 3 7 3 2 4 3 6 4 7 (1.5) Sample Output 1 2 (2) Lights Off (20%) We want to play a game called "Turn the lights off". Now we have 16 lights as a 4 by 4 array. Each light can be either on or off. Each light has a switch. The switch is designed so that if we toggle a switch, the status of this light, and the four neighboring lights will change their status. By changing the status we mean if the light is on then it will become off, and if it is off then it will become on. Note that if you toggle a switch around the boundary or the corner, then the number of its neighboring lights is 3 or 2, not 4. Now given the initial status of the lights, please find the minimum number of switches one has to toggle in order to turn off all the lights. There are two subtasks: 1. In the first subtask we ensure that we can use all of the switches. Please refer to the description and the input format for more details. (10%) That is, the last four line of the test case will be: .... .... .... .... 2. In the second subtask some switches may be broken. What is the minimum number of switches to toggle in order to turn off all lights? Note that the lights are independent from the switches and all lights are functional. For example, even if a switch is broken, its light will still change status if the switch next to it is toggled. It is just that in this subtask some switch cannot be used. (10%) (2.1) Input The first line of input is the number of test case T. Each test case contains 8 lines, each line with four-character string. The first four strings are the status of the lights as in the first subtask. The next four strings are the status of the switch - a '.' (character "dot") means off and an 'O' (letter O, not number) means on. The last four lines of test case indicates if the switch is broken - a dot '.' means that it works and an 'X' means that it is broken. (2.2) Output For each test case output the minimum number of switches to toggle in order to turn off all the lights. Print '-1' if it is impossible to turn off all the lights. (2.3) Technical Specification ˙ 1 ≦ T ≦ 50 (2.4) Sample Input 4 .... .... .... .... .... .... .... .... ..OO ...O .... .... .... .... .... .... .... .... .... .... XXXX XXXX XXXX XXXX ..OO ...O .... .... ..XX ...X .... .... (2.5) Sample Output 0 1 0 -1 (3) Builder (20%) We want to build an L-shape house in an N by N grid. Every sides of the house should align to the grid. Note that the width and length of this house is a power of 2, and is at least 2. Some cells in this grid is not suitable for building houses and should be avoided. Now please determine the maximum size of the house that can be built, and the number of possible placements on which we can build the largest houses. Note that the house can be rotated in four different orientations, and it is guaranteed that there will be at least one position that we can build the house. The places for building the largest house can overlap. For example, here are 4 size-2 L-shape houses in different directions: OOOO OOOO OO OO OOOO OOOO OO OO OO OO OOOO OOOO OO OO OOOO OOOO There are two subtasks: 1. In the first subtask we ensure that in any 2 by 2 cells in the grid, at least one of the cell is bad for construction. (6%) 2. The second subtask removes the condition given in subtask 1. The input and output specification are same as those of the first subtask. (14%) (3.1) Input The first line of the input is the number of test cases T. The first line of the test case has the size of the grid N, then followed by N lines. Each of the N lines has a string indicating the status of the grid. If the character in the string is a '.' then the cell is good for construction. If the character is an 'X' then the cell is bad. (3.2) Output Each test case should output two numbers in a line. The first number is the size of the largest house one can build, and the second is the number of placements that we can build this house. (3.3) Technical Specification ˙ 1 ≦ T ≦ 10 ˙ 2 ≦ N ≦ 500 (3.4) Sample Input 3 3 ... .X. ... 3 ... ... ... 4 ..XX ..XX .... .... (3.5) Sample Output 2 4 2 16 4 1 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.231.132.45 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1461419315.A.CE0.html