首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
admin
2019-12-10
17
问题
用递归算法实现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://jikaoti.com/ti/XXDjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns，命中率为p1；若Cache未命中，CPU需直接访问主存，访问时间为t2ns，主存命中率为p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据，进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位，这些数据块均存储在同一个磁盘上，因此，SPOO
操作数地址存放在寄存器的寻址方式叫()。
某银行的营业厅有多个柜员窗口，可以同时办理业务。银行的营业厅中安排有n张座椅供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码，若此前没有客户，则排队机就会唤醒一个柜员为储户服务，当没有储户时柜员便可以休息。若储户较多，则所有柜员均会参与服务，
设备管理中，设备映射表(DMT)的作用是()。
数据链路层采用后退N帧(GBN)协议，发送方已经发送了编号为0～7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是____。
如果表6—4所列是路由器R1的路由表，仔细分析各个表项的特点，并回答如下问题。 (1)给出m0和m1所在的网络号，以及可连接的最大主机数目。 (2)给出接口m0，m1和m2的合理的IP地址(注要求取最小的地址)。 (3)试给出网络的拓扑。
以下关于查找方法的说法正确的是()。 Ⅰ顺序查找法只能在顺序存储结构上进行 Ⅱ折半查找法可以在有序的双向链表上进行 Ⅲ分块查找的效率与线性表被分为多少块有关
随机试题
因产品存在缺陷造成人身、他人财产损害的，受害人()
适用简易程序审理案件，人民法院应当在
结核性脑膜炎椎管给药的适应证
A．CA125B．AFPC．hCGD．LDHE．CA19-9常用于滋养叶细胞诊断及病情监测的血清学标记物为
以下可以构成拒不执行判决、裁定罪的有：
下列各项中，属于计算机账务系统处理的凭证来源的有()。
能简化成本计算，但由于平时无法从账上提供发出和结存存货的单价及金额，不利于存货成本的日常管理与控制的是()。
根据第二次全国残疾人抽样调查推算，2006年××省共有残疾人221．1万人，占全省总人 口的比例为6．25％，略低于全国的比例6．34％。与第一次全国残疾人抽样调查结果相比，该省 残疾人口总量增加，残疾人比例上升，残疾类别结构有所变动。 以下不
保持在人脑中的过去的体验或信息，平时虽不被觉知，但可由需要时复现或提取而达到觉知的意识状态是()
在软件开发中，需求分析阶段产生的主要文档是()。
最新回复
(
0
)
