課程名稱︰資料結構與演算法 課程性質︰必修 課程教師：林軒田 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2012.04.24 考試時限（分鐘）：180分鐘 試題 : Midterm Examination Problem Sheet TIME: 04/24/2012, 14:20-17:20 This is an open-book exam. You can use any printed materials as your reference during the exam. Any electronic devices are not allowed. Any form of cheating, lying or plagiarism will not be tolerated. Students can get zero scores and/or get negative scores and/or fail the class and/or be kicked out of school and/or receive other punishments for those kinds of misconducts. Both English and Chinese (if suited) are allowed for answering the questions. We do not accept any other languages. ┌─────────────────────────────────────┐ │There are 10 questions in the exam, each worth 20 points ─ the full │ │credit is 200 points. For the 10 questions, 3 of them are marked with * │ │and are supposedly simple; 4 of them are marked with ** and are supposedly│ │regular; 3 of them are marked with *** and are supposedly difficult. The │ │questions are roughly ordered by the difficulty level. │ └─────────────────────────────────────┘ (1) (20%, *) George and Mary decide to be together forever (a.k.a. 一直走下去). To symbolize their love to each other, they decide to exchange their very first gifts. For the following code, the C++ function exchange is supposed to do the task, but the result appears incorrect. (a) Illustrate (with drawing) what the memory layout is for George, Mary, boy, girl at //DRAW. (b) Modify the code to complete the exchange successfully, without using any pointers. Please simply highlight which line you want to change (you only need to change one!), and write down how you want to change it. 1 typedef GIFT int; 2 struct Person { GIFT gift; }; 3 4 void exchange(Person boy, Person girl){ 5 GIFT onTable = girl.gift; 6 girl.gift = boy.gift; 7 boy.gift = onTable ; 8 //DRAW 9 } 10 11 Person George, Mary; 12 13 int main(){ 14 //some more code to let George and Mary prepare gifts 15 exchange(George, Mary); 16 //now George should take Mary's gift, and Mary takes George's 17 return 0; 18 } (2) (20%, *) Considering representing a queue by a fixed-size circular array of size 4, where the front and the tail of the (empty) queue are both at 0 in the beginning. After executing each step of the following operations sequentially, list the contents of the array, as well as where head and tail are. For locations without contents, please use a special character to represent them. enqueue(1); enqueue(3); dequeue(); enqueue(2); enqueue(4); dequeue(); enqueue(5); enqueue(6); dequeue(); dequeue(); (3) (20%, **) Consider having two stacks for storing integers, a red one and a blue one with the push and pop operations only. Illustrate how to implement the int pop_mth(color s, int m) operation that pops the m-th element from the top (and only that element) from stack s. Note that pop_mth(s, 1) should be equivalent to the usual pop from stack s, and after the operation, all other elements should remain in their original orders. (4) (20%, **) The following code causes illegal memory access. (a) Illustrate (with drawing) what the memory layout is at //DRAW. (b) Explain why the //SEGFAULT line could lead to illegal memory access. 1 class VectorBad{ 2 public: 3 int* data ; 4 VectorBad(){ data = new int[2]; } 5 ~VectorBad(){ delete[] data; } 6 } 7 }; 8 9 int main(){ 10 VectorBad a; a.data[0] = 1; a.data[1] = 3; 11 { 12 VectorBad temp = a; 13 for(int i = 0; i < 2; i++) temp.data[i] += (i * i); 14 //DRAW 15 } 16 a.data[1] = 5; //SEGFAULT 17 return 0; 18 } (5) (20%, **) The following recursive code reverses a singly-linked list. 1 void reverseList(Node* head){ 2 if(head->next){ 3 Node* tail = head->next; 4 reverseList(head->next) 5 tail->next = head; 6 } 7 } (a) Illustrate how the code reverses a linked list A->B->C when calling reverseList(A). You need to describe the steps clearly for the TAs. (b) Complete the following tail-recursive code that also reverses the linked list. 1 void reverseListAndAppend(Node* head, Node* append){ 2 if(head->next){ 3 Node* tmp = head->next; 4 head->next = append; 5 //what to put here? reverseListAndAppend(..., ...); 6 } 7 else{ 8 //what to put here? 9 } 10 } 11 void reverseList(Node* head){ 12 //what to put here? reverseListAndAppend(..., ...) 13 } (6) (20%, *) The lower-triangular matrix is a matrix M with M[r][c] = 0 whenever c > r. Naturally, we do not want to waste storage on the 0 part. A common way of storing a lower-triangular matrix is called a "rectangular representation." For instance, the content of a 4 by 4 lower triangular 10 9 1 0 0 0 1 6 matrix 2 3 0 0 can fit in a 5 by 2 rectangular matrix 2 3 . 4 5 6 0 4 5 7 8 9 10 7 8 Following the example above, design a data structure that implements the rectangular storage scheme for an arbitrary lower-triangular matrix (Hint: discuss cases of even or odd number of columns). Illustrate the scheme clearly and discuss how to access the element at row r and column c of the lower-triangular matrix. ┌─────────────────────────────────────┐ │For the following two questions, you can only use this definition: │ │Let f, g be functions from nonnegative integers to real numbers. We say │ │f(n) = O(g(n)) if there is a real constant c > 0 and an integer constant │ │n_0 ≧ 1 such that f(n) ≦ cg(n) for n ≧ n_0. │ └─────────────────────────────────────┘ (7) (20%, **) Prove or disapprove the following statement. "For non-negative functions f, g, h, if f(n) = O(g(n)), then f(n) + h(n) = O(g(n) + h(n))." (8) (20%, ***) Prove or disapprove the following statements. (a) "If a < 1 or (a = 1 and b ≦ 0), then 2^(an^2 + bn + c) = O(2^(n^2))." (b) "If 2^(an^2 + bn + c) = O(2^(n^2)), then a < 1 or (a = 1 and b ≦ 0)." (9) (20%, ***) A linked list allows a node to link to the next one, which can be slow if you want to access a node far far away. Consider the following multiply-linked list, which allows a node store K pointers, each linking to next-1, next-2 (a node two steps away), next-4 (a node four steps away), next-8, …, next-2^(K-1). Finish the code for getDataNext. Which walks s steps from the current node and then return the pointer to the destination node, and NULL otherwise. Your code should run within O(logN) of time complexity, where N is the number of elements in the multiply-linked list. Briefly explain why your code runs within O(logN). 1 #define K (32) 2 class MLNode{ 3 public: 4 int data; 5 MLNode next[K]; //next[i] links to a node (2^i) steps away 6 //or NULL if the node does not exist 7 8 MLNode* getDataNext(unsigned int s){ 9 if (s == 0) return this; 10 //FINISH THE REST OF THE CODE 11 } 12 }; (10) (20%, ***) Consider an array a of N integers a_0 < a_1 < a_2 < … < a_M and a_M > a_(M+1) > … > a_(N-1). In other words, a_M is the maximum element of the array. Write down an O(logN)-time algorithm that finds the value of a_M. Briefly describe why the algorithm is correct. (Hint: think about binary search.) --

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