本題15分請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列已_第1頁(yè)
本題15分請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列已_第2頁(yè)
本題15分請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列已_第3頁(yè)
本題15分請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列已_第4頁(yè)
本題15分請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列已_第5頁(yè)
已閱讀5頁(yè),還剩2頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論