1、第三章（10）已知f為單鏈表的表頭指針, 鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)下列運算的遞歸算法： 求鏈表中的最大整數(shù)； 求鏈表的結(jié)點個數(shù)； 求所有整數(shù)的平均值。#include <iostream.h>/定義在頭文件"RecurveList.h"中class List;class ListNode /鏈表結(jié)點類friend class List;private:int data;/結(jié)點數(shù)據(jù)ListNode *link;/結(jié)點指針ListNode ( const int item ) : data(item), link(NULL) /構(gòu)造函數(shù);class Li

2、st /鏈表類private:ListNode *first, current;int Max ( ListNode *f );int Num ( ListNode *f );float Avg ( ListNode *f, int& n );public:List ( ) : first(NULL), current (NULL) /構(gòu)造函數(shù)List ( ) /析構(gòu)函數(shù)ListNode* NewNode ( const int item );/創(chuàng)建鏈表結(jié)點, 其值為itemvoid NewList ( const int retvalue );/建立鏈表, 以輸入retvalue結(jié)束

3、void PrintList ( );/輸出鏈表所有結(jié)點數(shù)據(jù)int GetMax ( ) return Max ( first ); /求鏈表所有數(shù)據(jù)的最大值int GetNum ( ) return Num ( first ); /求鏈表中數(shù)據(jù)個數(shù)float GetAvg ( ) return Avg ( first ); /求鏈表所有數(shù)據(jù)的平均值;ListNode* List : NewNode ( const int item ) /創(chuàng)建新鏈表結(jié)點ListNode *newnode = new ListNode (item);return newnode;void List : NewL

4、ist ( const int retvalue ) /建立鏈表, 以輸入retvalue結(jié)束first = NULL; int value; ListNode *q;cout << "Input your data:n"/提示cin >> value;/輸入while ( value != retvalue ) /輸入有效q = NewNode ( value );/建立包含value的新結(jié)點if ( first = NULL ) first = current = q;/空表時, 新結(jié)點成為鏈表第一個結(jié)點else current->link

5、 = q; current = q; /非空表時, 新結(jié)點鏈入鏈尾cin >> value;/再輸入current->link = NULL;/鏈尾封閉void List : PrintList ( ) /輸出鏈表cout << "nThe List is : n"ListNode *p = first;while ( p != NULL ) cout << p->data << ' ' p = p->link; cout << n; int List : Max ( ListNo

6、de *f ) /遞歸算法 : 求鏈表中的最大值if ( f ->link = NULL ) return f ->data;/遞歸結(jié)束條件int temp = Max ( f ->link );/在當前結(jié)點的后繼鏈表中求最大值if ( f ->data > temp ) return f ->data;/如果當前結(jié)點的值還要大, 返回當前檢點值else return temp;/否則返回后繼鏈表中的最大值int List : Num ( ListNode *f ) /遞歸算法 : 求鏈表中結(jié)點個數(shù)if ( f = NULL ) return 0;/空表,

7、返回0return 1+ Num ( f ->link );/否則, 返回后繼鏈表結(jié)點個數(shù)加1float List : Avg ( ListNode *f , int& n ) /遞歸算法 : 求鏈表中所有元素的平均值if ( f ->link = NULL ) /鏈表中只有一個結(jié)點, 遞歸結(jié)束條件 n = 1; return ( float ) (f ->data ); else float Sum = Avg ( f ->link, n ) * n; n+; return ( f ->data + Sum ) / n; #include "R

8、ecurveList.h"/定義在主文件中int main ( int argc, char* argv ) List test; int finished;cout << “輸入建表結(jié)束標志數(shù)據(jù) ：”;cin >> finished;/輸入建表結(jié)束標志數(shù)據(jù) test.NewList ( finished );/建立鏈表test.PrintList ( );/打印鏈表cout << "nThe Max is : " << test.GetMax ( );cout << "nThe Num is

