民國110年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第61題
依序將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) 第三個雜湊函數共使用二次
- (2) 位址 6 中存放19
- (3) 第二個雜湊函數共使用三次
- (4) 共發生五次碰撞(Collision)
官方答案
(2) 位址 6 中存放19、(3) 第二個雜湊函數共使用三次
解析
依序插入：f1(12)=12 mod 7=5，位址5空，無碰撞。f1(33)=33 mod 7=5 碰撞，改算 f2(33)=(5×33) mod 7=165 mod 7=4，存入4。f1(19)=5 碰撞，f2(19)=(5×19) mod 7=95 mod 7=4 再碰撞，f3(19)=(4×19) mod 7=76 mod 7=6，存入位址6。f1(27)=27 mod 7=6 碰撞，f2(27)=(6×27) mod 7=162 mod 7=1，存入1。合計碰撞4次、f2使用3次、f3僅使用1次，故位址6存19與f2用三次正確。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。