108年 - 108年關務三等資料結構#75754

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

試卷資訊

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

選擇題 (0)

申論題 (14)

1若 X 指向一個雙向鏈結串列如下，其中 X->prev 指向 NULL，X->next 指向資料為 21 的節點。請顯示並說明 doit（&X）執行過後該串列變化結果。（10 分）

2若 X 指向一個雙向鏈結串列如下，其中 X->prev 指向資料為 17 的節點， X->next 指向資料為 35 的節點。請顯示並說明 doit（&X）執行過後該串列的變化結果。（5 分）

3若 X 指向一個環狀雙向鏈結串列（circular doubly linked list），請說明 doit（&X）是否仍能順利執行。（5 分）

1若有一些介於 1 及 1,000 的正整數被儲存於 T，且要搜尋數字 364，請說明搜尋過程是否有可能為 3, 400, 388, 220, 267, 383, 382, 279, 364？（5 分）

2若有一些介於 1 及 1,000 的正整數被儲存於 T，且要搜尋數字 364，請說明搜尋過程是否有可能為 926, 203, 912, 241, 913, 246, 364？（5 分）

3若對 T 進行前序遍歷（pre-order traversal）的結果為 30, 20, 10, 15, 25, 23, 39, 35, 42。請說明若以後序遍歷（post-order traversal），結果為何。（5 分）

4若對 T 進行後序遍歷（post-order traversal）的結果為 25, 20, 34, 37, 31, 49, 46, 57, 60, 52, 41。請說明若以中序遍歷（in-order traversal），結果為何。（5 分）

5請說明可將二元搜尋樹 T 轉換為最小堆積（min heap）的程序為何？（10 分）

1請說明若以 Kruskal’s 演算法建立最小生成樹（minimum spanning tree）的過程中，依序被加入生成樹的邊。（5 分）

2請說明若以 Prim’s 演算法建立最小生成樹（minimum spanning tree）的過程中，依序被加入生成樹的邊。（5 分）

3請說明 Dijkstra’s 演算法的用途，並說明該演算法應用上的限制。（10 分）

4請說明將圖 G 從 f 節點開始執行 Dijkstra’s 演算法的過程並顯示節點加入的順序。（10 分）

1若雜湊函數為 H(k) = k mod 11，並以線性探測（linear probing）解決溢位（overflow）問題，請顯示將 15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12, 0, 21 依序置入 11 桶（buckets）x 2 槽（slots）雜湊表的最終結果。（10 分）

2若雜湊函數為 H(k) = k mod 7，並以平方探測（quadratic probing）解決溢位（overflow）問題，請顯示將 15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12 依序置入 7 桶（buckets）x 2 槽（slots）雜湊表的最終結果。（10 分）