9．設n個元素進棧序列是p1,p2,…,pn，其輸出序列是1，2，3，……，n，若p3=1,則p1的值
a．可能是2 b．一定是1
c．不可能是2 d．不可能是3
10．設n個元素進棧序列是p1,p2,…,pn，其輸出序列是1，2，3，……，n，若p3=3,則p1的值
a．可能是2 b．一定是2
c．不可能是1 d．一定是1
11．設n個元素進棧序列是p1,p2,…,pn，其輸出序列是1，2，3，……，n，若pn=1,則pi(1≤i≤n-1)的值
a．n-i+1b．n-i
c．i d．有多種可能
12．判定乙個順序棧s為空的條件為
a． = b．
c． d． =
13．判定乙個順序棧s為棧滿的條件是
a． = b． =
c． d．
14．鏈棧與順序棧相比有乙個明顯的優點，即
a．插入操作方便b．通常不會出現棧滿的情況
c．不會出現棧空的情況 d．刪除操作更加方便
15．最不適合用作鏈棧的鍊錶是
a．只有表頭指標沒有表尾指標的迴圈雙鏈表
b．只有表尾指標沒有表頭指標的迴圈雙鏈表
c．只有表尾指標沒有表頭指標的迴圈單鏈表
d．只有表頭指標沒有表尾指標的迴圈單鏈表
16．如果以鍊錶作為棧的儲存結構，則退鏈棧操作時
a．必須判別鏈棧是否滿 b．判別鏈棧元素的型別
c．必須判別鏈棧是否空 d．對鏈棧不作任何判別
17．向乙個不帶頭結點的棧頂指標為1st的鏈棧中插入乙個s所指結點時，則執行
a．1st->next=s; b．s->next=1st->next;1st->next=s;
c．s->next=1st;1st=s; d．s->next=1st;1st->next;
18．從乙個不帶頭結點的棧頂指標為s的鏈棧中刪除乙個結點時，用x儲存被刪除結點的值，則執行
a．x=s; s = s ->next; b．x= s ->data;
c．s = s ->next;x= s ->data; d．x= s ->data; s = s ->next;
19．經過以下佇列運算後，隊頭的元素是
initqueue(qu);enqueue(qu,a);enqueue(qu,b);enqueue(qu,c);dequeue(qu);
a．a b．b
c．1d．0
20．經過以下佇列的運算後，queueempty(q) 的值是
initqueue(qu);enqueue(qu,a);enqueue(qu,b);dequeue(qu,x);dequeue(qu,y);
a．a b．b
c．1 d．0
21．元素a,b,c,d順序連續進入佇列qu後，隊頭元素是隊尾元素是
a．a b．b
c．c d．d
22．乙個佇列的入隊序列為1,2,3,4，則佇列可能的輸出序列是_______.
a．4,3,2,1 b．1,2,3,4
c．1,4,3,2d．3,2,4,1
二、填空題
1．棧是一種具有特性的線性表。
2．順序棧和鏈棧的區別僅在於不同。
3．如果棧的最大長度難以估計，則最好使用
4．乙個棧的輸入序列是1,2,3,4,5，則棧的輸出序列1,2,3,4,5是
5．若用不帶頭結點的單鏈表來表示鏈棧s，則建立乙個空棧所要執行的操作是
6．對於鏈棧s，進棧操作在端進行，出棧操作在端進行。
7．佇列是一種具有特性的線性表。
8．順序佇列和鏈佇列的區別僅在於的不同。
9．如果佇列的最大長度難以估計，則最好使用
三、判斷題
1．順序棧中元素值的大小是有序的。
2．在n個元素進棧後，它們的出棧順序和進棧順序一定正好相反。
3．棧頂元素和棧底元素有可能是同乙個元素。
4．若用s[1~m]表示順序棧的儲存空間，則對棧的進棧，出棧操作最多只能進行m次。
5．棧是一種對進棧，出棧操作總次數作了限制的線性表。
6．空棧沒有棧頂指標。
7．棧和佇列都是限制訪問端的線性表。
8．佇列是一種對進佇列，出佇列操作的次序作了限制的線性表。
9．n個元素進佇列的順序和出佇列的順序總是一致的。
10．順序隊中有多少元素，可以根據隊首指標的值和隊尾指標的值來計算。
11．若用「隊頭指標的值和隊尾指標的值相等」作為環形順序隊為空的標誌，則在設定乙個空佇列時，只需給隊頭指標和隊尾指標賦同乙個值，不管什麼值都可以。
12．無論是順序佇列，還是鏈佇列，入隊和出隊操作的時間複雜度都是o(1)。
13．佇列的輸入序列為1,2,3,…,n，輸出序列為a1,a2,…,an, 則ai四、簡答題
1．有5個元素，其進棧次序為a,b,c,d,e,在各種可能的出棧次序中，以元素c,d最先出棧（即c第乙個且d第二個出棧）的次序有哪幾個？
2．設輸入元素為1，2，3，p和a，入棧次序為1,2,3,p,a，元素經過棧後到達輸出序列，當所有元素均到達輸出序列後，有哪些序列可以作為高階語言的變數名？
3．設有乙個數列的輸入順序為1,2,3,4,5,6，若採用棧結構，並以a和d分別表示進棧和出棧操作，試問通過進棧和出棧操作的合法序列是什麼？
（1）能否得到輸出順序為3,2,5,6,4,1的序列。
（2）能否得到輸出順序為1,5,4,6,2,3的序列。
4．簡述線性表、棧和佇列的異同。
5．設棧s和佇列q的初始狀態都為空，元素a,b,c,d,e和f依次通過棧s，乙個元素出棧後即進入佇列q，若6個元素的出隊的序列是b,d,c,f,e,a，則棧s的容量至少應該存多少個元素。
五、演算法設計題
1．用乙個一維陣列s（設大小為maxsize）作為兩個棧的共享空間。請說明共享方法，棧滿和棧空的判斷條件，並用c/c++語言設計公用的初始化棧運算initstack1(st)、判棧空運算stackempty1(st,i)、入棧運算push(st,i,x)和出棧運算pop(st,i,x)，其中i為1或2，用於表示棧好，x為入棧或出棧元素。
2．設計乙個演算法，利用棧的initstack( )、push( )、pop( )和stackempty( )等基本運算返回指定棧中棧底元素。
3．用不帶頭結點的單鏈表儲存鏈棧，設計初始化棧、判斷棧是否為空、進棧和出棧相應的演算法。
4．在棧頂頭結點為1st的鏈棧中，設計乙個演算法計算該棧中結點個數。
《資料結構》習題3棧和佇列
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.棧結構通...
資料結構 棧與佇列
3311 請判斷下列表示式是否正確。輸入乙個表示式，表示式中包括 字母，數字，括號以及符號 判斷表達中各括號的位置是否遵循以下規則 1 各種括號左右數量相同。2 各種括號只能並列和巢狀，不能交差。輸入 只有一行，為乙個長度小於255的表示式。輸出 一行。如果表示式中各括號互相匹配，則輸出 yes 否...
資料結構1800試題 第3章棧和佇列答案
第三章棧和佇列 一 選擇題 二 判斷題 部分答案解釋如下。1 尾遞迴的消除就不需用棧 2 這個數是前序序列為1,2,3,n，所能得到的不相似的二叉樹的數目。三 填空題 1 操作受限 或限定僅在表尾進行插入和刪除操作 後進先出 2 棧 3 3 1 2 4 23 100ch 5 0 n 1 top 1 ...