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

admin2013-05-11 39

问题用递归算法实现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://kaotiyun.com/show/dnRZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

在IPv6中，地址类型是由格式前缀来区分的。IPv6可聚合全球单播地址的格式前缀是________。(2010年上半年试题)

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

路由欺骗是在(1)，直接修改(2)，使某些报文被转到其他处，而不能到达目标主机。DNS欺骗位于(3)，其修改的是(4)，使得用户在访问域名时被引到错误的站点。(2)

报文摘要算法MD5的输出是(1)位，SHA-1的输出是(2)位。(2010年下半年试题)(1)

某局域网采用SNMP进行网络管理，所有被管设备在15min内轮询一次，网络没有明显拥塞，单个轮询时间为0．4s，则该管理站最多可支持__________个设备。(2010年上半年试题)

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

妊娠周以后，经腹可触及子宫内胎体，妊娠周以后，触诊时能区分胎头、胎背、胎臀和胎儿肢体。

女性，64岁，车祸后4小时，临床高度怀疑骨盆粉碎性骨折。查体：血压80／54mmHg，脉搏128次／分，呼吸32次／分，经输血、输液等治疗后，病人血压和中心静脉压均升高不明显。考虑可能的原因为

3岁小儿不慎将异物误吸进气管后入院行全麻后支气管镜下取出异物，为避免麻醉后呛咳反应减弱使食物误入气管，护士应告知家长术后应禁食

施工总承包管理模式与施工总承包模式(　　)。

下列因素中，与固定增长股票内在价值呈反方向变化的有()。

管理评审是为了评审质量管理体系的适宜性、充分性和有效性,其中有效性是指_________。

基克认为，一般性的问题解决大致包括哪些阶段?()

维护个人利益是个人行为的唯一动机。因此，维护个人利益是影响个人行为的主要因素。以下哪项如果为真，最能削弱题干论证?

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

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

软考中级

在IPv6中，地址类型是由格式前缀来区分的。IPv6可聚合全球单播地址的格式前缀是________。(2010年上半年试题)

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

路由欺骗是在(1)，直接修改(2)，使某些报文被转到其他处，而不能到达目标主机。DNS欺骗位于(3)，其修改的是(4)，使得用户在访问域名时被引到错误的站点。(2)

报文摘要算法MD5的输出是(1)位，SHA-1的输出是(2)位。(2010年下半年试题)(1)

某局域网采用SNMP进行网络管理，所有被管设备在15min内轮询一次，网络没有明显拥塞，单个轮询时间为0．4s，则该管理站最多可支持__________个设备。(2010年上半年试题)

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

妊娠________周以后，经腹可触及子宫内胎体，妊娠________周以后，触诊时能区分胎头、胎背、胎臀和胎儿肢体。

女性，64岁，车祸后4小时，临床高度怀疑骨盆粉碎性骨折。查体：血压80／54mmHg，脉搏128次／分，呼吸32次／分，经输血、输液等治疗后，病人血压和中心静脉压均升高不明显。考虑可能的原因为

3岁小儿不慎将异物误吸进气管后入院行全麻后支气管镜下取出异物，为避免麻醉后呛咳反应减弱使食物误入气管，护士应告知家长术后应禁食

施工总承包管理模式与施工总承包模式( )。

下列因素中，与固定增长股票内在价值呈反方向变化的有()。

管理评审是为了评审质量管理体系的适宜性、充分性和有效性,其中有效性是指_________。

基克认为，一般性的问题解决大致包括哪些阶段?()

维护个人利益是个人行为的唯一动机。因此，维护个人利益是影响个人行为的主要因素。以下哪项如果为真，最能削弱题干论证?

妊娠周以后，经腹可触及子宫内胎体，妊娠周以后，触诊时能区分胎头、胎背、胎臀和胎儿肢体。

施工总承包管理模式与施工总承包模式(　　)。