[試題] 106-1 吳沛遠 資料結構 期中考
課程名稱︰資料結構
課程性質︰電機系選修
課程教師︰吳沛遠
開課學院：電機資訊學院
開課系所︰電機系
考試日期（年月日）︰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://www.ptt.cc/bbs/NTU-Exam/M.1547970730.A.CCE.html
→
05/07 15:57,
5年前
, 1F
05/07 15:57, 1F