課程名稱︰資料結構 課程性質︰電機系選修 課程教師︰吳沛遠 開課學院：電機資訊學院 開課系所︰電機系 考試日期（年月日）︰2017/11/06 考試時限（分鐘）：14:20~17:20 180分鐘 試題 : 1. (30 pt) Let f: Ｎ --> Ｒ＋, g: Ｎ --> Ｒ＋, h: Ｎ --> Ｒ＋ (a.k.a., f(n), g(n), h(n) are all positive functions with domain Ｎ, the set of positive integers.) (a) (6 pt) Give the formal definition of the following: (i) f ∈ O(g) (ii) f ∈ θ(g) (b) (6 pt) Prove that the big- Oh relation satisfies the following properties: (i) Reflexivity: f ∈ O(f) (ii) Transitivity: If f ∈ O(g), g ∈ O(h), then f ∈ O(h) (c) (4 pt) Prove that if f ∈ O(g), g ∈ O(f), then f ∈ θ(g) (d) (6 pt) Prove that the big- Theta relation satisfies the following three properties: (i) Reflexivity: f ∈ θ(f) (ii) Transitivity: If f ∈ θ(g), g ∈ θ(h), then f ∈ θ(h) (iii) Symmetry: If f ∈ θ(g), then g ∈ θ(f) In fact, those three properties imply that θ is an equivalence relation. (e) (8 pt) Order the following list of functions by the big- Oh notation in non- decreasing order. Group together(for example, by cycling) those functions that are big- Theta of one another. The logarithmic function is base of 2. 9n^(2/3) (2017n)^(1/2) 10^(10^100) log log n 2n + 2^n 3^n n^(2/3)*logn 10^100 * n + 10^(-100) * n^2 2^(2logn) 11*n^(1/2) 3*n^(3/2) + n 10^(-100)*0.5^n n^2 * log(n^5) n^n log(n^n) log(n!) n^(2^100) 2. (15 pt) Find a closed form solution of T(n) in big- Theta notation. Derivation is not required but may lead to partial credits in case your answer is incorrect. (a) (3 pt) T(n) = 9T(n/3) + n^2(log n)^2 (b) (3 pt) T(n) = 10T(n/3) + n^2(log n)^2 (c) (3 pt) T(n) = T(n^(1/2)) + 1 (d) (3 pt) T(n) = 3T(n - 1), T(1) = 1 (e) (3 pt) T(n) = 5T(n - 1) - 6T(n - 2), T(1) = 1, T(2) = 5 3. (20 pt) (a) (10 pt) Write a pseudo- code to compute the greattest common divisor(gcd, 最大公因數) between two positive integers. (b) (5 pt) Illustrate how your algorithm works to find the gcd between 62 and 36. (c) (5 pt) Analyze the worst-case time complexity (in big-Oh notation) of your algorithm. 4. (20 pt) Alice is a kindergarten teacher. She wants to give some candies to the children in her class. All the children sit in a line (their position is fixed), and each of them has a rating score according to his or her performance in the class. Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to save money, so she needs to minimize the total number of candies given to children. (a) (5 pt) Suppose there are 20 students in Alice's class with ratings as in the table below. Please fill up the table with the number of candies to be given to each student as well as the total amount of candies given. ID Rating Candies 1 14 2 11 3 13 4 6 5 16 6 3 7 5 8 10 9 15 10 1 11 19 12 7 13 2 14 20 15 4 16 12 17 18 18 17 19 19 20 8 Total: _____ candies (b) (10 pt) Write a pseudo-code to solve the problem with Input: Rating of each stuednt r_1, r_2, ..., r_n Output: Candies for each student c_1, c_2, ..., c_n (c) (5 pt) Analyze the worst-case time complexity (in big-Oh notation) of your algorithm. 5. (25 pt) Consider the following scnario. You have a sequence of numbers 1, 2 ,..., n and an empty stack. At each step you may choose to either (1) push a number into stack in order (a.k.a, First time push 1, second time push 2, and so on), or (2) pop a number to the output. After all numbers are pushed in or poped out, the output will be a permutation of 1, ..., n. For example, when n = 3, one may get the output 2,3,1 as follows: Step 1: push 1 Step 2: push 2 step 3: pop 2 step 4: push 3 step 5: pop 3 step 6: pop 1 (a) (6 pt) If n = 10, is it possible to achieve the following outputs? Please either list the steps to achieve the output, or explain why the output is impossible. (i) 3,5,6,4,7,9,8,2,10,1 (ii) 7,6,8,5,3,10,9,4,2,1 (b) (4 pt) Let a_n be the number of possible outputs when the input is 1,2,... ,n. Compute a_4, a_5, a_6, a_7 (c) (4 pt) Denote a_0 = 1, prove the following recurrence relation holds for each n >= 1 n-1 a_n = Σ a_k * a_n-k-1 k=0 (d) (8 pt) Solve a_n. Please show your derivation.(Hint: Define A(z) = Σa_n * z^n, prove that z[A(z)]^2 - A(z) + 1 = 0. You may assume the series Σa_n * z^n absolutely converge at |z| < r for some r > 0.) (e) (3 pt) If the stack data sturcture is replaced by a queue as follows, what is the number of all possible outputs when the input is 1, 2, ..., n ? Please elaborate your reasons. --

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