题目内容（请给出正确答案）

[主观题]

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

查看答案

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

您可能会需要：

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

更多“考查如教材348页代码12.10所示的quickSelect…”相关的问题

第1题

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

点击查看答案

第2题

考查如教材121页代码5.6所示的BinTree::updateHeightAbove（x)算法。a)试证明，在逆行向上依次更新x各祖先高度的过程中，一旦发现某一祖先的高度没有发生变化，算法即可提前终止;b)试按此思路改进这一算法;c)如此改进之后，算法的渐进复杂度是否会相应地降低？为什么？

点击查看答案

第3题

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

点击查看答案

第4题

考查如教材24页代码1.12所示的二分递归版fib（n)算法，试证明：a)对任一整数1≤k≤n，形如fib（k)的递归实例，在算法执行过程中都会先后重复出现fib（n-k+1)次;b)该算法的时间复杂度为指数量级;c)该算法的最大递归深度为o（n);d)该算法具有线性的空间复杂度。

点击查看答案

第5题

序列中元素A[i]和A[j]若满足i＜j且A[i]＞A[j]，则称之为一个逆序对（inversion)。考查如教材80页代

序列中元素A[i]和A[j]若满足i＜j且A[i]＞A[j]，则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort()，试证明：

a)若所有逆序对的间距均不超过k，则运行时间为o(kn);

b)特别地，当k为常数时，插入排序可在线性时间内完成;

c)若共有I个逆序对，则关键码比较的次数不超过o(I);

d)若共有I个逆序对，则运行时间为o(n+I)。

点击查看答案

第6题

考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。a)试证明，只要辅助队列Q的容量不低于[n/2]，就不致于出现中途溢出的问题;b)在规模为n的所有二叉树中，哪些的确会需要如此大容量的辅助队列？c)在层次遍历过程中，若Q中节点的总数的确会达到这么多，则至多可能达到多少次？

点击查看答案

第7题

根据教材2.8.3节所给递推关系以及边界条件试证明，如教材62页代码2.28所示mergeSort（)算法的运行时间T（n)=o（nlogn)。

点击查看答案

第8题

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

点击查看答案

第9题

对于几乎有序的向量，如教材代码2.26（60页)和代码2.27（60页)所示的起泡排序算法，都显得效率不足

对于几乎有序的向量，如教材代码2.26(60页)和代码2.27(60页)所示的起泡排序算法，都显得效率不足，比如，即便乱序元素仅限于A[0，√n)区间，最坏情况下仍需调用bubble()做Ω(√n)次调用，共做Ω(n)次交换操作和Ω(n^3/2)次比较操作，因此累计运行Ω(n^3/2)时间。

a)试改进原算法，使之在上述情况下仅需o(n)时间;

b)继续改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于A[n-√n，n)区间;

c)综合以上改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于任意的A[m，m+√n]区间。

点击查看答案

第10题

考查教材39页代码2.10中的无序向量查找算法find（e，lo，hi)。a)在最好情况下，该算法需要运行多少时间？为什么？b)若仅考查成功的查找，则平均需要运行多少时间？为什么？

点击查看答案

第11题

考查教材41页代码2.12中的无序向量删除算法remove（lo，hi)。a)若以自后向前的次序逐个前移后继元素，可能出现什么问题？b)何时出现这类问题？试举一例。

点击查看答案

湘ICP备19018096号湘公安备案43019002002136号营业执照

违法和不良信息举报电话：400-118-7898

举报/反馈/投诉邮箱：deng＃ujigu.com（请将＃替换成@）