本題15分請利用兩個棧S1和S2來模擬一個隊列已_第1頁
本題15分請利用兩個棧S1和S2來模擬一個隊列已_第2頁
本題15分請利用兩個棧S1和S2來模擬一個隊列已_第3頁
本題15分請利用兩個棧S1和S2來模擬一個隊列已_第4頁
本題15分請利用兩個棧S1和S2來模擬一個隊列已_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

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

溫馨提示

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

評論

0/150

提交評論