第三章棧和佇列習題
一、 選擇題
1. 乙個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是( )
a. edcba
b. decba
c. dceab
d. abcde
2.乙個佇列的入隊順序是1,2,3,4，則佇列的輸出順序是( )
a.4321
b.1234
c.1432
d.3241
3. 若已知乙個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為( )
a. i
b. n=i
c. n-i+1
d. 不確定
4. 棧是將插入或刪除操作限定在( )處進行的線性表。
a 端點
b 棧底
c 棧頂
d 中間
5. 若乙個順序棧st在初始化時top=-1，則判定這個棧（最多元素為m0個）為棧滿的條件是( )
a. top！=0;
b. top= =m0;
c. top！=m0;
d. top= =m0-1
6. 向乙個棧頂指標為hs的鏈棧中插入乙個s所指結點時，則執行( )(不帶空的頭結點)
a. b.
c. hs; hs=s;
d. hs; hs=
7. 從乙個棧頂指標為hs的鏈棧中刪除乙個結點時，用x儲存被刪結點的值，則執行的完整操作為( )(不帶空的頭結點)
a. x=hs; hs=
b. x=
c. hs= x=
d. x= hs=
8.最大容量為n的迴圈佇列，隊尾指標是rear,隊頭指標是front，則隊空的條件是（ ）
a.(rear+1)mod n=front
d.(rear-1)mod
9.設棧s和佇列q的初始狀態為空，元素e1、e2、e3、e4、e5、e6依次通過棧s，乙個元素出棧後即進入佇列q，若6個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧s的容量至少應該是（ ）
a.6b.4
c.3d.2
n=front
10. 表示式3*2^(4+2*2-6*3)-5求值過程中，當掃瞄到6時，運算元棧和算符棧為（）。
a 3,2,4,1,1；*^(+*-
b 3,2,4,4
c 3,2,4,2,2;*^(-
d 3,2,8; *^(-
二、 填空題
1．用s表示入棧操作，x表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的s和x的操作串為_______。
2. 迴圈佇列的引入，目的是為了克服_______。
3.佇列與一般的線性表的區別在於_______。
4．表示式求值是_______應用的乙個典型例子。
5．迴圈佇列用陣列a[0..m-1]存放其元素值，已知其頭尾指標分別是front和rear ，則當前佇列的元素個數是_______。
6.解決順序佇列假溢位的乙個有效的方法是將溢位條件 rear = maxsize 改為
7.同乙個棧內各元素的型別
8.在作入棧運算時，應先判別棧是否_____，在作出棧時應先判別棧是否_____。
9.設長度為n的鏈佇列用單迴圈鍊錶，若只設頭指標，則入隊和出隊操作的時間複雜度分別為_____和_____；若只設尾指標，則入隊和出隊操作的時間複雜度分別為_____和_____。
10.在有n個元素的棧中，進棧和退棧操作的時間複雜度為_____和_____。
三、 判斷
（ ）1. 棧是一種對所有插入、刪除操作限於在表的一端進行的線性表，是一種後進先出型結構。隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進後出型結構。
（ ）2. 棧和佇列是一種非線性資料結構。
（ ）3. 棧和佇列的儲存方式既可是順序方式，也可是鏈結方式。
（ ）4. 兩個棧共享一片連續記憶體空間時，為提高記憶體利用率，減少溢位機會，應把兩個棧的棧底分別設在這片記憶體空間的兩端。
（ ）5. 由於佇列遵循先進先出原則，所以佇列出隊操作只需要修改頭指標。
四、 實驗題
1,請編寫並實現演算法，將任意乙個非負的十進位制整數，採用輾轉相除法，轉換為其他進製的數。（要求畫流程圖。）
2,一班有m個女生、n個男生,舉辦一場舞會.男女生分別編號坐在舞池兩邊的椅子上，每曲開始時,依次從男生和女生中各出一人配對跳舞,本曲沒成功配對者坐著等待下一曲找舞伴，設計乙個程式模擬舞伴配對過程（男生多於女生，女生多於男生，男生女生人數相等）。
要求舞伴的排隊遵循先進先出原則。
3,（選做）、n個水手來到乙個島上，採了一堆椰子後，因為疲勞都睡著了。一段時間後，第乙個水手醒來，悄悄地將椰子等分成n份，多出m個椰子，便給了旁邊的猴子，然後自己藏起乙份再將剩下的椰子重新合在一起，繼續睡覺。不久，第二名水手醒來，同樣將椰子等分成n份，恰好也多出m個，也給了猴子。
然後自己也藏起乙份，再將剩下的椰子重新合在一起以後每個水手都如此分了一次並都藏起乙份，也恰好都把多出的m個給了猴子。第二天n個水手醒來，發現椰子少了許多，心照不宣，便把剩下的椰子分成n份，恰好又多出m個給了猴子。
對於給定的整數n、m(約定0 1.乙個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是 c a.edcba b.decba c.dceab d.abcde 2.若已知乙個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1 n，則pi為 c a.i b.n i c.n i 1 d.不確定 3.棧結構通... 實驗二第三章棧和佇列 一 棧 實驗原始碼 include include include define stack init size 100 define stackincrement 10 typedef int selemtype typedef int status typedef stru... 3311 請判斷下列表示式是否正確。輸入乙個表示式，表示式中包括 字母，數字，括號以及符號 判斷表達中各括號的位置是否遵循以下規則 1 各種括號左右數量相同。2 各種括號只能並列和巢狀，不能交差。輸入 只有一行，為乙個長度小於255的表示式。輸出 一行。如果表示式中各括號互相匹配，則輸出 yes 否...《資料結構》習題3棧和佇列
資料結構實驗棧和佇列
資料結構 棧與佇列