数据结构（Java语言版）-习题及答案 第5章递归习题答案

第5章递归习题参考答案 一、单选题ABCD递归模型如下：=1n=n+nn>1ABCD.=0.=1C.=1.n=n递归模型如下：=1n=n+nn>1其中递归体是 。ABCD.ABCD.=1C.n=n+n.n=nABCDABCD线性表栈队列树ABCD函数x，y定义如下：n=n+n+1当n>1n=1否则则ABCD10151620ABCD函数x，y定义如下：x，y=x，y+x，y)当x>且y>0x，y=x+y否则则，ABCD1234某递归算法的执行时间的递推关系如下：n=1当n=时n=n/+1当n>时则该算法的时间复杂度为 。ABCABCDOgn)On)Ongn)

ABCD设有一个递归算法如下：ntunntn){fn<=)reurn;eereurnn*unn;}ABCD计算fun(n)需要执行n次递归.un=0C.此递归算法最多只能计算到un).ABCABCD栈队列树图ABCD递归模型为=，n=n+n（n>ABCD.=0.=1C.=1.n=nABCD递归模型为=，n=n+n（n>ABCD.=0.=1C.n=n+n.n=nABCABCD递归出口递归体递归出口和递归体以上都不包含ABCD函数xy定义如下：xy=xy+xy)当x>且y>0xy=x+y否则则ABCD1234ABCD函数xy定义如下：n=n+n+1当n>1n=1否则则ABCD10151620ABCD某递归算法的执行时间的递推关系如下：n=1当n=时n=n/+1当n>时ABCDO)Ogn)On)Ongn)某递归算法的执行时间的递推关系如下：n=1当n=时n=n/+1当n>时则该算法的时间复杂度为（）。ABCABCDOgn)On)Ongn)某递归算法的执行时间的递推关系如下：n=1当n=时n=n/+n当n>时则该算法的时间复杂度为（）。ABCABCDOgn)On)Ongn)

