作者ccapricorntw (11)
看板Grad-ProbAsk
标题[理工] 108 台大资工 资演 对答案
时间Mon Jan 6 16:41:53 2020
题目支援：
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解：https://imgur.com/zMxXu3S
右下角有点的格子表示有做transform
另外9和10两题依照第一面的说明好像是可以不写过程只写答案的样子吗？
这样好像不会DP也能用看的猜答案欸XD
感谢各位~
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.73.195.105 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578300115.A.9B1.html
1F：→ DLHZ: 是 你直接凑也能得到 只不过会有危险...XD01/06 16:58
我也觉得XD
2F：推 gash55025502: 10.我写28 做#1 4 7 501/06 18:08
3F：推 jeremyyuan: 1. 我是从b1 开始01/06 18:10
4F：→ jeremyyuan: 10. 2801/06 18:10
5F：→ jeremyyuan: 其他都一样01/06 18:10
请问一下楼上两位大大10是怎麽做的QQ
靠对欸 我怎麽没看到这个= = 感谢 不过j大也是直接用看的？
7F：→ jeremyyuan: 我是先看说他平均一个可以扣1 所以最低就是28 然後再01/06 18:35
8F：→ jeremyyuan: 从左右往中间换01/06 18:35
10新增DP解
※ 编辑: ccapricorntw (42.73.195.105 台湾), 01/06/2020 20:06:10
9F：推 csvt32745: 6.C 我是想说如果 k%8=0的话 probing就没用了XD 02/01 16:39
10F：→ jimmy1112111: 第6题a. 少了全部还要再mod m 01/25 20:46