本題15分請利用兩個棧S1和S2來模擬一個隊列已VIP

1、廈門大學-數(shù)據(jù)結構-課程期末試卷信息科學與技術學院計算機科學系2005年級專業(yè)主考教師：試卷類型：(A卷/B卷)一、(本題15分)請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：Push(StackST,intx)：元素x入ST棧；Pop(StackST,intx):ST棧頂元素出棧，賦給變ix;StackEmpty(StackST):判ST棧是否為空。那么如何利用棧的運算來實現(xiàn)該隊列的三個運算：EnQueue插入一個元素入隊列；DeQueue:刪除一個元素出隊列；QueueEmpty判隊列為空。解：利用兩個棧S1、S2模擬一個隊列(如客尸隊列)時，當需要向隊列中輸入元素時，用

2、S1來存放輸入元素，用push運算實現(xiàn)。當需要從隊列中輸出元素時，到棧S2中去取，如果S2為空，則將S1中的元素全部送入到S2中，然后再從S2中輸出元素。判斷隊空的條件是：S1和S2同時為空。StatusEnQueue(DataTypex)ifStackFull(S1)S1棧滿ifStackEmpty(S2)/S1棧滿，S2?？誻hile(!StackEmpty(S1)Pop(S1,y);Push(S2,y);/棧S1的內(nèi)容反向搬到棧S2Push(S1,x);returnOK;else/S1棧滿，S2棧非空，則不可進行插入操作returnERROR;else/S1棧不滿，則宜接進棧Push(S

3、1,x);returnOK;StatusDeQueue(DataType&x)if!StackEmpty(S2)Pop(S2,x);returnOK;elseif!StackEmpty(S1)while(!StackEmpty(S1)Pop(S1,y);Push(S2,y);/棧S1的內(nèi)容反向搬到棧S2Pop(S2,x);returnOK;else/棧S1和S2都為空returnERROR;二、（本題15分）用孩子兄弟鏈表作為樹的存儲結構，設計算法求出樹的深度。解：算法思路：一棵樹的深度可以遞歸定義為：若樹為空，則深度為0,否則樹的深度為根結點的所有子樹深度的最大值加1。數(shù)據(jù)結構為：typed

4、efstructCSNodeElemTypedata;structCSNode葉irstchild,*nextsibling;CSNode,*CSTree;算法如下：intdepth(CSNode*t)CSNode*p;intm,d;if(t=NULL)return0;p=tfirstchild;m=0;while(p)d=depth(p);if(dm)m=d;p=pnextsibling;returnm+1;三、（本題15分）已知在莫并發(fā)處理系統(tǒng)的Petri網(wǎng)基礎上建立的可達圖如下圖所示。圖中每個頂點表示系統(tǒng)運行中的一種狀態(tài)，有向邊（?。┍硎臼录ㄓ胻表示），例如有向邊（Vi,Vj）表示系統(tǒng)

5、在狀態(tài)Vi時出現(xiàn)該事件將引發(fā)系統(tǒng)由狀態(tài)Vi到狀態(tài)Vj。（1）請分別給出該可達圖的鄰接表、鄰接矩陣以及鄰接矩陣的三元組3種存儲表示的形式說明和存儲結果示意圖，要求每種存儲結構能夠表達出該可達圖的全部信息，并分別對這三種形式中每個部分的含義予以簡要說明。若假設每個域（包括指針域）的長度為2個字節(jié)，請分別計算出這三種結構所占用的空間大小。四、（本題15分）設計一個算法，判斷無向圖G（圖中有n個頂點）是否是一棵樹。解：算法思路：從第v個頂點出發(fā)，對圖進行深度優(yōu)先搜索。若在算法結束之前，又訪問了莫一已訪問過的頂點，則圖G中必定存在環(huán), 頂點個數(shù)Boolean visitedMAX;Status ( *

6、VisitFu nc) (in t v);G不是一棵以v為根的樹。若在算法結束之后,所訪問的頂點數(shù)小于圖的n,則圖G不是連通圖，G也不是一棵以v為根的樹。/用于標識結點是否已被訪問過函數(shù)變MvoidDFSTraverse(GraphGStatus(*VisitFunc)(intv);VisitFunc=Visit;for(v=0;vvG.vexnum;+v)visitedv=false;if(DFS(G,v)=FALSE)returnFALSE;for(v=0;v=2(m/2)t-1反之，IElogm/2(冷八)1N+1因此，含有n個關鍵字的B-樹，最大深度為logm/2(2)10六、(本題1

7、0分)設關鍵字序列為：49,38,66,80,70,15,22。(1)用宜接插入排序法進行排序，寫出每趟的結果。(2)采用待排序列的第一個關鍵字作為樞軸，寫出用快速排序法的一趟和二趟排序之后的狀八態(tài)0解：(1)宜接插入排序法原始關鍵字序列為：(49)386680701522(3849)6680701522(384966)80701522(38496680)701522(3849667080)1522(3849667080)1522(153849667080)22(15223849667080)(2)快速排序法原始關鍵字序列為：49,38,66,80,70,15,22第一趟排序后223815(4

8、9)708066第二趟排序后15(22)3866(70)80七、(本題15分)有一種簡單的排序算法，叫做計數(shù)排序。這種排序算法對一個待排序的表進行排序，并將排序結果存放到另一個新的表中。必須注意的是，表中所有待排序的關鍵字互不相同。計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關鍵字比該記錄的關鍵字要小。假設針對莫一個記錄，統(tǒng)計出的計算值為c,那么這個記錄在新的有序表中的合適的存放位置為c+1。(1) 編寫實現(xiàn)計數(shù)排序的算法；(2) 分析該算法的時間復雜性。解：(1)假設數(shù)據(jù)結構如下：#defineMAXSIZE20typedefintKeyType;typedefstructKeyTypekey;InfoTypeotherinfo;RedType;typedefstructRedTyperMAXSIZE+1;/r0空或作哨兵intlength;SqList;voidCountSort(SqListL1,SqListL2)把L1計數(shù)排序后，結果放在L2inti,j,n,count;n=L1ength;L2.length=L1.length;for(i=1;i