ABCABCD线性表栈队列树ABCABCD较快较慢相同无法比较ABCABCD一般而言，使用递归解决问题较使用循环解决问题需要定义更多的变量递归算法的执行效率相对较低递归算法的执行需要用到栈以上都是错误的二、编程题POJ1664—放苹果时间限制：1000ms，空间限制：10000K。[描述]输入格式：第一行是测试数据的数目（≤≤）。以下每行均包含两个整数和n，以空格分开，≤，n≤。输出格式：对输入的每组数据m和n，用一行输出相应的k。答：prtvu*;prtvuScnner;pubccsn{pubccntventntn)//求解算法{1;eem<n)reurnve;ee==n)reurnve+;eereurnven+venn;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;=nnexIn;he>){=nnexIn;n=nnexIn;Syeuprnnven;}}}OJ—分形问题时间限制：，空间限制：。[描述]问题描述：分形是某种技术意义上在所有尺度上自相似方式显示的物体或数值。物体不需要在所有尺度上都具有完全相同的结构，但在所有尺度上必须具有相同的结构“类型”XXXX如果用B(n-1)表示n-1级盒子分形，那么递归地定义n级盒子分形如下B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)你的任务是画出n级盒子分形。输入格式：输入包含几个测试用例。输入的每一行包含一个不大于7的正整数n，输入的最后一行是负整数-1，表示输入的结束。输出格式：对于每个测试用例，使用表示法输出框分形。请注意是一个大写字母。在每个测试用例后打印一行只有一个短划线。答：prtvu*;prtvuScnner;pubccsn{cntN=;cben]p=newbenNN;cn]p=;//的n次幂表cvdventxntyntn) //求解算法{n==){pxy=rue;return;}vexyn; //递归绘制左上角的图形vexy+*pnn; //递归绘制右上角的图形vex+pny+pnn;//递归绘制中间的图形vex+*pnyn; //递归绘制左下角的图形vex+*pny+*pnn;//递归绘制右下角的图形}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;herue){n=nnexIn;fn==)rnt=;i<N;++)//p初始化rnt=;j<N;++)p=e;ven;rnt=;i<=pn;++){rnt=;j<=pn;++)p)Syeuprn"";eeSyeuprn"";Syeuprnn;}Syeuprnn"";}}}.：2000ms，空间限制：65536K8号了，但是对于学校财务处的工作人员来说，这一天则是很忙碌的一天，财务处的小胡老师最近就在考虑一个问题：如果每个老师的工资额都知道，最少需要准备多少张人民币，才能在给每位老师发工资的时候都不用老师找零呢？这里假设老师的工资都是正整数，单位元，人民币一共有100元、50元、10元、5元、2元和1n（n<100），表示老师的人数，然后是n个老师的工资。n=0表示输入的结束，不做处理。输出格式：对于每个测试实例输出一个整数x，表示至少需要准备的人民币张数。每个输出占一行。答：prtvu*;prtvuScnner;pubccsn{cntN=;cnt]=newnN;cnt]b=;pubccntgecunntx)//求解算法{x==)0;x>=)reurn+gecunx;eex>=0&x<)reurn+gecunx;eex<0&x>=)reurn+gecunx;eex<0&x>=)reurn+gecunx;eex<5&x>=)reurn+gecunx;ee //n=1reurn+gecunx;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;ntherue){n=nnexIn;n==)brek;rnt=;i<n;++)=nnexIn;u=;rnt=;j<n;++)u+=gecun;Syeuprnnu;}}}.HDU2013蟠桃记问题时间限制：2000ms，空间限制：65536K。[描述]问题描述：喜欢西游记的同学肯定都知道悟空偷吃蟠桃的故事，你们一定都觉得这猴子太闹腾了，其实你们是有所不知：悟空是在研究一个数学问题！什么问题？他研究的问题是蟠桃一共有多少个！不过，到最后他还是没能解决这个难题。当时的情况是这样的：第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多n（1<n<30），表示只剩下一个桃子的时候是在第n式：对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。答：prtvuScnner;pubccsn{pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntnn;henhNex){n=nnexIn;n=;n--;hen=)n=n+*;Syeuprnnn;}}}.H—汉诺塔问题时间限制：，空间限制：。描述问题描述：n个盘子的汉诺塔问题的最少移动次数是^n，即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱子从下往上的大小仍保持如下关系：n=+p+q>>…>mb>b>…>bpc>c>…>cq其中是柱上的盘的盘号系列，b是柱上的盘的盘号系列，ci是C柱上的盘的盘号系列，最初目标是将A柱上的n个盘子移到C盘。给出一个系列，判断它是否是在正确的移动中产生的系列。例，n=33//柱上只有盘号的盘2//柱上只有盘号的盘1//C柱上只有盘号的盘是正确的。而例，n=33//柱上只有盘号的盘1//柱上只有盘号的盘2//C柱上只有盘号的盘是不正确的。注：对于例如果目标是将柱上的n个盘子移到盘，则是正确的。输入格式：包含多组数据，首先输入t，表示有t组数据，每组数据4行，第1行n是盘子的数目n≤64，后3ma1a2ampb1b2bpqc1c2…cqn=+p+q，≤≤n，≤p≤n，≤q≤n。输出格式：对于每组数据，判断它是否是在正确的移动中产生的系列，正确输出rue，否则e。答：prtvu*;prtvuScnner;pubccsn{cntN=;cntp=newnN;cn]n=newn;cbenhnntnntntbntc){n==) //returntrue;pn==n)//当盘子n在上时，下面该判断盘子n是否在或上{n++;reurnhnncb;}eepcnc==n)//当盘子n在C上时，下面该判断盘子n是否在或C上{nc++;reurnhnnbc;}eereurne; //其他情况返回e}pubccvdnSrng]rg){Scnnern=newScnnerSyen;nt;=nnexIn;he>){ntnpq;rnt=;i<;++)//p初始化rnt=;j<N;++)p=;rnt=;i<;++)//n初始化n=;n=nnexIn;=nnexIn;rnt=;i<;++)p=nnexIn;p=nnexIn;rnt=;i<p;++)p=nnexIn;q=nnexIn;rnt=;i<q;++)p=nnexIn;hnn//初始个塔对应到2Syeuprnn"rue";eeSyeuprnn"e";}}}OJ—字母旋转游戏限制时间：，限制空间：。问题描述：：给定两个整数，n，生成一个×n的矩阵，矩阵中元素取值为至的个字母中的一个，在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过时又从开始填充。例如，当=，n=时，矩阵中的内容如图所示。输入格式：m为行数，n为列数，其中m，n都为大于0的整数。输出格式：分行输出相应的结果问题描述：：给定两个整数，n，生成一个×n的矩阵，矩阵中元素取值为至的个字母中的一个，在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过时又从开始填充。例如，当=，n=时，矩阵中的内容如图所示。n为列数，其中m，n都为大于0答：prtvuScnner;pubccsn{cnt=;cntN=;cchr]=newchrN;cntn;cntr=;pubccvdCreentxntyntntn)//递归创建矩阵{fm<=0||n<=) //递归结束条件return;f==1&n>) //矩阵只有第y行的n个元素{rnt=x;j<=x+n;++){y=chrn+r%;r++;}return;}f>0&n==) //矩阵只有第x列的个元素{rnt=y;i<=y+;++){x=chrn+r%;r++;}return;}rnt=x;j{y=chrn+r%;;r++;}rnt=y;i{x+n=chrn+r%;;r++;}rnt=x+n;>x;) //下一行{y+=chrn+r%;r++;}rnt=y+;>y;) //左一列{x=chrn+r%;r++;}Creex+y+n; //递归调用}pubccvdp //输出螺旋矩阵{rnt=;i{rnt=;jSyeuprn""+;Syeuprnn;}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;m=nnexIn;n=nnexIn;Creen;p;}}三、简答题什么是递归，递归有哪些形式？ 答：在定义一个函数时出现调用本函数的成分，称为递归。递归分为直接递归和间接递归两种形式。直接递归是指在函数在执行过程中调用本身。间接递归是指函数在执行过程中调用其它函数再经过这些函数调用本身。简述递归的特点。 答：递归的特点是它既有递堆过程，又有求值（回归）过程，而且在任何一个深度时，它的所有变量和参数的值都保存着，同一变量或参数在不同深度的值，都压入系统栈中。简述递归算法的优缺点。 答：递归算法优点是结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。递归算法的缺点是算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。推导出求x的n次幂的递归模型。 答：xn=x当n=时xn=n*xn)当n>时某递归算法求解时间复杂度的递推式如下：n=1当n=0n=n+n+3当n>0求该算法的时间复杂度。 答：四、填空题将递归算法转换为非递归算法时，通常使用这种数据结构。 答：栈递推式=，n=n+n的解是。 答：n(n-1)/2递推式=，n=n/+的解是。 答：设a是一个含有n个整数的数组，求该数组最大元素的递归定义是。 答：=，=}（≥）设a是一个含有n个整数的数组，求该数组最小元素的递归定义是。 答：=，=IN（≥）设a是一个含有n个整数的数组，求该数组所有元素之和的递归定义是。 答：=，=+)（≥）