软考真题
第184题
阅读以下说明、C函数和问题,回答问题1和问题2将解答填入答题纸的对应栏内。

【说明】
当数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。下面的函数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
(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
return biSearch_rec((5) ,key);

else

return biSearch_rec((6) ,key);

}/*if*/

return -1;

}/*biSearch_rec*/
【问题:4.1】(12分)
请填充C函数1和C函数2中的空缺,将解答填入答题纸的对应栏内。
【问题:4.2】(3分)
若有序数组中有n个元素,采用二分查找法查找一个元素时,最多与()个数组元素进行比较,即可确定查找结果。
(7)备选答案:
A.[log2(n+1)] B.[n/2] C.n-1 D.n
第4章数据结构与算法
正确答案:
你的答案:
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2017年 下半年 下午试卷 案例

笔记

请先在App中激活(应用市场搜“软考真题”)

2019-11-01