2014數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案2014 年第一章-第五章參考答案1. n(n-1)/22.0(n)3.常數(shù)階 O(n) 4. C 5.A 6.C 7.D 8.A9. O(n) 10.B 11.C 12.A 13.A 14.B 15.C 16.L-next=NULL 17. P-prior-next=P -nextP- next - prior =P- prior18.B 19.C20.3 21.C 22.A 23.A 24.C 25. D 26.D27. I have a dream , ave 28. 6 29.A 30.D 31.(a,b) (c,() 32.B 33.C二、算法題入到程表序的功能：對

2、長度大于等于2的單鏈表，將首元結(jié)點插2. (1)棧中的數(shù)據(jù)元素逆置(2)如果棧中存在元素e,將其從棧中清除。3. 程序的運行結(jié)果：(1) chris (2) card4. -10題答案：.#defi ne OK 1#defi ne ERROR 0typedef int Status;typedef struct LNodeint data;struct LNode *n ext;LNode,*Li nkList;4. 題答案int Length(LinkList L) 求鏈表的長度k=0; p=L;while (p-n ext) p=p-n ext;k+;return k;/Le ngth5.

3、 題答案LNode* Locate(LinkList L, Elemtype x)/鏈表上的元素查找，返回 指針 p=L-n ext;while (p&p-data!=x)p=p-n ext;return p;/Locate6. 題答案Status ListDelete_L(Li nkList & L,i nt i,ElemType & e)/將線性表L中第i個數(shù) 據(jù)元素刪除p=L;j=0;while(p-next &jn ext; +j;if(!(p-next)|ji-1) return ERROR; / 刪除位置不合理q=p- next; /臨時保存被刪結(jié)點的地址以備釋放p- next二q

4、- next;/改變刪除結(jié)點前驅(qū)結(jié)點的指針域e=q-data; 保存刪除結(jié)點的數(shù)據(jù)域free(q); /釋放刪除結(jié)點的空間return OK;/ListDelete_L7.題答案Status List In sert_L(L in kList &L,i nt i,ElemType e)/在第i個元素之前插入數(shù) 據(jù)元素ep=L;j=0;while(p&jnext;+j; / 尋找第 i-1 個結(jié)點 if(!p|ji-1)return ERROR; /i 大于表長 + 1 或者小于 1 s= (LinkList) malloc ( sizeof (LNode);/生成新結(jié)點 ss-data=e;將

5、結(jié)點s的數(shù)據(jù)域置為es-next=p-next;/將結(jié)點 s 插入 L 中p-n ext=s;return OK;/List In sert_L.題答案void CreateList_L(Li nkList & L,i nt n)正位序輸入n個元素的值，建立帶表頭結(jié)點的單鏈表LL=(Li nkList) malloc (sizeof (LNode);L-n ext=NULL;r=L;/尾指針r指向頭結(jié)點for(i=0;idata); / 輸入元素值 p-n ext=NULL; r-n ext=p;r=p;r指向新的尾結(jié)點9.題答案Status Delete_Between(Linklist &

6、L,int mink,int maxk)/刪除元素 遞增排列的鏈表L中值大于mink且小于maxk的所有元素 q=L; p =L-n ext;while(p & p-data n ext; /q 是最后一個不大于mink的元 素，p是第一個 大于mink的元素if(!p) return ERROR; /如果沒有比mink更大的元素 while(p & p-data n ext = p-n ext;free(p);p =q-n ext;return OK;10.題答案void MergeList_L(Li nkList & La,L in kList & Lb,Li nkList & Lc)pa

7、=La-next; pb=Lb-next;pc=Lc=La;/用La的頭結(jié)點作為while(pa & pb) if(pa-datadata) pc-n ext=pa;pc=pa;pa=pa-n ext; elsepc-n ext=pb; pc=pb; pb=pb-n ext; pc-n ext=pa?pa:pb;/ 插入剩余段free(Lb);第六章參考答案:1.C2. 1503.C4. A 5. D 6. D 7. B 8. A 9. B10. 1.9511. B二.解答題1.(1)先序遍歷：GADEFBC ;二叉樹的形態(tài)見左下圖;(2)對應(yīng)的樹見右下圖2. (1)畫出該二叉樹;(2)畫出對

8、應(yīng)的二叉樹g 、A3. (1) 二叉樹：樹形結(jié)構(gòu)同(2)(3 )二叉樹對(2)二叉樹的后序后繼線索樹bg應(yīng)的森林 GJHDBEIFCA4. (1)哈夫曼樹BFDC100 )(弋/*26280ZA1AE8 10 11(2)電文中六個字符的哈夫曼編碼如下:A : 01B: 000C： 111D: 110E： 10F： 0011175.方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹w=7,19,2,6,32,3,21,10按哈夫曼規(guī)則：/ 19(17)(40).21方案比較:字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.32字母編

9、號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.32610003方案1的WPL =2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)制編碼2、算法題答案(1)/求位于先序序列中第k個位置的結(jié)點的值，/ e中存放結(jié)點的返回值，i為計數(shù)器Status PONodeK(TEIemType & e, i nt & i, i nt k, BiT

10、ree &T) if(T)i+;if(i=k) e=T-data;elsePONodeK(e,i,k,T-lchild); PONodeK(e,i,k,T-rchild);return OK;(2)/求二叉樹中葉子結(jié)點的數(shù)目Status POLeafNodeNum(i nt &i, BiTree &T)if(T)if(!T-lchild & !T-rchild) i+; POLeafNodeNum(i,T-lchild); POLeafNodeNum(i,T-rchild);return OK(3)/按先序交換二叉樹的左右子樹Status Excha ngeBiTree(BiTree& T)B

11、iTree p;if(T)p=T-lchild;T-lchild=T-rchild;T- rchild=p;Excha ngeBiTree(T-lchild); Excha ngeBiTree(T-rchild); return OK;(4)/求二叉樹的深度int Depth (BiTree T )int depthLeft,depthRight,depthval;if ( !T ) depthval = 0;else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild );1 + depthLeft;if (depthLeft

12、depthRight ) depthval = else depthval = 1 + depthRight;retur n depthval;第七章參考答案:5.C6.D7.n(n-1)/28. B9.A1.B2. C 3.D4.B10.A 11. A 12. 15二解答題1.深度優(yōu)先生成樹廣度優(yōu)先生成樹陣存儲結(jié)構(gòu)0 1 01 0 10 1 00 0 11 0 10 1 02.(1)無向圖0 1 00 0 11 1 00 0 10 0 11 1 0A4.表1 各事件（頂點）的最早發(fā)生時間和最遲發(fā)生時間為:頂 占 八、abcdefghkve064577151418vl066710161418表

13、2 各活動（?。┑淖钤玳_始時間和最遲開始時間為:O（2）拓?fù)渑判蛴袃煞N可能結(jié)果:V1V2V3V4V6V5V7VV1V3V2 V4V6V5V7V弧abacadbecedfegehfhg kh ke0006457771514l0236687101614終 占 八、從V1到各終點的距離 和最短路徑的求解過 程i1i=2i=3i=4i=5i=6i=7V22V333V4oc76V5oc)0131312V6o)0oo10V7oc)0oooooo15Vo)0ooo161616v jv2v3v4v6v5v7v8注：斜粗體的部分為所求1.42. B 3.B二解答題4.C5.B6.D7.B8. C9.D第九章參考

14、答案:12丄也12Dec1.長度為12的有序表進(jìn)行折半查找的判定樹為:1110等概率查找成功時的平均查找長度為：(1X 1 + 2X 2+ 4X 3+ 5X 4) /12=37/12 2. 經(jīng)排序后的表及在折半查找時找到表中元素所經(jīng)比較的次數(shù)對照如K;Apr Aug Dec Feb Jan July June Mar May Nov Oct Sept342341342434等概率情況下査找成功時的平均査找長度為AS=言1 X 1+3X2+31 + 4X5) =邁(3)按教科書乳么1節(jié)所述求得的平衡二更樹為5.它在等概率情況下的平均查找怏度為I38ASL = Ad X1 + 2X2 十 mX4

15、+ 4X4 + 5Xi) =両3.0123456789103355236538402053(1+2+2+5+1+1+1+2)/8=15/8;(5+4+3+2+1+2+1+2+1+7+6)/11=34/11ASL nsucc=成功：ASLsucc= (1*4+2*2+3)/7=11/7;不成功:(1+1+2+3)/7=7/7=1畫表如下:01 :2 34567 3 9)10111213141516173164241334427394000167 查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63 vs31 ,no;然后順移，與46,47,32,17,63相比，一共比較了 6次！

16、 查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為 12號單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以應(yīng)當(dāng)只比較這一次即可。 對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)。“63”需要6次,“ 49”需要3次，“ 40”需要2次，“ 46”需要3次，“ 47”需要 3次，所以 ASL=1/11 (6+ 2+ 3X 3+6)= 23/116.02212345678910416730534613H(22)=(3*22)%1仁0H(53)=(3*53) % 11=5H(30)=(3*30) % 11=21) % 1仁3H(13)=(3*13) % 11=61)%

17、 1仁8H(41)=(3*41)%11=2H(46)=(3*46) % 11=6沖突 H1 =(2+( 1X (7*30)% 10+沖突 H1 =(6+( 1X (7*13) % 10 +H(1)=(3*1) % 11=3 沖突 H1 = (3+ (1X(7*1) % 10+ 1) %11=0沖突H2 =( 3+(2X (7*1)% 10 + 1) % 1仁8沖突H3 =( 3+(3X(7*1)% 10+ 1) % 1仁5沖突H4 = (3+(4X(7*1) %10+ 1) % 1仁2沖突H5 =(3+(5X (7*1) % 10+ 1) % 11=10H(67)=(3*67) % 1仁3 沖

18、突 H1 =( 3+( 1X (7*67) % 10 +1) % 11=2 沖突平均查找長度ASL =H2 =( 3+(2X (7*67) % 10+ 1)% 11=1(1 X 4+ 2X 2+ 3X 1+ 6) /8=17/7.建立2-3樹后的狀態(tài)刪除43后的2-3樹狀態(tài)：刪除24后的2-3樹狀態(tài)：三、算法題答案typedef int KeyType;typedef structKeyType key;char n ame20;SEIemType;typedef structSElemType elemMAXSIZE;int len gth;SSTable;(1)int Search_Seq

19、(SSTable ST, KeyType key) ST. elem0 .key = key;for ( int i = ST.le ngth; (ST.elemi.key != key); -i); return i;/Search_Seqint Search_Bi n( SSTable ST, KeyType key) int high,low,mid;low = 1;high = ST.Ien gth;while(low = high)mid = (low + high)/2;if (key = ST. elemmid .key) return mid;else if (key = ST

20、. elemmid .key) high = mid - 1; else low = mid +1;return 0;/Search_Bi n第十章參考答案:8.直接插1.C 2. A 3.D4.C5. C 6.B7.0(n2)入排序二解答題1.快速排序65, 56,21,65,56,i亠i21,口，56,21,i34,56,i m21,34,口，21,34,i3,8,76, 3,89,34, 21, 46 j j8,76,3,89,34,口,46j8,76,3,89,34,65,46jj8,76,3,89,口，65,46j8,76,3,89,56,65,46j-j8,76,口,89,56,6

21、5,46T* ij（1）希爾排序初始36573324序列75669416d=5363843852754679616 Id=3342853763861646579d=138233456781476656921, 34，3，8，口，76，89，56，65，46i j勺（21，34，3，8） 37 （76，89，56，65，46）第一趟排序結(jié)果:初始建堆堆排序初始關(guān)鍵字的完全二叉樹形式: 的結(jié)果：37，65，37，5，76，3，896，34，891,，能6 21，463421 46第一次交換之后的結(jié)果: 重建堆的結(jié)果：第一次交換之后821 892. (1)直接插入排序初始關(guān)鍵字：(503 )0875

22、12061275653426i=2 :(087503)512061275653426i=3 :(087503512 )061275653426i=4 :(061087503512 )275653426i=5 :(061087503512275653426i=6 :(061087170503275653426i=7 :(06108717050327565342690901901901908 )512512170170170170170908 )；9790；97；97；97；97；97；97908 )；97653i=8 : ( 061653i=9 :908 )i=10 :897087426 (06

23、1426(061908 )087087170275503512897170275503512653170275426503512希爾排序初始關(guān)鍵字I：275653503426087512061901170；97d1=5: I51265317090808775061426503；97d2=3:512653061908087275170426503；97d3=1:65397061908087170275426503512(3) 二路歸并 初始關(guān)鍵字：897275第一趟歸并結(jié)果275 897第二趟歸并結(jié)果897908503653087426061087426503 653 087512061908170061512170503512 170275第三趟歸并結(jié)果897908 426 653 061087426 653 170275503512908 第四趟歸并結(jié)果0