中科大研究生算法试卷.pdf

算法分析算法分析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 和持有的初值均互不相同，试写一个分布式算法使得根节点知道书中持有初值最大的节点，以及持有初值最小的节点。2、设集合 S 和 T 中各有 n 个互不相同的元素，要求：写一 Monte Carlo 算法判定 S 和 T 是否相等 分析算法出错的概率 算法是否有偏，若有偏，偏什么？