数据结构课后答案

6.4补考练习题及参考答案6.4.1单项选择题1.递归函数f(n)=f(n-1)+n(n>1)的递归出口是A.f⑴=1B.f⑴=0C.f(0)=0D.f(n)=n答：当n=0时，f⑴=0。本题答案为B。2.递归函数f(n)=f(n-1)+n(n>1)的递归体是A.f(1)=1B.f(0)=0C.f(n)=f(n-1)+nD.f(n)=n答：递归体反映递归过程。本题答案为C。3.f(n)=占+上+…+1和司，递归模型为A.f(n)=-^-1x221+3.f(n)=占+上+…+1和司，递归模型为A.f(n)=-^-1x221++…+2x3nx(n—1)B.f(n)=1+—+...+——1—+f(n-1)1x22x3(n-1)xnC.f(1)=1f(n)=f(n-1)+/1A2nx(n-1)D.f(n)=f(n-1)+/1Anx(n一1)答：递归模型由两部分组成，一是递归出口，另一是递归体，上述选项中只有C符合条件。本答案为C。4.将递归算法转换成对应的非递归算法时，通常需要使用保存中间结果。A.队列B.栈C.链表D.树答：递归计算过程是：先进行递归分解，知道递归出口为止，然后根据递归出口的结果反过来求值。这样通常需要后面的递推式先计算出结果，这正好满足栈的特点。所以本题答案为B。6.4.2填空题1.将h，转化成递归函数，其递归出口是―①，递归体是―②—答：①f(1)=0②f(n)=f(n-1)+inti;if(w!=1){print(wT);for(i=1;i<=w;i++)printf(“%3d”,w);printf("\n”)；}}调用语句print(4)的结果是。答：1223334444有如下递归过程：voidreverse(intm){printf("％d”,n%100);if(n/10!=0)reverse(n/10);}调用语句reverse(582)的结果是。答：reverse()函数将给定的参数逆转。本题答案为：285.6.4.3判断题判断以下叙述的正确性。任何递归算法都有递归出口。递归算法的执行效率比功能相同的非递归算法的执行效率高。递归算法不能转换成对应的非递归算法。答：(1)正确。错误。通常情况下递归算法的执行效率比功能相同的非递归算法的执行效率低。错误。可以用栈将递归算法转换成对应的非递归算法。6.4.3简答题设a是含有n个元素的整数数组。写出求n个整数之和的递归定义。写出求n个整数之积的递归定义。答：假定数组a的下标从0开始。设f(a,i)返回a[0]〜a[i-1]元素之和。当i=1,f(a,1)=a[0];假设数组a的前i-1个元素之和已经求出，即已知f(a,i-1),则f(a,i)=f(a,i-1)xa[i-1],所以得到以下递归定义：f(a,1)=a[0]f(a,i)=f(a,i-1)+a[i-1]a中n个整数之和=f(a,n)。设f(a,i)返回a[0]〜a[i-1]元素之积。当i=1,f(a,1)=a[0];假设数组a的前i-1个元素之积已经求出，即已知f(a,i-1),则f(a,i)=f(a,i-1)xa[i-1],所以得到以下递归定义：f(a,1)=a[0]f(a,i)=f(a,i-1)xa[i-1]a中n个整数之积=f(a,n)。以下算法是计算两个正整数u和v最大公因数的递归函数，给出其递归模型。intgcd(intu,intv){intr;if((r=u%v)==0)return(v);elsereturn(gcd(u,r));}答：由上述函数得到如下递归模型如下：gcd(u,v)=v当u%v=0时gcd(u,v)=gcd(u,u%v)其他情况6.4.4算法设计题编写一个递归过程，它读入一串任意长的字符串，该串字符以“.”作为结束，要求打印出它们的倒序字符串。解：首先获取用户按键，如果不是.字符，则递归调用该过程，否则显示该字符。对应的算法如下：voidreverse()charch;scanf("％c”，&ch);if(ch!=‘.’){reverse();printf("％c”,ch);}}全排列问题：输An个不同的字符，给出它们所有的n个字符的全排列。解：将n个不同的字符存放在字符串str中，求解全排列问题的递归模型如下:perm(str,k,n):输出产生的解若k=n-1perm(str,k,n):对于k〜n-1的i,str[i]与str[k]交换位置；其他情况perm(str,k+1,n);将str[k]与str[i]交换位置；/*回复环境*/对应的算法如下:voidprint(charstr[],intn)/*输出一个排列*/{for(inti=0;i<n;i++)printf("％c”，str[i]);printf("\n”);}voidperm(charstr[],intk,intn)inti;chartemp;if(k==n-1)print(str,n);else{for(i=k;i<n;i++){temp=str[k];/*交换str[k]与str[i]*/str[k]=str[i];str[i]=temp;perm(str,k+1,n);temp=str[i];/*恢复环境*/str[i]=str[k];str[k]=temp;组合问题：从自然数1,2,...,n中任取r个数的所有组合。解：设comb(a,m,k)为从1〜m中任取k个数的所有组合(每个组合放在数组a中)。当组合的第1个数字选定后，其后的数字是从余下的m-1个数中取k-1个数的组合。求解组合问题的递归模型如下：comb(a,m,k):输出产生的解若k=1comb(a,m,k):对于k〜m的i,a[k-1]=i;其他情况comb(a,i-1,k-1);对应的算法如下：intn,r;/*全局变量*/voidprint(inta[])/*输出一个组合*/{intj；for(j=r-1;j>=0;j--)printf("％d”，a[j]);printf("\n”)}voidcomb(inta[],intm,intk){inti;for(i=m;i>=k;i--){a[k-1]=i;if(k>1)comb(a,i-1,k-1);elseprint(a);}}Voidmain(){Inta[Maxsize];Printf(“输入n,r(r<=n):”)；Scanf(“％d,%d”，&n,&r);Printf(“输出结果:\n”);Comb(a,n,r);prinf("\n”);}棋子移动问题：有2n个棋子(n>=4)排成一行，开始位置为白色全部在左边，黑色全部在右边。移动棋子的规则是：每次必须同时移动相邻两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移)，要求最后能够移成黑白相间的一行棋子。解：n=4的求解过程下：初始状态，ooooeeee一一第1步Iooo——•••oe第2步：ooo»o««--•第3步]o--•◦••ooe第4步'o・o・o第5步，——o・o・o・o・设mv(n)表示求解2n个棋子移动的问题，则棋子移动问题求解的递归模型如下:mv(n):直接求解mv(n):将c[n]、c[n+1]棋子对移动到c[2n+1]、c[2n+2]处即mv(n);其他情况将c[2n-1]、c[2n]棋子对移动到c[n]、c[n+1]处即mv(2n-1);mv(n-1);对应的算法如下：#include<stdio.h>#include<string.h>constintMAX=100;charc[MAX][3]；intst=0,sp,n;voidprintf(){printf("step%-2d”，++st);for(inti=1;i<=2*n+2;i++)printf("％s”,c[i]);printf("\n”)}voidmvtosp(intk){for(intj=0;j<=1;j++){strcpy(c[sp+j],c[k+j]);strcpy(c[k+j],”一“}sp=k;print();}voidmv(intn){intist=0sp=2*n+1for(i=1;i<=n;i++)strcpy(c[i],”。”)；for(i=n+1;i<=2*n;i++)strcpy(c