[理工] 105 中央資工 資結 對答案

[yupog2003 (屁股)]

中央105板上只有數學有相關文章，那我就來對資結的答案拉XD

先上題目：http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_105_01.pdf

1.A  inorder  :1,2,4,5,6,7,8,9,10
     preorder :6,2,1,4,5,9,8,7,10
     postorder:1,5,4,2,7,8,10,9,6
  B
       6
      / \
     2    9
    / \  / \
   1  4  8 10
     / \ /
    3  5 7

2. insert 1:
       1
   insert 2:
       1
        \
         2
   insert 3:
       2
      / \
     1   3
   insert 4:
       2
      / \
     1   3
          \
           4
   insert 5:
       2
      / \
     1   4
        / \
       3   5

3.A:4+3+2+1=10
  B:3 洪逸給2，但我認為是8次
  C:3 4才對

4.A:52 O(n+k)=(51-15+1)+5=42
  B:51,42,33,24,15
  C:不知道該怎麼寫比較好

5.A
     [2,4]
     / | \
   [1][3][5]

  B.search，可降低tree的高度，且可減少disk access的次數

6.A 若存在一個polynomial-time reduction將problem X reduce到problem Y，則可
    證明problem Y為NP-hard
  B 只要再證明problem Y為NP即可，找出一個verification algorithm用來驗證
    problem Y的解是否正確，且此algorithm需可於polynomial time內完成
    (應該要寫出guess and verification那段比較好，但表達能力太差QQ)

7.A
   c[i,j]=min{
              c[i-1,j]+cost(delete)
              c[i,j-1]+cost(insert)
              c[i-1,j-1]+cost(substitution), if ai =\= bj
              c[i-1,j-1], if ai=bj
             }
  B
   c[i,0]=i*cost(delete)=i, for i=1,...,m
   c[0,j]=j*cost(insert)=2j,for j=1,...,n
  (先承認這題是抄林立宇講義的XD)

8.
  Algorithm BFSPA
  Input:A weighted graph G=(V,E), a source node s and a two dimension array
        w, where V is the node set, E is the edge set, and w[x][y] is the
        weight of the edge(x,y)
  Output:"YES" or "No". "YES" if the graph has a negative-weighted cycle
         "NO" otherwise.

  d[s] <- 0;
  for every node x in V-{s}
    d[x] <- ∞
  for i <- 1 to |V|-1 do
    for every edge (x,y) in E do
      if d[y] > d[x] + w[x][y] then
         d[y] <- d[x]+ w[x][y]
  for every edge (x,y) in E do
    if d[y] > d[x] + w[x][y] then
      return "YES"
  return "NO"

9.
  Algorithm knapsack-fractional
  Input:Capacity C and n objects o[1],...,o[n] with weights w[1],...,w[n]
        and profits p[1],...,p[n]
  Output:x[1],...,x[n] such that x[1]*w[1]+...+x[n]*w[n] <= C and
         x[1]*p[1]+...x[n]*p[n] is maximized

  sort [1,...,n] with key [p[1]/w[1],...,p[n]/w[n]] in non-increasing order
  and store in array A
  W=0
  for i = 1 to n
    x[i] = 0
  for i = 1 to n
    if W + w[A[i]] <= C
       W = W + w[A[i]]
       x[A[i]] = 1
    else
       break
  x[A[i]] = (C-W)/w[A[i]]
  return x

