回覆列表
  • 1 # 使用者1856473604127

    先建好表,然後可以算出每個位置不成功時的比較次數之和,再除以表空間個數!

    例如:雜湊函式為hash(x)=x MOD 13,用線性探測,建立了雜湊表之後,如何求查詢不成功時的平均查詢長度!?

    查詢成功時的平均查詢長度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2

    查詢不成功時的平均查詢長度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

    說明:

    第n個位置不成功時的比較次數為,第n個位置到第1個沒有資料位置的距離。至少要查詢多少次才能確認沒有這個值。

    (1)查詢hash(x)=0,至少要查詢9次遇到表值為空的時候,才能確認查詢失敗。

    (2)查詢hash(x)=1,至少要查詢8次遇到表值為空的時候,才能確認查詢失敗。

    (3)查詢hash(x)=2,至少要查詢7次遇到表值為空的時候,才能確認查詢失敗。

    (4)查詢hash(x)=3,至少要查詢6次遇到表值為空的時候,才能確認查詢失敗。

    (5)查詢hash(x)=4,至少要查詢5次遇到表值為空的時候,才能確認查詢失敗。

    (6)查詢hash(x)=5,至少要查詢4次遇到表值為空的時候,才能確認查詢失敗。

    (7)查詢hash(x)=6,至少要查詢3次遇到表值為空的時候,才能確認查詢失敗。

    (8)查詢hash(x)=7,至少要查詢2次遇到表值為空的時候,才能確認查詢失敗。

    (9)查詢hash(x)=8,至少要查詢1次遇到表值為空的時候,才能確認查詢失敗。

    (10)查詢hash(x)=9,至少要查詢1次遇到表值為空的時候,才能確認查詢失敗。

    (11)查詢hash(x)=10,至少要查詢2次遇到表值為空的時候,才能確認查詢失敗。

    (12)查詢hash(x)=11,至少要查詢1次遇到表值為空的時候,才能確認查詢失敗。

    (13)查詢hash(x)=12,至少要查詢10次遇到表值為空(迴圈查詢順序表)的時候,才能確認查詢失敗。

  • 中秋節和大豐收的關聯?
  • 父親因打傷別人需要繳納賠償款,這和兒子有關係嗎?