如果结果不匹配，请 
更多“试举例说明，在最坏情况下，Kruskal算法的确可能需要检查…”相关的问题
第2题
若图G的顶点取自平面上的点，各顶点间均有联边且权重就是其间的欧氏距离，则G的最小支撑树亦称作
欧氏最小支撑树(Euclidean Minimum Spanning Tree，EMST)，记作EMST(G)。
点击查看答案
a)若套用Kruskal或Prim算法构造EMST(G)，各需多少时间？
b)试设计一个算法，在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即，在坏情况下，任何此类算法都需要o(nlogn)时间)。
第3题
针对如教材第290页代码10.7所示的percolateUp（)上滤算法，10.2.2节曾指出其执行时间为O（logn)。然而，这只是对其最坏情况的估计;在通常的情况下，实际的效率要远高于此。试通过估算说明，在关键码均匀独立分布时，最坏情况极其罕见，且插入操作平均仅需常数时间。
第5题
设a[0:n-1]是有n个元素的数组,k（0≤k≤n-1)是一个非负整数.试设计一个算法将子数组a[0:k-1]与a[k:n-1]换位.要求:算法在最坏情况下耗时O（n),且只用到O（1)的辅助空间.
第7题
考查如教材76页代码3.14所示的List::deduplicate（)算法。a)给出其中循环体所具有的不变性，并通过数学归纳予以证明;b)试举例说明，该算法在最好情况下仅需o（n)时间;c)试改进该算法，使其时间复杂度降至o（nlogn);d)o（nlogn)的效率是否还有改进的余地？为什么？
