首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
admin
2018-11-21
49
问题
阅读以下说明、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://kaotiyun.com/show/B2jZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
双击某个非可执行程序的文件名将(24)。
在Excel中,下列符号属于比较运算符的是(43)。
企业上云就是企业采用云计算模式部署信息系统。企业上云已成为企业发展的潮流,其优势不包括()。
为使双击指定类型的文件名就能调用相应的程序来打开处理它,需要将这种文件类型与相应的程序建立文件(23)。
企业信息化总体架构中,计算机硬件、网络系统、操作系统、数据库管理系统等属于(16)。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
在Access中,查询“学生”数据表的所有记录及字段的SQL语句是______。
小张为本企业录入一篇领导讲话文稿。文稿中引用了该企业2008年的销售额和各产品的利润等数据。小张考虑到目前是2010年,从信息的实效性出发,决定对文稿中的这部分内容进行处理,则______做法最为恰当。
在网页中创建一个如下图所示的表单控件的HTML代码是(26)。
随机试题
A.先煎B.后下C.包煎D.另煎E.与他药同煎(2005年第88,89题)细辛入汤剂宦()
患者,男,19岁,既往有癫痫病史2年,长期服用卡马西平控制良好。1周前,患者无明显诱凶感胸骨后烧灼感,无腹痛、腹泻、恶心、呕吐等。查体:腹平软,无压痛及反跳痛,肝脾肋下未触及,肠鸣音正常。胃镜检查提示:胃食管反流病。医嘱:西咪替丁胶囊,口服,一次400mg
在Word2010中,查找范围的默认项是查找___________。
在下列哪些情况下使用作品,可以不经著作权人许可,不向其支付报酬?( )
在某建设项目单因素敏感性的分析图中,三个不确定因素的敏感程度由大到小排序是()。
关于全玻幕墙安装的技术要求,下列叙述正确的是()。
代理理论认为,高支付率的股利政策有助于降低企业的代理成本,但同时也会增加企业的外部融资成本。( )
简述信度和效度的关系。
形成性评价与终结性评价的主要差异在于()。
A、 B、 C、 B传达信息的陈述句→与得到信息相符的回答
最新回复
(
0
)