首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
admin
2019-12-10
45
问题
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
选项
A、n
B、[n／2]
C、[log
2
n]
D、[log
2
n]+1
答案
D
解析
根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为[log
2
n]+1次，查找结束。
折半查找法在查找成功时和给定值进行比较的关键字个数至多是[log
2
n]+1；在查找不成功时和给定值进行比较的关键字个数最多也不超过[log
2
n]+1。
转载请注明原文地址:https://kaotiyun.com/show/Um3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
某机的主要部件如下图所示。(1)请补充各部件间的主要连接线，并注明数据流动方向。(2)拟出指令SUB(R1)，一(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作，源操作数地址和目的操作数地址分别在
某计算机采用页式存储管理，内存中现有1000个页表项，CPU的cache中可以存放N个页表项，该系统中，CPU内存访问的时间为lOOns，对cache访问的时间是5ns，如果希望页表映射的平均时间降到20ns以下，那么cache中的N必须高于(
设某多道程序系统中有用户使用内存1000M，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算法，进程调度时机选择在进程执行结
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
快速排序算法中，如何选取一个界值(又称为轴元素)，影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如下表所示，该机有8位和16位两种指令字长，采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型，16位字长指令为寄存器～存储器(R—M)二地址变址类型(地址码范围在一12
下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多的是____。
随机试题
A．异烟肼、吡嗪酰胺B．左旋氧氟沙星C．链霉素D．糖皮质激素E．利福平上述哪种药物在初治结核患者中易引起类赫氏反应(暂时性恶化)
A、大青叶B、板蓝根C、野菊花D、鱼腥草E、白头翁长于凉血止痢的药物是（）。
患儿，10个月，阵发性哭闹，被诊断为“肠套叠”，大便的颜色为
甲公司拥有一项汽车仪表盘的发明专利，其权利要求记载的必要技术特征可以分解为a+b+c+d共四项。乙公司制造四种仪表盘，其必要技术特征可以作四种分解，甲公司与乙公司的必要技术特征所代表的字母相同，表明其相应的必要技术特征相同或等同。乙公司的哪项技术侵犯了甲公
(2009年)研究船体在水中航行的受力试验，其模型设计应采用()。
陆先生目前每月工资5000元。公司有两套员工激励方案：甲方案是“双薪”，即年底多发一个月工资5000元；乙方案是发放年终奖5000元。根据案例，回答以下问题。根据前面两题的计算结果，采用乙方案可比甲方案节税()元。
保险兼业代理人可以代理再保险业务。()
促销的手段主要有()。
构成挪用公款罪的行为有()。
Testinghasreplacedteachinginmostpublicschools.Myownchildren’sschoolweekisframedbypretests,drills,tests,andre
最新回复
(
0
)
