




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、第三章習題1. 按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進行車廂調(diào)度,回答: 如進站的車廂序列為123,則可能得到的出站車廂序列是什么?如進站的車廂序列為123456,能否得到435612和135426的出站序列,并說明原因。(即寫出以“S”表示進棧、以“X”表示出棧的棧操作序列)。2. 設(shè)隊列中有A、B、C、D、E這5個元素,其中隊首元素為A。如果對這個隊列
2、重復(fù)執(zhí)行下列4步操作:(1) 輸出隊首元素;(2) 把隊首元素值插入到隊尾;(3) 刪除隊首元素;(4) 再次刪除隊首元素。直到隊列成為空隊列為止,得到輸出序列: (1) A、C、E、C、C
3、 (2) A、C、E(3) A、C、E、C、C、C (4) A、C、E、C3. 給出棧的兩種存儲結(jié)構(gòu)形式名稱,在這兩種棧的存儲結(jié)構(gòu)中如何判別棧空與棧滿?4.
4、按照四則運算加、減、乘、除和冪運算()優(yōu)先關(guān)系的慣例,畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程: AB5. 試寫一個算法,判斷依次讀入的一個以為結(jié)束符的字母序列,是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如,a+b&b+a是屬該模式的字符序列,而+&則不是。6.
5、160; 假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法,將一個通常書寫形式且書寫正確的表達式轉(zhuǎn)換為逆波蘭式。7. 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針),試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。8. 要求循環(huán)隊列不損失一個空間全部都能得到利用, 設(shè)置一個標志域tag , 以tag為
6、0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿,請編寫與此結(jié)構(gòu)相應(yīng)的入隊與出隊算法。9. 簡述以下算法的功能(其中棧和隊列的元素類型均為int):(1)void proc_1(Stack S) int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i<=n; i+) &
7、#160; Push(&S, Ai); (2)void proc_2(Stack S, int e) Stack T; int d;InitStack(&T); while(!EmptyStack(S) Pop(&S, &d); if (d!=e) Push( &T, d); while(!EmptyStack(T) Pop(&T,&
8、#160; &d); Push( &S, d); (3)void proc_3(Queue *Q) Stack S; int d;InitStack(&S); while(!EmptyQueue(*Q) DeleteQueue(Q, &d);Push( &S, d); while(!EmptyStack(S) Pop
9、(&S, &d); EnterQueue(Q,d) 實習題1 回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫一個算法,判斷依次讀入的一個以為結(jié)束符的字母序列,是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如,a+b&b+a是屬該模式的字符序列,而+&則不是。2 停車場管理。設(shè)停車場是一個可停放n輛車的狹長通道,且只有一個大門可供汽車進出。在停車場內(nèi),汽車按到達的先后次序,由北向南依次
10、排列(假設(shè)大門在最南端)。若車場內(nèi)已停滿n輛 車,則后來的汽車需在門外的便道上等候,當有車開走時,便道上的第一輛車即可開入。當停車場內(nèi)某輛車要離開時,在它之后進入的車輛必須先退出車場為它讓 路,待該輛車開出大門后,其它車輛再按原次序返回車場。每輛車離開停車場時,應(yīng)按其停留時間的長短交費(在便道上停留的時間不收費)。試編寫程序,模擬上述管理過程。要求以順序棧模擬停車場,以鏈隊列模擬便道。從終端讀入汽車到達或離去的數(shù)據(jù),每組數(shù)據(jù)包括三項:是“到達”還是“離去”;汽車牌照號碼;“到達”或“離去”的時刻。與每組輸入信息相應(yīng)的輸出信息為:如果是到達的車輛,則輸出其在停車場中或便道上的位置;如果是離去的車
11、輛,則輸出其在停車場中停留的時間和應(yīng)交的費用。(提示:需另設(shè)一個棧,臨時停放為讓路而從車場退出的車。)3 商品貨架管理。商品貨架可以看成一個棧,棧頂商品的生產(chǎn)日期最早,棧底商品的生產(chǎn)日期最近。上貨時,需要倒貨架,以保證生產(chǎn)日期較近的商品在較下的位置。用隊列和棧作為周轉(zhuǎn),實現(xiàn)上述管理過程。第三章答案3.1按3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進行車廂調(diào)度,回答:(1) 如進站的車廂序列為123,則可能得到的出站車廂序列是什么?(2) 如進站的車廂序列為12
12、3456,能否得到435612和135426的出站序列,并說明原因(即寫出以“S”表示進棧、“X”表示出棧的棧序列操作)?!窘獯稹浚?)可能得到的出站車廂序列是:123、132、213、231、321。(2)不能得到435612的出站序列。因為有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此時按照“后進先出”的原則,出棧的順序必須為X(2)X(1)。能得到135426的出站序列。因為有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。 3.3給出棧的兩種存儲結(jié)構(gòu)形式名稱,在這兩種棧的存儲結(jié)構(gòu)中如何判別棧空與
13、棧滿?【解答】(1)順序棧 (top用來存放棧頂元素的下標)判斷棧S空:如果S->top=-1表示???。判斷棧S滿:如果S->top=Stack_Size-1表示棧滿。(2) 鏈棧(top為棧頂指針,指向當前棧頂元素前面的頭結(jié)點)判斷??眨喝绻鹴op->next=NULL表示棧空。判斷棧滿:當系統(tǒng)沒有可用空間時,申請不到空間存放要進棧的元素,此時棧滿。 3 4照四則運算加、減、乘、除和冪運算的優(yōu)先慣例,畫出對下列表達式求值時操作數(shù)棧和運算符棧的變化過程:A-B*C/D+
14、EF【解答】3 5寫一個算法,判斷依次讀入的一個以為結(jié)束符的字母序列,是否形如序列1&序列2的字符序列。序列1和序列2中都不含&,且序列2是序列1 的逆序列。例如,a+b&b+a是屬于該模式的字符序列,而1+3&3-1則不是?!窘獯稹克惴ㄈ缦拢?#160; int IsHuiWen() Stack *S;
15、0; Char ch,temp; InitStack(&S); Printf(“n請輸入字符序列:”); Ch=getchar();While( ch!=&)
16、160; /*序列1入棧*/ Push(&S,ch); ch=getchar();do /
17、*判斷序列2是否是序列1的逆序列*/ ch=getchar(); Pop(&S,&temp); if(ch!= temp) /*序列2不是序列1的逆序列*/ return(FALSE); printf(“nNO”
18、); while(ch!= && !IsEmpty(&S)if(ch = = && IsEmpty(&S) return(TRUE); printf(“nYES”); /*序列2是序列1的逆序列*/else
19、0; return(FALSE); printf(“nNO”); /*IsHuiWen()*/ 3.8 要求循環(huán)隊列不損失一個空間全部都能得到利用,設(shè)置一個標志tag,以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿,請編寫與此相應(yīng)的入隊與出隊算法。【解答】入隊算法:int EnterQueue
20、(SeqQueue *Q, QueueElementType x) /*將元素x入隊*/ if(Q->front=Q->front && tag=1) /*隊滿*/ return(FALSE); if(Q->front=Q->front && tag=0) /*x入隊前隊空,x入
21、隊后重新設(shè)置標志*/ tag=1;Q->elememtQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE; /*設(shè)置隊尾指針*/Return(TRUE); 出隊算法: int DeleteQueue( SeqQueue *Q , QueueElementType *x) /*刪除隊頭元素,用x返回其值*/if(Q->
22、front=Q->rear && tag=0) /*隊空*/ return(FALSE);*x=Q->elementQ->front;Q->front=(Q->front+1)%MAXSIZE; /*重新設(shè)置隊頭指針*/if(Q->front=Q->rear) tag=0; /*隊頭元素出隊后隊列為空,重新設(shè)置標志域*/Return(TUUE);
23、 編寫求解Hanoi問題的算法,并給出三個盤子搬動時的遞歸調(diào)用過程?!窘獯稹克惴ǎ?#160; void hanoi (int n ,char x, char y, char z) /*將塔座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規(guī)則搬到塔座Z上,Y可用做輔助塔座*/ if(n = =1) move(x,1,z); else
24、0; Hanoi(n-1,x,z,y); move(x, n, z); Hanoi(n-1, y,x,z); Hanoi(3,A,B,C)的遞歸調(diào)用過程: Hanoi(2,A,C,B): Hanoi(1,A,B,C) move(A->
25、C) 1號搬到C Move(A->B) 2號搬到B Hanoi(1,C,A,B) move(C->B) 1號搬到B Move(A->C)&
26、#160; 3號搬到CHanoi(2,B,A,C) Hanoi(1,B,C,A) move(B->A) 1號搬到A Move(B->C)
27、0; 2號搬到C Hanoi(1,A,B,C) move(A->C) 1號搬到C 提示:第3章 限定性線性表 棧和隊列習題1. 按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進行車廂調(diào)度,回答: 如進站的車廂序列為123,則可能得到的出站車廂序列是什么?
28、123、213、132、231、321(312)如進站的車廂序列為123456,能否得到435612和135426的出站序列,并說明原因。(即寫出以“S”表示進棧、以“X”表示出棧的棧操作序列)。SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 設(shè)隊列中有A、B、C、D、E這5個元素,其中隊首元素為A。如果對這個隊列重復(fù)執(zhí)行下列4步操作:(1)
29、 輸出隊首元素;(2) 把隊首元素值插入到隊尾;(3) 刪除隊首元素;(4) 再次刪除隊首元素。直到隊列成為空隊列為止,
30、則是否可能得到輸出序列:(1) A、C、E、C、C (2) A、C、E(3) A、C、E、C、C、C (4) A、C、E、C提示: &
31、#160; A、B、C、D、E (輸出隊首元素A) A、B、C、D、E、A (把隊首元素A插入到隊尾) B、C、D、E、A (刪除隊首元素A) C、D、E、A (再次刪除隊首元素B) C、D、E、A (輸出隊首元素C
32、) C、D、E、A、C (把隊首元素C插入到隊尾) D、E、A、C (刪除隊首元素C) E、A、C (再次刪除隊首元素D) 3. 給出棧的兩種存儲結(jié)構(gòu)形式名稱,在這兩種棧的存儲結(jié)構(gòu)中如何判別??张c棧滿?4. 按照四則運算加、減、乘、除和冪運算
33、()優(yōu)先關(guān)系的慣例,畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程: AB5. 試寫一個算法,判斷依次讀入的一個以為結(jié)束符的字母序列,是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如,a+b&b+a是屬該模式的字符序列,而+&則不是。提示:(1)
34、60; 邊讀邊入棧,直到&(2) 邊讀邊出棧邊比較,直到 6. 假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法,將一個通常書寫形式(中綴)且書寫正確的表達式轉(zhuǎn)換為逆波蘭式(后綴)。提示:例:中綴表達式:a+b 后綴表達式: ab+中綴表達式:a+b×
35、;c 后綴表達式: abc×+中綴表達式:a+b×c-d 后綴表達式: abc×+d-中綴表達式:a+b×c-d/e 后綴表達式: abc×+de/-中綴表達式:a+b×(c-d)-e/f 后綴表達式: abcd-×+ef/-·
36、160; 后綴表達式的計算過程:(簡便)順序掃描表達式,(1) 如果是操作數(shù),直接入棧;(2) 如果是操作符op,則連續(xù)退棧兩次,得操作數(shù)X, Y,計算X op Y,并將結(jié)果入棧。· 如何將中綴表達式轉(zhuǎn)換為后綴表達式?順序掃描中綴表達式,(1)如果是操作數(shù),直接輸出;(2)如果是操作符op2,則與棧頂操作符op1比較:如果op2 > op1,則op2入棧;如果op2 = op1,則脫括號;如果op2 < op1,則輸出op1; 7.
37、 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素結(jié)點(注意不設(shè)頭指針),試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。提示: 參P.56 P.70 先畫圖.typedef LinkList CLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x) 8.
38、60; 要求循環(huán)隊列不損失一個空間全部都能得到利用, 設(shè)置一個標志域tag , 以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿,請編寫與此結(jié)構(gòu)相應(yīng)的入隊與出隊算法。提示: 初始狀態(tài):front=0, rear=0, tag=0 隊空條件:front=rear, tag=0 隊滿條件:front=rear, tag=1 其它狀態(tài):front !=rear, tag=0(或1、2) 入隊操作:(入隊
39、)if (front=rear) tag=1;(或直接tag=1) 出隊操作:(出隊)tag=0; 問題:如何明確區(qū)分隊空、隊滿、非空非滿三種情況? 9. 簡述以下算法的功能(其中棧和隊列的元素類型均為int):(1)void proc_1(Stack S) int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i<=n; i+) Push(&S, Ai); 將棧S逆序。(2)void proc_2(Stack S, int e) Stack T; int d;InitStack(&T); while(!EmptyStack(S) Pop(&S, &d); if (d!=e) Push(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 北京2025年北京市大興區(qū)第一批事業(yè)單位招聘153人筆試歷年參考題庫附帶答案詳解
- 麗江云南麗江市婦女兒童醫(yī)院第一批編外備案制人員招聘6人筆試歷年參考題庫附帶答案詳解
- 未出資股權(quán)轉(zhuǎn)讓協(xié)議范例二零二五年
- 樁基工程勞務(wù)承包合同參考二零二五年
- 采礦權(quán)抵押協(xié)議合同書范例
- 微信公眾號運營合同范例
- 火鍋店合伙人協(xié)議書二零二五年
- 煤炭公司股權(quán)轉(zhuǎn)讓協(xié)議二零二五年
- 2025分成合同樣本:網(wǎng)絡(luò)課程推廣協(xié)議書(比例分成)、委托生產(chǎn)管理合同(利潤分攤)、利潤共享協(xié)議書
- 2025勞務(wù)派遣合同(合同范本)
- 江蘇省事業(yè)單位招聘考試綜合知識與能力素質(zhì)真題及解析(管理類和其他類)
- 慢性心力衰竭的護理課件整理
- 刷子李-虞大明課件
- 弱視的診斷與治療課件
- 測量儀器自檢記錄表(全站儀)
- 工程質(zhì)量目標質(zhì)量管理體系及技術(shù)組織措施
- 部編版小學(xué)一年級下冊寫字表田字格版字帖
- 中國風古人讀書教學(xué)課件PPT模板
- GB∕T 36665-2018 船舶和海上技術(shù) 船舶系泊和拖帶設(shè)備十字帶纜樁
- GB∕T 22517.6-2020 體育場地使用要求及檢驗方法 第6部分:田徑場地
- 箱梁預(yù)制場建設(shè)施工危險源辨識及風險分析
評論
0/150
提交評論