22 某雜湊表（hash table）有 13 個空格。假設雜湊函數（hash function）為 h(k) = k mod 13，且此雜湊表使用平 方探測法（quadratic probing，公式為 h(k,i) = ( h(k) + i2 ) mod 13）來處理碰撞（collision）。依此方法，若將 28、30、41、24、47、54、17 等 7 個數字依序存入後，則搜尋數字 2 時，需要與表內多少個數字作比對？
(A)3
(B)4
(C)5
(D)6

答案：登入後查看
統計： A(68), B(65), C(52), D(57), E(0) #806933

詳解 (共 9 筆)

#3295889


(共 1 字，隱藏中）
前往觀看
12
3
#1108595
怎麼算都是5
3
1
#1113241
最後一次也算才會是6次 

3
0
#5621897

633544d614fb8.jpg
提醒一下 ( h(k) + i2 ) -> i = 1, 2, 3, 4, 5.....

先存入數字 :
28 mod 13 = 2 (存入)

30 mod 13 = 4 (存入)

41 mod 13 = 2 (衝突)
2 + 12 = 3 (存入)

24 mod 13 = 11 (存入)

47 mod 13 = 8 (存入)

54 mod 13 = 2 (衝突)
2 + 12 = 3 (衝突)
2 + 22 = 6 (存入)

17 mod 13 = 4 (衝突)
4 + 12 = 5 (存入)

接著找數字 2 (直到找到空格為止)
 2 mod 13 = 2 (衝突) -> 28
2 + 12 = 3 (衝突) -> 41
2 + 22 = 6 (衝突) -> 54
2 + 32 = 11 (衝突) -> 24
2 + 42 = 18 ，18 mod 13 = 5 (衝突) -> 17
2 + 52 = 27 ，27 mod 13 = 1 (無資料) -> X

總共比對 5 個數字

1
0
#2186128
原本題目:22 某雜湊表（hash ta...
(共 489 字，隱藏中）
前往觀看
1
0
#2184968
平方探測法公式有誤，h(k,i) = (...
(共 100 字，隱藏中）
前往觀看
0
0
#1112861
平方探測法公式有誤，h(k,i) = ( h(k) + i^2 ) mod 13） ， i是平方!
如有碰撞再帶平方探測法公式，i所帶的值，為h(k) = k mod 13之餘數，計算出新的雜湊函數。
0
0
#1379909
求詳解?

0
0
#1054405
不懂?
0
1

私人筆記 (共 1 筆)

私人筆記#1359168
未解鎖
好像是比較5個數字,6次? 位置mod...
(共 244 字，隱藏中）
前往觀看
0
0