算法分析1、 單選(11*3)1、 下列描述正確的是_A、概率算法的期望執行時間是指反復解同一輸入實例所花的平均執行時間B、概率算法的期望執行時間是指所有輸入實例上所花的平均執行時間C、概率算法的平均期望時間是指算法執行時間的上界D、概率算法的最壞期望時間是指算法執行時間的上界2、 當問題只有一個正確的解，不存在近似解時，某概率算法總是給出一個未必正確的 解，但是隨著調用該算法次數的增加，可將錯誤的概率控制在任意給定的范圍，該 算法屬于_A、數字概率算法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時有可能產生錯誤的解。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的，若要求出錯概率不超過，則重復調用MC至少為_A、B、C、D、8、 若兩個環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、 在異步環上，一個O(n2)的leader選舉算法按順時針單向發送消息，假設只有最大標示符的結點可以當選為leader，則當環上標識符次序為_時該算法發送的消息數量最多。A、逆時針0,1,2，.，n-1B、逆時針n-1,n-2,.,0C、順時針0,1,2，.，n-1D、順時針n-1,n-2,.,010、 下列序列代表的環中，沒有空隙的環是_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、 設正整數d1,d2,.,dn是n個結點的標識符集合，x=mind1,d2,.,dn， y=maxd1,d2,.,dn，則同步環上非均勻的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），請列舉出所有并發事件，以及所有因果相關事件。3、對于同步環，一個均勻的leader的選舉算法的消息復雜性是多少？算法中一個id為i的msg以2i的速率被轉發的目的是什么？簡述原因，算法的時間復雜性是多少？4、試舉例說明Caukal Msg Delivery算法可能出現的死鎖情況。并分析為什么該算法通常被應用與組播通信的一部分？3、 算法題（35）1、設網絡的生成樹已經建立，各個節點Pi的id為i，并持有初值xi，且id和持有的初值均互不相同，試寫一個分布式算法使得根節點知道書中