[理工] 108中央資演 對答案
這份寫挺久的，思考很久
好多答案都不確定，都是寫的當下推出來的
單選
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
推
12/14 18:37,
4年前
, 1F
12/14 18:37, 1F
因為13左邊都小於他，右邊都大於他，13自然可能是pivot
而19左邊也都小於他，右邊都大於他，19也可以是pivot
→
12/14 18:37,
4年前
, 2F
12/14 18:37, 2F
→
12/14 18:37,
4年前
, 3F
12/14 18:37, 3F
推
12/14 19:25,
4年前
, 4F
12/14 19:25, 4F
推
12/14 20:49,
4年前
, 5F
12/14 20:49, 5F
→
12/14 20:54,
4年前
, 6F
12/14 20:54, 6F
→
12/14 20:54,
4年前
, 7F
12/14 20:54, 7F
C我算是172ㄟ，算好多次ㄌ
D的話，我是在我hash的過程中，感覺L找的次數比Q多，所以D我沒選
推
12/14 21:08,
4年前
, 8F
12/14 21:08, 8F
→
12/14 21:09,
4年前
, 9F
12/14 21:09, 9F
推
12/14 21:14,
4年前
, 10F
12/14 21:14, 10F
→
12/14 21:14,
4年前
, 11F
12/14 21:14, 11F
對ㄟ，好像B我寫錯了
※ 編輯: ponwar87123 (175.97.13.57 臺灣), 12/14/2019 21:37:46
推
01/05 18:45,
5年前
, 12F
01/05 18:45, 12F
→
01/23 17:35,
5年前
, 13F
01/23 17:35, 13F
推
01/26 14:52,
5年前
, 14F
01/26 14:52, 14F
→
01/26 14:52,
5年前
, 15F
01/26 14:52, 15F
→
01/26 14:53,
5年前
, 16F
01/26 14:53, 16F