题目
设哈希表长为14，哈希函数是H(key)=key％11，表中已有数据的关键字为15、38、61、84共4个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。A. 8B. 3C. 5D. 9
设哈希表长为14，哈希函数是H(key)=key％11，表中已有数据的关键字为15、38、61、84共4个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。
A. 8
B. 3
C. 5
D. 9
题目解答
答案
D. 9
解析
步骤 1：计算哈希值
根据哈希函数 H(key) = key % 11，计算关键字 49 的哈希值。
步骤 2：检查哈希值对应的位置
检查哈希值对应的位置是否已被占用。如果被占用，则使用二次探测再散列法解决冲突。
步骤 3：使用二次探测再散列法
如果哈希值对应的位置被占用，则使用二次探测再散列法计算新的位置。计算公式为 Hi(key) = (H(key) + di) % B，其中 di = ±1^2, ±2^2, …, ±k^2，B 为哈希表的长度。
步骤 4：找到空闲位置
根据二次探测再散列法计算出的新的位置，找到空闲位置，将关键字 49 的结点放入该位置。
根据哈希函数 H(key) = key % 11，计算关键字 49 的哈希值。
步骤 2：检查哈希值对应的位置
检查哈希值对应的位置是否已被占用。如果被占用，则使用二次探测再散列法解决冲突。
步骤 3：使用二次探测再散列法
如果哈希值对应的位置被占用，则使用二次探测再散列法计算新的位置。计算公式为 Hi(key) = (H(key) + di) % B，其中 di = ±1^2, ±2^2, …, ±k^2，B 为哈希表的长度。
步骤 4：找到空闲位置
根据二次探测再散列法计算出的新的位置，找到空闲位置，将关键字 49 的结点放入该位置。