数据结构
若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。A、 dB、 d+1C、 （d+1）/mD、 （d+1）%m
题目
若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。
- A、 d
- B、 d+1
- C、 （d+1）/m
- D、 （d+1）%m
相似问题和答案
第1题：
已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(41)；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(42)。
A．1.5
B．1.8
C．2
D．2.3
解析：根据题意，使用线性探测的开放定址法，各数的位置分别是(0，63)，(1，48)，(3，38)，(4，25)，(5，74)，(6，52)。平均查找长度为(1+3+1+1+2+4)/6=2.0；使用拉链法，0和6地址下有一个节点，3和4地址下有两个节点，即平均查找长度为(1+1+1+1+2+2)/6=4/3。
第2题：
● 已知一个线性表（16, 25, 35, 43, 51, 62, 87, 93），采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则构造的哈希表为 （57） ，在该散列表上进行等概率成功查找的平均查找长度为 （58） （为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度）。
第3题：
●已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (41) ；若利用拉链法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (42) 。
(41) A．1.5
B．1.8
C．2.0
D．2.3
(42) A．6/5
B．7/6
C．4/3
D．3/2
【解析】根据题意，使用线性探测的开放定址法，各数的位置分别是(0，63)，(1，48)，(3，38)，(4，25)，(5，74)，(6，52)。平均查找长度为(1+3+1+1+2+4)/6=2.0；使用拉链法，0和6地址下有一个节点，3和4地址下有两个节点，即平均查找长度为(1+1+1+1+2+2)/6=4/3。
第4题：
设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
正确答案:对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3+6）＝23/11
第5题：
查找哈希(Hash)表，不会发生冲突的哈希函数是(34)。
A．除留余数法
B．伪随机探测再散列法
C．直接地址法
D．线性探测再散列法
解析：本题考察数据结构中的查找哈希表问题。哈希表的目的是建立希望不经过任何比较，一次存取便能取得所查的记录。在哈希表存储时，一般是通过在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字和结构中的一个唯一的存储位置对应，而这个对应关系就是哈希函数。所谓的哈希冲突是指对不同的关键字可能得到同一哈希地址。为了不发生哈希冲突，构造哈希函数的方法应该选直接地址法，此方法是取关键字的某个线性函数值作为直接地址。
第6题：
此题为判断题(对，错)。
第7题：
已知一个线性表(38，25，74，63，52，48)，假定采用h(k)=k%6计算散列地址进行散列存储，若用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为(44)。
A．1.5
B．1.7
C．2
D．2.3
解析：用散列函数n(k)=k%6计算得到散列地址见表2。表2散列地址关键字散列地址用线性探测的开放定址法处理冲突所构造得到的散列表见表3。表3散列表该散查找次数列表的平均查找长度为(1×3+2×3)/6=1.5。
第8题：
哈希表的平均查找长度与处理冲突的方法无关()
A.对
B.错
第9题：
B.1.7，3/2
C.2，4/3
D.2.3，7/6
第10题：
查找哈希（Hash）表，解决冲突的的方法有（）
- A、除留余数法
- B、线性探测再散列法
- C、直接地址法
- D、链地址法
正确答案:B,D