高考申論題
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。請回答下列問題：
承上題，執行插入鍵值 12，請列出插入時的探查過程、操作停止的理由，並寫出 12 最後插入那一個儲存格。插入時，DELETED 標記視為可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分）
📝 此題為申論題
思路引導 VIP
處理 DELETED 欄位時插入的標準流程：因為題目規定「鍵值不能重複」，所以在探查到 DELETED 時，我們能先記下該位置，但必須繼續往下探查直到遇到「完全空」的儲存格，確認 12 確實不在表中，最後才能把 12 放進第一個遭遇的 DELETED 位置。