首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
admin
2018-11-21
26
问题
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。
【说明】
当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。
下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数组r中进行二分查找,函数biSearch_rec(int r[],int low,int high,int key)采用递归方式在数组r中进行二分查找,函数的返回值都为所找到元素的下标;若找不到,则返回一1。
【C函数1】
int biSearch(int r[],int low,int high,int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标,否则返回一1
{
int mid;
while( (1) ){
mid=(low+high)/2;
if(key==r[mid])
return mid;
else if(key<r[mid])
(2)
;
else
(3)
;
}/*while*/
return 一1;
}/*biSearch*/
【C函数2】
int biSearch—rec(int r[],int low,int high,int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组r中递归地查找与key相同的元素
//若找到则返回该元素在数组r的下标,否则返回一1
{
int mid;
if ( (4) ) (
mid=(low+high)/2;
if (key==r[mid])
return mid;
else if (key<r[mid])
return bisearch_rec(
(5)
,key);
else
return biSearch_rec(
(6)
,key);
}/*if*/
return -1;
}/*biSearch_rec*/
若有序数组中有n个元素,采用二分查找法查找一个元素时,最多与
(7)
个数组元素进行比较,即可确定查找结果。
(7)备选答案:
A.[log
2
(n+1)] B.[n/2] C.n一1 D. n
选项
答案
(7)A或[log
2
(n+1)]
解析
本题考查C程序的基本结构、递归运算逻辑和二分查找算法的实现。
二分查找算法要求查找表的元素已经有序,且可以随机访问元素,其基本思想是:首先令待查元素与中间位置上的元素进行比较,若相等,则查找成功结束;若大于中间元素,则继续在后半个查找表中继续进行二分查找,否则在前半个查找表中继续进行二分查找。
由于有序序列存储在数组中,所以查找表的开始位置(即最小元素的位置)用low表示,结束位置(即最大元素的位置)用high表示(即查找表可以通过[low,high]来表示),从而可以计算出中间位置mid为(low+high)/2,前半个查找表可用[low,mid一1]表示,后半个查找表可用[mod一1,high]表示。因此,在查找过程中,若待查元素小于中间位置的元素,则将high更新为mid-1;若待查元素大于中间位置的元素,则将low更新为mid+1,从而在继续进行二分查找时仍然通过[low,high]来表示查找表。显然,low<=high表示查找范围有效,即查找表至少有一个元素。
函数1中的空(1)处应填入“low<=high”,空(2)处表示要在前半个查找表中继续查找,因此需要修改表尾的位置参数,应填入“high=mid—1”;空(3)处表示要在后半个查找表中继续查找,因此需要修改表头的位置参数,应填入“low=mid+1”。
用递归方式实现二分查找算法时,表头位置参数或表尾位置参数的修改通过递归调用时的实参来表示。函数2中的空(4)处应填入“low<high”,表示查找表有效,空(5)处表示要在前半个查找表中继续查找,因此需要修改查找表的表尾位置参数,完整的递归调用为“biSearch_rec(r,low,mid—1,key)”;空(3)处表示要在后半个查找表中继续查找,因此需要修改查找表的表头位置参数,完整的递归调用为“biSearch_rec(r,mid+1,high,key)”。
二分查找算法的时间复杂度为O(log
2
n),最多与[log
2
(n+1)]个数组元素进行比较,即可确定查找结果。
转载请注明原文地址:https://jikaoti.com/ti/X8W7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
在PowerPoint中,执行插入新幻灯片的操作后,被插入的幻灯片将出现在(53)。
在Windows XP中,可用来改变窗口大小的光标是(37)。
为了提高磁盘存取效率,人们常每隔一段时间进行磁盘碎片整理。所谓磁盘碎片是指磁盘使用一段时间后,(20)。
某信息处理技术员正在做大批数据处理的大项目时,领导又交宋了另一项临时性的紧迫工作,要求优先处理。该信息处理技术员需要转而做新的工作,他对原工作的处理方式应该是(69)。
在Excel2007的A1单元格中输入函数“=LEFT(“CHINA”,1)”,按回车键后,则A1单元格中的值为()。
Word中“编辑”菜单下的“定位”命令的功能不能够定位(47)。
程序员一般用(7)软件编写和修改程序。
采购了多种品牌的部件进行计算机组装,每个部件都正常,连接、安装、配置操作也完全正确,但系统仍不能正常使用。很可能是____________问题。
180的正约数(能整除180的自然数,包括l和180本身)的个数是________。
综合布线系统由6个子系统组成,将图1-1中(1)~(6)处空缺子系统的名称填写在答题纸对应的解答栏内。考虑性能与价格因素,图1-1中(1)、(2)和(4)中各应采用什么传输介质?
随机试题
影响肺部药物吸收的因素有
简要回答旅游者的心理实质。
A.恶性高血压B.高血压脑病C.高血压性心脏病D.脑梗死E.高血压危象男性,30岁。阵发性头痛,烦躁,心悸,多汗,血压35.2/17.3kPa(265/130mmHg)。最可能的诊断为
关节松动术的禁忌证包括
双层石膏板暗龙骨吊顶,面层与基层板的接缝应(),并()同一根龙骨上。
《文物保护法》规定,不符合在文物保护单位保护范围和建设控制地带内从事建设活动的相关规定的是()
某制药企业2012年初拥有厂房原值3000万元,4月份给该厂房安装了配套通风管线,整体安装价值300万元;拥有办公楼原值2000万元,6月25日协议将该办公楼的1/3租给某培训机构做儿童家教培训中心,月租金5万元,6月30日该培训中心正式人住,自7月1日开
以下关于个人汽车贷款额度的描述,正确的是()。
下列描述错误的是()。
一个认识的完整过程是()。
最新回复
(
0
)