针对如教材第290页代码10.7所示的percolateUp（)上滤算法，10.2.2节曾指出其执行时间为O（logn)。然而，这只是对其最坏情况的估计;在通常的情况下，实际的效率要远高于此。试通过估算说明，在关键码均匀独立分布时，最坏情况极其罕见，且插入操作平均仅需常数时间。

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“针对如教材第290页代码10.7所示的percolateUp…”相关的问题

第1题

如教材346页代码12.9所示的median（)算法针对两个向量长度相差悬殊的情况做了优化处理。a)试分析该方法的原理，并证明其正确性;b)试证明，复杂度的精确上界应为o（log（min（n₁，n₂)))。

点击查看答案

第2题

如教材80页代码3.19所示，考查插入排序算法List::insertionSort（)。a)若输入列表为（61，60，59，...，5，4，3，2，0，1，2)，则共需要做多少次关键码比较？b)试通过实测验证你的结论。

点击查看答案

第3题

若输入的有序序列S₁和S₂以列表（而非向量)的方式实现，则：a)如教材344页代码12.8和346页代码12.9所示的两个median（)算法，分别应做哪些调整？b)调整之后的计算效率如何？

点击查看答案

第4题

考查如教材75页代码3.11所示的List::remove（)算法。当待副除的节点既是首节点也是末节点（即列表仅含单个节点)时，该算法是否依然适用？为什么？

点击查看答案

第5题

若输入的有序序列S₁和S₂以平衡二叉搜索树（而非序列)的方式给出，则：a)如教材344页代码12.8和346页代码12.9所示的两个median（)算法，分别应做哪些调整？b)调整之后的计算效率如何？

点击查看答案

第6题

在摘除原堆顶元素后，为恢复堆的结构性，为何采用如教材292页代码10.9所示的percolateDown（)算法，而不是自上而下地，依次以更大的孩子节点顶替空缺的父节点？

点击查看答案

第7题

考查如教材348页代码12.10所示的quickSelect（)算法。a)试举例说明，最坏情况下该算法的外循环需要执行Ω（n)次;b)在各元素独立等概率分布的条件下，该算法的平均时间复杂度是多少？

点击查看答案

第8题

如教材62页代码2.28所示mergeSort（)算法，即便在最好情况下依然需要Ω（nlogn)时间。实际上略微修改这段代码，即可使之在（子)序列业已有序时仅需线性时间，为此，mergeSort（)的每个递归实例仅需增加常数的时间，且其它情况下的总体计算时间仍然保持o（nlogn)。试给出你的改进方法，并说明其原理。

点击查看答案

第9题

考查如教材76页代码3.14所示的List::deduplicate（)算法。a)给出其中循环体所具有的不变性，并通过数学归纳予以证明;b)试举例说明，该算法在最好情况下仅需o（n)时间;c)试改进该算法，使其时间复杂度降至o（nlogn);d)o（nlogn)的效率是否还有改进的余地？为什么？

点击查看答案

第10题

考查如教材83页代码3.23所示的List::mergeSort（)算法，试证明：a)若为节省每次子列表的划分时间，而直接令m=min（c，n/2)，其中c为较小的常数（比如5)，则总体复杂度反而会上升至o（n²)；b)特别地，当取c=1时，该算法等效地退化为插入排序。

点击查看答案