使用递归算法实现折半查找算法int binarySearch（int a[], int low, int high, int key), key在数组a中时，返回位置索引，否则，返回-1； 编写main函数并测试它
使用递归算法实现折半查找算法int binarySearch（int a[], int low, int high, int key), key在数组a中时，返回位置索引，否则，返回-1； 编写main函数并测试它
参考答案和解析
B
相关考题：
以下 isprime 函数的功能是判断形参 a 是否为素数，是素数，函数返回 1 ，否则返回 0 。请填空int isprime(int a){ int i;for(i=2;i=a/2;i++)if(a ％ i==0) 【 1 5 】 ;【 1 6 】 ;}
若各选项中所用变量已正确定义，函数 fun 中通过 return 语句返回一个函数值，以下选项中错误的程序是A)main(){ …… x=fun(2,10); …… }float fun(int a,int b){ …… }B)float fun(int a,int b){ …… }main(){ …… x=fun(i,j); …… }C)float fun(int,int);main(){ …… x=fun(2,10); …… }float fun(int a,int b) { …… }D)main(){ float fun(int i,int j);…… x=fun(i,j); …… }float fun(int a,int b){ …… }
●试题七阅读以下说明和C++代码，将解答写入答题纸的对应栏内。【说明】请编写一个函数int SeqSearch(int list［］，int start，int n，int key)，该函数从start开始，在大小为n的数组list中查找key值，返回最先找到的key值的位置，如果没有找到则返回-1。请修改程序中画线部分的错误并将不同情况下的输出结果补充完整。【程序】文件search.cpp的内容如下：#include iostream.hint SeqSearch(int list［］，int start，int n，int key){for(int i=start；i=n；i++)// (1){if(list［i］=key) // (2){return i；}}return -1；}void main(){int A［10］；int key，count=0，pos；cout" Enter a list of 10 integers: "；for(pos=0；pos10；pos++){cinA； // (3)}cout"Enter a key: "；cinkey；pos=0；while((pos=SeqSearch(A，pos，10，key))!=-1){count++；pos++；}coutkey" occurs "count(count!=1?" times":" time")" in the list."endl；}第一种情况：输入2 3 12 6 8 45 8 33 7 输入key：8输出： (4)第二种情况：输入2 3 12 6 8 45 8 33 7 输入key：9输出： (5)
以下ispeime函数的功能是判断形参a是否为素数，是素数，函数返回1，否则返回0。请填空。int isprime(int a){int i; for(i=2;i=a/2;【】) if(a%i= =0) return(0); 【】；}
请编写两个函数int sum_of_powers(int k，int n)，powers(int m，int n)，求1～6的k次方的和,sum_of_powers中参数k和n分别表示k次方和所求数列中最大的一个自然数，最后返回所求值，powers中参数m和n分别表示m为底数n为指数，最后返回所求值。要求使用for循环和函数嵌套(int sum_of_powers中调用powers)实现算法。输出结果如下：sum of 4 powers of intergers from 1 to 6=2275注意：部分源程序已存在文件test25_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数sum_of_powers和powers的花括号中填写若干语句。文件test25_2.cpp的内容如下：include＜iostream.h＞const int k(4)；const int n(6)；int sum_of_powers(int k，int n)，powers(int m，int n)；void main(){cout＜＜"sum of "＜＜k＜＜" powers Of intergers from 1 to "＜＜n＜＜"="；cout＜＜sum_of_powers(k，n)＜＜endl；}int sum_of_powers(int k，int n){}int powers(int m， int n){}
函数int factors(int n)的功能是判断整数n(n＞=2)是否为完全数。如果n是完全数，则函数返回0，否则返回-1。所谓“完全数”是指整数n的所有因子(不包括n)之和等于n自身。例如，28的因子为1，2，4，7，14，而28=1+2+4+7+14，因此28是“完全数”。[C函数1]int factors(int n){ int i,s；for(i=1，s=0；i＜=n/2；i++)if(n%i=0) (1)______;if( (2)______ )return 0;rerurn-1；}[说明2]函数int maxint(int a[],int k)的功能是用递归方法求指定数组中前k个元素的最大值，并作为函数值返回。[C函数2]int maxint(int a[]，int k){ int t；if( (3)_____ ) return (4)_______；t=maxint(a+1， (5)______ )；return(a[0]＞t)?a[0]:t；}
N个有序整数数列已放在一维数组中，给定下列程序中，函数fun()的功能是：利用折半查找算法查找整数m在数组中的位置。若找到，则返回其下标值：反之，则返回-1。折半查找的基本算法是：每次查找前先确定数组中待查的范围：low和high(low＜high)，然后把m与中间位置(mid)中元素的值进行比较。如果m的值大于中间位置元素中的值，则下一次的查找范围放在中间位置之后的元素中；反之，下次查找范围落在中间位置之前的元素中。直到low＞high，查找结束。请改正程序中的错误，使它能得出正确的结果。注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。试题程序：include ＜stdio.h＞define N 10/*************found*********************/void fun(int a[],int m){ int low--0,high=N-l,mid;while (low＜=high){ mid=(low+high)/2;if(m＜a[mid])high=mid-1;/*************found*********************/else if(m＞=a [mid])low=mid+1;else return(mid);}return(-1);}main (){ int i,a[N]={-3,4,7,9,13,24,67,89,100,180},k,m;printf ("a数组中的数据如下: ");for(i=0;i＜N;i++) printf("%d",a[i]);printf ("Enter m: "); scanf ("%d", m);k=fun (a,m);if (k＞=0) printf ("m=%d, index=%d\n",m, k);else printf("Not be found!\n");}
下列说法不正确的是A．int *fun();----fun是一个返回int指针的函数B．int (*fun)();---fun是一个返回int指针的函数C．int (*array[5])();----array是一个有5个元素的数组，每一个元素都是一个函数指针，指向一个返回int的函数D．int (*fun(int))(int);----fun是带有一个int参数的函数，返回值是一个函数指针，这个指针指向带有一个int参数并返回int的函数
请编写一个函数sum(int array[],int len)，该函数返回数组array的所有整数元素的和，其中len为数组array的长度。注意：部分源程序已存在文件test34_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数sum的花括号中填写若干语句。程序输出结果如下：sum of array 15文件test34_2.cpp的内容如下：include ＜iostream.h＞int sum(int array[],int len){}void main(){static int a[5]-{1,2,3,4,5};int result=sum(a,5);cout＜＜"sum of array "＜＜result＜＜end1;}
阅读以下说明和C++代码，将解答写入对应栏内。【说明】请编写一个函数int SeqSearch(int list[]，int start，int n，int key)，该函数从start开始，在大小为n的数组list中查找key值，返回最先找到的key值的位置，如果没有找到则返回-1。请修改程序中画线部分的错误并将不同情况下的输出结果补充完整。【程序】文件search.cpp的内容如下：include ＜iostream. h ＞int SeqSearch( int list[ ] ,int start,int n,int key){for(int i=start;i＜=n;i++) //(1){if( list[i] = key)//(2){return i;}}return -1;}void main( ){int A[10]int key,count=0,pos;cout ＜＜" Enter a list of 10 integers:";for(pos=0;pos＜10;pos++){cin ＞＞A; //(3)}cout ＜＜" Enter a key; ";cin ＞＞ key;pos=0;while(( pos = SeqSearch ( A, pos, 10, key)) !=-1 ){count ++;pos ++;}cout＜＜key＜＜"occurs" ＜＜count＜＜ (count!=1?" times":" time") ＜＜" in the list,"＜＜ endl;}第一种情况：输入2 3 12 6 8 45 8 33 7输入key：8输出：(4)第二种情况：输入2 3 126 8 45 8 33 7输入k6y：9输出：(5)
阅读下列说明、流程图和算法，将应填(n)处的字句写在对应栏内。[说明]下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为 low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：[流程图][算法说明]将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int hieh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。[算法]void sort(int A[]，int L，int H) {if (L＜H) {k=p(A，L，R)； //p()返回基准数在数组A中的下标sort((4))； //小于基准敷的元素排序sort((5))； //大于基准数的元素排序}}
以下程序调用findmax()函数返回数组中的最大值。请填空完成此函数。include〈iostream〉using namespace std；int findmax(int*a，int n){int +p、*s；for(p=a，s=a；p-a〈n；p++)if(【 】)*s=*p；return(*S)；}int main(){int x[5]={12，21，14，16}；cout〈〈findmax(X，5)〈〈end1；return 0；}
阅读下列函数说明和C代码，将应填入 处的字句写在答题纸的对应栏内。[函数1.1说明]函数int factors(int n)的功能是判断整数n(n=2)是否为完全数。如果n是完全数，则函数返回0，否则返回-1。所谓“完全数”是指整数n的所有因子（不包括n)之和等于n自身。例如28的因子为1、2、4、7、14，而28=1+2+4+7+14，因此28是“完全数”。[函数1.1]int factors(int n){int i,s;for(i=1,s=0;i=n/2;i++)if(n%i==0) (1) ;if( (2) )return 0;return -1;}[函数1.2说明]函数int maxint(int a[], int k)的功能是用递归方法求指定数组中前k个元素的最大值，并作为函数值返回。[函数1.2]int maxint(int a[],int k){int t;if( (3) ) return (4) ;t=maxint(a+1, (5) );return (a[0]t)?a[0]:t;
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。【函数2.1说明】递归函数sum(int a[], int n)的返回值是数组a[]的前n个元素之和。【函数2.1】int sum (int a[],int n){if(n＞0) return (1);else (2);}【函数2.2说明】有3个整数，设计函数compare(int a，int b，int c)求其中最大的数。【函数2.2】int compare (int a, int b, int c ){ int temp, max;(3) a:b;(4) temp:c;}【函数2.3说明】递归函数dec(int a[]，int n)判断数组a[]的前n个元素是否是不递增的。不递增返回 1，否则返回0。【函数2.3】int dec( int a[], int n ){if(n＜=1) return 1;if(a[0]＜a[1]) return 0;return (5);}
请编写一个函数long Fibo(int n), 该函数返回n的Fibonacci数。规则如下：n等于1或者2时，Fibonacci数为1，之后每个Fibonacci数均为止前两个数之和， 即：F(n)=F(n-1)+F(n-2)注意：清使用递归算法实现该函数。部分源程序已存在文件test1_2.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数Fibo的花括号中填写若干语句。如n=8时，结果是21。文件test1_2.cpp清单如下:include＜iostream.h＞corlsh int N=8;long Fibo(int n);void main(){long f=Fibo(N);couk＜＜f＜＜endl;}long Fibo(int n){}
阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。【流程图说明】下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Array[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。【算法说明】将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int Array[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[]，int L，int H)的功能是实现数组Array中元素的递增排序。【算法】void sort(int Array[]，int L，int H){if (L＜H) {k=p(Array，L，H)；/*p()返回基准数在数组Array中的下标*/sort((4))；/*小于基准数的元素排序*/sort((5))；/*大于基准数的元素排序*/}}
请编写一个函数int sum(int n)，该函数完成1+2+3+…+n的运算，并返回运算结果，其中n＞0。注意：请使用递归算法实现该函数。注意：部分源程序已存在文件：test11.cpp中。请勿修改主函数main和其他函数中的任何内容，仅在函数sum的花括号中填写若干语句。文件test11_2.cpp的内容如下：include＜iostream.h＞int sum(int n){}void main(){int n；cout＜＜"输入n:"；cin＞＞n；int result；sum(n)；cout＜＜"结果为："＜＜result＜＜endl；}
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]已知r[1...n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录。若查找失败，则输出“failure",函数返回值为0；否则输出“success”，函数返回值为该记录的序号值。[C函数]int binary search(struct recordtype r[],int n,keytype k){ intmid,low=1,hig=n;while(low＜=hig){mid=(1);if(k＜r[mid].key) (2);else if(k==r[mid].key){printf("succesS\n");(3);}else (4);}printf("failure\n");(5);}
阅读以下说明和C函数，填补代码中的空缺（1）～（5），将解答填入答题纸的对应栏内。【说明1】 函数isPrime(int n)的功能是判断n是否为素数。若是，则返回1，否则返回0。素数是只能被1和自己整除的正整数。例如，最小的5个素数是2，3，5，7，11。 【C函数】 int isPrime (int n) { int k, t; if (n==2) return 1; if(n2|| （1） ) return 0; /* 小于2的数或大于2的偶数不是素数 */ t=(int)sqrt(n)+1; for (k=3; kt; k+=2) if ( （2） ) return 0; return 1; } 【说明2】 函数int minOne(int arr[], int k)的功能是用递归方法求指定数组中前k个元素中的最小者，并作为函数值返回。 【C函数】 int minOne (int arr[], int k) { int t; assert (k0) ; if(k==1) return （3） ; t=minOne(arr+1, （4） ; if (arr[0]t) return arr[0]; return （5） ; }
●试题二阅读下列说明、流程图和算法，将应填入(n)处的字句写在答题纸的对应栏内。【说明】下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：【流程图】图3流程图【算法说明】将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。【算法】void sort (int A[]， int 1，int H){if ( LH){k=p(A，L，R)；//p()返回基准数在数组A中的下标sort( (4) )；//小于基准数的元素排序sort( (5) )；//大于基准数的元素排序}}
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明1]函数int function(int a)的功能是判断指定的正整数是否为素数，若是，返回1，否则返回0。[C函数1]int function(int a){ int yes,i;i=2;yes=1;while(i＜=a/2 (1) ){if( (2) ) yes=0;i++;}return yes;}[说明2]函数int deleteARR(int*arr,intn)的功能是指定的有序数组压缩成各元素互不相同的有序数组，即相同数只保留一个，多余的被删除。函数返回值是互不相同的元素个数。[C函数2]int deleteARR(int*arr,int n){ int k,j;k=0;j=1;while(j＜n){if( (3) )(4)=arr[j];j++;}return (5);}
阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。[说明1]函数isPrime(int n)的功能是判断n是否为素数。若是，则返回1，否则返回0。素数是只能被1和自己整除的正整数。例如，最小的5个素数是2，3，5，7，11。[C函数] int isPrime(int n) { int k, t; if (n==2) return 1; if(n＜2 || ______)return 0; /*小于2的数或大于2的偶数不是素数// t=(int)Sqrt(n)+1; for(k=3; k＜t; k+=2) if(______) return 0; return 1; }[说明2]函数int minOne(int art[],int k)的功能是用递归方法求指定数组中前k个元素中的最小者，并作为函数值返回。[C函数]int minOne(int arr[],int k){int t;assert(k＞0);if(k==1)return ______;t=minOne(arr+1,______);if(arr[0]＜t)return amr[0];return ______;}
第四题 阅读以下说明、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
编写一个递归函数“int FF（int a[]， int n）”，求出数组a中所有n个元素之积并返回。