本題15分請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列已

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

2、S1來(lái)存放輸入元素，用push運(yùn)算實(shí)現(xiàn)。當(dāng)需要從隊(duì)列中輸出元素時(shí)，到棧S2中去取，如果S2為空，則將S1中的元素全部送入到S2中，然后再?gòu)腟2中輸出元素。判斷隊(duì)空的條件是：S1和S2同時(shí)為空。StatusEnQueue(DataTypex)ifStackFull(S1)S1棧滿(mǎn)ifStackEmpty(S2)/S1棧滿(mǎn)，S2?？誻hile(!StackEmpty(S1)Pop(S1,y);Push(S2,y);/棧S1的內(nèi)容反向搬到棧S2Push(S1,x);returnOK;else/S1棧滿(mǎn)，S2棧非空，則不可進(jìn)行插入操作returnERROR;else/S1棧不滿(mǎn)，則宜接進(jìn)棧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分）用孩子兄弟鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法求出樹(shù)的深度。解：算法思路：一棵樹(shù)的深度可以遞歸定義為：若樹(shù)為空，則深度為0,否則樹(shù)的深度為根結(jié)點(diǎn)的所有子樹(shù)深度的最大值加1。數(shù)據(jù)結(jié)構(gòu)為：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)基礎(chǔ)上建立的可達(dá)圖如下圖所示。圖中每個(gè)頂點(diǎn)表示系統(tǒng)運(yùn)行中的一種狀態(tài)，有向邊（?。┍硎臼录ㄓ胻表示），例如有向邊（Vi,Vj）表示系統(tǒng)

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

6、VisitFu nc) (in t v);G不是一棵以v為根的樹(shù)。若在算法結(jié)束之后,所訪(fǎng)問(wèn)的頂點(diǎn)數(shù)小于圖的n,則圖G不是連通圖，G也不是一棵以v為根的樹(shù)。/用于標(biāo)識(shí)結(jié)點(diǎn)是否已被訪(fǎng)問(wèn)過(guò)函數(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個(gè)關(guān)鍵字的B-樹(shù)，最大深度為logm/2(2)10六、(本題1

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

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