考查基于List::merge（)算法（教材82页代码3.22)实现的List::mergeSort（)算法（教材83页代码3.23)。该算法是稳定的吗？若是，请给出证明;否则，试举一实例。

查看答案

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

您可能会需要：

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

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

更多“考查基于List::merge（)算法（教材82页代码3.2…”相关的问题

第1题

从队列的角度回顾二路归并算法的两个版本，不难发现，无论Vector::merge（)（教材63页代码2.29)还是List::merge（)（教材82页代码3.22)，所用到的操作无非两类：从两个输入序列的前端删除元素；格元素插入至输出序列的后端。因此，若使用队列ADT接口来描述和实现该算法的过程，必将既简洁且深刻。试按照这一理解，编写二路归并算法的另一版本，实现任意一对有序队列的归并。

点击查看答案

第2题

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

点击查看答案

第3题

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

点击查看答案

第4题

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

点击查看答案

第5题

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