普考申論題
110年
[統計] 資料處理概要
第 三 題
📖 題組：
有一筆資料的鍵值依序為 32，17，85，16，51，60。使用除法雜湊函數 h(k) = k mod 7 來建立 7 個桶（buckets）且每個桶只有一個槽（slot）的雜湊表（hash table）。當發生碰撞（collision）與溢位問題時，
有一筆資料的鍵值依序為 32，17，85，16，51，60。使用除法雜湊函數 h(k) = k mod 7 來建立 7 個桶（buckets）且每個桶只有一個槽（slot）的雜湊表（hash table）。當發生碰撞（collision）與溢位問題時，
📝 此題為申論題，共 4 小題
小題 (三)
請說明何謂連結串列法（chaining）。（8 分）
思路引導 VIP
連結串列法與開放定址最大的不同在於「不會去搶別人的位置」。想像每個 Bucket 都是一個掛鉤，碰撞時就「往下掛」。關鍵字：外部連結、桶子包含指標、解決溢位。
小題 (一)
如果使用開放定址（open addressing）中的線性探測法（linear probing），請寫出產生的雜湊表格。（5 分）而此方法的主要缺點為何？（5 分）
思路引導 VIP
線性探測是「位置被占走就看下一個」。先計算每個 Key 的原始位置：32→4, 17→3, 85→1, 16→2, 51→2(撞), 60→4(撞)。接著按照順序處理碰撞。缺點則要聯想到「群聚效應」。
小題 (二)
如果使用開放定址（open addressing）中的平方探測法（quadratic probing），新的雜湊函數為：H(k, i) = [h(k) ± i^2] mod 7，其中 i 為目前進行的探測次數。請寫出產生的雜湊表格。（10 分）
思路引導 VIP
平方探測是以平方級距跳躍。注意公式中的 ± 符號。依照 i=1, 2... 進行探測。注意 mod 7 的結果必須為正數。一般實務上常只用 +i^2，但本題指定 ±，應優先考慮 + 再考慮 -（或依照題目公式邏輯）。
小題 (四)
請寫出使用連結串列法而產生的雜湊表格。（7 分）
思路引導 VIP
這是最簡單的填表題。只要把 mod 7 的結果算出來，相同的放在同一列即可。32(4), 17(3), 85(1), 16(2), 51(2), 60(4)。
雜湊碰撞處理：鏈結法
💡 以連結串列儲存衝突鍵值，克服雜湊表空間限制的外部定址技術。
| 比較維度 | 連結串列法 (Chaining) | VS | 開放定址法 (Open Addressing) |
|---|---|---|---|
| 儲存位置 | 外部串列 (表外) | — | 表內空位 |
| 裝載因子 | 可大於 1 | — | 必須小於等於 1 |
| 群聚效應 | 不會產生 | — | 容易產生 (如線性探測) |
| 刪除操作 | 簡單 (刪除節點) | — | 複雜 (需特別標記) |
💬鏈結法空間運用較彈性，適合資料量變動大且不希望有群聚效應的情境。
