高考申論題
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。請回答下列問題：
相較於系統 A，考慮另一個採用平方探查法之系統，系統 B 的表格大小為 8，索引亦從 0 開始，雜湊函數 $h^B(k)$ 及探查序列 $h_i^B(k)$ 分別定義為 $h^B(k) = k \bmod 8$、$h_i^B(k) = (h^B(k) + i + 2 \cdot i^2) \bmod 8 (i = 0,1,2,...)$。在非均勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用率可能較高？並說明理由。（5 分）
📝 此題為申論題
思路引導 VIP
比較系統 A (質數大小的普通平方探查) 與系統 B (2的冪次大小搭配特定探查函數) 覆蓋的槽位數量。對於質數大小 m 的表，傳統平方探查只能走訪約 (m+1)/2 個相異位置。而系統 B 的探查公式在 m=8 (即2的冪次) 時能成為一種排列(Permutation)，走訪所有 8 個位置。這使得系統 B 利用率較高。
🤖
AI 詳解
AI 專屬家教
【考點分析】 雜湊表平方探查法在不同表格大小與探查函數設計下的「探查覆蓋率（Probe Sequence Coverage）」。 【理論/法規依據】
▼ 還有更多解析內容