數(shù)據(jù)結(jié)構(gòu)考研試題精選及答案第三章棧和隊列答案

1、第三章 棧和隊列答案一、選擇題 1.B2.1B2.2A2.3B2.4D2.5.C3.B4.D5.D6.C7.D8.B9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD二、判斷題1.2.3. 4. 5.6.7.8. 9. 10.11. 12.13. 14.15. 16.17.18.19.20. 部分答案解釋如下。1、 尾遞歸的消除就不需用棧2、 這個數(shù)是前序序列為1,2,3

2、,n，所能得到的不相似的二叉樹的數(shù)目。三、填空題1、操作受限（或限定僅在表尾進行插入和刪除操作） 后進先出 2、棧 3、3 1 2 4、23 100CH 5、0 n+1 top1+1=top26、兩棧頂指針值相減的絕對值為1（或兩棧頂指針相鄰）。7、(1滿 (2空 (3n (4棧底 (5兩棧頂指針相鄰（即值之差的絕對值為1）8、鏈式存儲結(jié)構(gòu) 9、SSSS 10、data+top=x； 11、23.12.3*2-4/34.5*7/+108.9/+（注：表達式中的點(.表示將數(shù)隔開，如23.12.3是三個數(shù)）12、假溢出時大量移動數(shù)據(jù)元素。 13、(M+1 MOD N (M+1% N； 14、隊列

3、 15、先進先出 16、先進先出 17、s=(LinkedListmalloc(sizeof(LNode； s-data=x;s-next=r-next；r-next=s；r=s；18、犧牲一個存儲單元 設(shè)標記19、（TAIL+1）MOD M=FRONT (數(shù)組下標0到M-1，若一定使用1到M，則取模為0者，值改取M20、sq.front=(sq.front+1%(M+1；return(sq.data(sq.front；(sq.rear+1%(M+1=sq.front；21、棧 22、（rear-front+m）% m； 23、（R-P+N）% N；24、（1）ai或a1 （2）ai （3）p

4、op（s）或s1；25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b）26、（1）T0（2）i （ 3 ） T0 （ 4 ） top （ 5 ） top+1 （ 6 ） true （ 7 ） i-1 （ 8 ） top-1 （ 9 ） T+wi （ 10 ） false 四、應(yīng)用題1、棧是只準在一端進行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進先出（LIFO）表。2、隊列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的一端叫隊頭。最先插入隊的

5、元素最先離開（刪除），故隊列也常稱先進先出（FIFO）表。3、用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)（隊尾插入和隊頭刪除），容易造成“假溢出”現(xiàn)象，即隊尾已到達一維數(shù)組的高下標，不能再插入，然而隊中元素個數(shù)小于隊列的長度（容量）。循環(huán)隊列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊列下，通常采用“犧牲一個存儲單元”或“作標記”的方法解決“隊滿”和“隊空”的判定問題。4、（1）通常有兩條規(guī)則。第一是給定序列中S的個數(shù)和X的個數(shù)相等；第二是從給定序列的開始，到給定序列中的任一位置，S的個數(shù)要大于或等于X的個數(shù)。（2）可以得到相同的輸出元素序列。例如，輸入元素

6、為A，B，C，則兩個輸入的合法序列ABC和BAC均可得到輸出元素序列ABC。對于合法序列ABC，我們使用本題約定的SSS操作序列；對于合法序列BAC，我們使用SSS操作序列。5、三個：CDEBA，CDBEA，CDBAE6、輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終

7、結(jié)果135426。7、能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。8、借助棧結(jié)構(gòu)，n個入棧元素可得到1/(n+1(2n）！/（n!*n!）種出棧序列。本題4個元素，可有14種出棧序列，abcd和dcba就是其中兩種。但dabc和adbc是不可能得到的兩種。9、不能得到序列2，5，3，4，6。?？梢杂脝捂湵韺崿F(xiàn)，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設(shè)頭結(jié)點。10、如果ij，則對于pipj的情況，則說明要將pj

8、壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對于ijk，不可能出現(xiàn)pjpkpi的輸出序列。換句話說，對于輸入序列1，2，3，不可能出現(xiàn)3，1，2的輸出序列。11、（1）能得到325641。在123依次進棧后，3和2出棧，得部分輸出序列32；然后4，5入棧，5出棧，得部分出棧序列325；6入棧并出棧，得部分輸出序列3256；最后退棧，直到?？?。得輸出序列325641。其操作序列為AAADDAADADDD。（2）不能得到輸出順序為154623的序列。部分合法操作序列為ADAAAADDAD，得到部分輸出序列1546后，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列15462

9、3。12、（1）一個函數(shù)在結(jié)束本函數(shù)之前，直接或間接調(diào)用函數(shù)自身，稱為遞歸。例如，函數(shù)f在執(zhí)行中，又調(diào)用函數(shù)f自身，這稱為直接遞歸；若函數(shù)f在執(zhí)行中，調(diào)用函數(shù)g，而g在執(zhí)行中，又調(diào)用函數(shù)f，這稱為間接遞歸。在實際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。（2）遞歸程序的優(yōu)點是程序結(jié)構(gòu)簡單、清晰，易證明其正確性。缺點是執(zhí)行中占內(nèi)存空間較多，運行效率低。（3）遞歸程序執(zhí)行中需借助棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。（4）遞歸程序的入口語句和出口語句一般用條件判斷語句來實現(xiàn)。遞歸程序由基本項和歸納項組成?；卷検沁f歸程序出口，即不再遞歸即可求出結(jié)果的部分；歸納項是將原來問題化成簡單的且與原來形式一樣的問題，即向著“基

10、本項”發(fā)展，最終“到達”基本項。13、函數(shù)調(diào)用結(jié)束時vol=14。執(zhí)行過程圖示如下： vol（4） vol(4=vol(3+514 =vol(2+3+5=vol(1+4+3+5vol（3）+5 =vol(0+2+4+3+59 =0+2+4+3+5=14vol（2）+36vol（1）+42vol（0）+2014、過程p遞歸調(diào)用自身時，過程p由內(nèi)部定義的局部變量在p的2次調(diào)用期間，不占同一數(shù)據(jù)區(qū)。每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是遞歸定義所決定，用“遞歸工作?！眮韺崿F(xiàn)。15、設(shè)Hn為n個盤子的Hanoi塔的移動次數(shù)。(假定n個盤子從鋼針X移到鋼針Z，可借助鋼針Y則 Hn =2Hn-1+1 /先將n-1個

11、盤子從X移到Y(jié)，第n個盤子移到Z，再將那n-1個移到Z=2（2Hn-2+1）+1=22 Hn-2+2+1=22（2Hn-3+1）+2+1=23 Hn-3+22+2+1= 2k Hn-k+2k-1 +2k-2 +21 +20=2n-1 H1+2n-2+2n-3+21+20因為H1=1，所以原式Hn=2n-1+2n-2+21+20=2n-1故總盤數(shù)為n的Hanoi塔的移動次數(shù)是2n-1。16、運行結(jié)果為：1 2 1 3 1 2 1（注：運行結(jié)果是每行一個數(shù)，為節(jié)省篇幅，放到一行。）17、兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設(shè)共享數(shù)組為SMAX，則一個棧頂指針為-

12、1，另一個棧頂指針為MAX時，棧為空。用C寫的入棧操作push（i，x）如下：2014年MBA面試英文自我介紹模版2014年MBA聯(lián)考策略：面試英文自我介紹模版MY BACKGROUNDelemtype sMAXI was born in a small village of Shan Dong Province on April 4th，int top2In 1986 I was admitted by University of International Business and Economics （or： UIBE） to pursue a bachelor degree in Ec

13、onomics. My major is accounting in Department of International Business Management. The undergraduate education gave me a wide range of vision and taught me how to cooperate with others. I developed several professional interests in Accounting， Finance， and International Trade.The following eight-ye

14、ar working experience offered me a good chance to give full play to my creativity， intelligence and diligence. In 1990-1993， I worked as an assistant to funding manager in China National Technical Import and Export Corporation. In 1993-present， I was employed by China Kingdom Import and Export Corpo

15、ration to be the Manger of Financial and Accounting Division.elemtype 的元素的一維數(shù)組，由兩個棧共享其空間。 i 的值為 0 或 1 ， After graduating from UIBEelemtype的元素。本算法將x壓入棧中。如壓棧成功，返回 after one years hard work， I developed the internal banking system within the corporation based on the actual funding supply and need of th

16、e different divisions and projects. This internal banking system made full use of the corporationWHY CHOOSE YOUR MBA PROGRAM？ds.top1-ds.top0=1）printf（“棧滿”）；return（s business education. I am sure that， with my extensive business experienceswitch（i）case 0：ds.s+ds.topi=x；break；case 1：ds.s-ds.topi=x；ret

17、urn（1）；/入棧成功。18、本程序段查找棧S中有無整數(shù)為k的元素，如有，則刪除。采用的辦法使用另一個棧T。在S棧元素退棧時，若退棧元素不是整數(shù)k，則壓入T棧。遇整數(shù)k，k不入T棧，然后將T棧元素全部退棧，并依次壓入棧S中，實現(xiàn)了在S中刪除整數(shù)k的目的。若S中無整數(shù)k，則在S退成空棧后，再將T棧元素退棧，并依次壓入S棧。直至T?？铡＿@后一種情況下S棧內(nèi)容操作前后不變。19、中綴表達式8-(3+5*(5-6/2）的后綴表達式是： 8 3 5 + 5 6 2 / - * -棧的變化過程圖略（請參見22題），表達式生成過程為：中綴表達式exp1轉(zhuǎn)為后綴表達式exp2的規(guī)則如下：設(shè)操作符棧s，初始為

18、空棧后，壓入優(yōu)先級最低的操作符#。對中綴表達式從左向右掃描，遇操作數(shù)，直接寫入exp2；若是操作符（記為w），分如下情況處理，直至表達式exp1掃描完畢。（1）w為一般操作符（+，-，*，/等），要與棧頂操作符比較優(yōu)先級，若w優(yōu)先級高于棧頂操作符，則入棧；否則，棧頂運算符退棧到exp2，w再與新棧頂操作符作上述比較處理，直至w入棧。（2）w為左括號（），w入棧。（3）w為右括號（），操作符棧退棧并進入exp2，直到碰到左括號為止，左括號退棧（不能進入exp2），右括號也丟掉，達到exp2中消除括號的目的。（4）w為#，表示中綴表達式exp1結(jié)束，操作符棧退棧到exp2，直至碰到#，退棧，整個操

19、作結(jié)束。這里，再介紹一種簡單方法。中綴表達式轉(zhuǎn)為后綴表達式有三步：首先，將中綴表達式中所有的子表達式按計算規(guī)則用嵌套括號括起來；接著，順序?qū)⒚繉ㄌ栔械倪\算符移到相應(yīng)括號的后面；最后，刪除所有括號。例如，將中綴表達式8-(3+5*(5-6/2）轉(zhuǎn)為后綴表達式。按如上步驟：執(zhí)行完上面第一步后為：(8-(3+5*(5-(6/2；執(zhí)行完上面第二步后為：(8(35+(5(62/-*- ；執(zhí)行完上面第三步后為：8 3 5 + 5 6 2 / - * - ?？捎妙愃品椒▽⒅芯Y表達式轉(zhuǎn)為前綴表達式。20、中綴表達式轉(zhuǎn)為后綴表達式的規(guī)則基本上與上面19題相同，不同之處是對運算符*優(yōu)先級的規(guī)定。在算術(shù)運算中，先

20、乘除后加減，先括號內(nèi)后括號外，相同級別的運算符按從左到右的規(guī)則運算。而對*運算符，其優(yōu)先級同常規(guī)理解，即高于加減乘除而小于左括號。為了適應(yīng)本題中“從右到左計算”的要求，規(guī)定棧頂運算符*的級別小于正從表達式中讀出的運算符*，即剛讀出的運算符*級別高于棧頂運算符*，因此也入棧。下面以A*B*C為例說明實現(xiàn)過程。讀入A，不是操作符，直接寫入結(jié)果表達式。再讀入*，這里規(guī)定在讀入*后，不能立即當乘號處理，要看下一個符號，若下個符號不是*，則前個*是乘號。這里因為下一個待讀的符號也是*，故認為*是一個運算符，與運算符棧頂比較（運算符棧頂初始化后，首先壓入#作為開始標志），其級別高于#，入棧。再讀入B，直接

21、進入結(jié)果表達式。接著讀入*，與棧頂比較，均為*，我們規(guī)定，后讀入的*級別高于棧頂?shù)?，因此*入棧。接著讀入C，直接到結(jié)果表達式?，F(xiàn)在的結(jié)果（后綴）表達式是ABC。最后讀入#，表示輸入表達式結(jié)束，這時運算符棧中從棧頂?shù)綏５子袃蓚€*和一個#。兩個運算符*退棧至結(jié)果表達式，結(jié)果表達式變?yōu)锳BC*。運算符棧中只剩#，退棧，運算結(jié)束。21、（1）sum=21。當x為局部變量時，每次遞歸調(diào)用，都要給局部變量分配存儲單元，故x數(shù)值4，9，6和2均保留，其遞歸過程示意圖如下： sum（4）21sum（3）+4 （x=4）17sum（2）+9 （x=9）8sum（1）+6 （x=6）2sum（0）+2 （x=2

22、）0(2 sum=8,當x為全局變量時，在程序的整個執(zhí)行期間，x只占一個存儲單元，先后讀入的4個數(shù)(4,9,6,2,僅最后一個起作用。當遞歸調(diào)用結(jié)束，逐層返回時sum:=sum(n-1+x表達式中，x就是2，所以結(jié)果為sum=8。22、設(shè)操作數(shù)棧是opnd，操作符棧是optr，對算術(shù)表達式A-B*C/D-EF求值，過程如下：步驟opnd棧optr棧輸入字符主要操作 初始#A-B*C/D-EF#PUSH(OPTR,#1A#A-B*C/D-EF#PUSH(OPND,A2A# -B*C/D-EF#PUSH(OPTR,-3AB# -B*C/D-EF#PUSH(OPND,B4AB# - *C/D-EF#

23、PUSH(OPTR,*5ABC# - *C/D-EF#PUSH(OPND,C6AT(T=B*C# - /D-EF#PUSH(OPND,POP(OPND*POP(OPNDPUSH(OPTR,/7ATD# - /D-EF#PUSH(OPND,D8AT(T=T/DT(T=A-T# - # - -EF#x=POP(OPND;y=POP(OPNDPUSH(OPND,y/x;x=POP(OPND;y=POP(OPND;PUSH(OPND,y-xPUSH(OPTR,-9TE# -EF#PUSH(OPND,E10TE# -F#PUSH(OPTR, 11TEF# -F#PUSH(OPND,F12TETS(S=E

24、FR(R=T-S #-#X=POP(OPND Y=POP(OPNDPOP(OPTR PUSH(OPND,yxx=POP(OPND y=POP(OPNDPOP(OPTR PUSH(OPND,y-x 23、 步驟棧S1棧S2輸入的算術(shù)表達式（按字符讀入）初始A-B*C/D+E/F1AA-B*C/D+E/F2A-B*C/D+E/F3AB-B*C/D+E/F4AB-*C/D+E/F5ABC-*C/D+E/F6AT1（注：T1=B*C）-/D+E/F7AT1D-/D+E/F8AT2（注：T2=T1/D）T3 （注：T3=A-T2）-+E/F9T3E+E/F10T3E+/F11T3EF+/F12T3T4（

25、注：T4=E/F）T5（注：T5= T3+ T4）+24、XSXXXSSSXXSXXSXXSSSS25、S1和S2共享內(nèi)存中一片連續(xù)空間（地址1到m），可以將S1和S2的棧底設(shè)在兩端，兩棧頂向共享空間的中心延伸，僅當兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時，判斷為棧滿，當一個棧頂指針為0，另一個棧頂指針m+1時為兩棧均空。26、設(shè)棧S1和棧S2共享向量V1.m，初始時，棧S1的棧頂指針top0=0，棧S2的棧頂指針top1=m+1，當top0=0為左棧空，top1=m+1為右?？?；當top0=0并且top1=m+1時為全?？?。當top1-top0=1時為棧滿。27、（1）每個棧僅用一

26、個順序存儲空間時，操作簡便，但分配存儲空間小了，容易產(chǎn)生溢出，分配空間大了，容易造成浪費，各棧不能共享空間。（2）多個棧共享一個順序存儲空間，充分利用了存儲空間，只有在整個存儲空間都用完時才能產(chǎn)生溢出，其缺點是當一個棧滿時要向左、右棧查詢有無空閑單元。如果有，則要移動元素和修改相關(guān)的棧底和棧頂指針。當接近棧滿時，查詢空閑單元、移動元素和修改棧底棧頂指針的操作頻繁，計算復(fù)雜并且耗費時間。（3）多個鏈棧一般不考慮棧的溢出（僅受用戶內(nèi)存空間限制），缺點是棧中元素要以指針相鏈接，比順序存儲多占用了存儲空間。28、設(shè)top1和top2分別為棧1和2的棧頂指針（1）入棧主要語句if(top2-top1=1

27、 printf(“棧滿n”; exit(0;case1:top1+；SPACEtop1=x; /設(shè)x為入棧元素。case2:top2-；SPACEtop2=x;出棧主要語句case1：if（top1=-1） printf（“棧空n”）；exit（0）；top1-；return（SPACEtop1+1）； /返回出棧元素。case2：if（top2=N）printf（“?？課”）；exit（0）；top2+；return（SPACEtop2-1）； /返回出棧元素。（2）棧滿條件：top2-top1=1?？諚l件：top1=-1并且top2=N /top1=-1為左棧空，top2=N為右?？?9、

28、設(shè)順序存儲隊列用一維數(shù)組qm表示，其中m為隊列中元素個數(shù)，隊列中元素在向量中的下標從0到m-1。設(shè)隊頭指針為front，隊尾指針是rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。當front等于-1時隊空，rear等于m-1時為隊滿。由于隊列的性質(zhì)（“刪除”在隊頭而“插入”在隊尾），所以當隊尾指針rear等于m-1時，若front不等于-1，則隊列中仍有空閑單元，所以隊列并不是真滿。這時若再有入隊操作，會造成假“溢出”。其解決辦法有二，一是將隊列元素向前“平移”（占用0至rear-front-1）；二是將隊列看成首尾相連，即循環(huán)隊列（0.m-1）。在循環(huán)隊列下，仍定義fr

29、ont=rear時為隊空，而判斷隊滿則用兩種辦法，一是用“犧牲一個單元”，即rear+1=front（準確記是（rear+1）%m=front，m是隊列容量）時為隊滿。另一種解法是“設(shè)標記”方法，如設(shè)標記tag，tag等于0情況下，若刪除時導(dǎo)致front=rear為隊空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊滿。30、見上題29的解答。 31、參見上面29題。32、typedef struct nodeelemtype elemcqm; /m為隊列最大可能的容量。int front ,rear; /front和rear分別為隊頭和隊尾指針。cqnode;cqnode cq;(

30、1 初始狀態(tài)cq.front=cq.rear=0;(2 隊列空cq.front=cq.rear;(3 隊列滿(cq.rear+1%m=cq.front;33、棧的特點是后進先出，隊列的特點是先進先出。初始時設(shè)棧s1和棧s2均為空。（1）用棧s1和s2模擬一個隊列的輸入：設(shè)s1和s2容量相等。分以下三種情況討論：若s1未滿，則元素入s1棧；若s1滿，s2空，則將s1全部元素退棧，再壓棧入s2，之后元素入s1棧；若s1滿，s2不空（已有出隊列元素），則不能入隊。（2）用棧s1和s2模擬隊列出隊（刪除）：若棧s2不空，退棧，即是隊列的出隊；若s2為空且s1不空，則將s1棧中全部元素退棧，并依次壓入s

31、2中，s2棧頂元素退棧，這就是相當于隊列的出隊。若棧s1為空并且s2也為空，隊列空，不能出隊。（3）判隊空 若棧s1為空并且s2也為空，才是隊列空。討論：s1和s2容量之和是隊列的最大容量。其操作是，s1棧滿后，全部退棧并壓棧入s2（設(shè)s1和s2容量相等）。再入棧s1直至s1滿。這相當隊列元素“入隊”完畢。出隊時，s2退棧完畢后，s1棧中元素依次退棧到s2，s2退棧完畢，相當于隊列中全部元素出隊。在棧s2不空情況下，若要求入隊操作，只要s1不滿，就可壓入s1中。若s1滿和s2不空狀態(tài)下要求隊列的入隊時，按出錯處理。34、（1）隊空s.front=s.rear； /設(shè)s是sequeuetp類型變

32、量（2）隊滿：（s.rear+1）MOD MAXSIZE=s.front /數(shù)組下標為0. MAXSIZE-1具體參見本章應(yīng)用題第29題35、typedef structelemtp qm;int front,count; /front是隊首指針，count是隊列中元素個數(shù)。cqnode; /定義類型標識符。(1判空：int Empty(cqnode cq /cq是cqnode類型的變量 if(cq.count=0 return(1；else return(0; /空隊列入隊: int EnQueue(cqnode cq，elemtp xif(count=mprintf(“隊滿n”；exit(

33、0; cq.q(cq.front+count%m=x; /x入隊count+; return(1; /隊列中元素個數(shù)增加1,入隊成功。出隊: int DelQueue(cqnode cqif (count=0printf(“隊空n”；return(0;printf(“出隊元素”，cq.qcq.front;x=cq.qcq.front;cq.front=(cq.front+1%m; /計算新的隊頭指針。return(x(2 隊列中能容納的元素的個數(shù)為m。隊頭指針front指向隊頭元素。36、循環(huán)隊列中元素個數(shù)為（REAR-FRONT+N）%N。其中FRONT是隊首指針，指向隊首元素的前一位置；R

34、EAR是隊尾指針，指向隊尾元素；N是隊列最大長度。37、循環(huán)隊列解決了用向量表示隊列所出現(xiàn)的“假溢出”問題，但同時又出現(xiàn)了如何判斷隊列的滿與空問題。例如：在隊列長10的循環(huán)隊列中，若假定隊頭指針front指向隊頭元素的前一位置，而隊尾指針指向隊尾元素，則front=3，rear=7的情況下，連續(xù)出隊4個元素，則front=rear為隊空；如果連續(xù)入隊6個元素，則front=rear為隊滿。如何判斷這種情況下的隊滿與隊空，一般采取犧牲一個單元的做法或設(shè)標記法。即假設(shè)front=rear為隊空，而（rear+1）%表長=front為隊滿，或通過設(shè)標記tag。若tag=0，front=rear則為隊

35、空；若tag=1，因入隊而使得front=rear，則為隊滿。本題中隊列尾指針rear，指向隊尾元素的下一位置,listarrayrear表示下一個入隊的元素。在這種情況下，我們可規(guī)定，隊頭指針front指向隊首元素。當front=rear時為隊空，當（rear+1）%n=front時為隊滿。出隊操作（在隊列不空情況下）隊頭指針是front=（front+1）%n，38、既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是dbca。39、（1）4132 （2）4213 （3）423140、（1）隊空的初始條件：f=r=0；（2）執(zhí)行操作A3后，r=3；/ A3表示三次入隊

36、操作執(zhí)行操作D1后，f=1；/D1表示一次出隊操作執(zhí)行操作A5后，r=0；執(zhí)行操作D2后，f=3；執(zhí)行操作A1后，r=1；執(zhí)行操作D2后，f=5；執(zhí)行操作A4后，按溢出處理。因為執(zhí)行A3后，r=4，這時隊滿，若再執(zhí)行A操作，則出錯。41一般說，高級語言的變量名是以字母開頭的字母數(shù)字序列。故本題答案是:AP321,PA321,P3A21,P32A1,P321A。五、算法設(shè)計題1、題目分析兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時，s1棧頂指針為-1，s2棧頂為maxsize。兩棧頂指針相鄰時為棧滿。兩棧頂相向，迎面增長，棧頂指針指向棧頂元素。#define maxsize 兩棧共享順序存儲

37、空間所能達到的最多元素數(shù)#define elemtp int /假設(shè)元素類型為整型typedef structelemtp stackmaxsize; /?？臻gint top2; /top為兩個棧頂指針stk;stk s; /s是如上定義的結(jié)構(gòu)類型變量，為全局變量。(1入棧操作：int push(int i,int x/入棧操作。i為棧號，i=0表示左邊的棧s1，i=1表示右邊的棧s2，x是入棧元素。入棧成功返回1，否則返回0。if(i1printf(“棧號輸入不對”;exit(0;if(s.top1-s.top0=1 printf(“棧已滿n”;return(0;switch(icase 0

38、: s.stack+s.top0=x; return(1; break;case 1: s.stack-s.top1=x; return(1; /push（2） 退棧操作elemtp pop(int i/退棧算法。i代表棧號，i=0時為s1棧，i=1時為s2棧。退棧成功返回退棧元素，否則返回-1。if(i1printf(“棧號輸入錯誤n”；exit(0;switch(icase 0: if(s.top0=-1 printf(“?？課”；return（-1）；else return(s.stacks.top0-;case 1: if(s.top1=maxsize printf(“?？課”; re

39、turn(-1;else return(s.stacks.top1+;/算法結(jié)束算法討論 請注意算法中兩棧入棧和退棧時的棧頂指針的計算。兩棧共享空間示意圖略，s1棧是通常意義下的棧，而s2棧入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。2、#define maxsize ?？臻g容量void InOutS(int smaxsize/s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。int top=0; /top為棧頂指針，定義top=0時為?？铡or(i=1; i=n; i+ /n個整數(shù)序列作處理。scanf(“%d”,&x; /從鍵盤讀入整數(shù)序列。if(x!=-1 / 讀入的

40、整數(shù)不等于-1時入棧。if(top=maxsize-1printf(“棧滿n”;exit(0;else s+top=x; /x入棧。else /讀入的整數(shù)等于-1時退棧。if(top=0printf(“?？課”;exit(0; else printf(“出棧元素是%dn”,stop-；/算法結(jié)束。3、題目分析判斷表達式中括號是否匹配，可通過棧，簡單說是左括號時進棧，右括號時退棧。退棧時，若棧頂元素是左括號，則新讀入的右括號與棧頂左括號就可消去。如此下去，輸入表達式結(jié)束時，棧為空則正確，否則括號不匹配。int EXYX(char E,int n/E是有n字符的字符數(shù)組，存放字符串表達式，以#結(jié)束

41、。本算法判斷表達式中圓括號是否匹配。char s30; /s是一維數(shù)組，容量足夠大，用作存放括號的棧。int top=0; /top用作棧頂指針。stop= #; /#先入棧，用于和表達式結(jié)束符號#匹配。int i=0; /字符數(shù)組E的工作指針。while(Ei!= # /逐字符處理字符表達式的數(shù)組。switch(Eicase(: s+top=(; i+ ; break ;case: if(stop=(top-; i+; break;elseprintf(“括號不配對”;exit(0;case#: if(stop=#printf(“括號配對n”;return (1;else printf(“

42、括號不配對n”;return (0; /括號不配對default : i+; /讀入其它字符，不作處理。/算法結(jié)束。算法討論本題是用棧判斷括號匹配的特例：只檢查圓括號的配對。一般情況是檢查花括號（，）、方括號（，）和圓括號（，）的配對問題。編寫算法中如遇左括號（，或（）就壓入棧中，如遇右括號（，或），則與棧頂元素比較，如是與其配對的括號（左花括號，左方括號或左圓括號），則彈出棧頂元素；否則，就結(jié)論括號不配對。在讀入表達式結(jié)束符#時，棧中若應(yīng)只剩#，表示括號全部配對成功；否則表示括號不匹配。另外，由于本題只是檢查括號是否匹配，故對從表達式中讀入的不是括號的那些字符，一律未作處理。再有，假設(shè)棧容量

43、足夠大，因此入棧時未判斷溢出。4、題目分析逆波蘭表達式(即后綴表達式求值規(guī)則如下：設(shè)立運算數(shù)棧OPND,對表達式從左到右掃描(讀入，當表達式中掃描到數(shù)時，壓入OPND棧。當掃描到運算符時，從OPND退出兩個數(shù)，進行相應(yīng)運算，結(jié)果再壓入OPND棧。這個過程一直進行到讀出表達式結(jié)束符$，這時OPND棧中只有一個數(shù)，就是結(jié)果。float expr( /從鍵盤輸入逆波蘭表達式，以$表示輸入結(jié)束，本算法求逆波蘭式表達式的值。float OPND30; / OPND是操作數(shù)棧。init(OPND; /兩棧初始化。float num=0.0; /數(shù)字初始化。scanf (“%c”,&x;/x是字符型變量。w

44、hile(x!=$switchcase0=x=0&x=0&xjprintf(“序列非法n”；exit(0;i+; /不論Ai是I或O，指針i均后移。if(j!=k printf(“序列非法n”；return(false;else printf(“序列合法n”；return(true;/算法結(jié)束。算法討論在入棧出棧序列（即由I和O組成的字符串）的任一位置，入棧次數(shù)（I的個數(shù)）都必須大于等于出棧次數(shù)（即O的個數(shù)），否則視作非法序列，立即給出信息，退出算法。整個序列（即讀到字符數(shù)組中字符串的結(jié)束標記0），入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序列。6、題目分析表達式

45、中的括號有以下三對：（、）、，使用棧，當為左括號時入棧，右括號時，若棧頂是其對應(yīng)的左括號，則退棧，若不是其對應(yīng)的左括號，則結(jié)論為括號不配對。當表達式結(jié)束，若棧為空，則結(jié)論表達式括號配對，否則，結(jié)論表達式括號不配對。int Match(LinkedList la/算術(shù)表達式存儲在以la為頭結(jié)點的單循環(huán)鏈表中，本算法判斷括號是否正確配對char s; /s為字符棧，容量足夠大p=la-link; /p為工作指針，指向待處理結(jié)點StackInit(s; /初始化棧swhile (p!=la /循環(huán)到頭結(jié)點為止 switch (p-chcase (:push(s,p-ch; break;case :i

46、f(StackEmpty(s|StackGetTop(s!=(printf(“括號不配對n”; return(0; else pop(s;break;case :push(s,p-ch; break;case : if(StackEmpty(s|StackGetTop(s!=printf(“括號不配對n”; return(0; else pop(s;break;case :push(s,p-ch; break;case : if(StackEmpty(s|StackGetTop(s!=printf(“括號不配對n”; return(0; else pop(s;break; p=p-link;

47、后移指針/whileif (StackEmpty(s printf(“括號配對n”; return(1; elseprintf(“括號不配對n”; return(0;/算法match結(jié)束算法討論算法中對非括號的字符未加討論。遇到右括號時，若?？栈驐ｍ斣夭皇瞧鋵?yīng)的左圓（方、花）括號，則結(jié)論括號不配對，退出運行。最后，若棧不空，仍結(jié)論括號不配對。7、題目分析棧的特點是后進先出，隊列的特點是先進先出。所以，用兩個棧s1和s2模擬一個隊列時，s1作輸入棧，逐個元素壓棧，以此模擬隊列元素的入隊。當需要出隊時，將棧s1退棧并逐個壓入棧s2中，s1中最先入棧的元素，在s2中處于棧頂。s2退棧，相當于隊列

48、的出隊，實現(xiàn)了先進先出。顯然，只有棧s2為空且s1也為空，才算是隊列空。(1 int enqueue(stack s1,elemtp x/s1是容量為n的棧，棧中元素類型是elemtp。本算法將x入棧，若入棧成功返回1，否則返回0。if(top1=n & !Sempty(s2 /top1是棧s1的棧頂指針，是全局變量。printf(“棧滿”;return(0; /s1滿s2非空,這時s1不能再入棧。if(top1=n & Sempty(s2 /若s2為空，先將s1退棧,元素再壓棧到s2。while(!Sempty(s1 POP(s1,x;PUSH(s2,x;PUSH(s1,x; return(

49、1; /x入棧，實現(xiàn)了隊列元素的入隊。(2 void dequeue(stack s2,s1/s2是輸出棧，本算法將s2棧頂元素退棧，實現(xiàn)隊列元素的出隊。if(!Sempty(s2 /棧s2不空，則直接出隊。POP(s2,x; printf(“出隊元素為”,x; else /處理s2空棧。if(Sempty(s1 printf(“隊列空”;exit(0;/若輸入棧也為空，則判定隊空。else /先將棧s1倒入s2中，再作出隊操作。while(!Sempty(s1 POP(s1,x;PUSH(s2,x;POP(s2,x; /s2退棧相當隊列出隊。printf(“出隊元素”，x;/結(jié)束算法dequ

50、ue。(3 int queue_empty(/本算法判用棧s1和s2模擬的隊列是否為空。if(Sempty(s1&Sempty(s2 return(1;/隊列空。else return(0; /隊列不空。算法討論算法中假定棧s1和棧s2容量相同。出隊從棧s2出，當s2為空時，若s1不空，則將s1倒入s2再出棧。入隊在s1，當s1滿后，若s2空，則將s1倒入s2，之后再入隊。因此隊列的容量為兩棧容量之和。元素從棧s1倒入s2，必須在s2空的情況下才能進行，即在要求出隊操作時，若s2空，則不論s1元素多少（只要不空），就要全部倒入s2中。類似本題敘述的其它題的解答：（1） 該題同上面題本質(zhì)相同，只有敘述不同，請參考上題