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

100年公務人員特種考試海岸巡防人員考試、100年公務 人員特種考試關務人員考試、100年公務人員特種考試稅 務人員考試、100年特種考試退除役軍人轉任公務人員考 試及100年國軍上校以上軍官轉任公務人員考試試題 類(科)別： 資訊處理 考試時間： 2 小時 座號： ㈡不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。 （請接背面） 、下圖為二元搜尋樹（binary search tree），請回答下列問題：（每小題5 分，共30 分） 一 70 50 ㈠35 的successor 為何？ ㈡50 的successor 為何？ ㈢寫出Entry<E> successor(Entry<E> e) 的pseudo code。 ㈣寫出preorder traversal。 ㈤寫出postorder traversal。 ㈥寫出inorder traversal。 二、下圖為min heap，請回答下列問題：（25 分） 10 15 21 19 30 50 ㈠畫出min heap 實際上在大小為10 的array 中的data structure。 ㈡insert 11 至min heap 之後， 1.畫出insert 後的tree-like min heap。 2.畫出其array data structure。 ㈢承上，再delete root 且向left sub-tree 調整， 1.畫出調整後的tree-like min heap。 2.畫出其array data structure。 80 60 20 10 30 55 35 100年公務人員特種考試海岸巡防人員考試、100年公務 人員特種考試關務人員考試、100年公務人員特種考試稅 務人員考試、100年特種考試退除役軍人轉任公務人員考 試及100年國軍上校以上軍官轉任公務人員考試試題 類(科)別： 資訊處理 題組：請根據下圖回答第三至五題： 圖中表示有4 個朋友，名（name）叫張三（Chang San, CS）、李四（Lee Si, LS）、 王五（Wang Wu, WW）及趙六（Chao Liu, CL），用兩個字母代表各人，如CS 代表 張三，並標示兩兩住家交通狀況及距離（distance），如張三家有7 公里的路到李四 家。 hash function：h(name) = int (1st char of name)*31+int(2nd char of name) hash table size：11 (index 0 - 10) index：h(name) mod 11 int( “C” )=67, int( “S” )=83, int( “L” )=76, int( “W” )=87 舉張三為例： index( “CS” )=(int( “C” )*31+int( “S” )) mod 11 = (67*31+83) mod 11 = 4 三、用HashMap <Name, LinkedList <NameDistancePair>> 的Java data structure 畫出此 directed weighted graph。（15 分） 四、找出張三到王五的Dijkstra’s Shortest Path，要畫出3 個data structures: 1. weight sum 2. predecessor 3. priority queue 的最後結果。（15 分） 五、找出以張三為root 的Prim’s Minimal Spanning Tree，要畫出1. tree 2. priority queue 2 個data structures 的最後結果。（15 分）

假設有一整數資料陣列 B[0..7]，裡面儲存8 個整數數值分別為{25, 57, 86, 37, 12, 92, 48, 33}。今欲對此陣列進行由小到大排序： ㈠試寫出氣泡浮昇排序（bubble sort）演算法或函式。（10 分） ㈡將排序過程中每一回合（iteration）陣列內容的變化情形寫出。（10 分）

假設鏈結串列（linked list）資料結構的宣告如下： struct node { char info; struct node *next; } *list; ㈠試寫一函式（function）計算並回傳鏈結串列 list 內部節點（node）之數量。 （10 分） ㈡試寫一函式（function）將鏈結串列list 進行反轉（inverse）。（10 分）

依序輸入一組整數資料{25, 57, 86, 37, 12, 92, 48, 33}並建立出二元搜尋樹（binary search tree）。 ㈠說明對二元搜尋樹（binary search tree）加入一筆資料的方法為何？（10 分） ㈡請畫出所建立之二元搜尋樹（binary search tree）。（10 分）

給一個加權連通無向圖（weighted connected graph），所有邊線的加權值為正整數。 使用下列的貪婪演算法（Greedy algorithm）尋找從出發的節點Start 到目的地節點 Goal 之最短路徑。 初始化集合Path ={Start} 初始化集合VisitedVertices ={Start} 如果Start =Goal, 離開;否則,繼續第4 步驟 找出具有最小加權值的邊線edge（Start, v）其中v 不在集合VisitedVertices 內 將 {v} 加入集合Path 將 {v} 加入集合VisitedVertices 將Start 設為v 並執行第3 步驟 ㈠請問是否可以正確找到最短路徑？（10 分） ㈡請說明原因或理由。（需舉圖例說明理由，否則不予計分）（10 分）