假定有K个关键字互为同义词,若用线性探测再散列法把这K个关键字存入散列表中,至少要进行(42)次探

Question

假定有K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行(42)次探测。

A．K-1

B．K

C．K(K-1)/2

D．K(K+1)/2

Answer 1

正确答案：D
解析：哈希涉及到构造哈希函数和处理)中突。解决冲突就是为出现冲突的关键字找到另一个”空”的哈希地址。开放地址法是常用的一种方法。开放地址法：Hi=(H(key)+di)%mi=1，2，...k(km-1)，其中H(key)为哈希函数；m为哈希表表长；di为增量序列，当di1，2，3，...，m-1时，称为线性探测再散列。用线性探测再散列法把这K个关键字存入散列表中，第1个关键字最少需进行1次探测，第2个关键字最少需进行2次探测，...第A个关键字最少需进行七次探测，所以最少要进行K(K+1)/2次探测。