数据结构教程李春葆课后答案第5章递归.pdf

《数据结构教程李春葆课后答案第5章递归.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第5章递归教材中练习题及参考答案1.有以下递归函数：voidfun(intn){if(n==1)printf("a:%d",n);else{printf("b:%d",n);fun(n-1);printf("c:%d",n);}}分析调用fun(5)的输出结果。解：调用递归函数fun(5)时，先递推到递归出口，然后求值。这里的递归出口语句是printf("a:%d",n)，递推时执行的语句是printf("b:%d",n)，求值时执行的语句是printf("c:%d",n)。调用fun(5)的输出结果如下：

2、b:5b:4b:3b:2a:1c:2c:3c:4c:52.已知A[0..n-1]为整数数组，设计一个递归算法求这n个元素的平均值。解：设avg(A，i)返回A[0..i]共i+1个元素的平均值，则递归模型如下：avg(A，i)=A[0]当i=0avg(A，i)=(avg(A，i-1)*i+A[i])/(i+1)其他情况对应的递归算法如下：floatavg(intA[],inti){if(i==0)return(A[0]);elsereturn((avg(A,i-1)*i+A[i])/(i+1));}2数据结构教程学习指导求A[n]

3、中n个元素平均值的调用方式为：avg(A，n-1)。3.设计一个算法求正整数n的位数。解：设f(n)为整数n的位数，其递归模型如下：f(n)=1当n<10时f(n)=f(n/10)+1其他情况对应的递归算法如下：intfun(intn){if(n<10)return1;elsereturnfun(n/10)+1;}4.上楼可以一步上一阶，也可以一步上两阶。设计一个递归算法，计算共有多少种不同的走法。解：设f(n)表示n阶楼梯的不同的走法数，显然f(1)=1，f(2)=2（两阶有一步一步走和两步走2种走法）。f(n-1)表示n-1阶

4、楼梯的不同的走法数，f(n-2)表示n-2阶楼梯的不同的走法数，对于n阶楼梯，第1步上一阶有个f(n-1)种走法，第1步上两阶有个f(n-2)种走法，则f(n)=f(n-1)+f(n-2)。对应的递归算法如下：intfun(intn){if(n==1

5、

6、n==2)returnn;elsereturnfun(n-1)+fun(n-2);}5.设计一个递归算法，利用顺序串的基本运算求串s的逆串。解：经分析，求逆串的递归模型如下：f(s)=s若s=Φf(s)=Concat(f(SubStr(s，2，StrLength(s)-1))，Su

7、bStr(s，1，1))其他情况递归思路是：对于s=“s1s2„sn”的串，假设“s2s3„sn”已求出其逆串即f(SubStr(s，2，StrLength(s)-1))，再将s1（为SubStr(s，1，1)）单个字符构成的串连接到最后即得到s的逆串。对应的递归算法如下：#include"sqstring.cpp"//顺序串的基本运算算法SqStringinvert(SqStrings){SqStrings1,s2;if(StrLength(s)>0){s1=invert(SubStr(s,2,StrLength(s)-1));

8、s2=Concat(s1,SubStr(s,1,1));}elseStrCopy(s2,s);returns2;第5章递归3}6.设有一个不带表头结点的单链表L，设计一个递归算法count(L)求以L为首结点指针的单链表的结点个数。解：对应的递归算法如下：intcount(LinkNode*L){if(L==NULL)return0;elsereturncount(L->next)+1;}7.设有一个不带表头结点的单链表L，设计两个递归算法，traverse(L)正向输出单链表L的所有结点值，traverseR(L)反向输出单链表

9、L的所有结点值。解：对应的递归算法如下：voidtraverse(LinkNode*L){if(L==NULL)return;printf("%d",L->data);traverse(L->next);}voidtraverseR(LinkNode*L){if(L==NULL)return;traverseR(L->next);printf("%d",L->data);}8.设有一个不带表头结点的单链表L，设计两个递归算法，del(L，x)删除单链表L中第一个值为x的结点，delall(L，x)删除单链表L中所有值为x的结点。解

10、：对应的递归算法如下：voiddel(LinkNode*&L,ElemTypex){LinkNode*t;if(L==NULL)return;if(L->data==x){t=L;L=L->next;free(t);return;}del(L->n