數(shù)據(jù)結(jié)構(gòu)第三章測(cè)驗(yàn)

1、第三章習(xí)題按圖3.1（b）所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答：如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？如進(jìn)站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進(jìn)棧、以“X”表示出棧的棧操作序列）。設(shè)隊(duì)列中有A、B、C、DE這5個(gè)元素，其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作：（1）輸出隊(duì)首元素；（2）把隊(duì)首元素值插入到隊(duì)尾；（3）刪除隊(duì)首元素；（4）再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止，得到輸出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C給

2、出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（f）優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：ABC/D+EfF試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1+3&31則不是。假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注

3、意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。要求循環(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ì)算法。簡(jiǎn)述以下算法的功能（其中棧和隊(duì)列的元素類型均為int）：（1）voidproc_1（StackS）inti,n,A255;n=0;while(!EmptyStack(S)n+;Pop(&S,&An);for(i=1;itop=-1表示棧空。判斷棧S滿：如果S-top=Stack_Size-1表示棧滿。(2)鏈棧(top為棧頂指針，指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn))判斷棧空：如果to

4、p-next=NULL表示?？张袛鄺M：當(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+EfF【解答】OVSOPTROVSOPTR,+,=OPTR,1VV生成A-T(2)0TA,+OPTF?7,生成T(1)/DOVSOPTROVSOPTR運(yùn)算結(jié)果TT(3)運(yùn)算結(jié)果T(2)ovsOPTR右邊畀生成T(2)+T右邊界PTR；t1生成EtF運(yùn)算結(jié)果T(4)OVS運(yùn)算結(jié)果T(5)OVSOPTR3.5寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否形如序列1&序列2的

5、字符序列。序列1和序列2中都不含&,且序列2是序列1的逆序列。例如，a+b&b+a是屬于該模式的字符序列，而1+3&3則不是。解答】算法如下：intIsHuiWen()Stack*S;Charch,temp;InitStack(&S);Printf(n請(qǐng)輸入字符序列：”)；Ch=getchar();While(ch!=&)/*序列1入棧*/Push(&S,ch)；ch=getchar()；do/*判斷序列2是否是序列1的逆序列*/ch=getchar()；Pop(&S,&temp)；if(ch!=temp)/*序列2不是序列1的逆序列*/return(FALSE);printf(n“NO”);

6、while(ch!=while(ch!=&!IsEmpty(&S)if(ch=&IsEmpty(&S)return(TRUE);printf(n“YES”);/*序列2是序列1的逆序列*/elsereturn(FALSE);printf(n“NO”);/*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ì)算法：intEnterQueue(SeqQueue*Q,QueueElementTypex)/*將元素x入隊(duì)*/if(Q-front=Q-front&

7、tag=1)/*隊(duì)滿*/return(FALSE);if(Q-front=Q-front&tag=0)/*x入隊(duì)前隊(duì)空，x入隊(duì)后重新設(shè)置標(biāo)志*/tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;/*設(shè)置隊(duì)尾指針*/Return(TRUE);出隊(duì)算法：intDeleteQueue(SeqQueue*Q,QueueElementType*x)/*刪除隊(duì)頭元素，用x返回其值*/if(Q-front=Q-rear&tag=0)/*隊(duì)空*/return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXS

8、IZE;/*重新設(shè)置隊(duì)頭指針*/if(Q-front=Q-rear)tag=0;/*隊(duì)頭元素出隊(duì)后隊(duì)列為空，重新設(shè)置標(biāo)志域*/Return(TUUE);編寫求解Hanoi問題的算法，并給出三個(gè)盤子搬動(dòng)時(shí)的遞歸調(diào)用過程?！窘獯稹克惴ǎ簐oidhanoi(intn,charx,chary,charz)/*將塔座X上按直徑由小到大且至上而下編號(hào)為1到n的n個(gè)圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座*/if(n=1)move(x,1,z);elseHanoi(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,

9、C,B):Hanoi(1,A,B,C)move(A-C)1號(hào)搬到CMove(A-B)2號(hào)搬到BHanoi(1,C,A,B)move(C-B)1號(hào)搬到BMove(A-C)3號(hào)搬到CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B-A)1號(hào)搬到AMove(B-C)2號(hào)搬到CHanoi(1,A,B,C)move(A-C)1號(hào)搬到C提示：第3章限定性線性表?xiàng)：完?duì)列習(xí)題按圖3.1（b）所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答：如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？123、213、132、231、321（312）如進(jìn)站的車廂序列為123456，能否得到4

10、35612和135426的出站序列，并說明原因。（即寫出以“S”表示進(jìn)棧、以“X”表示出棧的棧操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素，其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作：1）輸出隊(duì)首元素；2）把隊(duì)首元素值插入到隊(duì)尾；3）刪除隊(duì)首元素；4）再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止，則是否可能得到輸出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C提示：A、B、C、D、E（輸出隊(duì)首元素A）A、B、C、D、E、A（把隊(duì)首元素A插入到隊(duì)尾）B、C、D、E

11、、A（刪除隊(duì)首元素A）C、D、E、A（再次刪除隊(duì)首元素B）C、D、E、A（輸出隊(duì)首元素C）C、D、E、A、C（把隊(duì)首元素C插入到隊(duì)尾）D、E、A、C（刪除隊(duì)首元素C）E、A、C（再次刪除隊(duì)首元素D）給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？按照四則運(yùn)算加、減、乘、除和幕運(yùn)算（f）優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：ABC/D+EfF試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1

12、+3&31則不是。提示：（1）邊讀邊入棧，直到&（2）邊讀邊出棧邊比較，直到假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式（中綴）且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式（后綴）。提示：例：中綴表達(dá)式：a+b后綴表達(dá)式：ab+中綴表達(dá)式：a+bxc后綴表達(dá)式：abcx+中綴表達(dá)式：a+bxc-d后綴表達(dá)式：abcx+d-中綴表達(dá)式：a+bxc-d/e后綴表達(dá)式：abcx+de/-中綴表達(dá)式：a+bx（c-d）-e/f后綴表達(dá)式：abcd-x+ef/-后綴表達(dá)式的計(jì)算過程：（簡(jiǎn)便）順序掃描表達(dá)式，（1）如果是操作數(shù)，直接入棧；（2）如果是操作符op,則連續(xù)退棧兩次，得操作

13、數(shù)X,Y,計(jì)算XopY,并將結(jié)果入棧。如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？順序掃描中綴表達(dá)式，（1）如果是操作數(shù)，直接輸出;(2)如果是操作符op?,則與棧頂操作符opi比較：如果0P2opi,貝S0P2入棧；如果op2=op1,則脫括號(hào)；如果op2opi,則輸出opi；假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。提示：參先畫圖.typedefLinkListCLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intD

14、eleteQueue(CLQueueQ,QueueElementType*x)要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用,設(shè)置一個(gè)標(biāo)志域tag,以tag為0或i來區(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ì))if(front=rear)tag=1；(或直接tag=1)出隊(duì)操作：(出隊(duì))tag=0；問題：如何明確區(qū)分隊(duì)空、隊(duì)滿、非空非滿三種情況？簡(jiǎn)述以下算法的

15、功能(其中棧和隊(duì)列的元素類型均為int)：(1)voidproc_1(StackS)inti,n,A255;n=0;while(!EmptyStack(S)n+;Pop(&S,&An);for(i=1;i=n;i+)Push(&S,Ai);將棧S逆序。(2)voidproc_2(StackS,inte)StackT;intd;InitStack(&T);while(!EmptyStack(S)d);Pop(&S,&d);if(d!=e)Push(&T,while(!EmptyStack(T)Pop(&T,&d);Push(&S,d);刪除棧S中所有等于e的元素。3)voidproc_3(Que

16、ue*Q)StackS;intd;InitStack(&S);while(!EmptyQueue(*Q)DeleteQueue(Q,&d);Push(&S,d);while(!EmptyStack(S)Pop(&S,&d);EnterQueue(Q，d)將隊(duì)列Q逆序。實(shí)習(xí)題1回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而1+3&31則不是。2.停車場(chǎng)管理。設(shè)停車場(chǎng)是一個(gè)可停放n輛車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)內(nèi)，汽車按到達(dá)的先后次序，由北向南依次排列（假設(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)）。試編寫程序，模擬上述管理過程。要求以順序棧模