第3章棧和佇列
一選擇題
1. 對於棧運算元據的原則是（ ）。【青島大學 2001
五、2（2分）】
a. 先進先出 b. 後進先出 c. 後進後出 d. 不分順序
2. 在作進棧運算時,應先判別棧是否( ① ),在作退棧運算時應先判別棧是否( ② )。當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為( ③ )。
為了增加記憶體空間的利用率和減少溢位的可能性,由兩個棧共享一片連續的記憶體空間時,應將兩棧的 ( ④ )分別設在這片記憶體空間的兩端,這樣,當( ⑤ )時，才產生上溢。
①, ②: a. 空 b. 滿 c. 上溢 d. 下溢
③: a. n-1 b. n c. n+1 d. n/2
④: a. 長度 b. 深度 c. 棧頂 d. 棧底
⑤: a. 兩個棧的棧頂同時到達棧空間的中心點.
b. 其中乙個棧的棧頂到達棧空間的中心點.
c. 兩個棧的棧頂在棧空間的某一位置相遇.
d. 兩個棧均不空,且乙個棧的棧頂到達另乙個棧的棧底.
【上海海運學院 1997
二、1（5分）】【上海海運學院 1999
二、1（5分）】
3. 乙個棧的輸入序列為123…n，若輸出序列的第乙個元素是n，輸出第i（1<=i<=n）個元素是（ ）。
a. 不確定 b. n-i+1 c. i d. n-i
【中山大學 1999
一、9(1分)】
4. 若乙個棧的輸入序列為1,2,3,…,n，輸出序列的第乙個元素是i，則第j個輸出元素是（ ）。
a. i-j-1 b. i-j c. j-i+1 d. 不確定的
【武漢大學 2000
二、3】
5. 若已知乙個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pn,若pn是n，則pi是( )。
a. i b. n-i c. n-i+1 d. 不確定
【南京理工大學 2001
一、1（1.5分）】
6. 有六個元素6，5，4，3，2，1 的順序進棧，問下列哪乙個不是合法的出棧序列？（ ）
a. 5 4 3 6 1 2 b. 4 5 3 1 2 6 c. 3 4 6 5 2 1 d. 2 3 4 1 5 6
【北方交通大學 2001
一、3（2分）】
7. 設棧的輸入序列是1，2，3，4,則（ ）不可能是其出棧序列。【中科院計算所2000
一、10(2分)】
a. 1，2，4，3， b. 2，1，3，4， c. 1，4，3，2，
d. 4，3，1，2， e. 3，2，1，4，
8. 乙個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ ）。
a. 2 3 4 1 5 b. 5 4 1 3 2 c. 2 3 1 4 5 d. 1 5 4 3 2
【南開大學 2000
一、1】【山東大學 2001
二、4 (1分)】【北京理工大學 2000
一、2（2分）】
9. 設乙個棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ ）。
a. 5 1 2 3 4 b. 4 5 1 3 2 c. 4 3 1 2 5 d. 3 2 1 5 4
【合肥工業大學 2001
一、1（2分）】
10. 某堆疊的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ ）。
a. a，c，b，d b. b, c，d，a c. c, d，b, a d. d, c，a，b
【北京航空航天大學 2000
一、3（2分）】【北京郵電大學 1999
一、3（2分）】
11. 設abcdef以所給的次序進棧，若在進棧操作時，允許退棧操作,則下面得不到的序列為（ ）。
a．fedcba b. bcafed c. dcefba d. cabdef
【南京理工大學 1996
一、9（2分）】
12. 設有三個元素x，y，z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是( )。
a．xyz b. yzx c. zxy d. zyx
【南京理工大學 1997
一、5（2分）】
13. 輸入序列為abc，可以變為cba時，經過的棧操作為（ ）【中山大學 1999
一、8(1分)】
a. push,pop,push,pop,push,pop b. push,push,push,pop,pop,pop
c. push,push,pop,pop,push,pop d. push,pop,push,push,pop,pop
14. 若乙個棧以向量v[1..n]儲存，初始棧頂指標top為n+1，則下面x進棧的正確操作是( )。
a．top:=top+1; v [top]:=x b. v [top]:=x; top:=top+1
c. top:=top-1; v [top]:=x d. v [top]:=x; top:=top-1
【南京理工大學 1998
一、13（2分）】
15. 若棧採用順序儲存方式儲存，現兩棧共享空間v[1..m]，top[i]代表第i個棧( i =1,2)棧頂，棧1的底在v[1]，棧2的底在v[m]，則棧滿的條件是（ ）。
a. |top[2]-top[1]|=0 b. top[1]+1=top[2] c. top[1]+top[2]=m d. top[1]=top[2]
【南京理工大學 1999
一、14（1分）】
16. 棧在（ ）中應用。【中山大學 1998
二、3（2分）】
a. 遞迴呼叫 b. 子程式呼叫 c. 表示式求值 d. a，ｂ，ｃ
17. 乙個遞迴演算法必須包括（ ）。【武漢大學 2000
二、2】
a. 遞迴部分 b. 終止條件和遞迴部分 c. 迭代部分 d.終止條件和迭代部分
18. 執行完下列語句段後，i值為：（ ）【浙江大學 2000 一 、6 (3分)】
int f(int x)
int i ;
i =f(f(1));
a．2 b. 4 c. 8 d. 無限遞迴
19. 表示式a*(b+c)-d的字尾表示式是( )。【南京理工大學 2001
一、2（1.5分）】
a．abcd*+- b. abc+*d- c. abc*+d- d. -+*abcd
20. 表示式3* 2^(4+2*2-6*3)-5求值過程中當掃瞄到6時，物件棧和算符棧為（ ），其中^為乘冪 。
a. 3,2,4,1,1；(*^(+*- b. 3,2,8；(*^- c. 3,2,4,2,2；(*^(- d. 3,2,8；(*^(-
【青島大學 2000
五、5（2分）】
21. 設計乙個判別表示式中左，右括號是否配對出現的演算法，採用（ ）資料結構最佳。
a．線性表的順序儲存結構 b. 佇列 c. 線性表的鏈式儲存結構 d. 棧
【西安電子科技大學 1996
一、6（2分）】
22. 用鏈結方式儲存的佇列，在進行刪除運算時（ ）。【北方交通大學 2001
一、12（2分）】
a. 僅修改頭指標 b. 僅修改尾指標 c. 頭、尾指標都要修改 d. 頭、尾指標可能都要修改
23. 用不帶頭結點的單鏈表儲存佇列時,其隊頭指標指向隊頭結點,其隊尾指標指向隊尾結點，則在進行刪除操作時( )。【北京理工大學 2001
六、3（2分）】
a．僅修改隊頭指標 b. 僅修改隊尾指標
c. 隊頭、隊尾指標都要修改 d. 隊頭,隊尾指標都可能要修改
24. 遞迴過程或函式呼叫時，處理引數及返回位址，要用一種稱為（ ）的資料結構。
a．佇列 b．多維陣列 c．棧 d. 線性表
【福州大學 1998
一、1（2分）】
25. 假設以陣列a[m]存放迴圈佇列的元素,其頭尾指標分別為front和rear，則當前佇列中的元素個數為（ ）。【北京工商大學 2001
一、2（3分）】
a．(rear-front+m)%m b．rear-front+1 c．(front-rear+m)%m d．(rear-front)%m
26. 迴圈佇列a[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前佇列中的元素數是( )。【南京理工大學 2001
一、5（1.5分）】
a. (rear-front+m)%m b. rear-front+1 c. rear-front-1 d. rear-front
27. 迴圈佇列儲存在陣列a[0..m]中，則入隊時的操作為（ ）。【中山大學 1999
一、6（1分）】
a. rear=rear+1 b. rear=(rear+1) mod (m-1)
c. rear=(rear+1) mod m d. rear=(rear+1)mod(m+1)
28. 若用乙個大小為6的陣列來實現迴圈佇列，且當前rear和front的值分別為0和3，當從佇列中刪除乙個元素，再加入兩個元素後，rear和front的值分別為多少？( )【浙江大學1999
四、1(4分)】
a. 1和 5 b. 2和4 c. 4和2 d. 5和1
29. 已知輸入序列為abcd 經過輸出受限的雙向佇列後能得到的輸出序列有（ ）。
a. dacb b. cadb c. dbca d. bdac e. 以上答案都不對
【西安交通大學 1996
三、3 (3分)】
30. 若以1234作為雙端佇列的輸入序列，則既不能由輸入受限的雙端佇列得到，也不能由輸出受限的雙端佇列得到的輸出序列是( )。【西安電子科技大學 1996
一、5（2分）】
a. 1234 b. 4132 c. 4231 d. 4213
31. 最大容量為n的迴圈佇列，隊尾指標是rear，隊頭是front，則隊空的條件是 （ ）。
a. (rear+1) mod n=front b. rear=front
c．rear+1=front d. (rear-l) mod n=front
【南京理工大學 1999
一、16（2分）】
32. 棧和佇列的共同點是（ ）。【燕山大學 2001
一、1（2分）】
a. 都是先進先出 b. 都是先進後出
c. 只允許在端點處插入和刪除元素 d. 沒有共同點
33. 棧的特點是（ ① ）,佇列的特點是（ ② ）,棧和佇列都是（ ③ ）。若進棧序列為1,2,3,4 則（ ④ ）不可能是乙個出棧序列（不一定全部進棧後再出棧）；若進佇列的序列為1,2,3,4 則（ ⑤ ）是乙個出佇列序列。
【北方交通大學 1999
一、1（5分）】
資料結構第三章自測題答案
第3章棧和佇列自測卷答案姓名班級 一 填空題 每空1分，共15分 1.向量 棧和佇列都是線性結構，可以在向量的任何位置插入和刪除元素 對於棧只能在棧頂插入和刪除元素 對於佇列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 不允許插入和刪除運算的一端稱為棧底 ...
資料結構第三章排序自測題
第9章排序自測卷姓名班級 一 填空題 每空1分，共24分 1.大多數排序演算法都有兩個基本的操作和 2.在對一組記錄 54，38，96，23，15，72，60，45，83 進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。3.在插入和選擇排序中，若初始資料基本正序，則...
資料結構課後習題第三章
1.對於棧，運算元據的原則是 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.一般情況下，將遞迴演算法轉換成非遞迴應通過設定 實現。a.陣列 b.線性表 c.佇列d.棧 3.棧和佇列的共同點是 a.都是先進後出b.都是先進先出 c.只允許在端點處插入和刪除元素 d.沒有共同點 4.若元素...