结构推理
在有19个单元的散列表中存储下面所给的关键码,要发生多少次碰撞?用下面要求的方法来存储并处理碰撞。在所有的关键码都插入完毕后,散列表的装填因子是多少?等概率情况下平均成功检索的比较次数又是多少?
224562,137456,214562,140145,214576,162145,144467,199645,23d534,190010,168874,140164,214752,164045,191910
【正确答案】首先用除余法处理关键码:
224562/%19=1
137456/%19=10
214562/%19=14
140145/%19=1(发生碰撞,线性探查单元2,为空单元,插入)
214576/%19=9
162145/%19=18
144467/%19=10(发生碰撞,线性探查单元11,为空单元,插入)
199645/%19=12
234534/%19=17
190010/%19=10(发生碰撞,线性探查单元11,不是空单元;继续探查单元12,不是空单元;探查单元13,是空单元,插入)
168874/%19=2(发生碰撞,线性探查单元3,为空单元,插入)
140164/%19=1(发生碰撞,线性探查单元2,不是空单元;继续探查单元3,不是空单元;线性探查单元4,为空单元,插入)
214752/%19=14(发生碰撞,线}生探查单元15,为空单元,插入)
164045/%19=18(发生碰撞,线性探查单元1,不是空单元;线性探查单元2,不是空单元;继续探查单元3,不是空单元;线性探查单元4,不是空单元;继续探查单元5,为空单元,插入)
191910/%19=10(发生碰撞,线性探查单元11,不是空单元;继续探查单元12,不是空单元;探查单元13,不是空单元;线性探查单元14,不是空单元;线性探查单元15,不是空单元:继续探查单元16,为空单元,插入)
共发生碰撞21次。
装填因子为15/19=0.79;平均比较次数为(15+21)/15=2.4。
【答案解析】