中國科學院研究生院軟件學院大連教學點中國科學院研究生院軟件學院大連教學點中國科學院研究生院軟件學院大連教學點中國科學院研究生院軟件學院大連教學點--PAGE3---PAGE4-《計算機算法設計與分析》試卷 考試時間120分鐘2002年-2003年第二學期學號 姓名 成績一、闡述題請說明算法的五個基本特性，并進行簡要的分析(5答：算法的五個基本特性如下：相當清楚的、無二義性的。原理上能由人用紙和筆在有限時間內完成。0對象集合。④輸出一個算法產生一個或多個輸出，這些輸出是同輸人有某種特定關系的量。完成。這里的有窮的概念不是純數學的，而是在實際上是合理的，可以接受的。做計算過程。若森林非空，請按照森林和樹相互遞歸的定義，闡述森林的兩種遍歷的方法。(10m(m≥0)合即為森林。所以，森林和樹是可以相互遞歸定義的。F=(T，T，…，TTF1 2 m 1

T

構成的森林。于是，可得到森林的兩種遍歷算法。1 2 m①先序遍歷森林若森林非空，則可按下述規則遍歷這個森林：訪問樹中第一棵樹的根結點；先序遍歷第一棵中根結點的所有子樹構成的森林；先序遍歷除去第一棵樹外剩下的樹構成的森林。②中序遍歷森林若森林非空，則可按下述規則遍歷這個森林：中序遍歷第一棵中根結點的所有子樹構成的森林；訪問樹中第一棵樹的根結點；二、計算題考慮下列三個函數 (5分)n2， nf(n)=

n ， 0≤n≤100(n)=

(n)=n1.51 n3， n為正偶數 ， 2 n2， n＞100 ， 3 ，3О(i,j)，Ω(i,j)。其中，О(i,j)，Ω(i,j)的定義分別如下：Y，f(n)=О

(n))

(n)=Ω

(n))О(i,j)= i

j Ω(i,j)= i

j 1≤i,j≤3N，else ； N，else ， 。請將答案填寫在下面的方框中。О(i,j) f f fYNYNNYYNYYYf1f2f3

Ω(i,j) f f fYYYYYNYYNNYf1f2f3設和M=35，使用過程SumOfSub找出W中使得和數等M的全部子集并畫出所生成的部分狀態空間樹。 (5分)答：sX(i)的取值為左分枝取‘1‘0’)，k是結點的層次號)，r界函數是B(X(1)，…，X(k))=true當且僅當kn k∑W(i)X(i)+∑W(i)≥M且∑W(i)X(i)+W(k+1)≤Mi=1 i=k+1 i=1n定義s=∑W(i)X(i)；r=∑W(i)i=1 i=k使用過程SumOfSub找出W中使得和數等于M的全部子集的部分狀態空間樹如下：0,1,87X(1)=10,1,875,2,820,2,825,2,820,2,8212,3,755,3,757,3,750,3,7512,3,755,3,757,3,750,3,750,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,3,650,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,4,500,1,870,1,870,1,870,1,870,1,870,1,870,1,870,1,870,1,870,1,870,1,870,1,870,1,87三、證明題 在已知根R(i,j)（0≤i＜j≤n）的情況下寫一個構造最優二分檢索樹T的算法證明這樣的樹能在О(n)時間內構造出來。 (10分)答：R(i,j)（0≤i＜j≤n）中記錄的是構造最優二分檢索樹T成本的k值。

時滿足最小根據最優二分檢索樹的定義知道n（無重復。T

{a，a，

}，而則a的右ijk+1

Kk+2

},且當i=j時，Tj

點k-1 K根據上述思路，可依據如下算法構造一棵最優二分檢索樹。采用二叉鏈表作為存儲結構，結點的定義如下：typedefstructOBSTNode{char data; //標識符類型，可以是字符串struct OBSTNode *lchild,*rchild; //左右孩子結點的指針}OBSTNode,*OBSTreeVoid OBSTCreate(OBSTreeP,inti,intj) intk；OBSTreeS；if(i〈〉j){k=r[i][j]； //R[][]是全局變量new(S)； //產生一個新的結點,讓S指向該結S->data=a[k]； //數據A[]是全局變量If(!P){P=S}； //Else{if(S->data<P->data){ //新產生的結點是P結點的左孩P->lchild=S； P=S；}else { //新產生的結點是P結點的右孩P->rchild=S； P=S；}}；OBSTCreate(P,i,k-1)；OBSTCreate(P,k+1,j)；}}//OBSTCreatemainOBST0(OBSTree&T，intn){//數組A[]和R[][]是全局變if(n<1) returnerror；OBSTCreate(T,0,n)；}時間復雜度證明T(n)=T(k)+T(n-k)+c c為常數 0≤k≤n=…=(n+1)*T(0)+n*c因為T(0)=0所以T(n)=cn即，T(n)=○(n)證畢和為內部路徑長度，記為I；E。試證明：具有n個內部結點的這樣的判定樹，滿足E=I+2n。(10分)證明該等式不成立n3n+6n3=(n3n)。 (5分)四、算法題對于下表左部給定的算法，計算該算法的時間漸進復雜性。 (10分)語句boolBubble(elemTyoea[],intn){//a[0:n-1]中的最大元素冒泡至最后boolswapped=false;for(inti=0;i<n-1;i++){if(a[i]>a[i+1]){Swap(a[i],a[i+1]);swapped=true;//發生了交換

s/e 頻率 總步數};returnswapped;}voidBubbleSort(elemTyoea[],intn){//及時終止的冒泡排序算法for(inti=n;i>1&&Bubble(a,i);i--);}總計下面的算法是依據分治策略設計出來的仔細閱讀該算法思路在劃線處填寫適當的語句完成整個算法。 (15分)問題：編寫出函數reverse(s)的遞歸程序，使字符串s反序。i，jsi，ji1j1i≥j。#include<string.h>voidreverse(chars[]){voidreverser(chars[],inti,intreverser(s, ① ,strlen(s))；}voidreverser(chars[],inti,intlen){intc，j；j=②if(i<j)--PAGE5-中國科學院研究生院軟件學院大連教學點{c=s[i]；s[i]=s[j]；s[j]=c；reverser(s,++i,③)；}}分)voidABC(A，n) {//A(0:n)是一個一維數組，共有n個可比較值大小的元素；//且A(0)未存放元素；變量x是與A(i)同類型的數據元素。1 integeri,j；2 for(j=2；j<=n；j++){3 i=j-l；4 A[0]=A[j]；5 while(A[0]<A[i]) {6 x=A[i+1]；7 A[i+1]=A[i]；8 A[i]=x；9 i=i-1；10 }；//wh