棧和佇列資料結構的特點

第三章習題

一、基本題

1．填空：線性表、棧和佇列都是_____結構，可以**性表的_____位置插入和刪除元素，對於棧只能在_______位置插入和刪除元素，對於隊只能在______位置插入和______位置刪除元素。

2. 棧和佇列資料結構的特點，什麼情況下用到棧，什麼情況下用到佇列？

3．設有編號為1，2，3，4的四輛車，順序進入乙個棧式結構的站台，試寫出這四輛車開出車站的所有可能的順序（每輛車可能入站，可能不入站，時間也可能不等）。

4．試證明：若借助棧由輸入序列1，2，… ，n得到輸出序列為p1p2…pn (它是輸入序列的乙個排列)，則在輸出序列中不可能出現這樣的情形：存在著i二、設計演算法題

1．假設稱正讀和反讀都相同的字串行為「回文」，例如，「abcddcba」、「qwerewq」是回文，「ashgash」不是回文。是寫乙個演算法判斷讀入的乙個以『@』為結束符的字串行是否為回文。

2．設以陣列se[m]存放迴圈佇列的元素，同時設變數rear 和front分別作為隊頭隊尾指標，且隊頭指標指向隊頭前乙個位置，寫出這樣設計的迴圈隊列入隊出隊的演算法。

3．假設以陣列se[m]存放迴圈佇列的元素，同時設變數rear 和num分別作為隊尾指標和隊中元素個數記錄，試給出判別此迴圈佇列的隊滿條件，並寫出相應入隊和出隊的演算法。

4．假設以帶頭結點的迴圈鍊錶表示乙個佇列，並且只設乙個隊尾指標指向尾元素結點（注意不設頭指標），試寫出相應的置空隊、入隊、出隊的演算法。

5．設計乙個演算法判別乙個算術表示式的圓括號是否正確配對。

6．寫乙個演算法，借助於棧將乙個單鏈表置逆。

7．兩個棧共享向量空間v[m]，它們的棧底分別設在向量的兩端，每個元素佔乙個分量，試寫出兩個棧公用的棧操作演算法：push(i,x)、pop(i)和top(i)，i=0和1 ,用以指示棧號。

三、實驗題目

1．揹包問題的求解：

假設有乙個能裝入總體積為t的揹包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿揹包，即使w1 +w2 + … + wn=t，要求找出所有滿足上述條件的解。例如：當t=10，各件物品的體積時，可找到下列4組解：

（1，4，3，2）

1，4，5）

8，2）

3，5，2）。

提示：可利用回溯法的設計思想來解決揹包問題。首先將物品排成一列，然後順序選取物品裝入揹包，假設已選取了前i 件物品之後揹包還沒有裝滿，則繼續選取第i+1件物品，若該件物品「太大」不能裝入，則棄之而繼續選取下一件，直至揹包裝滿為止。

但如果在剩餘的物品中找不到合適的物品以填滿揹包，則說明「剛剛」裝入揹包的那件物品「不合適」，應將它取出「棄之一邊」，繼續再從「它之後」的物品中選取，如此重複，，直至求得滿足條件的解，或者無解。

由於回溯求解的規則規則是「後進先出」因此自然要用到棧。