首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
admin
2019-12-10
16
问题
用递归算法实现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/BB3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
(1)根据无类IP地址的规则，每个网段中有两个地址是不分配的：主机号全0表示网络地址，主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2，即254台。该网络要划分为两个子网，每个子网要120台主机，因此主机位数X应该满足下面三个条件：
在操作系统中，P，V操作是一种()。
在操作系统层次结构中，()是操作系统的核心部分，它位于最内层。
某计算机字长为16位，主存地址空间大小为128KB，按字编址。采用单字长指令格式，指令各字段定义如图B-4所示。转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义见表B-1。请回答下列问题：若操作码0010B表示加法操作(助记符为ad
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。
下列关于RISC的叙述中，错误的是____。
下面对计算机网络体系结构中协议所做的描述，错误的是()。
下列关于并行微程序控制器的说法正确的是()。
硬磁盘共有4个记录面，存储区域内半径为10cm，外半径为15．5cm，道密度为60道／cm，外层位密度为600bit／cm，转速为6000r／min。问：硬磁盘的容量是多少?磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系?
随机试题
A、 B、 C、 D、 C
呃逆的发生，除由于胃气上逆所致以外，尚与下述何脏腑有关
下列不能控制生理性运动伪影措施的是
砌体结构房屋，当梁跨度大到一定程度时，在梁支承处宜加设壁柱。对砌块砌体而言，现行规范规定的该跨度限值是：
当吊车为中级工作制时，试问，作用在每个车轮处的横向水平荷载标准值(kN)，应与下列( )项数值最为接近。吊车梁上翼缘板与腹板采用双面角焊缝连接。当对上翼缘焊缝进行强度计算时，试问，应采用下列( )项荷载的共同作用。
针对了解被审计单位及其环境的目的，下列说法中，正确的有()。
下面属于创造性游戏的是()。
Americanchildrencustomarilygotrick-or-treatingonHalloween.
曹魏时期确立的八议制度中，对前朝皇室宗亲予以议决减免刑罚的情形称为()。
Detailsofclimbingclub:meets________
最新回复
(
0
)
