第3章棧和佇列自測卷
一、填空題
1. 向量(線性表)、棧和佇列都是線性結構，可以在向量的任意位置插入和刪除元素；對於棧只能在棧頂插入和刪除元素；對於佇列只能在隊尾插入和隊首刪除元素。
2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 。不允許插入和刪除運算的一端稱為棧底 。
3. 佇列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。
4. 在乙個迴圈佇列中，隊首指標指向隊首元素的前乙個位置。
5. 在具有n個單元的迴圈佇列中，隊滿時共有 n -1 個元素。
6. 向棧中壓入元素的操作是先移動棧頂指標後存入元素
7. 從迴圈佇列中刪除乙個元素時，其操作是先移動隊首指標 ，後取出元素 。
8. 帶表頭結點的空迴圈雙向鍊錶的長度等於 0 。
二、判斷正誤（判斷下列概念的正確性，並作出簡要的說明。）（每小題1分，共10分）
（ 錯 ）1. 線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
（ 錯 ）2. 在表結構中最常用的是線性表，棧和佇列不太常用。
（ 對 ）3. 棧是一種對所有插入、刪除操作限於在表的一端進行的線性表，是一種後進先出型結構。
（ 對 ）4. 對於不同的使用者，乙個表結構既可以是棧，也可以是佇列，也可以是線性表。
（ 錯 ）5. 棧和鍊錶是兩種不同的資料結構。
（ 錯 ）6. 棧和佇列是一種非線性資料結構。
（ 對 ）7. 棧和佇列的儲存方式既可是順序方式，也可是鏈結方式。
（ 對 ）8. 兩個棧共享一片連續記憶體空間時，為提高記憶體利用率，減少溢位機會，應把兩個棧的棧底分別設在這片記憶體空間的兩端
（ 錯 ）9. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進後出型結構。
（ 錯 ）10. 乙個棧的輸入序列是12345，則棧的輸出序列不可能是12345。
三、單項選擇題（每小題1分，共20分）
（ b ）1. 棧中元素的進出原則是
ａ．先進先出 ｂ．後進先出 ｃ．棧空則進 ｄ．棧滿則出
（ c ）2. 若已知乙個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為
ａ．i ｂ．n=i ｃ．n-i+1 ｄ．不確定
（ b ）3. 判定乙個棧st（最多元素為m0）為空的條件是
ａ．st->top<>0 ｂ．st->top=0 ｃ．st->top<>m0 ｄ．st->top=m0
（ a ）4. 判定乙個佇列qu（最多元素為m0）為滿佇列的條件是
ａ．qu->rear － qu->front = = m0 ｂ．qu->rear － qu->front －1= = m0
ｃ．qu->front = = qu->rearqu->front = = qu->rear+1
（ d ）5．陣列ｑ［ｎ］用來表示乙個迴圈佇列，ｆ為當前佇列頭元素的前一位置，ｒ為隊尾元素的
（ａ）r－fn＋f－r）% n; （ｃ）n＋r－fn＋r－f）% n
6. 設有4個資料元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進棧或進隊操作時，按a1、a2、a3、a4次序每次進入乙個元素。假設棧或隊的初始狀態都是空。
現要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是 a ，第二次出棧得到的元素是 b ；類似地，考慮對這四個資料元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是 c ，第二次出隊得到的元素是 d 。經操作後，最後在棧中或隊中的元素還有 e 個。
a～d：①a1 ②a2 ③ a3 ④a4e： ①1 ②2 ③ 3 ④ 0
答：a、b、c、d、e分別為 2 、 4 、 1 、 2 、 2
7. 棧是一種線性表，它的特點是 a 。設用一維陣列a[1,…,n]來表示乙個棧，a[n]為棧底，用整型變數t指示當前棧頂位置，a[t]為棧頂元素。
往棧中推入（push）乙個新元素時，變數t的值 b ；從棧中彈出（pop）乙個元素時，變數t的值 c 。設棧空時，有輸入序列a，b，c，經過push，pop，push，push，pop操作後，從棧中彈出的元素的序列是 d ，變數t的值是 e 。
a： ① 先進先出 ②後進先出 ③進優於出出優於進 ⑤ 隨機進出
b，c： ① 加1 ②減1不變清0 ⑤ 加2 ⑥減2
d： ① a,bb,cc,ab,ac,ba,c
e： ① n+1 ②n+2nn-1 ⑤ n-2
答：a、b、c、d、e分別為 2 、 2 、 1 、 6 、 4
8. 在做進棧運算時，應先判別棧是否 a ；在做退棧運算時，應先判別棧是否 b 。當棧中元素為n個，做進棧運算時發生上溢，則說明該棧的最大容量為 c 。
為了增加記憶體空間的利用率和減少溢位的可能性，由兩個棧共享一片連續的記憶體空間時，應將兩棧的 d 分別設在這片記憶體空間的兩端，這樣，只有當 e 時，才產生上溢。
a，b：①空滿 ③ 上溢 ④ 下溢
c： ①n-1 ② nn+1 ④ n/2
d： ① 長度 ②深度 ③ 棧頂 ④ 棧底
e：①兩個棧的棧頂同時到達棧空間的中心點 ②其中乙個棧的棧頂到達棧空間的中心點
③兩個棧的棧頂在達棧空間的某一位置相遇 ④兩個棧均不空，且乙個棧的棧頂到達另乙個棧的棧底
答：a、b、c、d、e分別為 2 、 1 、 2 、 4 、 3
四、簡答題（每小題4分，共20分）
1. 說明線性表、棧與隊的異同點。
2. 設有編號為1，2，3，4的四輛列車，順序進入乙個棧式結構的車站，具體寫出這四輛列車開出車站的所有可能的順序。
3. 假設正讀和反讀都相同的字串行為「回文」，例如，『abba』和『abcba』是回文，『abcde』 和『ababab』則不是回文。假設一字串行已存入計算機，請分析用線性表、堆疊和佇列等方式正確輸出其回文的可能性？
4. 順序隊的「假溢位」是怎樣產生的？如何知道迴圈佇列是空還是滿？
5. 設迴圈佇列的容量為40（序號從0到39），現經過一系列的入隊和出隊運算後，有
① front=11，rear=19; ② front=19，rear=11；問在這兩種情況下，迴圈佇列中各有元素多少個？
五、閱讀理解（每小題5分，共20分）
1. 按照四則運算加、減、乘、除和冪運算（↑）優先關係的慣例，並仿照教材例3-2的格式，畫出對下列算術表示式求值時運算元棧和運算子棧的變化過程：
a－b×c/d+e↑f
2. 寫出下列程式段的輸出結果（棧的元素型別selem type為char）。
void main( );
printf(x);
}4. 簡述以下演算法的功能（棧和佇列的元素型別均為int）。
void algo3(queue &q);
while(!stackempty(s))
}六、演算法設計（每小題5分，共15分。至少要寫出思路）
1. 假設乙個算術表示式中包含圓括弧、方括弧和花括弧三種型別的括弧，編寫乙個判別表示式中括弧是否正確配對的函式correct(exp,tag)；其中：exp為字串型別的變數（可理解為每個字元占用乙個陣列元素），表示被判別的表示式，tag為布林型變數。
資料結構第3章棧與佇列習題
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 一...
資料結構1800試題 第3章棧和佇列答案
第三章棧和佇列 一 選擇題 二 判斷題 部分答案解釋如下。1 尾遞迴的消除就不需用棧 2 這個數是前序序列為1,2,3,n，所能得到的不相似的二叉樹的數目。三 填空題 1 操作受限 或限定僅在表尾進行插入和刪除操作 後進先出 2 棧 3 3 1 2 4 23 100ch 5 0 n 1 top 1 ...
《資料結構》習題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.棧結構通...