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

admin2013-05-11 36

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

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

软考中级

POP3协议采用(1)模式，当客户机需要服务时，客户端软件(OutlookExpress或Fox．Mail)与POP3服务器建立(2)连接。(2011年下半年试题)(2)

FTP客户上传文件时，通过服务器建立的连接是(1)，FTP客户端应用进程的端口可以为(2)。(2011年上半年试题)(2)

下面给出的网络地址中，属于私网地址的是__________。(2010年下半年试题)

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

以太网帧格式如下图所示，其中的“长度"字段的作用是__________。(2010年下半年试题)

ISO／IEC9126软件质量模型中第一层定义了6个质量特性，并为各质量特性定义了相应的质量子特性。子特性__________属于可靠性质量特性。

在BGP4协议中，(1)报文建立两个路由器之间的邻居关系，(2)报文给出了新的路由信息。(2012年下半年试题)(1)

"TheTruthAboutPlastic"Ifyouknowwheretofindagoodplastic-freeshampoo,canyoutellJeanneHaegele?LastSeptember

对于一手个人住房贷款，商业银行最主要的合作单位是()。

()反映的是特定社会对受教育者的基本要求，是确定教育内容、选择教育方法、检查和评价教育效果的依据。

Africa’selephantsaredividedbetweenthesavannahsofeasternandsouthernAfricaandtheforestsofcentralAfrica.Somebiol

流量分析属于()方式。

HowtoapproachReadingTestPartFour•ThispartoftheReadingTesttestsyourvocabulary.•Readthewholetextquicklytof

CommunicateComplexIdeasSuccessfullyIntoday’slecture,wewilldiscusshowtocommunicatecomplexideassuccessfullywhe

PlayIsaSeriousBusinessA)Playingisaseriousbusiness.Childrenengrossedinamake-believeworld,foxcubsplay-fightingo