首頁 > 線上測驗 > 公職考試>地方特考/三等>資訊處理 > 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),注意,務必考慮其他棋子 阻礙的因素。「象」或「相」的移動規則: 田字形的對角移動;田字正中央有棋子時,不能移動前往。
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)