數(shù)據(jù)結構課后答案

6.4補考練習題及參考答案6.4.1單項選擇題1.遞歸函數(shù)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.遞歸函數(shù)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.樹答：遞歸計算過程是：先進行遞歸分解，知道遞歸出口為止，然后根據(jù)遞歸出口的結果反過來求值。這樣通常需要后面的遞推式先計算出結果，這正好滿足棧的特點。所以本題答案為B。6.4.2填空題1.將h，轉化成遞歸函數(shù)，其遞歸出口是―①，遞歸體是―②—答：①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()函數(shù)將給定的參數(shù)逆轉。本題答案為：285.6.4.3判斷題判斷以下敘述的正確性。任何遞歸算法都有遞歸出口。遞歸算法的執(zhí)行效率比功能相同的非遞歸算法的執(zhí)行效率高。遞歸算法不能轉換成對應的非遞歸算法。答：(1)正確。錯誤。通常情況下遞歸算法的執(zhí)行效率比功能相同的非遞歸算法的執(zhí)行效率低。錯誤?？梢杂脳⑦f歸算法轉換成對應的非遞歸算法。6.4.3簡答題設a是含有n個元素的整數(shù)數(shù)組。寫出求n個整數(shù)之和的遞歸定義。寫出求n個整數(shù)之積的遞歸定義。答：假定數(shù)組a的下標從0開始。設f(a,i)返回a[0]?a[i-1]元素之和。當i=1,f(a,1)=a[0];假設數(shù)組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個整數(shù)之和=f(a,n)。設f(a,i)返回a[0]?a[i-1]元素之積。當i=1,f(a,1)=a[0];假設數(shù)組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個整數(shù)之積=f(a,n)。以下算法是計算兩個正整數(shù)u和v最大公因數(shù)的遞歸函數(shù)，給出其遞歸模型。intgcd(intu,intv){intr;if((r=u%v)==0)return(v);elsereturn(gcd(u,r));}答：由上述函數(shù)得到如下遞歸模型如下：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]交換位置；/*回復環(huán)境*/對應的算法如下: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];/*恢復環(huán)境*/str[i]=str[k];str[k]=temp;組合問題：從自然數(shù)1,2,...,n中任取r個數(shù)的所有組合。解：設comb(a,m,k)為從1?m中任取k個數(shù)的所有組合(每個組合放在數(shù)組a中)。當組合的第1個數(shù)字選定后，其后的數(shù)字是從余下的m-1個數(shù)中取k-1個數(shù)的組合。求解組合問題的遞歸模型如下：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)排成一行，開始位置為白色全部在左邊，黑色全部在右邊。移動棋子的規(guī)則是：每次必須同時移動相鄰兩個棋子，顏色不限，可以左移也可以右移到空位上去，但不能調換兩個棋子的左右位置。每次移動必須跳過若干個棋子(不能平移)，要求最后能夠移成黑白相間的一行棋子。解：n=4的求解過程下：初始狀態(tài)，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