高考申論題
107年
[資訊處理] 資料結構
第 一 題
📖 題組：
一、
一、
📝 此題為申論題，共 2 小題
小題 (一)
請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的差異（13 分）。
思路引導 VIP
這題考驗考生對「靜態資料結構（陣列）」與「動態資料結構（樹）」的本質區別。分析時應從以下維度切入：1. 空間分配（連續 vs 非連續）；2. 建置成本（排序 vs 逐一插入）；3. 搜尋邏輯（Index計算 vs 指標追蹤）。考生應意識到二分搜尋通常前提是已排序陣列，而BST是透過指標鏈結。
小題 (二)
若有 n 個鍵值，以下列甲和乙兩種資料結構策略儲存：
策略甲：由小到大依序儲存在一陣列中
策略乙：以 AVL tree 架構儲存
請以 Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或兩者效能相近：
1. 尋找特定鍵值 k；
2. 尋找排序為 j 的鍵值；
3. 刪除特定鍵值 k；
4. 刪除排序為 j 的鍵值；
5. 插入新鍵值；
6. 依序輸出所有鍵值。（12 分）
思路引導 VIP
此題是典型的資料結構比較題。策略甲是「已排序陣列」，策略乙是「平衡二元搜尋樹（AVL）」。 解題關鍵在於：陣列擁有 O(1) 的隨機存取能力，但在插入/刪除時需移動大量元素 O(n)；AVL 樹在搜尋、插入、刪除均維持 O(log n) 的穩定效率，但隨機存取（尋找第 j 個）並非其天生強項，除非節點有記錄子樹大小（Size）。