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

[ccapricorntw (11)]

題目支援：
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: 是 你直接湊也能得到 只不過會有危險...XD
我也覺得XD
推 gash55025502: 10.我寫28 做#1 4 7 5
推 jeremyyuan: 1. 我是從b1 開始
→ jeremyyuan: 10. 28
→ jeremyyuan: 其他都一樣
請問一下樓上兩位大大10是怎麼做的QQ
→ jeremyyuan:  https://i.imgur.com/PtXgo55.jpg
靠對欸 我怎麼沒看到這個= = 感謝 不過j大也是直接用看的？
→ jeremyyuan: 我是先看說他平均一個可以扣1 所以最低就是28 然後再
→ jeremyyuan: 從左右往中間換
10新增DP解
※ 編輯: ccapricorntw (42.73.195.105 臺灣), 01/06/2020 20:06:10
推 csvt32745: 6.C  我是想說如果 k%8=0的話 probing就沒用了XD
→ jimmy1112111: 第6題a. 少了全部還要再mod m