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

admin2013-05-11 57

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

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

软考中级

某报文的长度是1000字节，利用MD5计算出来的报文摘要长度是(1)位，利用SHA计算出来的报文摘要长度是(2)位。(2010年下半年试题)(2)

下面关于IPv6单播地址的描述中，正确的是__________。(2013年上半年试题)

采用ADSL虚拟拨号接入方式中，用户端需要安装__________软件。(2011年上下半年试题)

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

利用__________可以对软件的技术信息、经营信息提供保护。(2010年下半年试题)

按照网络分级设计模型，通常把网络设计分为3层，即核心层、汇聚层和接入层，以下关于分级网络的描述中，不正确的是()。

处于同一条无差异曲线上的两个点，说明()

患者，男，25岁。胃脘隐痛，喜按喜暖，兼泛吐清水，便溏，舌淡苔薄，脉虚弱，治疗除主穴外，应加取

()属于企业的资产。

某地区三种农副产品的收购资料如表7—2所示。请根据上述资料从下列备选答案中选出正确答案。收购价格指数()。

验资报告应当合理地保证已验证的被审验单位注册资本的实收或变更情况符合国家相关法规的规定和协议、合同、章程的要求,同时也应被视为对被审验单位验资报告日后资本保全、偿债能力和持续经营能力等的保证。()

下列关于企业发行可转换公司债券会计处理的表述中，正确的有()。

在小组中，专注与倾听能够有效地传达社会工作者对组员的尊重与接纳。下列做法中，属于专注与倾听的表现有()。

“严格公正司法”是社会主义法治理念的基本要求之一，下列选项不符合社会主义法治理念的精神和要求的是：

一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的【】。