首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
阅读以下说明、C函数和问题,回答问题,将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数
admin
2018-11-21
51
问题
阅读以下说明、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
程序员下午应用技术考试
软考初级
相关试题推荐
设10个数{Xi|i=1,10)的平均值为a,则{10Xi+1|i=1,10)的平均值为(5)。
某个字段的数据是原始数据计算的结果,该字段的宽度和小数位数对数据的精度有影响。一般来说,小数位数的确定需要考虑______。
在Word中可以用“编辑”→“定位”命令对需要寻找的位置进行快速定位,(48)不属于定位目标。
在Excel中,设单元格A1中的值为80,B1中的值为35,若在C1单元格中输入函数“=IF(AND(A1>=60,B1>=60),“不及格”,“补考”)”,按回车键后,C1单元格中的值为()。
某工厂信息处理技术员设计了如下统计表:该表设计中包含的问题以及改进方法是______。
在Access中,查询“学生”数据表的所有记录及字段的SQL语句是______。
文件的扩展名可以说明文件类型。下面的“文件类型一扩展名”对应关系错误的是:
程序员一般用(7)软件编写和修改程序。
在Exeel2010中,___________可以对A1单元格数值的小数部分进行四舍五入运算。
一批数据的__________代表这批数据的一般水平,掩盖了其中各部分数据的差异。
随机试题
高效液相色谱法用于含量测定时,对系统性能的要求
刚体作平动时,某瞬时体内各点的速度与加速度为:
()的主要投资对象是资本市场上的上市股票与债券,货币市场上的短期票据与银行同业拆借,以及金融期货、黄金、期权交易、不动产等。
根据现行国家工程建设消防技术标准的要求,下列供暖系统的设置不符合相关规定的是()。
居民乙因拖欠居民甲180万元款项无力偿还,2010年6月经当地有关部门调解,以房产抵偿该笔债务,居民甲因此取得该房产的产权并支付给居民乙差价款20万元。假定当地省政府规定的契税税率为5%。下列表述中正确的是()。(2010年)
阅读下列材料:为了让高中一年级学生能够完整地体验信息处理的全过程,教师通常会设计一个综合性的主题学习活动。“我的悠长假期”主题学习活动即以图像处理为栽体,让学生体验信息采集、加工与表达的全过程。下面是本次主题活动方案:活动目的:以图片处理为载体体验信息
“三弦”这种乐器属于民族乐器中的()类。
元认知指的是对认知的认知,即认知主体关于自己认知过程的知识和调节这些过程的能力,对思维和学习活动的知识和控制。元认知的实质是对认知活动的自我意识和自我调节。根据上述定义,以下包含元认知的是()。
DerVatergibt______TochterdenWagen.
I_______thepicturefromthewallinordertocleanit.
最新回复
(
0
)