加載中. ..
PDF
100
年公務人員特種考試海岸巡防人員考試、
100
年公務
人員特種考試關務人員考試、
100
年公務人員特種考試稅
務人員考試、
100
年特種考試退除役軍人轉任公務人員考
試及
100
年國軍上校以上軍官轉任公務人員考試試題
代號：23560
等 別： 三等關務人員考試
類(科)別： 資訊處理
科 目： 資料結構
考試時間： 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
年國軍上校以上軍官轉任公務人員考試試題
代號：23560
等 別： 三等關務人員考試
類(科)別： 資訊處理
科 目： 資料結構
全一張
（
背面
）
題組：請根據下圖回答第三至五題：
圖中表示有 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 分）