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

[主观题]

考查教材42页代码2.14中的无序向量唯一化算法deduplicate（)。a)试证明，即便在最好情况下，该算法也需要运行Ω（n²)时间;b)试参照教材46页代码2.19中有序向量唯一化算法uniquify（)的技巧，改进该算法，并分析其时间复杂度;c)试继续改进该算法，使其时间复杂度降至0（nlogn);d)这一效率是否还有改进的余地？为什么？

查看答案

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

您可能会需要：

更多“考查教材42页代码2.14中的无序向量唯一化算法dedupl…”相关的问题

第1题

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

第2题

考查majEleCandidate（)法（教材343页代码12.6)的返回值maj。a)该候选者尽管不见得必然是众数，但是否一定是原向量中出现最频繁者？为什么？b)该返回值在向量中出现的次数最少可能是多少？试就此举一实例。

第3题

考查采用DFS算法（教材162页代码6.4)遍历而生成的DFS树，试证明：a)顶点v是u的祖先，当且仅当b)v与

考查采用DFS算法(教材162页代码6.4)遍历而生成的DFS树，试证明：

a)顶点v是u的祖先，当且仅当

b)v与u无承袭关系，当且仅当

第4题

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

第5题

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

第6题

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

第7题

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

第8题

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

第9题

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

第10题

设计教学法是指教师不再上课向学生系统讲授教材，而只为学生分别指定自学参考书、布置作

业，由学生自学和独立作业，有疑难时才请教师辅导，学生完成一定阶段的学习任务后，向教师汇报学习情况和接受考查。

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

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