99年特種考試地方政府公務人員三等考試 資料結構

解釋下列名詞並舉例說明：
(1) 演算法（algorithm）
(2) 時間複雜度（time complexity）
(3) 遞迴式的解決問題方法（recursive solution）
(4) 雙向佇列（Deque）
(5) 最小成本生成樹（minimum cost spanning tree）

請用二元樹（binary tree）針對10 筆資料：「陳、劉、王、蘇、高、胡、
蔡、何、簡、莊」設計出以鏈結（link）表示的二元樹資料結構，10 筆資
料的排序方式可自行決定（例如，依據筆劃數、注音符號、拼音或其他）。
(1) 請用任意程式語言寫出插入（insert）一個節點的演算法。
(2) 請用任意程式語言寫出刪除（delete）一個節點的演算法。
(3) 請用任意程式語言寫出中序（inorder）尋訪的演算法。
(4) 請將「陳、劉、王、蘇、高、胡、蔡、何、簡、莊」及你決定並明確
寫出的排序方式，用插入演算法逐一插入二元樹，請畫出最後的二元
樹。
(5) 請分析二元樹搜尋（searching）的O( )時間複雜度。

考慮某地區的地圖，地圖上有n 個城市，城市之間共有m 條相通的公路，
每條公路有一個長度（例如，10 公里）。某人經常需從城市S 出發，開
車前往另一城市T 送貨，請你設計一個軟體系統的資料結構與演算法，
幫忙找出路程最短的建議路徑與該路徑的總長度。
(1) 請設計一資料結構表示出地圖之n 個城市、m 條公路及公路長度。
(2) 依據你設計的資料結構，寫出Dijkstra 演算法，找出路程最短的建議
路徑與該路徑的總長度，並舉例說明。
(3) 分析Dijkstra 的時間複雜度。

給予資料：3, 1, 5, 7, 15, 13, 9, 11，
(1) 請寫出Shell 排序演算法。
(2) 並用Shell 排序法，將資料排成由大到小排列，請務必將每一步驟詳細
畫出並詳細說明。

考慮設計中式象棋（如圖）電腦程式系統：
(1) 請設計一資料結構使能隨時表示出棋盤現狀（current state），包含所
有棋子的位置、有那些棋子在棋盤上。
(2) 寫出一演算法能產生「象」或「相」在任意位置之下一步可前往且合
規則的所有位置（next feasible positions），注意，務必考慮其他棋子
阻礙的因素。「象」或「相」的移動規則：
田字形的對角移動；田字正中央有棋子時，不能移動前往。