1、數(shù)據(jù)結(jié)構(gòu)習(xí)題第6章,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 谷方明,6-1,遞歸函數(shù)F(n)=F(n-1)+n+1(n1)的遞歸終止條件是 . A F(0)=0 B F(1)=1 C F(0)=1 D F(n)=n,參考答案,B,6-2,函數(shù)F(x, y)定義為 F(2, 1)的值是 . A 1 B 2 C 3 D 4,參考答案,D,6-3,設(shè)有一個(gè)遞歸算法如下： int fact (int n) if (n=0) return 1; else return fact(n-1); 下面敘述正確的是 . A 計(jì)算fact(n)需要執(zhí)行n-1次遞歸調(diào)用 B fact(70)=5040 C 此遞歸算法最多只能

2、計(jì)算到fact(8) D 以上結(jié)論都不對(duì),參考答案,D,6-6,有如下遞歸函數(shù): double pow(double x, int n) if(n = 0) return 1.0; return x*pow(x,n-1); （1）函數(shù)pow(double x, int n)的功能是什么？思想是什么？ （2）執(zhí)行pow(2,5)的結(jié)果是什么，pow(2,5)執(zhí)行過(guò)程中發(fā)生了幾次遞歸調(diào)用？ （3）執(zhí)行pow(x,n)最多發(fā)生了幾次遞歸調(diào)用？,【分級(jí)提示】 （1）此遞歸函數(shù)返回x的n次方值。要計(jì)算x的n次方值，可以首先遞歸計(jì)算x的n-1次方值，然后再將所的結(jié)果與x相乘。當(dāng)n的值為0時(shí)，返回值為1，遞

3、歸終止； （2）執(zhí)行pow(2,5)的結(jié)果是32，pow(2,5)執(zhí)行過(guò)程中發(fā)生了5次遞歸調(diào)用； （3）執(zhí)行pow(x,n)最多發(fā)生了n次遞歸調(diào)用。,6-11,已知Ackerman函數(shù)定義如下： n+1 m=0 Ack(m,n)= Ack(m-1,1) m0,n=0 Ack(m-1,Ack(m,n-1) m 0,n 0 (1)寫(xiě)出計(jì)算Ackerman函數(shù)的遞歸算法； (2)使用一個(gè)數(shù)組，寫(xiě)出計(jì)算Ackerman函數(shù)的非遞歸算法； (3)根據(jù)非遞歸算法求出Ack(2,1)的值。,參考答案,遞歸算法 int Ack(int m,int n) if(m=0) return n+1; if(n=0)

4、return Ack(m-1,1); return Ack(m-1,Ack(m,n-1); ,參考答案,非遞歸算法（使用堆棧） 算法Ack(m,n) /*非遞歸方法求解Ackerman(m,n)*/ A1初始化 CREATS(s). S(m,n). A2非遞歸求解，堆棧模擬問(wèn)題分解 WHILE(NOT StackEmpty(s) DO( (mt,nt) S; IF(mt=0) THEN(x nt+1. IF(StackEmpty(s)THEN RTURN x. ELSE ( (mt,nt) S. S(mt,x).). ELSEIF(nt=0) THEN S(mt-1,1). ELSE (S(m

5、t-1,0). S(mt,nt-1).) ). ,參考答案,非遞歸算法（使用堆棧） int Ack(int m,int n) int mmMAXS,nnMAXS,top=-1,mt,nt,x; top+,mmtop=m,nntop=n; while(top=0) mt=mmtop,nt=nntop,top-; if(mt=0) x=nt+1; if(top=0) nntop=x;else return x; else if(nt=0) top+,mmtop=mt-1,nntop=1; else top+,mmtop=mt-1; top+,mmtop=mt,nntop=nt-1; ,參考答案,非遞歸求Ack(2,1),非遞歸求Ack(1,3),一種錯(cuò)誤的做法,非遞歸算法 int Ack(int m,int n) for(int i=0;i=n;i+) a0i=i+1; for(i=1;i=m;i+) ai0=ai-11; for(j=1;j=m;j+) aij=ai-1aij-1; return amn; ,非遞歸求Ack(2,1),6-12,