中科大研究生算法試卷.doc

算法分析1、 單選(11*3)1、 下列描述正確的是_A、概率算法的期望執(zhí)行時間是指反復解同一輸入實例所花的平均執(zhí)行時間B、概率算法的期望執(zhí)行時間是指所有輸入實例上所花的平均執(zhí)行時間C、概率算法的平均期望時間是指算法執(zhí)行時間的上界D、概率算法的最壞期望時間是指算法執(zhí)行時間的上界2、 當問題只有一個正確的解，不存在近似解時，某概率算法總是給出一個未必正確的 解，但是隨著調(diào)用該算法次數(shù)的增加，可將錯誤的概率控制在任意給定的范圍，該 算法屬于_A、數(shù)字概率算法B、Las Vegas算法C、Monte Carlo 算法D、Sherwood算法3、 Las Vegas算法的一般形式是_Obstinate(x)Repeat LV(x,y,success)Until success;Return y設p(x)是LV成功的概率，s(x)和e(x)分別是LV成功和失敗的期望時間，t(x)是算法obstinate得到一個正確解的期望時間，則t(x)的表達式應該是_A、t(x)=s(x)+e(x)(1-p(x)/p(x)B、t(x)=p(x)t(x)+(1-p(x)(e(x)+t(x)C、t(x)=p(x)s(x)+(1-p(x)(e(x)+s(x)D、t(x)=p(x)s(x)+(1-p(x)(t(x)+s(x)4、 若一個一致的、p-正確的MC算法是有偏的，則p至少應該滿足_A、p0 C、p=1/2 D、p1/25、 若A是一個偏真的MC算法，則下列陳述正確的是_A、只有A返回true時解正確B、A以較大的概率返回trueC、A返回true時解必正確，A返回false時解必錯誤D、A返回true時解必正確，A返回false時有可能產(chǎn)生錯誤的解。6、 用Las Vegas算法求解某問題，已知obstinate(x)找到正確的解的期望時間是288。其 中LV成功的概率為p(x)=0.2，成功時的期望s(x)是8，則失敗的期望時間e(x)是_A、70 B、102 C、210 D、2807、 一個MC算法是一致的、3/5-正確的，偏y0的，若要求出錯概率不超過，則重復調(diào)用MC至少為_A、B、C、D、8、 若兩個環(huán)x0,x1,.,xn-1和y0,y1,.,yn-1是序等價的，則通常是指_A、若對每個i0,n-1，均有xi和yi匹配B、若對每個i0,n-1，均有xi和yi匹配C、若ij，則有xixj,且yiyj;D、要求x0,x1,.,xn-1,和y.均是有序序列9、 在異步環(huán)上，一個O(n2)的leader選舉算法按順時針單向發(fā)送消息，假設只有最大標示符的結(jié)點可以當選為leader，則當環(huán)上標識符次序為_時該算法發(fā)送的消息數(shù)量最多。A、逆時針0,1,2，.，n-1B、逆時針n-1,n-2,.,0C、順時針0,1,2，.，n-1D、順時針n-1,n-2,.,010、 下列序列代表的環(huán)中，沒有空隙的環(huán)是_A、10,30,20,40,60,90,80,100B、10,20,30,40,50,60,70,80C、1,9,30,40,50,60,70,80D、其他序列11、 設正整數(shù)d1,d2,.,dn是n個結(jié)點的標識符集合，x=mind1,d2,.,dn， y=maxd1,d2,.,dn，則同步環(huán)上非均勻的leader選舉算法的時間復雜度是_A、O（n）B、O ( xn )C、O ( yn )D、O ( n*logn)2、 簡答題（4*8）1、設F(x)是一個MC算法，若F(x)以大于1/2的概率返回true，且返回true時算法正確，則下述算法F2（x）是偏真的還是偏假的？請分析F2（x）出錯的概率是多少？F2(x)if F(x) then return trueelse return F(x);2、已知事件e1,e2,e3和m1的時間戳分別為（1,0,0,0），（2,5,0,0），（0,0,1,2），（3,6,4,3），請列舉出所有并發(fā)事件，以及所有因果相關(guān)事件。3、對于同步環(huán)，一個均勻的leader的選舉算法的消息復雜性是多少？算法中一個id為i的msg以2i的速率被轉(zhuǎn)發(fā)的目的是什么？簡述原因，算法的時間復雜性是多少？4、試舉例說明Caukal Msg Delivery算法可能出現(xiàn)的死鎖情況。并分析為什么該算法通常被應用與組播通信的一部分？3、 算法題（35）1、設網(wǎng)絡的生成樹已經(jīng)建立，各個節(jié)點Pi的id為i，并持有初值xi，且id和持有的初值均互不相同，試寫一個分布式算法使得根節(jié)點知道書中