民國107年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第71題
依序將12, 33, 19, 27 存入7 個bucket(單一slot,位址為0 至6),若以重雜湊(Rehashing)來處 理溢位情形,雜湊函數如下:第一…
題目
依序將12, 33, 19, 27 存入7 個bucket(單一slot,位址為0 至6),若以重雜湊(Rehashing)來處 理溢位情形,雜湊函數如下:第一個雜湊函數 f1 (key) = key mod 7, 第二個雜湊函數 f2 (key) = (f1 (key)*key) mod 7 ,第三個雜湊函數 f3 (key) = (f2 (key)*key) mod 7 ,則下列敘述那些是正確?
- (1) 共發生五次碰撞(Collision)
- (2) 第二個雜湊函數共使用三次
- (3) 第三個雜湊函數共使用二次
- (4) 位址 6 中存放19
官方答案
(2) 第二個雜湊函數共使用三次、(4) 位址 6 中存放19
解析
依序插入並計算：12 代入 f1=12 mod 7=5，位址5空，存入5。33 的 f1=33 mod 7=5，碰撞，改用 f2=(5×33) mod 7=165 mod 7=4，存入4。19 的 f1=19 mod 7=5，碰撞，f2=(5×19) mod 7=95 mod 7=4 又碰撞，再用 f3=(4×19) mod 7=76 mod 7=6，存入6。27 的 f1=27 mod 7=6 碰撞，f2=(6×27) mod 7=162 mod 7=1，存入1。全程序共碰撞3次、f2使用3次、f3使用1次，位址6存放19，故第2、4項正確。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。