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

admin2013-05-11 43

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

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

软考中级

某网站向CA申请了数字证书。用户通过(1)来验证网站的真伪。在用户与网站进行安全通信时，用户可以通过(2)进行加密和验证，该网站通过(3)进行解密和签名。(2009年下半年试题)(1)

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

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

ARPAnetisawideareanetwork(WAN)．AnetworkthatconnectedDepartmentofDefenseresearchsitesacross(1)．Createdin1969wit

参见下图，主机Aping主机B，当数据帧到达主机B时，其中包含的源MAC地址和源IP地址为__________。(2013年上半年试题)

以下是在Linux操作系统中输入ps命令后得到的进程状态信息，其中处于“僵死”状态进程的PID为(1)，若要终止处于“运行"状态的进程的父进程，可以输入命令(2)。(2008年上半年试题)(2)

Kerberos由认证服务器(AS)和票证授予服务器(TGS)两部分组成，当用户A通过Kerberos向服务器V请求服务时，认证过程如下图所示，图中①处为(1)，②处为(2)。(2011年下半年试题)(1)

网络管理基本模型是由网络管理者、网管代理、管理信息库等要素构成，下列选项属于网络管理者的操作是()。

毛毛第一次看到骆驼时惊呼道：“快看，大马背上长东西了!”按皮亚杰的理论，毛毛的反应可以用下列哪个概念解释?()

下列关于脑动脉粥样硬化的说法，错误的是

维生素B。4h负荷试验时，成人的负荷剂量为()。

执法

社会评价中判断一个项目好坏的标准是()。

简便易行但比较粗糙且带有主观判断的混合成本分解方法是()。

下列与审计相关的内部控制的说法中，正确的是()。

Inthispassage,"Hollywood"isusedtodescribe.Thepassagemmainlyabout.

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

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

软考中级

某网站向CA申请了数字证书。用户通过(1)来验证网站的真伪。在用户与网站进行安全通信时，用户可以通过(2)进行加密和验证，该网站通过(3)进行解密和签名。(2009年下半年试题)(1)

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

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

ARPAnetisawideareanetwork(WAN)．AnetworkthatconnectedDepartmentofDefenseresearchsitesacross(1)．Createdin1969wit

参见下图，主机Aping主机B，当数据帧到达主机B时，其中包含的源MAC地址和源IP地址为__________。(2013年上半年试题)

以下是在Linux操作系统中输入ps命令后得到的进程状态信息，其中处于“僵死”状态进程的PID为(1)，若要终止处于“运行"状态的进程的父进程，可以输入命令(2)。(2008年上半年试题)(2)

Kerberos由认证服务器(AS)和票证授予服务器(TGS)两部分组成，当用户A通过Kerberos向服务器V请求服务时，认证过程如下图所示，图中①处为(1)，②处为(2)。(2011年下半年试题)(1)

网络管理基本模型是由网络管理者、网管代理、管理信息库等要素构成，下列选项属于网络管理者的操作是()。

毛毛第一次看到骆驼时惊呼道：“快看，大马背上长东西了!”按皮亚杰的理论，毛毛的反应可以用下列哪个概念解释?()

下列关于脑动脉粥样硬化的说法，错误的是

维生素B。4h负荷试验时，成人的负荷剂量为()。

执法

社会评价中判断一个项目好坏的标准是()。

简便易行但比较粗糙且带有主观判断的混合成本分解方法是()。

下列与审计相关的内部控制的说法中，正确的是()。

Inthispassage,"Hollywood"isusedtodescribe______.Thepassagemmainlyabout______.

Inthispassage,"Hollywood"isusedtodescribe.Thepassagemmainlyabout.