※ [本文转录自 NTU-Exam 看板 #1Lko34Bp ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 标题: [试题] 103下 林轩田 资料结构与演算法 期中考+解答 时间: Fri Jul 31 15:16:17 2015 课程名称︰资料结构与演算法 课程性质︰必修 课程教师：林轩田 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2015.04.21 考试时限（分钟）：120分钟 试题 : Midterm Examination Problem Sheet TIME: 04/21/2015, 14:20-16:20 This is a 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 5 problems in the exam, each worth 40 points─the full credit is│ │200 points. Some problems come with two sub-problems to help you get │ │partial credits, making a total of 9 sub-problems. For the 9 problems, 3 │ │of them are marked with * and are supposedly simple; 4 of them are marked │ │with ** and are supposedly regular; 2 of them are marked with *** and are │ │supposedly difficult. │ └─────────────────────────────────────┘ 1. C and C++ (a) (20%, *) Give a concrete example in C/C++ to explain in your own words on how memory leak could happen. Ans: int &func(){ int *res = new int(1126); return (*res); } int a = func(); In the code above, "res" is allocated in func, and then (*res) is copied to a. So the space pointed by res can never be freed, and becomes "garbage" (memory leak) in the memory. (b) (20%, *) Suppose we use the following class to represent the homework scores of a student in DSA class: 1 class myScore { 2 public: 3 myScore(int n = 10){ size = n; hwScore = new int[size]; } 4 ~myScore(){ delete[] hwScore; } 5 string name; 6 int *hwScore; 7 }; Draw the memory layout after running the following code snippet, and explain the potential hazards/problems of the code. 1 myScore a(6); 2 a.name = "John"; a.hwScore[0] = 85; a.hwScore[1] = 90; 3 myScore b = a; 4 b.name = "Mary"; b.hwScore[0] = 70; Ans: a b ┌────────┐ ┌────────┐ name│ "John" │ name│"John" → "Mary"│ ├────────┤ ├────────┤ hwScore│ │ hwScore│ │ └────┼───┘ └────┼───┘ │ ┌────────┘ │ ↓ │ ┌───┬──┬──┬──┬──┬──┐ └──→│85→70│ 90 │ 0 │ 0 │ 0 │ 0 │ └───┴──┴──┴──┴──┴──┘ The copy constructor called at "myScore b = a" copies the address of a.hwScore to b.hwScore, making the two objects share the same array which is wrong and dangerous (In destructor, there can be double-free) 2. arrays and linked lists (a) (20%, **) Assume that you have a vector of N integers that are between 1 and M. Write down the pseudo code of an O(N)-time O(M)-space algorithm that determines whether all the integers are different from each other (that is, whether they are all distinct). Ans: ‧ initialize an array count[1…M] with 0 ‧ for i ← 1 to N count[i-th element of vector] increased by 1 if count[i-th element of vector] > 1 return FALSE ‧ return TRUE (b) (20%, *) Suppose we have a singly linked list with each node defined by the following class: 1 class node { 2 public: 3 string data; 4 node *next; 5 } Write a C/C++ function invert(node *head) that can invert the list pointed to by head and return the pointer to the inverted list without doing any dynamic memory allocation. (Hint: Note that your function should not need more than 20 lines.) Ans: node *invert(node *head) { node *current = head; node *prev = NULL; while(current->next != NULL){ node *tmp = curent->next; current->next = prev; prev = current; current = tmp; } current->next = prev; return current; } 3. stacks and queues (a) (20%, **) Show how a stack can be used to evaluate the postfix expression 9 8 7 2 3 * - / - 5 2 - * 3 / step by step. All the operators within the expression are binary, and you should draw the stack status after each step. Ans: word stack 9 9 8 98 7 987 2 9872 3 98723 * 9876 - 981 / 98 - 1 5 15 2 152 - 13 * 3 3 33 / 1 (b) (20%, **) Suppose you have a deque D that stores N elements (d_0, d_1, ..., d_(N-1)), in this order, and an initially empty queue Q. Give a pseudo-code description of a function that uses only D and Q (and no other variables or objects) such that the elements within D are reversed─that is, are stored like (d_(N-1), d_(N-2), ..., d_0) in D. Ans: ‧ while not D.empty() Q.enqueue(D.pop_back()) ‧ while not Q.empty() D.push_back(Q.dequeue()) 4. the evil complexity ┌───────────────────────────────────┐ │The notation f(n) = O(g(n)) applies to functions f(n) and g(n) from N │ │to R+∪{0}, and f(n) = O(g(n)) if and only if there exists n_0 ≧ 1 │ │and c > 0 such that ∀n ≧ n_0, f(n) ≦ cg(n). Please only use the │ │definition above in your proof. │ └───────────────────────────────────┘ (a) (20%, **) Prove or disprove the following statement: If f(n) = O(g(n)), then (f(n))^2 = O((g(n))^2). Ans: if f(n) = O(g(n)) ∃ n_0 ≧ 1 and c > 0 s.t. f(n) ≦ c·g(n) for n ≧ n_0 then by f(n) ≧ 0 (f(n): N → R+∪{0}) for n ≧ n_0, (f(n))^2 ≦ c·g(n)·f(n) ≦ c·g(n) · c·g(n) ＝ (c^2)·(g(n))^2 let n_1 = n_0, c_1 = c^2 from above, for n ≧ n_1, (f(n))^2 ≦ c_1·(g(n))^2 that is, (f(n))^2 ＝ O((g(n))^2) (b) (20%, ***) Prove or disprove the following statement: If |f(n) - g(n)| = O(1), then 2^(f(n)) = O(2^(g(n))). Ans: if |f(n) - g(n)| = O(1) ∃ n_0 ≧ 1 and c > 0 s.t. |f(n) - g(n)| ≦ c for n ≧ n_0 then f(n) - g(n) ≦ |f(n) - g(n)| ≦ c that is f(n) ≦ g(n) + c => 2^(f(n)) ≦ 2^(g(n))·2^c let n_1 = n_0, c_1 = c^2 from above, for n ≧ n_1, 2^(f(n)) ≦ c_1·2^(g(n)) that is, 2^(f(n)) ＝ O(2^(g(n))) 5. (40%, ***) Given a sorted (ordered) vector a with N distinct integers where a[0] < a[1] < ... < a[N-1]. The N integers define N+1 non-overlapping ranges (-∞, a[0]], (a[0], a[1]], ..., (a[N-1], ∞) in R. Given a value x, a common task is to determine the range that x falls in. Write down the pseudo code of a (logN)-time algorithm that determines the range. For simplicity, you can assume that x is different from all elements in a. (Hint: Think about binary search and finding the largest a[n] that is smaller than x) Ans: func. find Range (a, N, X) if x ≦ a[0] return (-∞, a[0]] else if x > a[N-1] return (a[N-1], ∞) else left ← 0 right ← N-1 while(left < right - 1){ mid ← floor((left + right) / 2) if a[mid] ≧ x right ← mid else left ← mid } return (a[left], a[right]) --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.162.254.199 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1438326980.A.2F3.html

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: w4a2y4 (140.112.4.192), 03/14/2016 19:31:57