9、: " << test.GetNum ( );cout << "nThe Ave is : " << test.GetAve () << 'n'printf ( "Hello World!n" );return 0;第五章2應用題（1）試找出滿足下列條件的二叉樹 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相同 中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是“根左子樹右子樹”，中序遍歷“左子樹根右子樹”，后序遍歷順序是：“左子樹右子樹根，根據(jù)以上原則，本題解

10、答如下：（）  若先序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹（）  若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹（）  若先序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹（）  若中序序列與層次遍歷序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹（2）設一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對應的樹（或森林）。  ABMFD(3)CEMHG 

11、;       (1) (2)（3） 假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個字母設計赫夫曼編碼。 試設計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17

12、 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號對應編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號對應編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(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

13、方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼 （4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài): weightparentlchildrchild13000212000370004400052000680007110008 0009 00010 00011 00012 00013 000  weightparen

14、tlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112終態(tài)3算法設計題以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法：（1）統(tǒng)計二叉樹的葉結(jié)點個數(shù)。int LeafNodeCount(BiTree T)if(T=NULL)return 0; /如果是空樹，則葉子結(jié)點個數(shù)為0else if(T->lchild=NULL&&T->rchild=NULL)return 1; /判斷該結(jié)點是否是葉子結(jié)點（左孩子右孩子都為空），若是則返

15、回1elsereturn LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);（2）判別兩棵樹是否相等。（3）交換二叉樹每個結(jié)點的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;elsetemp = T->lchild;T->lchild = T->rchild;T->rchild = temp;ChangeLR(T->lchild);ChangeL

16、R(T->rchild);（4）設計二叉樹的雙序遍歷算法（雙序遍歷是指對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點，再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點，接下來按雙序遍歷它的右子樹）。void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T->lchild=NULL&&T->rchild=NULL)cout<<T->data;elsecout<<T->data;DoubleTraverse(T->lchild);cout<<T->dat

17、a;DoubleTraverse(T->rchild);（5）計算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點個數(shù)的最大值）。題目分析 求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法，記下各層結(jié)點數(shù)，每層遍歷完畢，若結(jié)點數(shù)大于原先最大寬度，則修改最大寬度。int Width(BiTree bt)/求二叉樹bt的最大寬度if (bt=null) return (0); /空二叉樹寬度為0else BiTree Q;/Q是隊列，元素為二叉樹結(jié)點指針，容量足夠大 front=1;rear=1;last=1;/front隊頭指針,rear隊尾指針,last同層最右結(jié)點在隊列

18、中的位置 temp=0; maxw=0; /temp記局部寬度, maxw記最大寬度 Qrear=bt; /根結(jié)點入隊列 while(front<=last) p=Qfront+; temp+; /同層元素數(shù)加1 if (p->lchild!=null) Q+rear=p->lchild; /左子女入隊if (p->rchild!=null) Q+rear=p->rchild; /右子女入隊 if (front>last) /一層結(jié)束， last=rear;if(temp>maxw) maxw=temp;/last指向下層最右元素, 更新當前最大寬度

