6.4    补考练习题及参考答案
6.4.1  单项选择题
1.  递归函数的递归出口是_______。
A.  =1      B.  =0  C. =0        D. 
答：当n=0时，。本题答案为B。
2.  递归函数的递归体是________。
A.    B. C.   D. 
答：递归体反映递归过程。本题答案为C。
3.  ，递归模型为_____。
A. 
B.   
C.   
D. 
    答：递归模型由两部分组成，一是递归出口，另一是递归体，上述选项中只有C符合条件。本答案为C    。
4.将递归算法转换成对应的非递归算法时，通常需要使用________保存中间结果。
A.队列                B.栈                  C.链表                D.树
答：递归计算过程是：先进行递归分解，知道递归出口为止，然后根据递归出口的结果反过来求值。这样通常需要后面的递推式先计算出结果，这正好满足栈的特点。所以本题答案为B。
6.4.2填空题
1.将转化成递归函数，其递归出口是___①____,递归体是___②___
答：①数据结构与算法第二版课后题答案    ②
2.有如下递归过程：
void print(int w)
{
    int i;
    if (w!=1)
    { print(w-1);
        for(i=1;i<=w;i++)
            printf(“%3d”,w);
        printf(“\n”);
    }
}
调用语句print(4)的结果是________。
答：
    1
22
33  3
44  4  4
3.有如下递归过程：
void reverse(int m)
{  printf(“%d”,n%100);
    if (n/10!=0)
        reverse(n/10);
}
调用语句reverse(582)的结果是________。
答：reverse()函数将给定的参数逆转。本题答案为：285.
6.4.3    判断题
判断以下叙述的正确性。
（1）任何递归算法都有递归出口。
（2）递归算法的执行效率比功能相同的非递归算法的执行效率高。
（3）递归算法不能转换成对应的非递归算法。
答：（1）正确。
  （2）错误。通常情况下递归算法的执行效率比功能相同的非递归算法的执行效率低。
  （3）错误。可以用栈将递归算法转换成对应的非递归算法。
6.4.3简答题
1.设a是含有n个元素的整数数组。
（1）写出求n个整数之和的递归定义。
（2）写出求n个整数之积的递归定义。
答：假定数组a的下标从0开始。
（1）设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)a[i-1],所以得到以    下递归定义：
    f(a,1)=a[0]
    f(a,i)=f(a,i-1)+a[i-1]
a中n个整数之和=f(a,n)。
（2）设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)a[i-1],所以得到以    下递归定义：
    f(a,1)=a[0]
    f(a,i)=f(a,i-1)a[i-1]
a中n个整数之积=f(a,n)。
2.以下算法是计算两个正整数u和v最大公因数的递归函数，给出其递归模型。
int gcd(int u,int v)
{
    int r;
    if((r=u%v)==0)
        return(v);
    else
        return(gcd(u,r));
}
答：由上述函数得到如下递归模型如下：
gcd(u,v)=v                      当u%v=0时
gcd(u,v)= gcd(u, u%v)          其他情况
6.4.4算法设计题
1.编写一个递归过程，它读入一串任意长的字符串，该串字符以“.”作为结束，要求打印出它们的倒序字符串。
解：首先获取用户按键，如果不是.字符，则递归调用该过程，否则显示该字符。对应的算法
如下：
void reverse()
{
    char ch;
    scanf(“%c”,&ch);
    if(ch!=‘.’)
    {    reverse();
        printf(“%c”,ch);
    }
}
2.全排列问题：输入n个不同的字符，给出它们所有的n个字符的全排列。
解：将n个不同的字符存放在字符串str中，求解全排列问题的递归模型如下：
perm(str,k,n):输出产生的解                      若k=n-1
perm(str,k,n):对于k～n-1的i，str[i]与str[k]交换位置；其他情况
                perm(str,k+1,n);
                将str[k]与str[i]交换位置；/*回复环境*/
对应的算法如下：
void print(char str[],int n)    /*输出一个排列*/
{
    for(int i=0;i<n;i++)
        printf(“%c”,str[i]);
    printf(“\n”);
}
void perm(char str[],int k,int n)
{
    int i;
    char temp;
    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;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。