题5
题目
Q:下列关于散列冲突处理方法的说法中, 正确的有 ( ).
I. 采用平方探测法处理冲突时不易产生聚集
II. 采用线性探测法处理冲突时, 所有同义词在散列表中一定相邻
III. 采用链地址法处理冲突时, 若限定在链首插入, 则插入任意一个元素的时间相同
IV. 采用链地址法处理冲突易引起聚集现象
A. I 和 III
B. I、 II 和 III
C. III 和 IV
D. I 和 IV
分析
A:如何理解这个冲突，这个冲突一定是两个元素通过哈希函数得到了同样的索引值这种情况，因为有一个先来的已经占据了一个位置，后面新的这个同索引的，就要一直+1退避到一个新的空位，如果它沿着表走，一直有其他的元素一路上占着位置，他就会走很远
我会 认为他们相邻是因为，我把这个冲突涉及的对象扩大了，我觉得被冲突的元素周围挤满了元素，导致新的元素要走很远这个过程，也叫做冲突，事实上通过刚才的描述，新来的这个冲突的元素已经退避到和被冲突元素相比，很远的地方了
解
A
平方探测法采用的增量序列是非线性的, 它可以跳过一些已被占用的单元, 而不是顺序地探测下一单元,这样能减小冲突的概率,I 正确。
散列地址
III 正确。同义词冲突不等于聚集, 链地址法处理冲突时将同义词放在同一个链表中, 不会引起聚集现象, IV 错误。