遞歸函數(shù)基礎(chǔ)試題及答案姓名：____________________

一、單項(xiàng)選擇題（每題2分，共10題）

1.下列關(guān)于遞歸函數(shù)的描述，正確的是（）。

A.遞歸函數(shù)必須有返回值

B.遞歸函數(shù)不能直接訪問局部變量

C.遞歸函數(shù)可以解決所有問題

D.遞歸函數(shù)必須有一個明確的結(jié)束條件

2.下列哪個函數(shù)不能正確實(shí)現(xiàn)遞歸調(diào)用？（）

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.以下關(guān)于遞歸函數(shù)效率的描述，錯誤的是（）。

A.遞歸函數(shù)效率通常比迭代函數(shù)低

B.遞歸函數(shù)可以節(jié)省內(nèi)存空間

C.遞歸函數(shù)在遞歸深度較大時可能引起棧溢出

D.遞歸函數(shù)通常比迭代函數(shù)更容易理解和編寫

4.下列哪個函數(shù)可以正確實(shí)現(xiàn)斐波那契數(shù)列的計(jì)算？（）

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.下列關(guān)于遞歸函數(shù)的調(diào)用棧的描述，正確的是（）。

A.調(diào)用棧的大小只與遞歸深度有關(guān)

B.調(diào)用棧的大小與遞歸深度和遞歸函數(shù)的參數(shù)有關(guān)

C.調(diào)用棧的大小與遞歸函數(shù)的局部變量有關(guān)

D.調(diào)用棧的大小與遞歸函數(shù)的返回值有關(guān)

6.以下哪個函數(shù)可以實(shí)現(xiàn)漢諾塔問題的求解？（）

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.以下哪個函數(shù)可以實(shí)現(xiàn)迷宮問題的求解？（）

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.以下哪個函數(shù)可以實(shí)現(xiàn)二分查找算法？（）

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.以下哪個函數(shù)可以實(shí)現(xiàn)快速排序算法？（）

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.以下哪個函數(shù)可以實(shí)現(xiàn)歸并排序算法？（）

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);}

二、多項(xiàng)選擇題（每題3分，共10題）

1.遞歸函數(shù)的特點(diǎn)包括（）。

A.遞歸函數(shù)必須有一個明確的結(jié)束條件

B.遞歸函數(shù)可以節(jié)省內(nèi)存空間

C.遞歸函數(shù)通常比迭代函數(shù)更容易理解和編寫

D.遞歸函數(shù)效率通常比迭代函數(shù)低

E.遞歸函數(shù)可以解決所有問題

2.以下哪些情況可能會導(dǎo)致遞歸函數(shù)調(diào)用棧溢出？（）

A.遞歸深度過大

B.遞歸函數(shù)中存在死循環(huán)

C.遞歸函數(shù)中局部變量過多

D.遞歸函數(shù)中遞歸調(diào)用次數(shù)過多

E.遞歸函數(shù)的參數(shù)過多

3.遞歸函數(shù)的內(nèi)存占用主要包括（）。

A.函數(shù)調(diào)用棧

B.函數(shù)局部變量

C.全局變量

D.遞歸函數(shù)的參數(shù)

E.系統(tǒng)堆內(nèi)存

4.以下哪些函數(shù)可以實(shí)現(xiàn)階乘的計(jì)算？（）

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.以下哪些函數(shù)可以實(shí)現(xiàn)漢諾塔問題的求解？（）

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.以下哪些函數(shù)可以實(shí)現(xiàn)二分查找算法？（）

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.以下哪些函數(shù)可以實(shí)現(xiàn)快速排序算法？（）

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.以下哪些函數(shù)可以實(shí)現(xiàn)歸并排序算法？（）

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.以下哪些函數(shù)可以實(shí)現(xiàn)迷宮問題的求解？（）

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.以下哪些函數(shù)可以實(shí)現(xiàn)斐波那契數(shù)列的計(jì)算？（）

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

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