杂度是_______A、O（
）B、Ox
C、Oy
D、O
log

二、简答题（48）
1、设Fx是一个MC算法，若Fx以大于12的概率返回true，且返回true时算法正确，则下述算法F2（x）是偏真的还是偏假的？请分析F2（x）出错的概率是多少？F2xifFxthe
retur
trueelseretur
Fx
2、已知事件e1e2e3和m1的时间戳分别为（1000），（2500），（0012），（3643），请列举出所有并发事件，以及所有因果相关事件。
f3、对于同步环，一个均匀的leader的选举算法的消息复杂性是多少？算法中一个id为i的msg以2i的速率被转发的目的是什么？简述原因，算法的时间复杂性是多少？
4、试举例说明CaukalMsgDelivery算法可能出现的死锁情况。并分析为什么该算法通常被应用与组播通信的一部分？
三、算法题（35）
1、设网络的生成树已经建立，各个节点Pi的id为i，并持有初值xi，且id和持有的初值均互不相同，试写一个分布式算法使得根节点知道书中持有初值最大的节点，以及持有初值最小的节点。
2、设集合S和T中各有
个互不相同的元素，要求：●写一Mo
teCarlo算法判定S和T是否相等●分析算法出错的概率●算法是否有偏，若有偏，偏什么？
fr