第3章棧和佇列自測卷答案
一、填空題（每空1分，共15分）
1.向量、棧和佇列都是線性結構，可以在向量的任何位置插入和刪除元素；對於棧只能在棧頂插入和刪除元素；對於佇列只能在隊尾插入和隊首刪除元素。
2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 。不允許插入和刪除運算的一端稱為棧底 。
3. 佇列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。
4. 在乙個迴圈佇列中，隊首指標指向隊首元素的前乙個位置。
5. 在具有n個單元的迴圈佇列中，隊滿時共有 n-1 個元素。
6. 向棧中壓入元素的操作是先移動棧頂指標 ，後存入元素 。
7. 從迴圈佇列中刪除乙個元素時，其操作是先移動隊首指標 ，後取出元素 。
8.帶表頭結點的空迴圈雙向鍊錶的長度等於 0 。
解：二、判斷正誤（判斷下列概念的正確性，並作出簡要的說明。）（每小題1分，共10分）
（ × ）1. 線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
錯，線性表是邏輯結構概念，可以順序儲存或鏈式儲存，與元素資料型別無關。
（ × ）2. 在表結構中最常用的是線性表，棧和佇列不太常用。
錯，不一定吧？呼叫子程式或函式常用，cpu中也用佇列。
（ √ ）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 ｄ．不確定
解釋：當p1=n，即n是最先出棧的，根據棧的原理，n必定是最後入棧的（事實上題目已經表明了），那麼輸入順序必定是1，2，3，…，n，則出棧的序列是n，…，3，2，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
解：隊滿條件是元素個數為m0。由於約定滿隊時隊首指標與隊尾指標相差1，所以不必再減1了，應當選a。
當然，更正確的答案應該取模，即：qu->front = = (qu->rear+1)% m0
（ 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 ④a4
e： ①1 ②2 ③ 3 ④ 0
答：abcde＝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,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c
e：① n+1 ②n+2 ③ nn-1 ⑤ n-2
答案：abcde=2, 2, 1, 6, 4
注意，向位址的高階生長，稱為向上生成堆疊；向位址低端生長叫向下生成堆疊，本題中底部為n，向位址的低端遞減生成，稱為向下生成堆疊。
8.從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。
在做進棧運算時，應先判別棧是否 a ；在做退棧運算時，應先判別棧是否 b 。當棧中元素為n個，做進棧運算時發生上溢，則說明該棧的最大容量為 c 。
為了增加記憶體空間的利用率和減少溢位的可能性，由兩個棧共享一片連續的記憶體空間時，應將兩棧的 d 分別設在這片記憶體空間的兩端，這樣，只有當 e 時，才產生上溢。
供選擇的答案：
a，b：①空滿 ③ 上溢 ④ 下溢
c： ①n-1 ② nn+1 ④ n/2
d： ① 長度 ②深度 ③ 棧頂 ④ 棧底
e：①兩個棧的棧頂同時到達棧空間的中心點 ②其中乙個棧的棧頂到達棧空間的中心點
③兩個棧的棧頂在達棧空間的某一位置相遇 ④兩個棧均不空，且乙個棧的棧頂到達另乙個棧的棧底
答案：abcde＝2, 1, 2, 4, 3
四、簡答題（每小題4分，共20分）
1. 【嚴題集3.2①和3.11①】說明線性表、棧與隊的異同點。
劉答：相同點：都是線性結構，都是邏輯結構的概念。都可以用順序儲存或鍊錶儲存；棧和佇列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。
不同點：①運算規則不同，線性表為隨機訪問，而棧是只允許在一端進行插入、刪除運算，因而是後進先出表lifo；佇列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表fifo。
② 用途不同，堆疊用於子程呼叫和保護現場，佇列用於多道作業處理、指令寄存及其他運算等等。
2.設有編號為1，2，3，4的四輛列車，順序進入乙個棧式結構的車站，具體寫出這四輛列車開出車站的所有可能的順序。
劉答：至少有14種。
① 全進之後再出情況，只有1種：4，3，2，1
② 進3個之後再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4
③ 進2個之後再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4
④ 進1個之後再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3
3.假設正讀和反讀都相同的字串行為「回文」，例如，『abba』和『abcba』是回文，『abcde』 和『ababab』則不是回文。假設一字串行已存入計算機，請分析用線性表、堆疊和佇列等方式正確輸出其回文的可能性？
答：線性表是隨機儲存，可以實現，靠迴圈變數（j--）從表尾開始列印輸出；
堆疊是後進先出，也可以實現，靠正序入棧、逆序出棧即可；
佇列是先進先出，不易實現。
哪種方式最好，要具體情況具體分析。若正文在機內已是順序儲存，則直接用線性表從後往前讀取即可，或將堆疊棧頂開到陣列末尾，然後直接用pop動作實現。（但堆疊是先減後壓還是……）
若正文是單鏈表形式儲存，則等同於佇列，需開輔助空間，可以從鏈首開始入棧，全部壓入後再依次輸出。
4.順序隊的「假溢位」是怎樣產生的？如何知道迴圈佇列是空還是滿？
答：一般的一維陣列佇列的尾指標已經到了陣列的上界，不能再有入隊操作，但其實陣列中還有空位置，這就叫「假溢位」。
採用迴圈佇列是解決假溢位的途徑。
資料結構C語言版第45章習題答案
第4 5章串和陣列自測卷答案 一 填空題 每空1分，共20分 1.不包含任何字元 長度為0 的串稱為空串 由乙個或多個空格 僅由空格符 組成的串稱為空白串。對應嚴題集4.1 簡答題 簡述空串和空格串的區別 2.設s a document mary.doc 則strlen s 20的字元定位的位置為 ...
資料結構C語言版第2章練習題
第2章線性表練習題 一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n...
資料結構C語言版部分習題及答案
第二章習題與解答 一判斷題 1 線性表的邏輯順序與儲存順序總是一致的。2 順序儲存的線性表可以按序號隨機訪問。3 順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。4 線性表中的元素可以是各種各樣的，但同一線性表中的資料元素具有相同的特性，因此是屬於同一資料物...