资源描述：
《数据结构习题课6.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构习题第6章吉林大学计算机科学与技术学院谷方明6-1递归函数F(n)=F(n-1)+n+1(n>1)的递归终止条件是.[A]F(0)=0[B]F(1)=1[C]F(0)=1[D]F(n)=n参考答案B6-2函数F(x,y)定义为F(2,1)的值是.[A]1[B]2[C]3[D]4参考答案D6-3设有一个递归算法如下：intfact(intn){if(n<=0)return1;elsereturnfact(n-1);}下面叙述正确的是.[A]计算fact(n)需要执行n-1次递归调用[B]fact
2、(70)=5040[C]此递归算法最多只能计算到fact(8)[D]以上结论都不对参考答案D6-6有如下递归函数:doublepow(doublex,intn){if(n==0)return1.0;returnx*pow(x,n-1);}（1）函数pow(doublex,intn)的功能是什么？思想是什么？（2）执行pow(2,5)的结果是什么，pow(2,5)执行过程中发生了几次递归调用？（3）执行pow(x,n)最多发生了几次递归调用？【分级提示】（1）此递归函数返回x的n次方值。要计算x的n次方
3、值，可以首先递归计算x的n-1次方值，然后再将所的结果与x相乘。当n的值为0时，返回值为1，递归终止；（2）执行pow(2,5)的结果是32，pow(2,5)执行过程中发生了5次递归调用；（3）执行pow(x,n)最多发生了n次递归调用。6-11已知Ackerman函数定义如下：n+1m=0Ack(m,n)=Ack(m-1,1)m≠0,n=0Ack(m-1,Ack(m,n-1))m≠0,n≠0(1)写出计算Ackerman函数的递归算法；(2)使用一个数组，写出计算Ackerman函数的非递归算法；(
4、3)根据非递归算法求出Ack(2,1)的值。参考答案递归算法intAck(intm,intn){if(m=0)returnn+1;if(n=0)returnAck(m-1,1);returnAck(m-1,Ack(m,n-1));}参考答案非递归算法（使用堆栈）算法Ack(m,n)/*非递归方法求解Ackerman(m,n)*/A1[初始化]CREATS(s).S(m,n).A2[非递归求解，堆栈模拟问题分解]WHILE(NOTStackEmpty(s))DO((mt,nt)S;IF(mt=0)T
5、HEN(x←nt+1.IF(StackEmpty(s)THENRTURNx.ELSE((mt,nt)S.S(mt,x).)).ELSEIF(nt=0)THENS(mt-1,1).ELSE(S(mt-1,0).S(mt,nt-1).)).▌参考答案非递归算法（使用堆栈）intAck(intm,intn){intmm[MAXS],nn[MAXS],top=-1,mt,nt,x;top++,mm[top]=m,nn[top]=n;while(top>=0){mt=mm[top],nt=nn[top
6、],top--;if(mt==0){x=nt+1;if(top>=0)nn[top]=x;elsereturnx;}elseif(nt==0)top++,mm[top]=mt-1,nn[top]=1;else{top++,mm[top]=mt-1;top++,mm[top]=mt,nn[top]=nt-1;}}}参考答案非递归求Ack(2,1)(2,1)(2,0)(1,x)(1,1)(1,x)(1,0)(0,y)(1,x)(0,1)(0,y)(1,x)(0,2)(1,x)(1,3)非递归求Ack(1,
7、3)(1,2)(0,x)(1,1)(0,y)(0,x)(1,0)(0,z)(0,y)(0,x)(0,1)(0,z)(0,y)(0,x)(0,2)(0,y)(0,x)(0,3)(0,x)(0,4)一种错误的做法非递归算法intAck(intm,intn){for(inti=0;i<=n;i++)a[0][i]=i+1;for(i=1;i<=m;i++){a[i][0]=a[i-1][1];for(j=1;j<=m;j++)a[i][j]=a[i-1][a[i][j-1]];}returna[m][n];
8、}非递归求Ack(2,1)i=0i=1i=2j=0123j=1235j=234j=345j=456-12根据例6.4和例6.5，(1)给出HR（3，1，2，3）递归算法的移动过程；(2)以HI（3，1，2，3）为例，给出堆栈的变化过程。【提示】参考例6.4和例6.5
