




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第三章習(xí)題1. 按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度,回答: 如進(jìn)站的車廂序列為123,則可能得到的出站車廂序列是什么?如進(jìn)站的車廂序列為123456,能否得到435612和135426的出站序列,并說明原因。(即寫出以“S”表示進(jìn)棧、以“X”表示出棧的棧操作序列)。2. 設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素,其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列
2、重復(fù)執(zhí)行下列4步操作:(1) 輸出隊(duì)首元素;(2) 把隊(duì)首元素值插入到隊(duì)尾;(3) 刪除隊(duì)首元素;(4) 再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止,得到輸出序列: (1) A、C、E、C、C
3、 (2) A、C、E(3) A、C、E、C、C、C (4) A、C、E、C3. 給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別??张c棧滿?4.
4、按照四則運(yùn)算加、減、乘、除和冪運(yùn)算()優(yōu)先關(guān)系的慣例,畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程: AB5. 試寫一個(gè)算法,判斷依次讀入的一個(gè)以為結(jié)束符的字母序列,是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如,a+b&b+a是屬該模式的字符序列,而+&則不是。6.
5、160; 假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法,將一個(gè)通常書寫形式且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。7. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。8. 要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用, 設(shè)置一個(gè)標(biāo)志域tag , 以tag為
6、0或1來區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿,請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。9. 簡(jiǎn)述以下算法的功能(其中棧和隊(duì)列的元素類型均為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) 實(shí)習(xí)題1 回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫一個(gè)算法,判斷依次讀入的一個(gè)以為結(jié)束符的字母序列,是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如,a+b&b+a是屬該模式的字符序列,而+&則不是。2 停車場(chǎng)管理。設(shè)停車場(chǎng)是一個(gè)可停放n輛車的狹長(zhǎng)通道,且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)內(nèi),汽車按到達(dá)的先后次序,由北向南依次
10、排列(假設(shè)大門在最南端)。若車場(chǎng)內(nèi)已停滿n輛 車,則后來的汽車需在門外的便道上等候,當(dāng)有車開走時(shí),便道上的第一輛車即可開入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí),在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓 路,待該輛車開出大門后,其它車輛再按原次序返回車場(chǎng)。每輛車離開停車場(chǎng)時(shí),應(yīng)按其停留時(shí)間的長(zhǎng)短交費(fèi)(在便道上停留的時(shí)間不收費(fèi))。試編寫程序,模擬上述管理過程。要求以順序棧模擬停車場(chǎng),以鏈隊(duì)列模擬便道。從終端讀入汽車到達(dá)或離去的數(shù)據(jù),每組數(shù)據(jù)包括三項(xiàng):是“到達(dá)”還是“離去”;汽車牌照號(hào)碼;“到達(dá)”或“離去”的時(shí)刻。與每組輸入信息相應(yīng)的輸出信息為:如果是到達(dá)的車輛,則輸出其在停車場(chǎng)中或便道上的位置;如果是離去的車
11、輛,則輸出其在停車場(chǎng)中停留的時(shí)間和應(yīng)交的費(fèi)用。(提示:需另設(shè)一個(gè)棧,臨時(shí)停放為讓路而從車場(chǎng)退出的車。)3 商品貨架管理。商品貨架可以看成一個(gè)棧,棧頂商品的生產(chǎn)日期最早,棧底商品的生產(chǎn)日期最近。上貨時(shí),需要倒貨架,以保證生產(chǎn)日期較近的商品在較下的位置。用隊(duì)列和棧作為周轉(zhuǎn),實(shí)現(xiàn)上述管理過程。第三章答案3.1按3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度,回答:(1) 如進(jìn)站的車廂序列為123,則可能得到的出站車廂序列是什么?(2) 如進(jìn)站的車廂序列為12
12、3456,能否得到435612和135426的出站序列,并說明原因(即寫出以“S”表示進(jìn)棧、“X”表示出棧的棧序列操作)?!窘獯稹浚?)可能得到的出站車廂序列是:123、132、213、231、321。(2)不能得到435612的出站序列。因?yàn)橛蠸(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此時(shí)按照“后進(jìn)先出”的原則,出棧的順序必須為X(2)X(1)。能得到135426的出站序列。因?yàn)橛蠸(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。 3.3給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別??张c
13、棧滿?【解答】(1)順序棧 (top用來存放棧頂元素的下標(biāo))判斷棧S空:如果S->top=-1表示棧空。判斷棧S滿:如果S->top=Stack_Size-1表示棧滿。(2) 鏈棧(top為棧頂指針,指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn))判斷??眨喝绻鹴op->next=NULL表示???。判斷棧滿:當(dāng)系統(tǒng)沒有可用空間時(shí),申請(qǐng)不到空間存放要進(jìn)棧的元素,此時(shí)棧滿。 3 4照四則運(yùn)算加、減、乘、除和冪運(yùn)算的優(yōu)先慣例,畫出對(duì)下列表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程:A-B*C/D+
14、EF【解答】3 5寫一個(gè)算法,判斷依次讀入的一個(gè)以為結(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請(qǐng)輸入字符序列:”); 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)隊(duì)列不損失一個(gè)空間全部都能得到利用,設(shè)置一個(gè)標(biāo)志tag,以tag為0或1來區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿,請(qǐng)編寫與此相應(yīng)的入隊(duì)與出隊(duì)算法?!窘獯稹咳腙?duì)算法:int EnterQueue
20、(SeqQueue *Q, QueueElementType x) /*將元素x入隊(duì)*/ if(Q->front=Q->front && tag=1) /*隊(duì)滿*/ return(FALSE); if(Q->front=Q->front && tag=0) /*x入隊(duì)前隊(duì)空,x入
21、隊(duì)后重新設(shè)置標(biāo)志*/ tag=1;Q->elememtQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE; /*設(shè)置隊(duì)尾指針*/Return(TRUE); 出隊(duì)算法: int DeleteQueue( SeqQueue *Q , QueueElementType *x) /*刪除隊(duì)頭元素,用x返回其值*/if(Q->
22、front=Q->rear && tag=0) /*隊(duì)空*/ return(FALSE);*x=Q->elementQ->front;Q->front=(Q->front+1)%MAXSIZE; /*重新設(shè)置隊(duì)頭指針*/if(Q->front=Q->rear) tag=0; /*隊(duì)頭元素出隊(duì)后隊(duì)列為空,重新設(shè)置標(biāo)志域*/Return(TUUE);
23、 編寫求解Hanoi問題的算法,并給出三個(gè)盤子搬動(dòng)時(shí)的遞歸調(diào)用過程。【解答】算法: void hanoi (int n ,char x, char y, char z) /*將塔座X上按直徑由小到大且至上而下編號(hào)為1到n的n個(gè)圓盤按規(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號(hào)搬到C Move(A->B) 2號(hào)搬到B Hanoi(1,C,A,B) move(C->B) 1號(hào)搬到B Move(A->C)&
26、#160; 3號(hào)搬到CHanoi(2,B,A,C) Hanoi(1,B,C,A) move(B->A) 1號(hào)搬到A Move(B->C)
27、0; 2號(hào)搬到C Hanoi(1,A,B,C) move(A->C) 1號(hào)搬到C 提示:第3章 限定性線性表 棧和隊(duì)列習(xí)題1. 按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度,回答: 如進(jìn)站的車廂序列為123,則可能得到的出站車廂序列是什么?
28、123、213、132、231、321(312)如進(jìn)站的車廂序列為123456,能否得到435612和135426的出站序列,并說明原因。(即寫出以“S”表示進(jìn)棧、以“X”表示出棧的棧操作序列)。SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素,其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作:(1)
29、 輸出隊(duì)首元素;(2) 把隊(duì)首元素值插入到隊(duì)尾;(3) 刪除隊(duì)首元素;(4) 再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止,
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 (輸出隊(duì)首元素A) A、B、C、D、E、A (把隊(duì)首元素A插入到隊(duì)尾) B、C、D、E、A (刪除隊(duì)首元素A) C、D、E、A (再次刪除隊(duì)首元素B) C、D、E、A (輸出隊(duì)首元素C
32、) C、D、E、A、C (把隊(duì)首元素C插入到隊(duì)尾) D、E、A、C (刪除隊(duì)首元素C) E、A、C (再次刪除隊(duì)首元素D) 3. 給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別??张c棧滿?4. 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算
33、()優(yōu)先關(guān)系的慣例,畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程: AB5. 試寫一個(gè)算法,判斷依次讀入的一個(gè)以為結(jié)束符的字母序列,是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序列。例如,a+b&b+a是屬該模式的字符序列,而+&則不是。提示:(1)
34、60; 邊讀邊入棧,直到&(2) 邊讀邊出棧邊比較,直到 6. 假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法,將一個(gè)通常書寫形式(中綴)且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式(后綴)。提示:例:中綴表達(dá)式:a+b 后綴表達(dá)式: ab+中綴表達(dá)式:a+b×
35、;c 后綴表達(dá)式: abc×+中綴表達(dá)式:a+b×c-d 后綴表達(dá)式: abc×+d-中綴表達(dá)式:a+b×c-d/e 后綴表達(dá)式: abc×+de/-中綴表達(dá)式:a+b×(c-d)-e/f 后綴表達(dá)式: abcd-×+ef/-·
36、160; 后綴表達(dá)式的計(jì)算過程:(簡(jiǎn)便)順序掃描表達(dá)式,(1) 如果是操作數(shù),直接入棧;(2) 如果是操作符op,則連續(xù)退棧兩次,得操作數(shù)X, Y,計(jì)算X op Y,并將結(jié)果入棧。· 如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式?順序掃描中綴表達(dá)式,(1)如果是操作數(shù),直接輸出;(2)如果是操作符op2,則與棧頂操作符op1比較:如果op2 > op1,則op2入棧;如果op2 = op1,則脫括號(hào);如果op2 < op1,則輸出op1; 7.
37、 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。提示: 參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)隊(duì)列不損失一個(gè)空間全部都能得到利用, 設(shè)置一個(gè)標(biāo)志域tag , 以tag為0或1來區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿,請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。提示: 初始狀態(tài):front=0, rear=0, tag=0 隊(duì)空條件:front=rear, tag=0 隊(duì)滿條件:front=rear, tag=1 其它狀態(tài):front !=rear, tag=0(或1、2) 入隊(duì)操作:(入隊(duì)
39、)if (front=rear) tag=1;(或直接tag=1) 出隊(duì)操作:(出隊(duì))tag=0; 問題:如何明確區(qū)分隊(duì)空、隊(duì)滿、非空非滿三種情況? 9. 簡(jiǎn)述以下算法的功能(其中棧和隊(duì)列的元素類型均為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等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 營(yíng)業(yè)執(zhí)照申請(qǐng)書
- 跳高運(yùn)動(dòng)會(huì)的廣播稿
- 小學(xué)一年級(jí)數(shù)學(xué)兩位數(shù)加減一位數(shù)同步練習(xí)試題帶答案
- 貧困捐款倡議書
- 金風(fēng)年終總結(jié)
- 質(zhì)量管理員面試自我介紹
- 針刺傷預(yù)防與處理措施
- 中國(guó)政治思想史知到課后答案智慧樹章節(jié)測(cè)試答案2025年春南昌大學(xué)
- 輪椅轉(zhuǎn)運(yùn)流程指引
- 人教寧夏 九年級(jí) 下冊(cè) 語文 第四單元《 短文兩篇》習(xí)題課 課件
- GB/T 22500-2024動(dòng)植物油脂紫外吸光度的測(cè)定
- 肺結(jié)核宣傳課件下載
- (高鴻業(yè))微觀經(jīng)濟(jì)學(xué)習(xí)題解析+微觀經(jīng)濟(jì)學(xué)題庫(kù)解析
- 躲在蚊子后面的大象讀書
- 6S管理控制程序文件
- 華為認(rèn)證HCIA-5G(H35-660)考試題附答案
- 消防管道及設(shè)備安裝技術(shù)交底
- 精裝修項(xiàng)目主要分項(xiàng)工程施工技術(shù)方案
- 四川省成都市航天中學(xué)2025屆高三二診模擬考試物理試卷含解析
- 巧繪節(jié)氣圖(教學(xué)設(shè)計(jì))-2024-2025學(xué)年二年級(jí)上冊(cè)綜合實(shí)踐活動(dòng)蒙滬版
- 《2024年 《法學(xué)引注手冊(cè)》示例》范文
評(píng)論
0/150
提交評(píng)論