哈希题目

1.采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找()//对
解释:发生冲突时，向后位移一位，如果删除中间的，导致后面无法查找到，如1222223，删除一个2，1 22223，导致中间断裂，下次查找，搜索不到2
2.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入哈希表中,至少要进行多少次探测?()//k(k-1)/2次
解释:
本人觉得此题无答案，解释如下：
有k个关键字相同，对第一个进行哈希值计算时对应位置没有存放数，直接插入，无需探测。
对第二个数插入时探测次数为1，
以此类推
第k个插入时探测数为k-1.
所以
1+2+……+k-1=k*（k-1）/2才正确。
3.散列法存储的思想是由关键字值决定数据的存储地址，这样的说法正确吗？//正确
4.以下哪个不属于单向哈希表的特征（假设没有冲突）（）//它把固定的信息转换成任意长度信息输出
解释:
哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系。
A，hash函数可以把字符串等任意长度的输入映射成固定长度的整数，也就是哈希值
B，与A说法相反，错误
C，哈希表建立了哈希值与原值信息存储之间的联系，可以通过哈希值查找到原值信息
D，不同的信息产生相同的哈希值叫哈希冲突。设计哈希函数应尽量避免哈希冲突。因此一般很难冲突。
5.随着装填因子a的增大,用闭哈希法解决冲突,其平均搜索长度比用开哈希法解决冲突时的平均搜索长度增长得慢()//错
开哈希表----链式地址法
闭哈希表----开发地址法
装填因子增大，意味着哈希表的空间利用率在增大。
开哈希和闭哈希主要的区别在于，随着哈希表的密集度提高，使用闭哈希时，不仅会与相同哈希值的元素发生冲突，还容易与不同哈希值的元素发生冲突；而开哈希则不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长度不会增长。
6.稀疏矩阵压缩的存储方法是三元组和十字链表
7.产生哈希冲突的影响因素有装填因子、哈希函数和处理冲突的方法
8.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )//9
解释:

49%11=5被占用了
（5+1^2）%11=6还是被占用了
（5-1^2）%11=4被占用了
（5+2^2）%11=9未被占用，所以在9的位置放入49