用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

admin2019-12-10 25

问题用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

选项 A、n
B、[n／2]
C、[log₂n]
D、[log₂n]＋1

答案D

解析根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为[ log₂n]＋1次，查找结束。
[归纳总结]折半查找法在查找成功时和给定值进行比较的关键字个数至多是[log₂n]＋1；在查找不成功时和给定值进行比较的关键字个数最多也不超过[log₂n]＋1。

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

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

计算机408

学硕统考专业

从下面关于虚拟设备的论述中，选择一条正确的论述()。

某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45纳秒，主存的存取周期为200纳秒。已知在一段给定的时间内，CPU共访问内存4500次，其中340次访问主存。问：(1)Cache的命中率是多少?(2)CPU访问内存的平均

在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。

一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

单级中断系统中，中断服务程序内的执行顺序是____。I．保护现场Ⅱ．开中断Ⅲ．关中断Ⅳ．保存断点V．中断事件处理Ⅵ．恢复现场Ⅶ．中断返回

假设一个序列1，2，3，…，n依次进栈，如果出栈的第一个元素是n，那么第i(1≤i≤n)个出栈的元素是()。

对于4个元素依次进栈，可以得到()种出栈序列。

正确描述网络体系结构中的分层概念的是()。

正常使用极限状态包括()。

患者，女，37岁。因皮肤出血点及瘀斑、牙龈出血入院，诊断为特发性血小板减少性紫癜，给予糖皮质激素泼尼松治疗后，血小板逐渐恢复至正常，下一步的治疗是

计算建筑物耗热量指标时所采用的室外计算温度应为：[2007年第89题]

通过试算平衡不能发现的错误有()。

实行定期定额征收方式的个体工商户需要停业的，应当在停业前向税务机关申报办理停业登记。纳税人的停业期不得超过()。

()被称为杭州天主教开教日。

体育课程实施的本质是()。

SpeakerA:Hi.MynameisMark.I’mfromHouston,Texas.SpeakerB:I’mBill.Gladtomeetyou.Whatyearareyou?SpeakerA:__

Samba的工作原理是：让(1)和NetBIOS这两种协议运行于TCP/IP通信协议之上，且通过Windows的(2)协议让用户的Linux计算机可以在Windows的网络邻居上被看到。Samba服务器配置工具是用来管理Samba共享、用户及基本服

TheHomesteadActof1862gavebeadsoffamiliesorindividualsagedtwenty-oneor　　　oldertherighttoown160acres

用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

计算机408

学硕统考专业

从下面关于虚拟设备的论述中，选择一条正确的论述()。

某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45纳秒，主存的存取周期为200纳秒。已知在一段给定的时间内，CPU共访问内存4500次，其中340次访问主存。问：(1)Cache的命中率是多少?(2)CPU访问内存的平均

在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。

一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

单级中断系统中，中断服务程序内的执行顺序是____。I．保护现场Ⅱ．开中断Ⅲ．关中断Ⅳ．保存断点V．中断事件处理Ⅵ．恢复现场Ⅶ．中断返回

假设一个序列1，2，3，…，n依次进栈，如果出栈的第一个元素是n，那么第i(1≤i≤n)个出栈的元素是()。

对于4个元素依次进栈，可以得到()种出栈序列。

正确描述网络体系结构中的分层概念的是()。

正常使用极限状态包括()。

患者，女，37岁。因皮肤出血点及瘀斑、牙龈出血入院，诊断为特发性血小板减少性紫癜，给予糖皮质激素泼尼松治疗后，血小板逐渐恢复至正常，下一步的治疗是

计算建筑物耗热量指标时所采用的室外计算温度应为：[2007年第89题]

通过试算平衡不能发现的错误有()。

实行定期定额征收方式的个体工商户需要停业的，应当在停业前向税务机关申报办理停业登记。纳税人的停业期不得超过()。

()被称为杭州天主教开教日。

体育课程实施的本质是()。

SpeakerA:Hi.MynameisMark.I’mfromHouston,Texas.SpeakerB:I’mBill.Gladtomeetyou.Whatyearareyou?SpeakerA:__

Samba的工作原理是：让(1)和NetBIOS这两种协议运行于TCP/IP通信协议之上，且通过Windows的(2)协议让用户的Linux计算机可以在Windows的网络邻居上被看到。Samba服务器配置工具是用来管理Samba共享、用户及基本服

TheHomesteadActof1862gavebeadsoffamiliesorindividualsagedtwenty-oneor oldertherighttoown160acres

　　　TheHomesteadActof1862gavebeadsoffamiliesorindividualsagedtwenty-oneor　　　oldertherighttoown160acres