作者ponwar87123 (干我屁事喔北七)
看板Grad-ProbAsk
标题[理工] 108中央资演 对答案
时间Fri Dec 13 11:25:20 2019
这份写挺久的，思考很久
好多答案都不确定，都是写的当下推出来的
单选
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1576207524.A.C76.html
※ 编辑: ponwar87123 (122.116.148.248 台湾), 12/13/2019 11:25:39
1F：推 GlassesKJ: 本肥宅第一题就不清楚为啥不是B了 12/14 18:37
因为13左边都小於他，右边都大於他，13自然可能是pivot
而19左边也都小於他，右边都大於他，19也可以是pivot
2F：→ GlassesKJ: 为什麽第一次分割完之後的pivot不是一定是13啊，是有什 12/14 18:37
3F：→ GlassesKJ: 麽条件让他可能变19吗 12/14 18:37
4F：推 GlassesKJ: 4，5直接挤了一个程式跑是对的 12/14 19:25
5F：推 GlassesKJ: 以上都是指单选 12/14 20:49
6F：→ GlassesKJ: 多选6感觉是AC是对的，然後D怎麽判断我不会QQ，就这题 12/14 20:54
7F：→ GlassesKJ: 感觉Q的确大於L 12/14 20:54
C我算是172ㄟ，算好多次ㄌ
D的话，我是在我hash的过程中，感觉L找的次数比Q多，所以D我没选
8F：推 GlassesKJ: 第8感觉是AB，D如果走43152可以压到3而不是11 12/14 21:08
9F：→ GlassesKJ: 啊抱歉上面我算D时忘了k没事哈哈 12/14 21:09
10F：推 GlassesKJ: 反而是B，d[5,4]=-3应该是k=3之後吧？走5214，在那之前 12/14 21:14
11F：→ GlassesKJ: 都是8 12/14 21:14
对ㄟ，好像B我写错了
※ 编辑: ponwar87123 (175.97.13.57 台湾), 12/14/2019 21:37:46
12F：推 ss201: 最後一题我看107考的时候是给=temp欸 01/05 18:45
13F：→ alfred4086: 8.9题是Floy-Warshall 8答案是ABD 没错 01/23 17:35
14F：推 mistel: 问答2初始条件写错了，0 if(i=j) 01/26 14:52
15F：→ mistel: 下面i<k<j要改成i<=k<j 01/26 14:52
16F：→ mistel: 而且你没加pi-1*pk*pj 01/26 14:53