用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

admin2019-12-10 33

问题用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

选项 A、n
B、[n／2]
C、[log₂n]
D、[log₂n]+1

答案D

解析根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为[log₂n]+1次，查找结束。
折半查找法在查找成功时和给定值进行比较的关键字个数至多是[log₂n]+1；在查找不成功时和给定值进行比较的关键字个数最多也不超过[log₂n]+1。

转载请注明原文地址:https://kaotiyun.com/show/Um3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

计算机408

学硕统考专业

设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

UNIX系统中，输入／输出设备看作是()。

假定有4个整数用8位补码分别表示r1=FEH，r2=F2H，r3=90H，r4=F8H，若将运算结果存放在一个8位寄存器中，则下列运算中会发生溢出的是____。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

已知定点小数x的补码为1．x1x2x3，且x≤－0．75，则必有()。

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y，要求写出详细的

计算

男性，35岁，因撞伤造成左尺骨鹰嘴骨折，并行手术治疗，40天后关节屈伸活动范围约110°。12周后肘关节屈伸范围缩小。X线见肘前方软组织雾状密度增高影。考虑为

病人男，45岁，因在工地干活时，被生锈铁钉刺入足跟而致破伤风，收住入院。对此病人实施操作时哪项不妥()。

从地球大气层外层空间，距地面80km以上，以宇宙飞行器或人造地球卫星等作为遥感平台的探测方法是()。

会计电算化岗位及其权限设置应该由()来进行设置。

下列各项中，属于税法适用原则的有()。

沈从文的散文和小说创作共同表现了他的()。

caique

程序设计的任务包括()。

A、Sonandmother.B、Customerandshopassistant.C、ClerkandbossD、Studentandteacher.B信息词bought和department可说明他们的关系是顾客和售货员。