第三章棧和隊列習題數據結構

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

2、3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.2341564.設有一順序棧S，元素s1s2s3s4s5s6依次進棧，如果6個元素出棧的順序是s2s3s4s6s5s1則棧的容量至少應該是（）A.2B.3C.5D.65.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(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.表達式32^(42263)5求值過程中當掃描到6時，對象棧和算符棧為（），其中^為乘冪。A.32411；(^(B.328；(^C.32422；(^(D.328

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

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

6、QueptrTplqDataTypex)LqueueTppp=(LqueueTp)malloc(sizeof(LqueueTp))________________=xpnext=NULL(lqrear)next=________________________________三、應用題三、應用題1給出棧的兩種存儲結構形式名稱，在這兩種棧的存儲結構中如何判別棧空與棧滿？2.畫出對算術表達式ABCDE↑F求值時操作數棧和運算符棧的變化過程。

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

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