高考申論題
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。請回答下列問題：
給定一個空的雜湊表，依序插入下列鍵值 22、1、13、24、35、46、7、18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值 46 時的完整探查過程。（10 分）
📝 此題為申論題
思路引導 VIP
本題考查開放定址法中的平方探查法（Quadratic Probing）。首先，根據雜湊函數 h(k) = k mod 11 計算初始位置。若發生碰撞，則依次代入 i = 1, 2, 3... 進行探查。需一步步將給定數列插入並記錄索引。特別注意對於 46 插入時的每一次探查計算，需完整列出以符合題目要求。
🤖
AI 詳解
AI 專屬家教
【考點分析】 雜湊表（Hash Table）的插入操作，特別是碰撞解決機制中的平方探查法（Quadratic Probing）。 【理論/法規依據】
▼ 還有更多解析內容