資訊處理 99 年資料結構考古題

解釋下列名詞並舉例說明：（每小題5 分，共25 分） ㈠演算法（algorithm） ㈡時間複雜度（time complexity） ㈢遞迴式的解決問題方法（recursive solution） ㈣雙向佇列（Deque） ㈤最小成本生成樹（minimum cost spanning tree）

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

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

給予資料：3, 1, 5, 7, 15, 13, 9, 11， ㈠請寫出Shell 排序演算法。（15 分） ㈡並用Shell 排序法，將資料排成由大到小排列，請務必將每一步驟詳細畫出並詳 細說明。（10 分） 99年特種考試地方政府公務人員考試試題 類 科： 資訊處理

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

㈠寫出以深度優先搜尋（depth first search）之順序。（5 分） ㈡寫出以廣度優先搜尋（breadth first search）之順序。（5 分） ㈢試說明如何以堆疊（stack）完成深度優先搜尋（depth first search）演算法之關鍵 技術。（10 分）