[理工] 108 台大資工資演對答案

看板Grad-ProbAsk作者ccapricorntw (11)時間6年前 (2020/01/06 16:41)推噓3(3推 0噓 6→)

留言9則, 4人參與討論串1/2 (看更多)

題目支援： 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1578300115.A.9B1.html

→

DLHZ

01/06 16:58, 6年前 , 1^F

01/06 16:58, 1^F

我也覺得XD

推

gash55025502

01/06 18:08, 6年前 , 2^F

01/06 18:08, 2^F

推

jeremyyuan

01/06 18:10, 6年前 , 3^F