高考申論題
106年
[資訊處理] 資料結構
第 一 題
📖 題組：
遊樂園設計公司正在設計新的遊樂園，遊樂園將有 9 個遊樂設施，設施名稱暫定為 A, B, C, D, E, F, G, H, I。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園的初步規劃如表一，表內數字為兩遊樂設施之間商店街道之預計長度（每條街道長度皆不同）。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決定實際建置那些商店街道。 表一（節錄）：(A,B):18, (A,D):5, (A,E):13, (A,F):1; (B,C):9, (B,E):10, (B,F):16, (B,I):8; (C,E):11, (C,G):7, (C,H):12, (C,I):3; (D,E):17, (D,G):19; (E,G):2; (F,H):14, (F,I):15; (G,H):4; (H,I):6。 （一）若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分） （二）請計算符合上述（一）小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分） （三）但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）
遊樂園設計公司正在設計新的遊樂園，遊樂園將有 9 個遊樂設施，設施名稱暫定為 A, B, C, D, E, F, G, H, I。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園的初步規劃如表一，表內數字為兩遊樂設施之間商店街道之預計長度（每條街道長度皆不同）。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決定實際建置那些商店街道。 表一（節錄）：(A,B):18, (A,D):5, (A,E):13, (A,F):1; (B,C):9, (B,E):10, (B,F):16, (B,I):8; (C,E):11, (C,G):7, (C,H):12, (C,I):3; (D,E):17, (D,G):19; (E,G):2; (F,H):14, (F,I):15; (G,H):4; (H,I):6。 （一）若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分） （二）請計算符合上述（一）小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分） （三）但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）
📝 此題為申論題，共 4 小題
小題 (一)
若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分）
思路引導 VIP
- 關鍵字分析：「到達所有設施」（連通性）、「總長度越短越好」（權重總和最小）。
- 識別圖論模型：這符合「最小生成樹 (Minimum Spanning Tree, MST)」的定義。
小題 (二)
請計算符合上述（一）小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分）
思路引導 VIP
- 使用 Kruskal 演算法進行計算（較直觀）。
- 首先列出所有邊並依權重排序：
小題 (三)
但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）
思路引導 VIP
- 拆解需求：
- 「玩遍所有設施並回到起點」：迴路。
小題 (四)
AVL樹（AVL tree）
思路引導 VIP
看到 AVL 樹，應立即聯想到其「自平衡二元搜尋樹」的特性（任一節點左右子樹高度差不大於 1）。因此樹高被嚴格限制在 O(log n)，其搜尋、插入、刪除的操作時間皆與樹高成正比。