計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

原本題目:

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

修改成為

22 某雜湊表（hash table）有 13 個空格。假設雜湊函數（hash function）為 h(k) = k mod 13，且此雜湊表使用平 方探測法（quadratic probing，公式為 h(k,i) = ( h(k) + i² ) mod 13）來處理碰撞（collision）。依此方法，若將 28、30、41、24、47、54、17 等 7 個數字...

原本題目:

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

修改成為

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

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

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

30 mod 13 = 4 (存入)

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

24 mod 13 = 11 (存入)

47 mod 13 = 8 (存入)

54 mod 13 = 2 (衝突)
2 + 1² = 3 (衝突)
2 + 2² = 6 (存入)

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

接著找數字 2 (直到找到空格為止)

2 mod 13 = 2 (衝突) -> 28
2 + 1² = 3 (衝突) -> 41
2 + 2² = 6 (衝突) -> 54
2 + 3² = 11 (衝突) -> 24
2 + 4² = 18 ，18 mod 13 = 5 (衝突) -> 17
2 + 5² = 27 ，27 mod 13 = 1 (無資料) -> X

總共比對 5 個數...

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

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

30 mod 13 = 4 (存入)

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

24 mod 13 = 11 (存入)

47 mod 13 = 8 (存入)

54 mod 13 = 2 (衝突)
2 + 1² = 3 (衝突)
2 + 2² = 6 (存入)

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

接著找數字 2 (直到找到空格為止)

2 mod 13 = 2 (衝突) -> 28
2 + 1² = 3 (衝突) -> 41
2 + 2² = 6 (衝突) -> 54
2 + 3² = 11 (衝突) -> 24
2 + 4² = 18 ，18 mod 13 = 5 (衝突) -> 17
2 + 5² = 27 ，27 mod 13 = 1 (無資料) -> X

總共比對 5 個數字