東南大學(xué)十套數(shù)據(jù)結(jié)構(gòu)試題及答案.doc

《東南大學(xué)十套數(shù)據(jù)結(jié)構(gòu)試題及答案.doc》由會員分享，可在線閱讀，更多相關(guān)《東南大學(xué)十套數(shù)據(jù)結(jié)構(gòu)試題及答案.doc（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

數(shù)據(jù)結(jié)構(gòu)試卷（一） 三、計算題（每題 6 分，共24分） 1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2. 請畫出下圖的鄰接矩陣和鄰接表。 3. 已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。 四、閱讀算法（每題7分，共14分） 1. LinkList mynote(LinkList L) {//L是不帶頭結(jié)點的單鏈表的頭指針 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。 2. void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout<data<< ; } } 該算法的功能是： 五、算法填空（共8分） 二叉搜索樹的查找——遞歸算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失敗 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(itemdata) return Find(______________,item); else return Find(_______________,item); }//if } 六、編寫算法（共8分） 統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。 int CountX(LNode* HL,ElemType x) 數(shù)據(jù)結(jié)構(gòu)試卷（二） 三、應(yīng)用題(36分) 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）。 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。 5． 設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。 四、算法設(shè)計題(16分) 1． 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。 2． 設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。 數(shù)據(jù)結(jié)構(gòu)試卷（三） 二．填空題 1. 下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。 struct record{int key; int others;}; int hashsqsearch(struct record hashtable[ ],int k) { int i,j; j=i=k % p; while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1); } 2. 下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。 typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) { if (t==0 ) return(0);else while (t!=0) if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; } 三、計算題(每題10分，共30分) 1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。 2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）= K mod 7，若發(fā)生沖突采用線性探查法處理，試： （1）計算出每一個元素的散列地址并在下圖中填寫出散列表： ` 0 1 2 3 4 5 6 （2）求出在查找每一個元素概率相等情況下的平均查找長度。 3．已知序列（10，18，4，3，6，12，1，9，18，8）請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。 四、算法設(shè)計題(每題15分，共30分) 1． 設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。 2． 設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。 數(shù)據(jù)結(jié)構(gòu)試卷（四） 1． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。 2． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。 3． 設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是______________________。 4． 設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。 5． 設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。 6． 設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。 typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) { int i,k; lklist *s; for(i=0;ikey=a[i]; k=a[i] % p; s->next=hashtable[k];_______________________; } } 三、計算題(每題10分，共30分) 1、畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲結(jié)構(gòu)。 2、下圖所示的森林： (1) 求樹（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹； 3、設(shè)散列表的地址范圍是[ 0..9 ]，散列函數(shù)為H（key）= （key 2 +2）MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。 四、算法設(shè)計題(每題10分，共30分) 1． 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。 2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。 3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。 數(shù)據(jù)結(jié)構(gòu)試卷（五） 1. 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。 void bubble(int r[n]) { for(i=1;i<=n-1; i++) { for(exchange=0,j=0; j<_____________;j++) if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if (exchange==0) return； } } 2. 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { ________________________________; if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1; } return(0); } 三、應(yīng)用題(32分) 1. 設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。 2. 設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。 3. 設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。 4. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。 四、算法設(shè)計題(28分) 1． 設(shè)計判斷兩個二叉樹是否相同的算法。 2． 設(shè)計兩個有序單鏈表的合并排序算法。 數(shù)據(jù)結(jié)構(gòu)試卷（六） 四、算法設(shè)計題(20分) １． 設(shè)計在順序有序表中實現(xiàn)二分查找的算法。 ２． 設(shè)計判斷二叉樹是否為二叉排序樹的算法。 ３． 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法 數(shù)據(jù)結(jié)構(gòu)試卷（七） 三、填空題(30分) 1. 下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。 struct record {int key;datatype others;}; void quickpass(struct record r[], int s, int t, int &i) { int j=t; struct record x=r[s]; i=s; while(ix.key) j=j-1; if (idata=k;t->lchild=t->rchild=0;} else if (t->data>k) bstinsert(t->lchild,k);else__________________________; } 3． 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next; _________________;。 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。 6． 完全二叉樹中第5層上最少有__________個結(jié)點，最多有_________個結(jié)點。 7． 設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 9． 設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有___________條邊。 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 四、算法設(shè)計題(20分) 1. 設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。 2. 設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。 數(shù)據(jù)結(jié)構(gòu)試卷（九） 五、算法設(shè)計題(20分) 1． 設(shè)計計算二叉樹中所有結(jié)點值之和的算法。 2． 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。 3． 設(shè)計判斷單鏈表中元素是否是遞增的算法。 數(shù)據(jù)結(jié)構(gòu)試卷（十） 二、填空題(48分，其中最后兩小題各6分) 1. 設(shè)指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為： q=p->next；p->data=q->data；p->next=___________；feee(q)； 2. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。 3. 設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為_________；用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為_________。 4. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k % 7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是________。 5. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。 6. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為______________________。 7. 設(shè)有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，則該圖的一個拓?fù)湫蛄袨開________________________。 8. 下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。 typedef struct node{int data;struct node *lchild;________________;}bitree; void createbitree(bitree *&bt) { scanf(“%c”,&ch); if(ch==#) ___________;else { bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);} } 9. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。 typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ) { for (i=1;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;____________;} } } 三、算法設(shè)計題(22分) 1． 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。 2． 設(shè)計在二叉排序樹上查找結(jié)點X的算法。 3． 設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。 數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案 三、計算題（每題6分，共24分） 1. 線性表為：（78，50，40，60，34，90） 2. 鄰接矩陣： 鄰接表如圖11所示： 圖11 3. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 見圖12 4 4 4 4 4 2 2 2 5 5 2 8 5 2 8 3 4 5 2 8 4 3 圖12 四、 讀算法（每題7分，共14分） 1. （1）查詢鏈表的尾結(jié)點 （2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹? 五、 法填空（每空2分，共8 分） true BST->left BST->right 六、 編寫算法（8分） int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i為計數(shù)器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循環(huán)時i中的值即為x結(jié)點個數(shù) return i; }//CountX 數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案 三、應(yīng)用題 1. (22，40，45，48，80，78)，(40，45，48，80，22，78) 2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略 5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6. 略 四、算法設(shè)計題 1. 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。 void quickpass(int r[], int s, int t) { int i=s, j=t, x=r[s]; while(ix) j=j-1; if (inext) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案 二．填空題 13.j+1，hashtable[j].key==k 14.return(t)，t=t->rchild 三、計算題 1． 2、H(36)=36 mod 7=1; H１(22)=(1+1) mod 7=2; ….沖突 H(15)=15 mod 7=1;….沖突 H2(22)=(2+1) mod 7=3; H１(15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1; ….沖突 （1） 0 1 2 3 4 5 6 63 36 15 22 40 （2）ASL= 3、(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法設(shè)計題 1. 設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 2. 設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf("not found x\n"); else if (i<=r) printf("%c",bt->data); else printf("not parent");} 數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案 二、填空題 1. (19，18，16，20，30，22) 2. (16，18，19，20，32，22) 3. A[i][j]=1 4. 等于 5. BDCA 6. hashtable[i]=0，hashtable[k]=s 三、計算題 1． 2． (1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹； 3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6 四、算法設(shè)計題 1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。 typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>=A && p->data<=Z) {p->next=ha; ha=p;} else if (p->data>=0 && p->data<=9) {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。 typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; } 3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。 #define n 10 typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) { if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); } void createbsttree(bitree *&bt) { int i; for(i=1;i<=n;i++) bstinsert(bt,random(100)); } 數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案 二、填空題 1. n-i，r[j+1]=r[j] 2. mid=(low+high)/2，r[mid].key>k 三、應(yīng)用題 2. DEBCA 3. E={(1,5),(5,2),(5,3),(3,4)},W=10 4. ASL=(1*1+2*2+3*4)/7=17/7 5. ASL1=7/6，ASL2=4/3 四、算法設(shè)計題 1. 設(shè)計判斷兩個二叉樹是否相同的算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) { if (bt1==0 && bt2==0) return(1); else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 2. 設(shè)計兩個有序單鏈表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; } 數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案 四、算法設(shè)計題 1. 設(shè)計在順序有序表中實現(xiàn)二分查找的算法。 struct record {int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { mid=(low+high)/2; if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; } return(0); } 2. 設(shè)計判斷二叉樹是否為二叉排序樹的算法。 int minnum=-32768,flag=1; typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);} } 3. 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計直接插入排序算法 void straightinsertsort(lklist *&head) { lklist *s,*p,*q; int t; if (head==0 || head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next) { for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p; else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;} } }  數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案 三．填空題 1. inext==0) return; for(q=head; q!=0;q=q->next) { min=q->data; s=q; for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } } 2. 設(shè)計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。 void substring(char s[ ], long start, long count, char t[ ]) { long i,j,length=strlen(s); if (start<1 || start>length) printf("The copy position is wrong"); else if (start+count-1>length) printf("Too characters to be copied"); else { for(i=start-1,j=0; ikey==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);} } 數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案 三、填空題 1. (49，13，27，50，76，38，65，97) 2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k) 3. p->next=s 4. head->rlink，p->llink 5. CABD 6. 1，16 7. 0 8. (13，27，38，50，76，49，65，97) 9. n-1 10. 50 四、算法設(shè)計題 1. 設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。 void countnode(bitree *bt,int &count) { if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} } 2. 設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。 typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) { int i,j; glinklistnode *p; for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) { p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p;} } 數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案 四、算法設(shè)計題 1． 設(shè)計計算二叉樹中所有結(jié)點值之和的算法。 void sum(bitree *bt,int &s) { if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} } 2． 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。 void quickpass(int r[], int s, int t) { int i=s,j=t,x=r[s]; while(inext==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1);} 數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案 二、填空題 1. q->next 2. 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu) 3. O(n2)， O(n+e) 4. 8/3 5. (38，13，27，10，65，76，97) 6. (10，13，27，76，65，97，38) 7. 124653 8. struct node *rchild，bt=0，createbitree(bt->lchild) 9. lklist，q=p 三、算法設(shè)計題 1. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; } 2. 設(shè)計在二叉排序樹上查找結(jié)點X的算法。 bitree *bstsearch1(bitree *t, int key) { bitree *p=t; while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild; return(0); } 3. 設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。 void adjustheap(int r[ ],int n) { int j=n,i=j/2,temp=r[j-1]; while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp; }