首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
admin
2018-11-21
52
问题
阅读以下说明、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
程序员下午应用技术考试
软考初级
相关试题推荐
在PowerPoint中,执行插入新幻灯片的操作后,被插入的幻灯片将出现在(53)。
为了提高磁盘存取效率,人们常每隔一段时间进行磁盘碎片整理。所谓磁盘碎片是指磁盘使用一段时间后,(20)。
删除Windows中某个应用程序的快捷方式,意味着(39)。
在Excel2007的A1单元格中输入函数“=LEFT(“CHINA”,1)”,按回车键后,则A1单元格中的值为()。
在Word2007的绘图工具栏上选定矩形工具,按住(36)________________按钮可绘制正方形。
在数据库中能够唯一地标识一个记录被称为______。
在网页中创建一个如下图所示的表单控件的HTML代码是(26)。
由多台计算机组成的一个系统,这些计算机之间可以通过通信来交换信息,互相之间无主次之分,它们共享系统资源,程序由系统中的全部或部分计算机协同执行,执行过程对用户透明。管理上述计算机系统的操作系统是_________。
现在,企业数字化转型已是大势所趋。以下关于企业数字化转型的叙述中,不正确的是_________。
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。说明某公司内部有一个采用TCP/IP作为传输协议的100BASE-TX局域网,包括1台服务器和20台客户机,通过一台16端口的交换机与一台8端口共享集线器级连,其网络结构如图11所
随机试题
膀胱癌最常见的临床表现是
A.窄谱抗生素B.广谱抗生素C.抑菌性抗生素D.杀菌性抗生素E.联合应用抗生素广谱抗生素治疗中发生真菌感染,除选用抗真菌药物外,宜选用
[2016真题·多选]填料式补偿器主要由带底脚的套筒、插管和填料函三部分组成,其主要特点有()。
施工现场固体废物的处理方法主要有()。
道槽区挖方为石方时,则超挖()为褥垫层。
甲上市公司(以下简称“甲公司”)自2×15年起实施了一系列股权交易计划,具体情况如下:(1)2×15年10月,甲公司与乙公司控股股东w公司签订协议,协议约定:甲公司向w公司定向发行20000万股本公司股票,以换取W公司持有的乙公司80%的股权。甲公司定向
若A,B是正交矩阵,则下列说法错误的是()。
鸡蛋和豆浆属于相克的两种食物,若同时吃下鸡蛋和豆浆,鸡蛋的营养将不能够被有效吸收,从而影响食疗功效。()
下图是在一台主机上用sniffer捕获的数据包。请根据图中信息回答下列问题。(1)该主机使用的DNs服务器的域名是【1】,DNs服务器的IP地址是【2】。(2)如果上图显示的是在该主机上执行某个操作过程捕获的所有数据
构造类集框架的基础接口是【】。
最新回复
(
0
)