[理工] 108中央资演 对答案

楼主: ponwar87123 (干我屁事喔北七)   2019-12-13 11:25:20
这份写挺久的,思考很久
好多答案都不确定,都是写的当下推出来的
单选
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.超不确定,虽然读过但是当下推的QQ,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
还请大家讨论和侦错
谢谢!
作者: GlassesKJ (gg)   2019-12-14 18:37:00
本肥宅第一题就不清楚为啥不是B了为什么第一次分割完之后的pivot不是一定是13啊,是有什么条件让他可能变19吗4,5直接挤了一个程式跑是对的以上都是指单选多选6感觉是AC是对的,然后D怎么判断我不会QQ,就这题感觉Q的确大于L第8感觉是AB,D如果走43152可以压到3而不是11啊抱歉上面我算D时忘了k没事哈哈反而是B,d[5,4]=-3应该是k=3之后吧?走5214,在那之前都是8

Links booklink

Contact Us: admin [ a t ] ucptt.com