首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。
admin
2019-12-10
27
问题
用递归算法实现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/NgDjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
有n个生产者进程向1个有限的缓冲区不断地发送消息，这些消息通过缓冲区分发到m个消费者，缓冲区的大小只可以存放1条消息。生产者和消费者的工作遵循如下规则：(1)生产者和消费者对缓冲区的访问互斥；(2)对每1条放入缓冲区的消息，所有消费者都
某32位计算机系统采用段页式虚拟存储管理，现有一个进程被分成5段，其段号和段长见下表，段内分页，页表见下，存放在内存中，每页的长度为4096B。进程运行到某一个指令，其地址为(2，3，010)，当前CPU的寄存器和地址加法器的状态如图所示，当上述指令执行时
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条
下面是给出的一段IP数据包头所包含的数据，0000305252400080062C23C0A80101D803E215，请根据IPv4头部格式回答如下问题：(1)该IP包的发送主机和接收主机的地址分别是什么?
在某个操作系统中，通过大量的实验，人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比，即可用内存加倍，缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns，但若发生了缺页中断就需要1ms。一个程序运行了60s，期
已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：求图G的关键路径，并计算该关键路径的长度。
某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100gs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和
假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题足找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
随机试题
PASSAGEONEAccordingtothecontext,whatdoestheword"trepidation"mean?
简述蛛网膜下腔出血的临床表现。
A、阴性B、可疑C、弱阳性D、强阳性E、极强阳性皮肤红硬，平均直径8mm，则皮内结核菌素试验反应分度为（）。
新建工业投资项目的现金流入主要包括()。
元朝末年，政治极其腐败，社会矛盾空前激化，在安徽大地上首先点燃了()的烈火。
下面这段话最想传达给读者的意思是()。无论懒惰者还是勤勉者，养金鱼都不成问题。勤勉者可以每一天换一次水，懒惰者尽可以一月换一次。只是如果突然改变换水的习惯，变一天为一月，或变一月为一天，金鱼都可能莫名其妙地暴死。勤勉者据此得出结论：金鱼必须一天
中数相当于第几个四分位差?
按照宪法的分类，我国现行宪法属于()。
A、Themanisinterviewingthewomanforajob.B、Thetwospeakersfirstmeteachothereightyearsago.C、Thetwospeakersonce
Thetwoeconomistscalltheirpaper"MentalRetirement",andtheirargumenthasarousedtheinterestofbehavioralresearchers.
最新回复
(
0
)
