算法设计与分析问答题每日一练(2020.06.10)

问答题
写出Prim算法描述，并给出时间复杂度的分析。
答案：假设N=（V，E），TE是N最小生成树边的集合。算法从U={u0}（u0∈V），TE={}开始，重复执行下述操...
问答题
在最接近点对问题中，用一条垂直线L：x=m将平面点集分为大致相等的两个子集S1和S2。设P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域，d1和d2分别是S1和S2中最小距离，且设d=min{d1，d2}。对于P1中任意一个点p，可能和在P2中点q构成全平面点集的最接近点对的候选点对，请证明：P2中最多有6对这样的候选点对。
答案：根据鸽笼原理：如果n+1只鸽子飞入n个笼子中，那么至少有一个笼子里包含两只或两只以上的鸽子。
将矩形R的长为2...
问答题
证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足nmod（k-1）=1。
答案：
问答题
如果n=2k，循环赛最少需要进行几天；
答案：8天
问答题
快速排序算法最坏情况下需要多少次比较运算？
答案：最坏情况下快速排序退化成冒泡排序，需要比较n²次。