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

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