用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

admin2013-05-11 56

问题用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

选项 A、n
B、n/2
C、log₂n
D、log₂(n+1)

答案D

解析二分查找亦称折半查找，其基本思想：设查找表的元素存储在一维数组r[1..n]中，首先将待查的key值与表r中间位置上(下标为mid)的记录的关键字进行比较，若相等，则查找成功：若key＞r[mid]．key，则说明待查记录只可能在后半个子表r[mid+1..n](注意：是mid+1，而不是mid)中，下一步应在后半个子表中再进行折半查找，若key＜r[mid].key，则说明待查记录只可能在前半个子表r[1..mid-1](注意：是mid-1，而不是mid)中，下一步应在前半个子表中再进行折半查找，这样通过逐步缩小范围，直到查找成功或予表为空时失败为止。
在表中的元素已经按关键字递增(或递减)的方式排序的情况下，才可进行折半查找。
等概率情况下顺序查找成功的平均查找长度为：

当n值较大时，ASLbs≈log₂(n+1)-1。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

软件设计师上午基础知识考试

软考中级

指令寄存器的位数取决于(2)。

要将一个IP地址为206．17．45．0的网络分解为多个子网，每个子网要25个主机ID并要求尽可能多的子网。指定子网掩码为__________。

网络地址和端口翻译(NAPT)用于(1)，这样做的好处是(2)。(2010年上半年试题)(2)

下图所示为一种数字签名方案，网上传送的报文是(1)，防止A抵赖的证据是(2)。(2010年下半年试题)(2)

已经发布实施的标准(包括已确认或修改补充的标准)，经过实施一定时期后，对其内容再次审查，以确保其有效性、先进性和适用性，其周期一般不超过__________年。(2005年下半年试题)

如图3-1所示为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(1)，图中的(2)是可以合并的状态。

细胞内ATP／AMP比值增加可以抑制

8个月婴儿，于11月8日因呕吐、水样泻、发热、流涕2天入院，大便镜检白细胞1～3个／HP，可见脂肪滴，大便偏酸性，可能的病原体是

女，4l岁。继发性痛经进行性加重1年。妇科检查子宫增大，如2个月妊娠大小，质硬，有压痛，双侧附件正常。本例应诊断为

以下行为不属于想象竞合犯的是()。

工作扩大化的主要方式不包括()。

在商业组织理论中，基尼系数是衡量()的指标之一。

在关系模型中，若属性A是关系R的主码，则在只的任何元组中，属性A的取值都不允许为空，这种约束称为【】规则。

Therearestockmarketsinlargecitiesinmanycountries.StockmarketsinParis,London,Tokyo,ShanghaiandNewYorkareamon

ThestandardofficialretirementagetoqualifyforapublicpensioninmostOECDcountriesiscurrently65.Thechief【C1】______