有寫的一起來對答案囉！再麻煩大家幫我訂正了，謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.85.61.62
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484983415.A.2CF.html
※ 編輯: yupog2003 (219.85.61.62), 01/21/2017 16:21:38
推 weilun911: 第三題題庫班好像有B：2次 C：4次
推 weilun911: 前面ds的部分和你一樣 後面演算法gg…
→ weilun911: 都不太會寫QQ
推 k2shouai: 3 B 8次 C 4次
→ yupog2003: 3.C:我的想法：第一次partition完：[1,4,3,2,5]
→ yupog2003: 第二次partition完：1,[4,3,2],5
→ yupog2003: 第三次partition完：1,[2,3],4,5
→ yupog2003: 剩兩個就直接比較就好，還是說這一步應該也要用
→ yupog2003: partition才對呢？或是我的過程有什麼錯誤？
→ yupog2003: 第一次partition完應該是:[1,4,3,2],5才對，打錯
→ yupog2003: 3.B:我的想法：[[5,4],3],[2,1]，總共call了三次，剩下
→ yupog2003: 應該算merge的事情？
推 banana0423: 4.A 37  51-15+1=37
→ banana0423: 4.C 我的想法是題目的stable是針對該round而言 例如
→ banana0423: 31 32 33 第二round放桶子時 如果不stable 可能輸出
→ banana0423: 32 31 33這樣的結果
→ yupog2003: 4.A我一開始寫也37，先找出min,max值後可以優化得到的
→ yupog2003: 結果，但是題目沒說可不可以優化所以我很苦惱
→ k2shouai: Quick sort你直接看code就懂了 洪逸algo版
→ k2shouai: Merge sort遞迴要分到都剩下一個才合併吧
→ yupog2003: Quick sort的部份我懂了，最後一步還要一個partition
→ yupog2003: 因為判斷式是if i < j
→ yupog2003: Merge sort剛剛看了程式碼的確要剩一個才merge，那麼
→ yupog2003: 確實是8次，感覺這題的程式碼要完全照他的走答案才會一
→ yupog2003: 樣，不是自己想一個作法就可以的
→ k2shouai: 4.A是O(n+k)吧 n data數 k值域
→ yupog2003: 對吼，沒考慮到n，只考慮到k...
※ 編輯: yupog2003 (219.85.61.62), 01/22/2017 16:23:20
→ yupog2003: 先謝謝k大、b大、w大
推 AllenPaul: 第三題的 B 洪毅給2
→ yupog2003: 5,4,3,2,1用merge sort竟然只要2次recursive calls...
→ yupog2003: 顯然我對recursive call的定義有些誤解...
※ 編輯: yupog2003 (219.85.61.62), 01/22/2017 18:49:26
推 AllenPaul: 原來說過
→ AllenPaul: 老實說我也 ... 覺得怪怪
→ yupog2003: 洪逸有說為什麼嗎？
→ yupog2003: 要2層recursive我還可以理解，可是只要2次@@
推 AllenPaul: 我至今還不解阿~~~
→ ken52011219: 不可能= =
→ yupog2003: 用程式跑了一次是9次，扣掉一開始那次是8次，怒改答案
※ 編輯: yupog2003 (219.85.61.62), 01/22/2017 19:42:23
推 as23041248: 揹包那提是不是有點瑕疵 return x上面那行
→ as23041248: 先算下一個 可是你回圈跑到n 會跑到n+1
→ as23041248: 我覺得直接在加一個 else x[A[i]]=(C-W)/w[i]
→ as23041248: 然後那行去掉
→ as23041248: 另外我覺得你寫成 sort o1,...on with corresponding
→ as23041248: key p1/w1...pn/wn比較好 有點吹毛求疵 因為看你input
→ as23041248: 有宣告o1...on但是 裡面沒用到
→ as23041248: 抱歉for迴圈那邊別理我 我看成雙層for><
→ as23041248: 剛剛重新想了一下 你的if是不是要加break
→ as23041248: 不然x[A[i+1]]一定都是x[A[n+1]]?
→ yupog2003: 先感謝as大的關注，我一開始的確是寫sort o1,...,on
→ yupog2003: 可是我想要表達的是排序index，所以寫成那樣到後面會卡
→ yupog2003: 住，不知道該怎麼描述index的概念，我想說有1,...,n就
→ yupog2003: 直接sort 1,...,n了
→ yupog2003: with corresponding key這個英文的表達更好，學起來XD
→ yupog2003: 嗯嗯對，應該要加break，不然就全錯了，感謝提醒
※ 編輯: yupog2003 (219.85.61.62), 01/24/2017 15:16:59
※ 編輯: yupog2003 (219.85.61.62), 02/06/2017 07:48:53
→ yupog2003: 更正knapsack fractional最後for loop跳出後的部份
→ Marcolod: 請問 為什麼第七題的B，為什麼他的j要乘以2呢？
推 stu199712: @Marcolod 因為B每多一個字 A就要insert一個字才一樣