數據結構第三章：棧與隊列習題解析指南（嚴蔚敏版）

章節概覽

本文整理了《數據結構》（嚴蔚敏、吳偉民版）第三章「棧和隊列」配套習題集的完整解析。內容分為基礎知識題與算法設計題，涵蓋棧的基本操作、隊列與雙端隊列特性、遞歸與非遞歸算法轉換、表達式求值、迷宮求解、括號匹配、回文判斷、模擬鐵路調度等經典應用。所有習題均提供詳細邏輯分析、代碼框架及關鍵難點提示。

一、基礎知識題（3.1~3.14）

棧的基本特性與應用

3.1 鐵路調度模型：給定進站序列，分析可能的出站序列，並給出棧操作序列（S=入棧，X=出棧）。
3.2 簡述棧與線性表的區別（限制性線性表）。
3.3 追蹤棧操作代碼輸出結果（字符元素）。
3.4 分析兩個棧算法功能：algo1逆序棧元素，algo2刪除棧中所有值為e的元素。
3.5 合法棧操作序列判別準則（任意前綴中S數≥X數，總數相等）及證明不同合法序列輸出元素實體序列不同。
3.6 證明棧輸出排列中不存在模式 pj < pk < pi (i 3.7 畫出含冪運算的算術表達式求值過程中操作數棧與運算符棧變化。
3.8 推導n階漢諾塔最少移動次數（2^n - 1）。
3.9 將給定遞推過程（倒序輸出）改寫為遞歸。
3.10 將帶輸入輸出的遞歸函數改寫為非遞歸（模擬棧）。
3.11 比較隊列與棧的同異（FIFO vs LIFO）。
3.12 追蹤隊列操作代碼輸出結果。
3.13 分析利用棧逆置隊列元素的算法功能。
3.14 雙端隊列輸出序列分類：輸入受限/輸出受限/雙端均受限可得到的序列特徵。

二、算法設計題

順序棧（3.15~3.27）

• 3.15 共享數組雙向棧初始化、入棧、出棧算法，討論過程/函數設計優劣。
• 3.16 火車調度：將軟席車廂移至硬席前，輸出操作序列。
• 3.17 判別字符序列是否為「序列1&序列2」且序列2為序列1逆序（回文結構）。
• 3.18 判別表達式中括號配對（單類型）。
• 3.19 三種括號任意嵌套配對判別（順序表存儲表達式）。
• 3.20 種子填充算法：二維數組圖像區域顏色替換（4鄰域遞歸/棧）。
• 3.21 中綴轉後綴（逆波蘭）表達式算法（單字母變量、四則運算）。
• 3.22 後綴表達式求值算法。
• 3.23 判斷後綴表達式是否合法逆波蘭式，合法則轉前綴（波蘭式）。
• 3.24 遞歸函數g(m,n)實現及求g(5,2)棧變化圖解。
• 3.25 遞歸函數F(n)實現與消除遞歸。
• 3.26 平方根迭代法遞歸實現與消除遞歸。
• 3.27 Ackerman函數遞歸/非遞歸算法及akm(2,1)棧變化。

鏈隊列（3.28）

帶頭結點循環鏈表僅設尾指針實現初始化、入隊、出隊。

順序隊列/循環隊列（3.29~3.34）

• 3.29 設置tag域區分空/滿的循環隊列入/出隊算法，時空權衡討論。
• 3.30 用rear和length定義循環隊列，給出滿條件及入/出隊算法。
• 3.31 利用循環隊列判別回文（以@結束）。
• 3.32 循環隊列求k階斐波那契數列前n+1項（滿足fn≤max
• 3.33 順序存儲實現輸出受限雙端循環隊列，短作業優先入隊策略。
• 3.34 輸出受限雙端隊列調度三類車廂（P、H、S），輸出操作序列（E/D/A）。

資源鏈接

課本源碼、習題解析合輯、測試數據下載請參考原文檔說明中的鏈接。