2. 计算机
  3. 阅读以下说明、C函数和问题，回答问题，将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时，可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[]，int low,int high，int key)用非递归方式在数

阅读以下说明、C函数和问题，回答问题，将解答填入对应栏内。 【说明】 当数组中的元素已经排列有序时，可以采用折半查找(二分查找)法查找一个元素。 下面的函数biSearch(int r[]，int low,int high，int key)用非递归方式在数

admin2018-11-21  32
问题 阅读以下说明、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．[log2(n+1)]    B．[n／2]    C．n一1    D． n
选项
答案(7)A或[log2(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(log2n)，最多与[log2(n+1)]个数组元素进行比较，即可确定查找结果。
转载请注明原文地址:https://kaotiyun.com/show/B2jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)