高考申論題
106年
[資訊處理] 資料結構
第 四 題
📖 題組：
下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average case），搜尋（search）、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列的各項資料已事先填入作為範例。（每小題 5 分，共 20 分） | | 搜尋(search) | 插入(insertion) | 刪除(deletion) | | :--- | :---: | :---: | :---: | | 陣列 | O(n) | O(n) | O(n) | | (一)佇列（queue） | | | | | (二)雙向連結串列（doubly-linked list） | | | | | (三)二元搜尋樹（binary search tree） | | | | | (四)AVL樹（AVL tree） | | | |
下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average case），搜尋（search）、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列的各項資料已事先填入作為範例。（每小題 5 分，共 20 分） | | 搜尋(search) | 插入(insertion) | 刪除(deletion) | | :--- | :---: | :---: | :---: | | 陣列 | O(n) | O(n) | O(n) | | (一)佇列（queue） | | | | | (二)雙向連結串列（doubly-linked list） | | | | | (三)二元搜尋樹（binary search tree） | | | | | (四)AVL樹（AVL tree） | | | |
📝 此題為申論題，共 4 小題
小題 (四)
AVL樹（AVL tree）
思路引導 VIP
看到 AVL 樹，應立即聯想到其「自平衡二元搜尋樹」的特性（任一節點左右子樹高度差不大於 1）。因此樹高被嚴格限制在 O(log n)，其搜尋、插入、刪除的操作時間皆與樹高成正比。
小題 (一)
若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分）
思路引導 VIP
- 關鍵字分析：「到達所有設施」（連通性）、「總長度越短越好」（權重總和最小）。
- 識別圖論模型：這符合「最小生成樹 (Minimum Spanning Tree, MST)」的定義。
小題 (二)
請計算符合上述（一）小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分）
思路引導 VIP
- 使用 Kruskal 演算法進行計算（較直觀）。
- 首先列出所有邊並依權重排序：
小題 (三)
但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）
思路引導 VIP
- 拆解需求：
- 「玩遍所有設施並回到起點」：迴路。