19、temp=0; /if /while return (maxw);/結(jié)束width（6）用按層次順序遍歷二叉樹的方法，統(tǒng)計樹中具有度為1的結(jié)點數(shù)目。int Level(BiTree bt) /層次遍歷二叉樹，并統(tǒng)計度為1的結(jié)點的個數(shù)int num=0; /num統(tǒng)計度為1的結(jié)點的個數(shù) if(bt)QueueInit(Q); QueueIn(Q,bt)；/Q是以二叉樹結(jié)點指針為元素的隊列 while(!QueueEmpty(Q)p=QueueOut(Q); printf(p->data); /出隊,訪問結(jié)點if(p->lchild && !p->rchild |

20、!p->lchild && p->rchild)num+;/度為1的結(jié)點if(p->lchild) QueueIn(Q,p->lchild); /非空左子女入隊if(p->rchild) QueueIn(Q,p->rchild); /非空右子女入隊 /if(bt) return(num); /返回度為1的結(jié)點的個數(shù) （7）求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點的值。題目分析因為后序遍歷棧中保留當前結(jié)點的祖先的信息，用一變量保存棧的最高棧頂指針，每當退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助棧中，輔助棧始終保

21、存最長路徑長度上的結(jié)點，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。void LongestPath(BiTree bt)/求二叉樹中的第一條最長路徑長度BiTree p=bt,l,s; /l, s是棧，元素是二叉樹結(jié)點指針，l中保留當前最長路徑中的結(jié)點 int i，top=0,tag,longest=0; while(p | top>0) while(p) s+top=p；tagtop=0; p=p->Lc; /沿左分枝向下 if(tagtop=1) /當前結(jié)點的右分枝已遍歷 if(!stop->Lc && !stop->Rc) /只有到葉子結(jié)點時，才查

22、看路徑長度if(top>longest) for(i=1;i<=top;i+) li=si; longest=top; top-;/保留當前最長路徑到l棧，記住最高棧頂指針，退棧 else if(top>0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top>0)/結(jié)束LongestPath（8）輸出二叉樹中從每個葉子結(jié)點到根結(jié)點的路徑。題目分析采用先序遍歷的遞歸方法，當找到葉子結(jié)點*b時，由于*b葉子結(jié)點尚未添加到path中，因此在輸出路徑時還需輸出b->data值。對應的遞歸算法如下：void AllPath(B

23、TNode *b,ElemType path,int pathlen) int i; if (b!=NULL) if (b->lchild=NULL && b->rchild=NULL) /*b為葉子結(jié)點 cout << " " << b->data << "到根結(jié)點路徑:" << b->data; for (i=pathlen-1;i>=0;i-) cout << endl; else pathpathlen=b->data; /將當前結(jié)點放

24、入路徑中 pathlen+; /路徑長度增1 AllPath(b->lchild,path,pathlen); /遞歸掃描左子樹 AllPath(b->rchild,path,pathlen); /遞歸掃描右子樹 pathlen-; /恢復環(huán)境 第六章2應用題（1）已知如圖6.27所示的有向圖，請給出： 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 圖6.27 有向圖 （2）已知如圖6.28所示的無向網(wǎng)，請給出： 鄰接矩陣； 鄰接表； 最小生成樹圖6.28 無向網(wǎng) ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5

25、f2h6hc5d4g6（3）已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖6.29 鄰接矩陣（4）有向網(wǎng)如圖6.30所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑，完成表6.9。 圖6.30 有向網(wǎng)D終點i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(a,c,f,g)16(a,c,f,g)14(a,c,

26、f,d,g)S終點集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b （5）試對圖6.31所示的AOE-網(wǎng)： 求這個工程最早可能在什么時間結(jié)束； 求每個活動的最早開始時間和最遲開始時間；圖6.31 AOE-網(wǎng) 確定哪些活動是關鍵活動【解答】按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l - e = 0? 來確定關鍵活動，從而確定關鍵路徑。 1 ¶ 2 ¸ 3 · 4 ¹ 5 º 6 » Ve 0

27、 19 15 29 38 43 Vl 0 19 15 37 38 43<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6><5, 6> e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38l-e 17 0 0 8 0 12 8 0此工程最早完成時間為43。關鍵路徑為<1, 3><3, 2><2, 5><5, 6> 第七章2應用題（1）假定對有序表：（3，4，5，7，24，30，

28、42，54，63，72，87，95）進行折半查找，試回答下列問題： 畫出描述折半查找過程的判定樹； 若查找元素54，需依次與哪些元素比較？ 若查找元素90，需依次與哪些元素比較？ 假定每個元素的查找概率相等，求查找成功時的平均查找長度。先畫出判定樹如下（注：mid=ë(1+12)/2û=6）：305 633 7 42 87 4 24 54 72 95查找元素54，需依次與30, 63, 42, 54 元素比較；查找元素90，需依次與30, 63,87, 95元素比較；求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前3層共查找12×24×3=17次；但

29、最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL1/12（1720）37/123.08（2）在一棵空的二叉排序樹中依次插入關鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉排序樹。 127 17 2 11 16 21 4 9 13驗算方法： 用中序遍歷應得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，21（3）已知如下所示長度為12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出

30、插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。 若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。解： （4）對下面的3階B-樹，依次執(zhí)行下列操作，畫出各步操作的結(jié)果。 插入90 插入25 插入45 刪除60   （5）設哈希表的地址范圍為017，哈希函數(shù)為：H（key）=key%16。用線性探測法處理沖突，輸入關鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列

31、問題： 畫出哈希表的示意圖； 若查找關鍵字63，需要依次與哪些關鍵字進行比較？ 若查找關鍵字60，需要依次與哪些關鍵字比較？ 假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為12號單元為空（應當有空標記），所以應當只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較1次；共

32、6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（623×3+6）23/11（6）設有一組關鍵字（9，01，23，14，55，20，84，27），采用哈希函數(shù)：H（key）=key %7 ，表長為10，用開放地址法的二次探測法處理沖突。要求：對該關鍵字序列構(gòu)造哈希表，并計算查找成功的平均查找長度。散列地址0123456789關鍵字140192384275520  比較次數(shù)1112 3 412  平均查找長度：ASLsucc=（1+1+1+

33、2+3+4+1+2）/8=15/8以關鍵字27為例：H（27）=27%7=6（沖突） H1=（6+1）%10=7（沖突） H2=（6+22）%10=0（沖突） H3=（6+33）%10=5 所以比較了4次。（7）設哈希函數(shù)H（K）=3 K mod 11，哈希地址空間為010，對關鍵字序列（32，13，49，24，38，21，4，12），按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucc和ASLunsucc。 線性探測法； 鏈地址法。散列地址012345678910關鍵字 4 12493813243221 比較次

34、數(shù) 1 1121212 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 ASLsucc =（1*5+2*3）/8=11/8ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11（5）設哈希表的地址范圍為017，哈希函數(shù)為：H（key）=key%16。用線性探測法處理沖突，輸入關鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列問題： 畫出哈希表的示意圖； 若查找關鍵字63，需要依次

35、與哪些關鍵字進行比較？ 若查找關鍵字60，需要依次與哪些關鍵字比較？ 假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。解： （1）畫表如下：012345678910111213141516173217634924401030314647（2） 查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次！（3）查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為12號單元為空（應當有空標記），所以應當只比較這一次即可。（4） 對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不

36、相同，要統(tǒng)計移位的位數(shù)。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（623×3+6）23/11第八章2應用題（1）設待排序的關鍵字序列為12，2，16，30，28，10，16*，20，6，18，試分別寫出使用以下排序方法，每趟排序結(jié)束后關鍵字序列的狀態(tài)。 直接插入排序 折半插入排序 希爾排序（增量選取5，3，1） 冒泡排序 快速排序 簡單選擇排序 堆排序 二路歸并排序直接插入排序2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 2

37、8 10 16* 20 6 18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 18 20 28 30 折半插入排序 排序過程同 希爾排序（增量選取5，3，1）10 2 16 6 18 12 16* 20 30 28 （增量選取5）6 2 12 10 18 16 16* 20 30 28 （增量選取3）2 6 10 12 16 16* 18 20 28 30 （增量選取1） 冒泡排序2 12 16 28 10 16* 20 6 18 30 2 12 16 10 16* 20 6 18 28 30 2 12 10 16 16* 6 18 20 28 30 2 10 12 16 6 16* 18 20 28 30 2 10 12 6 16 16* 1