a)基于教材346页代码12.9中的median（)算法，添加整型输入参数k，实现在S₁∪S₂中选取第k个元素的功能;b)新算法的时间复杂度是多少？

答案

查看答案

发布时间：2022-08-10

更多“a)基于教材346页代码12.9中的median（)算法，添加整型输入参数k，实现在S1∪S2中选取第k个元素的功能;b)新算法的时间复杂度是多少？”相关的问题

第1题

试按照PFS搜索的统一框架（教材173页代码6.7)，通过设计并实现对应的prioUpdater函数对象，分别实现BFS和DFS算法。

点击查看答案

第2题

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

点击查看答案

第3题

与其它算法类似，searchIn（)算法的递归版（教材186页代码7.3)也存在效率低下的问题。试将该算法改写为迭代形式。请注意保持出口时返回值和hot的语义。

点击查看答案

第4题

设采用实现如教材48页代码2.21所示的二分查找binSearch（)算法版本A，针对独立均匀分布于[0，2n]

设采用实现如教材48页代码2.21所示的二分查找binSearch()算法版本A，针对独立均匀分布于[0，2n]内的整数目标，在固定的有序向量(1，3，5，...，2n-1)中查找。

a)若将平均的成功和失败查找长度分别记作S和F，试证明：(S+1)•n=F•(n+1);

b)上述结论，是否适用于binSearch()算法的其它版本？为什么？

c)上述结论，是否适用于fibSearch()算法的各个版本？为什么？

d)若待查找的整数按照其它的随机规律分布，以上结论又应如何调整？

点击查看答案

第5题

假设将教材34页代码2.4中expand（)算法的扩容策略改为“每次追加固定数目的单元”。a)试证明，在最坏情况下，单次操作中消耗于扩容的分摊时间为θ（n)，其中n为向量规模;b)试举例说明，这种最坏情况的确可能发生。

点击查看答案

第6题

试证明，采用BST::remove（)算法（教材198页代码7.6)从二叉搜索树中删除节点，若实际被删除的节点为x，则此后：a)除x的历代祖先以外，其余节点的高度无需更新;b)祖先高度不会增加，但至多减一;c)一旦某个祖先高度不变，更高的祖先也必然高度不变。d)利用以上事实，进一步改进updateHeightAbove（)方法，提高效率。

点击查看答案

第7题

智能图像识别技术主要用于集装箱号和箱型代码的识别，是基于光学字符识别发展而来的一种实用技术，包括触发、图像抓拍、字符识别等几个关键环节。判断对错

点击查看答案

第8题

二路归并算法merge（)中的循环体，虽然形式上简洁，但流程控制逻辑却较为复杂。a)试分情况验证并解释该算法的正确性;b)基于以上理解，该循环体可以如何简化？c)如果从代码可维护性及运行效率的角度出发，该算法应该如何实现？

点击查看答案

第9题

为使二叉搜索树结构支持多个相等数据项的并存，需要增加一个BST::searchAll（e)接口，以查找出与

为使二叉搜索树结构支持多个相等数据项的并存，需要增加一个BST::searchAll(e)接口，以查找出与指定目标e相等的所有节点(如果的确存在)。

a)试在BST模板类(教材185页代码7.2)的基础上，扩充接口BST::searchAll(e)。要求该接口的时间复杂度不超过o(k+h)，其中h为二叉搜索树的高度，k为命中节点的总数;

b)同时，改进原有的BST::search(e)接口，使之总是返回最早插入的节点e—即先进先出。