110年 - 110 公務升官等考試_薦任_資訊處理：資料結構#103713

科目：公職◆資料結構 | 年份：110年 | 選擇題數：0 | 申論題數：12

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (12)

(一) B⁺樹（B⁺ Tree）

(二)完美雜湊函數（Perfect Hash Function）

(三)霍夫曼編碼（Huffman Coding）

(四)拓撲排序（Topology Sort）

(一)將指標 p 之後面連續兩個節點位置交換，如下圖所示。（15 分）

(二)將指標 p 之前後節點位置交換，如下圖所示。（15 分）

(一)此二維空間平面分割結果將為何？

(二)對應的二元樹將為何？

(一)使用 Kruskal’s algorithm 找最小成本擴張樹（Minimal Cost Spanning 。執行過程中，將邊（edge）逐步加入此 MST 之順序為何？ Tree, MST）請以邊所對應的兩端節點表示此邊。（5 分）

(二)使用 Prim’s algorithm 找出最小成本擴張樹（MST），從節點 a 出發。執行過程中，將邊（edge）逐步加入此 MST 之順序為何？請以邊所對應的兩端節點表示此邊。（5 分）

(三)使用 Dijkstra’s algorithm 找出從節點 a（來源節點）到其五個節點（目的節點）之最短路徑（shortest path）。執行過程中，逐步找出最短路徑的目的節點順序為何？從節點 a 到目的節點之最短路徑被找出表示演算法不再檢視此目的節點之其它可能最短路徑。（10 分）

(四)來源節點 a 出發到其他五個目的節點之最短路徑走法與成本分別為何？（10 分）