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

1、第三章 棧和隊(duì)列答案一、選擇題 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、 這個(gè)數(shù)是前序序列為1,2,3

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

3、 15、先進(jìn)先出 16、先進(jìn)先出 17、s=(LinkedListmalloc(sizeof(LNode； s-data=x;s-next=r-next；r-next=s；r=s；18、犧牲一個(gè)存儲(chǔ)單元 設(shè)標(biāo)記19、（TAIL+1）MOD M=FRONT (數(shù)組下標(biāo)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、棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出（LIFO）表。2、隊(duì)列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊(duì)尾，允許刪除的一端叫隊(duì)頭。最先插入隊(duì)的

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

6、為A，B，C，則兩個(gè)輸入的合法序列ABC和BAC均可得到輸出元素序列ABC。對(duì)于合法序列ABC，我們使用本題約定的SSS操作序列；對(duì)于合法序列BAC，我們使用SSS操作序列。5、三個(gè)：CDEBA，CDBEA，CDBAE6、輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個(gè)元素（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，三個(gè)元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。8、借助棧結(jié)構(gòu)，n個(gè)入棧元素可得到1/(n+1(2n）！/（n!*n!）種出棧序列。本題4個(gè)元素，可有14種出棧序列，abcd和dcba就是其中兩種。但dabc和adbc是不可能得到的兩種。9、不能得到序列2，5，3，4，6。?？梢杂脝捂湵韺?shí)現(xiàn)，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設(shè)頭結(jié)點(diǎn)。10、如果ij，則對(duì)于pipj的情況，則說明要將pj

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

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

10、本項(xiàng)”發(fā)展，最終“到達(dá)”基本項(xiàng)。13、函數(shù)調(diào)用結(jié)束時(shí)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)用自身時(shí)，過程p由內(nèi)部定義的局部變量在p的2次調(diào)用期間，不占同一數(shù)據(jù)區(qū)。每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是遞歸定義所決定，用“遞歸工作?！眮韺?shí)現(xiàn)。15、設(shè)Hn為n個(gè)盤子的Hanoi塔的移動(dòng)次數(shù)。(假定n個(gè)盤子從鋼針X移到鋼針Z，可借助鋼針Y則 Hn =2Hn-1+1 /先將n-1個(gè)

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

12、1，另一個(gè)棧頂指針為MAX時(shí)，棧為空。用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ù)組，由兩個(gè)棧共享其空間。 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的元素，如有，則刪除。采用的辦法使用另一個(gè)棧T。在S棧元素退棧時(shí)，若退棧元素不是整數(shù)k，則壓入T棧。遇整數(shù)k，k不入T棧，然后將T棧元素全部退棧，并依次壓入棧S中，實(shí)現(xiàn)了在S中刪除整數(shù)k的目的。若S中無整數(shù)k，則在S退成空棧后，再將T棧元素退棧，并依次壓入S棧。直至T?？?。這后一種情況下S棧內(nèi)容操作前后不變。19、中綴表達(dá)式8-(3+5*(5-6/2）的后綴表達(dá)式是： 8 3 5 + 5 6 2 / - * -棧的變化過程圖略（請(qǐng)參見22題），表達(dá)式生成過程為：中綴表達(dá)式exp1轉(zhuǎn)為后綴表達(dá)式exp2的規(guī)則如下：設(shè)操作符棧s，初始為

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

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

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

21、進(jìn)入結(jié)果表達(dá)式。接著讀入*，與棧頂比較，均為*，我們規(guī)定，后讀入的*級(jí)別高于棧頂?shù)?，因此*入棧。接著讀入C，直接到結(jié)果表達(dá)式?，F(xiàn)在的結(jié)果（后綴）表達(dá)式是ABC。最后讀入#，表示輸入表達(dá)式結(jié)束，這時(shí)運(yùn)算符棧中從棧頂?shù)綏５子袃蓚€(gè)*和一個(gè)#。兩個(gè)運(yùn)算符*退棧至結(jié)果表達(dá)式，結(jié)果表達(dá)式變?yōu)锳BC*。運(yùn)算符棧中只剩#，退棧，運(yùn)算結(jié)束。21、（1）sum=21。當(dāng)x為局部變量時(shí)，每次遞歸調(diào)用，都要給局部變量分配存儲(chǔ)單元，故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,當(dāng)x為全局變量時(shí)，在程序的整個(gè)執(zhí)行期間，x只占一個(gè)存儲(chǔ)單元，先后讀入的4個(gè)數(shù)(4,9,6,2,僅最后一個(gè)起作用。當(dāng)遞歸調(diào)用結(jié)束，逐層返回時(shí)sum:=sum(n-1+x表達(dá)式中，x就是2，所以結(jié)果為sum=8。22、設(shè)操作數(shù)棧是opnd，操作符棧是optr，對(duì)算術(shù)表達(dá)式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ù)表達(dá)式（按字符讀入）初始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è)在兩端，兩棧頂向共享空間的中心延伸，僅當(dāng)兩棧頂指針相鄰（兩棧頂指針值之差的絕對(duì)值等于1）時(shí)，判斷為棧滿，當(dāng)一個(gè)棧頂指針為0，另一個(gè)棧頂指針m+1時(shí)為兩棧均空。26、設(shè)棧S1和棧S2共享向量V1.m，初始時(shí)，棧S1的棧頂指針top0=0，棧S2的棧頂指針top1=m+1，當(dāng)top0=0為左棧空，top1=m+1為右棧空；當(dāng)top0=0并且top1=m+1時(shí)為全?？?。當(dāng)top1-top0=1時(shí)為棧滿。27、（1）每個(gè)棧僅用一

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

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

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

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

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

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

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

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

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

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

37、空間所能達(dá)到的最多元素?cái)?shù)#define elemtp int /假設(shè)元素類型為整型typedef structelemtp stackmaxsize; /棧空間int top2; /top為兩個(gè)棧頂指針stk;stk s; /s是如上定義的結(jié)構(gòu)類型變量，為全局變量。(1入棧操作：int push(int i,int x/入棧操作。i為棧號(hào)，i=0表示左邊的棧s1，i=1表示右邊的棧s2，x是入棧元素。入棧成功返回1，否則返回0。if(i1printf(“棧號(hào)輸入不對(duì)”;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代表?xiàng)Ｌ?hào)，i=0時(shí)為s1棧，i=1時(shí)為s2棧。退棧成功返回退棧元素，否則返回-1。if(i1printf(“棧號(hào)輸入錯(cuò)誤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é)束算法討論 請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。兩棧共享空間示意圖略，s1棧是通常意義下的棧，而s2棧入棧操作時(shí)，其棧頂指針左移（減1），退棧時(shí)，棧頂指針右移（加1）。2、#define maxsize ?？臻g容量void InOutS(int smaxsize/s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。int top=0; /top為棧頂指針，定義top=0時(shí)為?？?。for(i=1; i=n; i+ /n個(gè)整數(shù)序列作處理。scanf(“%d”,&x; /從鍵盤讀入整數(shù)序列。if(x!=-1 / 讀入的

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

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

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

43、足夠大，因此入棧時(shí)未判斷溢出。4、題目分析逆波蘭表達(dá)式(即后綴表達(dá)式求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND,對(duì)表達(dá)式從左到右掃描(讀入，當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí)，從OPND退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)果。float expr( /從鍵盤輸入逆波蘭表達(dá)式，以$表示輸入結(jié)束，本算法求逆波蘭式表達(dá)式的值。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的個(gè)數(shù)）都必須大于等于出棧次數(shù)（即O的個(gè)數(shù)），否則視作非法序列，立即給出信息，退出算法。整個(gè)序列（即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記0），入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序列。6、題目分析表達(dá)式

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

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

47、后移指針/whileif (StackEmpty(s printf(“括號(hào)配對(duì)n”; return(1; elseprintf(“括號(hào)不配對(duì)n”; return(0;/算法match結(jié)束算法討論算法中對(duì)非括號(hào)的字符未加討論。遇到右括號(hào)時(shí)，若棧空或棧頂元素不是其對(duì)應(yīng)的左圓（方、花）括號(hào)，則結(jié)論括號(hào)不配對(duì)，退出運(yùn)行。最后，若棧不空，仍結(jié)論括號(hào)不配對(duì)。7、題目分析棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。所以，用兩個(gè)棧s1和s2模擬一個(gè)隊(duì)列時(shí)，s1作輸入棧，逐個(gè)元素壓棧，以此模擬隊(duì)列元素的入隊(duì)。當(dāng)需要出隊(duì)時(shí)，將棧s1退棧并逐個(gè)壓入棧s2中，s1中最先入棧的元素，在s2中處于棧頂。s2退棧，相當(dāng)于隊(duì)列

48、的出隊(duì)，實(shí)現(xiàn)了先進(jìn)先出。顯然，只有棧s2為空且s1也為空，才算是隊(duì)列空。(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非空,這時(shí)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入棧，實(shí)現(xiàn)了隊(duì)列元素的入隊(duì)。(2 void dequeue(stack s2,s1/s2是輸出棧，本算法將s2棧頂元素退棧，實(shí)現(xiàn)隊(duì)列元素的出隊(duì)。if(!Sempty(s2 /棧s2不空，則直接出隊(duì)。POP(s2,x; printf(“出隊(duì)元素為”,x; else /處理s2空棧。if(Sempty(s1 printf(“隊(duì)列空”;exit(0;/若輸入棧也為空，則判定隊(duì)空。else /先將棧s1倒入s2中，再作出隊(duì)操作。while(!Sempty(s1 POP(s1,x;PUSH(s2,x;POP(s2,x; /s2退棧相當(dāng)隊(duì)列出隊(duì)。printf(“出隊(duì)元素”，x;/結(jié)束算法dequ

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