2017-02-16 89 views
1

1月份我失敗了算法考試。我明天要去口試。當我有一個我無法理解的答案時,我正在通過普通考試和答案。 Here is the question參加考試的考點

根據答案,答案是A.爲什麼? 20模7是6,但12模7是5並且是空的。希望你能幫助我。

PS:很抱歉,如果格式是錯誤的

+0

不要忘記把k乘以2 –

+0

然後(2 * 20 + 3 * 0^2)mod 7是5.而第5個槽是空的 –

+0

這就是其中20在回答a) –

回答

0
h(20,0) = 5 
h(12,0) = 3 
h(5,0) = 3* 
h(5,1) = 6 
h(3,0) = 6* 
h(3,1) = 2 
h(1,0) = 2* 
h(1,1) = 5* 
h(1,2) = 0 

* collision 
1
i k 
------------------------- 
0 20 (2*20+3*0^2) mod 7 = (40 + 0) mod 7 = 40 mod 7 = 5 <- [e, e, e, e, e, 20, e] 
0 12 (2*12+3*0^2) mod 7 = (24 + 0) mod 7 = 24 mod 7 = 3 <- [e, e, e, 12, e, 20, e] 
0  5 (2*5+3*0^2) mod 7 = (10 + 0) mod 7 = 10 mod 7 = 3 <- collision 
1  5 (2*5+3*1^2) mod 7 = (10 + 3) mod 7 = 13 mod 7 = 6 <- [e, e, e, 12, e, 20, 5] 
0  3 (2*3+3*0^2) mod 7 = (6 + 0) mod 7 = 6 mod 7 = 6 <- collision 
1  3 (2*3+3*1^2) mod 7 = (6 + 3) mod 7 = 9 mod 7 = 2 <- [e, e, 3, 12, e, 20, 5] 
0  1 (2*1+3*0^2) mod 7 = (2 + 0) mod 7 = 2 mod 7 = 2 <- collision 
1  1 (2*1+3*1^2) mod 7 = (2 + 3) mod 7 = 5 mod 7 = 5 <- collision 
2  1 (2*1+3*2^2) mod 7 = (2 + 12) mod 7 = 14 mod 7 = 0 <- [1, e, 3, 12, e, 20, 5] 

所以

[1, empty, 3, 12, empty, 20, 5] 
+0

爲什麼我只有0,1和2,而不是3? –

+0

對於每個數字'k',以'i = 0'開頭。對於每次碰撞,你增加'i'並計算二次散列函數,直到找到一個空插槽。在這個特定的問題中,你永遠不會到達'i = 3',因爲當'i = 2'時你會發現'k = 1'的空插槽。 –

1

這裏是如何工作的,每次發生碰撞,二次探測將被使用(用i=1,2,..),直到散列表中存在可用空間:

enter image description here