題目支援：
https://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/108/108_graduate_4
1.
a. bn = b0*bn-1 + b1*bn-2 + ... + bn-1*b0, n>=1
b0 = 1
b. bn = C(2n, n)/(n+1)
2. acbd+*/ea-/c*
3. 4
/ \
5 7
/
9
4. bottom-up heapify
5.
a. F F T
b. {5, 5, 5, 5, 5} => O(n^2)
c. A. q1 = q1 + 1
B. q2 = q2 - 1
C. j = j + 1
6.
a. h(k, i) = h'(k) + i
b.
index 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15
slot 16, 1, , 3,17,31, , ,19,35,51,67, , , ,15
c. input sequence = {2, 18, 34, 50, 66}
index 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15
slot , , 2, , , ,18, , , ,34, , , ,50,
則key 66找不到位置放
7. F F F
8. A. 1
B. 0
C. 1
D. 2
9. a.
等同LCS，要比較精確應該只能畫出表格？但表格有點大，我畫到一半出現5我就寫了
結果後來檢討把表格填完才發現是6 = =
b. 2, 3, 7, 9, 10, 12
10.a.
好像也是DP？但不太知道怎麼設計，我是直接用看的，只看到cost = 29的解，不知道對
更正：28
b. 5, 7, 5 (好像有好幾組)
更正：1, 4, 7, 5 一樣有很多組
DP解：
右下角有點的格子表示有做transform
另外9和10兩題依照第一面的說明好像是可以不寫過程只寫答案的樣子嗎？
這樣好像不會DP也能用看的猜答案欸XD
感謝各位~