第三章棧和隊(duì)列習(xí)題數(shù)據(jù)結(jié)構(gòu)

1、習(xí)題三習(xí)題三棧和隊(duì)列棧和隊(duì)列一單項(xiàng)選擇題單項(xiàng)選擇題1.在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否(①)在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否(②)。當(dāng)棧中元素為n個(gè)作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢則說明該棧的最大容量為(③)。①②:A.空B.滿C.上溢D.下溢③:A.n1B.nC.n1D.n22若已知一個(gè)棧的進(jìn)棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，...，pn，若p1＝3，則p2為()。A可能是2B一定是2C可能是1D一定是13.有六個(gè)元素6，5，4，

2、3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（）A.543612B.453126C.346521D.2341564.設(shè)有一順序棧S，元素s1s2s3s4s5s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2s3s4s6s5s1則棧的容量至少應(yīng)該是（）A.2B.3C.5D.65.若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個(gè)棧(i=12)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（）。A

3、.|top[2]top[1]|=0B.top[1]1=top[2]C.top[1]top[2]=mD.top[1]=top[2]6.執(zhí)行完下列語句段后，i值為：（）intf(intx)return((x0)xf(x1):2)intii=f(f(1))A2B.4C.8D.無限遞歸7.表達(dá)式32^(42263)5求值過程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（），其中^為乘冪。A.32411；(^(B.328；(^C.32422；(^(D.328

4、；(^(8.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改9.遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列B多維數(shù)組C棧D.線性表10設(shè)C語言數(shù)組Data[m1]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語句為（）A.front=front1B.front=（front1）%mC.re

5、ar=(rear1)%(m1)D.front=(front1)%(m1)11.循環(huán)隊(duì)列的隊(duì)滿條件為()A.(sq.rear1)%maxsize==(sq.front1)%maxsizeB.(sq.front1)%maxsize==sq.rear________________return(1)；elsereturn(0)12.以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的入隊(duì)列，請?jiān)赺_______________處用適當(dāng)句子予以填充。VoidEnQueue(

6、QueptrTplqDataTypex)LqueueTppp=(LqueueTp)malloc(sizeof(LqueueTp))________________=xpnext=NULL(lqrear)next=________________________________三、應(yīng)用題三、應(yīng)用題1給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？2.畫出對(duì)算術(shù)表達(dá)式ABCDE↑F求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程。

7、3.將兩個(gè)棧存入數(shù)組V[1..m]應(yīng)如何安排最好？這時(shí)?？?、棧滿的條件是什么？4.怎樣判定循環(huán)隊(duì)列的空和滿？四、算法設(shè)計(jì)題四、算法設(shè)計(jì)題1借助棧(可用棧的基本運(yùn)算)來實(shí)現(xiàn)單鏈表的逆置運(yùn)算。2.設(shè)表達(dá)式以字符形式已存入數(shù)組E[n]中，‘#’為表達(dá)式的結(jié)束符，試寫出判斷表達(dá)式中括號(hào)（‘（’和‘）’）是否配對(duì)的C語言描述算法：EXYX(E)(注：算法中可調(diào)用棧操作的基本算法。)3.假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧

8、和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（1）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通過對(duì)（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。4.設(shè)有兩個(gè)棧S1S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[O..maxsize1