问题 问答题

设某文件有14个记录,其关键字分别为{25,75,125,93,241,203,19,198,121,173,218,80,214,329}。桶的容量M=3,此时采用除留余数法构造散列函数,且散列函数为h(k)=k%5,画出该散列文件的结构图,并说明如何对其进行删除或插入、检索等操作。

答案

参考答案:

由于散列函数h(k)=k%5,从而可得按散列函数方法组织的文件结构如下(可选桶数为(14/3)×(1+10%)=5);

当需对该散列文件中的记录进行检索时,可首先根据给定记录的关键字值,用散列函数求出其对应的散列地址,此地址即为桶的编号,然后按照散列表中第i项给出的地址把该桶中的所有记录读入内存,并对这些记录进行顺序检索。若找到说明检索成功,否则,若该桶不满或其指针域为空,说明检索失败。此时若其指针域不空,则该指针把第一个溢出桶的记录读入内存,继续检索直到检索成功或失败时为止。 当要对散列文件中的记录进行删除操作时,同样可首先利用散列函数求出该记录所在的存储桶并把它读入内存,接着把该记录与最后一个记录对调,然后把该桶重新写回到外存储器的原来的位置。当从最后一个桶中删除最后一个记录时,可将此空桶释放回系统,以节省存储空间。 当要对散列文件中的记录进行更新或修改时,可首先检索该记录所在的存储桶,并把该桶记录读入内存,接着检索该记录,并修改,然后把修改过的桶重新写回到原来的位置即可。

单项选择题
单项选择题