递归函数基础试题及答案

递归函数基础试题及答案姓名：____________________

一、单项选择题（每题2分，共10题）

1.下列关于递归函数的描述，正确的是（）。

A.递归函数必须有返回值

B.递归函数不能直接访问局部变量

C.递归函数可以解决所有问题

D.递归函数必须有一个明确的结束条件

2.下列哪个函数不能正确实现递归调用？（）

A.intfactorial(intn){if(n<=1)return1;elsereturnn*factorial(n-1);}

B.intpower(intbase,intexp){if(exp==0)return1;elsereturnbase*power(base,exp-1);}

C.voidprintStar(intn){if(n>0){printStar(n-1);printf("*\n");}}

D.intfib(intn){if(n<=1)returnn;elsereturnfib(n-1)+fib(n-2);}

3.以下关于递归函数效率的描述，错误的是（）。

A.递归函数效率通常比迭代函数低

B.递归函数可以节省内存空间

C.递归函数在递归深度较大时可能引起栈溢出

D.递归函数通常比迭代函数更容易理解和编写

4.下列哪个函数可以正确实现斐波那契数列的计算？（）

A.intfib(intn){if(n<=1)returnn;elsereturnfib(n-1)+fib(n-2);}

B.intfib(intn){if(n<=1)return1;elsereturnfib(n-1)+fib(n-2);}

C.intfib(intn){if(n<=1)return1;elsereturnfib(n)+fib(n-1);}

D.intfib(intn){if(n<=1)return0;elsereturnfib(n-1)+fib(n-2);}

5.下列关于递归函数的调用栈的描述，正确的是（）。

A.调用栈的大小只与递归深度有关

B.调用栈的大小与递归深度和递归函数的参数有关

C.调用栈的大小与递归函数的局部变量有关

D.调用栈的大小与递归函数的返回值有关

6.以下哪个函数可以实现汉诺塔问题的求解？（）

A.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n-1,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,to_rod,from_rod);}}

B.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n,aux_rod,to_rod,from_rod);}}

C.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n-1,from_rod,to_rod,aux_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,from_rod,to_rod);}}

D.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,from_rod,to_rod);}}

7.以下哪个函数可以实现迷宫问题的求解？（）

A.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

B.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);}}

C.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

D.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

8.以下哪个函数可以实现二分查找算法？（）

A.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid-1,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

B.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

C.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid-1,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

D.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

9.以下哪个函数可以实现快速排序算法？（）

A.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi-1);quickSort(arr,pi+1,high);}

B.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi);quickSort(arr,pi+1,high);}

C.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi-1);quickSort(arr,pi+1,high);}

D.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi);quickSort(arr,pi+1,high);}

10.以下哪个函数可以实现归并排序算法？（）

A.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

B.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

C.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m,r);merge(arr,l,m,r);}

D.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

二、多项选择题（每题3分，共10题）

1.递归函数的特点包括（）。

A.递归函数必须有一个明确的结束条件

B.递归函数可以节省内存空间

C.递归函数通常比迭代函数更容易理解和编写

D.递归函数效率通常比迭代函数低

E.递归函数可以解决所有问题

2.以下哪些情况可能会导致递归函数调用栈溢出？（）

A.递归深度过大

B.递归函数中存在死循环

C.递归函数中局部变量过多

D.递归函数中递归调用次数过多

E.递归函数的参数过多

3.递归函数的内存占用主要包括（）。

A.函数调用栈

B.函数局部变量

C.全局变量

D.递归函数的参数

E.系统堆内存

4.以下哪些函数可以实现阶乘的计算？（）

A.intfactorial(intn){if(n<=1)return1;elsereturnn*factorial(n-1);}

B.intfactorial(intn){if(n==0)return1;elsereturnn*factorial(n-1);}

C.intfactorial(intn){if(n==1)return1;elsereturnn*factorial(n-1);}

D.intfactorial(intn){if(n<=0)return1;elsereturnn*factorial(n-1);}

E.intfactorial(intn){if(n>=0)returnn*factorial(n-1);}

5.以下哪些函数可以实现汉诺塔问题的求解？（）

A.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n-1,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,to_rod,from_rod);}}

B.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n,aux_rod,to_rod,from_rod);}}

C.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n-1,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,to_rod,from_rod);}}

D.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,from_rod,to_rod);}}

E.voidhanoi(intn,charfrom_rod,charto_rod,charaux_rod){if(n==1)printf("Movedisk1fromrod%ctorod%c\n",from_rod,to_rod);else{hanoi(n-1,from_rod,aux_rod,to_rod);printf("Movedisk%dfromrod%ctorod%c\n",n,from_rod,to_rod);hanoi(n-1,aux_rod,to_rod,from_rod);}}

6.以下哪些函数可以实现二分查找算法？（）

A.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid-1,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

B.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

C.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid-1,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

D.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

E.intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid-1,x);returnbinarySearch(arr,mid+1,r,x);}return-1;}

7.以下哪些函数可以实现快速排序算法？（）

A.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi-1);quickSort(arr,pi+1,high);}

B.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi);quickSort(arr,pi+1,high);}

C.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi-1);quickSort(arr,pi+1,high);}

D.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi);quickSort(arr,pi+1,high);}

E.voidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<high;j++){if(arr[j]<=pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);intpi=i+1;quickSort(arr,low,pi-1);quickSort(arr,pi+1,high);}

8.以下哪些函数可以实现归并排序算法？（）

A.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

B.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

C.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m,r);merge(arr,l,m,r);}

D.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

E.voidmergeSort(intarr[],intl,intr){if(l<r){intm=l+(r-l)/2;mergeSort(arr,l,m);mergeSort(arr,m+1,r);merge(arr,l,m,r);}

9.以下哪些函数可以实现迷宫问题的求解？（）

A.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

B.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);}}

C.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

D.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

E.voidmazeSolver(charmaze[][5],inti,intj){if(maze[i][j]=='E'){printf("Exitfoundat(%d,%d)\n",i,j);}elseif(maze[i][j]==''){maze[i][j]='x';mazeSolver(maze,i,j+1);mazeSolver(maze,i,j-1);mazeSolver(maze,i+1,j);mazeSolver(maze,i-1,j);maze[i][j]='';}}

10.以下哪些函数可以实现斐波那契数列的计算？（）

A.intfib(intn){if(n<=1)returnn;elsereturnfib(n-1)+fib(n-2);}

B.intfib(intn){if(n<=1