题目
设散列表长 m=14 ,散列函数为 H(key)=key%11 ,表中仅有 4 个结点 H(15)=4 , H(38)=5 , H(61)=6 , H(84)=7 ,若采用线性探测法处理冲突,则关键字为 49 的结点地址是 ().A. 3B. 5C. 8D. 9
设散列表长 m=14 ,散列函数为 H(key)=key%11 ,表中仅有 4 个结点 H(15)=4 , H(38)=5 , H(61)=6 , H(84)=7 ,若采用线性探测法处理冲突,则关键字为 49 的结点地址是 ().
A. 3
B. 5
C. 8
D. 9
题目解答
答案
C. 8
解析
步骤 1：计算关键字 49 的散列值
根据散列函数 H(key) = key % 11，计算关键字 49 的散列值。
\[ H(49) = 49 \% 11 = 5 \]
步骤 2：检查散列值对应的位置是否已占用
根据题目描述，表中已有 4 个结点，其散列值分别为 4、5、6、7。因此，散列值为 5 的位置已经被关键字 38 占用。
步骤 3：使用线性探测法处理冲突
由于散列值为 5 的位置已被占用，需要使用线性探测法寻找下一个空闲位置。线性探测法是指从散列值开始，依次检查下一个位置，直到找到空闲位置为止。
\[ H(49) = 5 \]
\[ H(49) + 1 = 6 \]（已被关键字 61 占用）
\[ H(49) + 2 = 7 \]（已被关键字 84 占用）
\[ H(49) + 3 = 8 \]（空闲位置）
根据散列函数 H(key) = key % 11，计算关键字 49 的散列值。
\[ H(49) = 49 \% 11 = 5 \]
步骤 2：检查散列值对应的位置是否已占用
根据题目描述，表中已有 4 个结点，其散列值分别为 4、5、6、7。因此，散列值为 5 的位置已经被关键字 38 占用。
步骤 3：使用线性探测法处理冲突
由于散列值为 5 的位置已被占用，需要使用线性探测法寻找下一个空闲位置。线性探测法是指从散列值开始，依次检查下一个位置，直到找到空闲位置为止。
\[ H(49) = 5 \]
\[ H(49) + 1 = 6 \]（已被关键字 61 占用）
\[ H(49) + 2 = 7 \]（已被关键字 84 占用）
\[ H(49) + 3 = 8 \]（空闲位置）