[理工] 108中央資演 對答案

[ponwar87123 (干我屁事喔北七)]

這份寫挺久的，思考很久
好多答案都不確定，都是寫的當下推出來的

單選
1.A
2.A
3.A
4.B
5.A
(4 5極度不確定)

複選題
6.A
7.D
8.ABD
9.BCE
10.AE
11.DE
12.ADE

問答題
1.
(a)
MergeSort(A,p,r){
    if(p<r){
        int min=(p+r)/2
        mergeSort(A,p,min)
        mergeSort(A,min+1,r)
        MERGE(A,p,min,r)
    }
}
(b)
T(n) = 2T(n/2)+O(n)
(樹狀圖)
T(n) = logn*O(n) = O(nlogn)

2.超不確定，雖然讀過但是當下推的ＱＱ，DP一直是弱項

m[i,j] = Pi-1*Pi*Pj if j=i+1
       = min{m[i,k]*m[k+1,j]} if j>i
        i<k<j

3.
B3:D[i][j] > D[i][k] + D[k][j]
B4:D[i][j] = D[i][k] + D[k][j]
B5:D[i][j] = C[i][j]

4.
B6:A[child/2] = A[child]
B7:A[child/2] = rootkey

還請大家討論和偵錯
謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.148.248 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576207524.A.C76.html
※ 編輯: ponwar87123 (122.116.148.248 臺灣), 12/13/2019 11:25:39
推 GlassesKJ: 本肥宅第一題就不清楚為啥不是B了
因為13左邊都小於他，右邊都大於他，13自然可能是pivot
而19左邊也都小於他，右邊都大於他，19也可以是pivot
→ GlassesKJ: 為什麼第一次分割完之後的pivot不是一定是13啊，是有什
→ GlassesKJ: 麼條件讓他可能變19嗎
推 GlassesKJ: 4，5直接擠了一個程式跑是對的
推 GlassesKJ: 以上都是指單選
→ GlassesKJ: 多選6感覺是AC是對的，然後D怎麼判斷我不會QQ，就這題
→ GlassesKJ: 感覺Q的確大於L
C我算是172ㄟ，算好多次ㄌ
D的話，我是在我hash的過程中，感覺L找的次數比Q多，所以D我沒選
推 GlassesKJ: 第8感覺是AB，D如果走43152可以壓到3而不是11
→ GlassesKJ: 啊抱歉上面我算D時忘了k沒事哈哈
推 GlassesKJ: 反而是B，d[5,4]=-3應該是k=3之後吧？走5214，在那之前
→ GlassesKJ: 都是8
對ㄟ，好像B我寫錯了
※ 編輯: ponwar87123 (175.97.13.57 臺灣), 12/14/2019 21:37:46
推 ss201: 最後一題我看107考的時候是給=temp欸
→ alfred4086: 8.9題是Floy-Warshall 8答案是ABD 沒錯
推 mistel: 問答2初始條件寫錯了，0 if(i=j)
→ mistel: 下面i<k<j要改成i<=k<j
→ mistel: 而且你沒加pi-1*pk*pj