高考申論題
115年
[資訊處理] 資料結構
第 鿪 題
📖 題組：
某系統 A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重複鍵值，雜湊表有 11 個儲存格，索引從 0 開始，雜湊函數（hash function）為 $h^A(k) = k \bmod 11$，其用平方探查法（quadratic probing）處理碰撞（collision）問題，探查序列為 $h_i^A(k) = (h^A(k) + i^2) \bmod 11 (i = 0,1,2,...)$，刪除資料時，被刪除資料的位置標記為特殊符號 DELETED。請回答下列問題：
某系統 A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重複鍵值，雜湊表有 11 個儲存格，索引從 0 開始，雜湊函數（hash function）為 $h^A(k) = k \bmod 11$，其用平方探查法（quadratic probing）處理碰撞（collision）問題，探查序列為 $h_i^A(k) = (h^A(k) + i^2) \bmod 11 (i = 0,1,2,...)$，刪除資料時，被刪除資料的位置標記為特殊符號 DELETED。請回答下列問題：
承上題，依序刪除鍵值 24、13，畫出刪除後的雜湊表狀態。並說明為什麼刪除鍵值時需用 DELETED 標記，而不能將該鍵值所在的儲存格恢復成「從未存放過鍵值」的空狀態。（5 分）
📝 此題為申論題
思路引導 VIP
本題測試考生對開放定址法中刪除機制的理解。刪除時不可直接清空，應將對應索引位置標註為 DELETED。分析理由時，需點出若直接清空（設為 null），會截斷後續因碰撞而向後尋址的其他鍵值（例如 35、46）的探查路徑，導致尋找失敗。