一、单项选择题

————————————————————

————————————————————

解析：顺序查找可以是顺序存储或链式存储;折半查找只能是顺序存储且要求关键字有序;树形查找法要求采用树的存储结构，既可以采用顺序存储也可以采用链式存储;散列查找中的链地址法解决冲突时，采用的是顺序存储与链式存储相结合的方式。

正确答案：B

————————————————————

————————————————————

解析：关键字集合与地址集合之间存在对应关系时，通过散列函数表示这种关系。这样，查找以计算散列函数而非比较的方式进行查找。

正确答案：D

————————————————————

————————————————————

解析：冲突(碰撞)是不可避免的，与装填因子无关，因此需要设计处理冲突的方法，Ⅰ错误。散列查找的思想是计算出散列地址来进行查找，然后比较关键字以确定是否查找成功，Ⅱ错误。散列查找成功的平均查找长度与装填因子有关，与表长无直接关系，Ⅲ错误。在开放定址的情形下，不能随便删除散列表中的某个元素，否则可能会导致搜索路径被中断(因此通常的做法是在要删除的地方做删除标记，而不是直接删除)，Ⅳ正确。

正确答案：D

————————————————————

————————————————————

解析：在开放定址法中散列到同一个地址而产生的“堆积”问题，是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，降低了散列的效率。因此要选择好的处理冲突的方法来避免“堆积”。

正确答案：C

————————————————————

————————————————————

解析：平方探测法采用的增量序列是非线性的，它可以跳过一些已被占用的单元，而不是顺序地探测下一单元，这样能减小冲突的概率，Ⅰ正确。散列地址i的关键字，和为解决冲突形成的某次探测地址为i的关键字，都争夺地址i, i+1,…，因此不一定相邻，Ⅱ错误。Ⅲ正确。同义词冲突不等于聚集，链地址法处理冲突时将同义词放在同一个链表中，不会引起聚集现象，Ⅳ错误。

正确答案：A

————————————————————

————————————————————

解析：

正确答案：A

————————————————————

————————————————————

解析：K个关键字在依次填入的过程中，只有第一个不会发生冲突，所以探测次数为1+2+3+…+K=K(K＋1)/2。

正确答案：D

————————————————————

————————————————————

解析：散列表的平均查找长度与装填因子α直接相关，表的查找效率不直接依赖于表中已有表项个
数n或表长m。若表中存放的记录全是某个地址的同义词。则平均查找长度为O(n)而非O(1)。

正确答案：C

————————————————————

————————————————————

解析：聚集是因选取不当的处理冲突的方法，而导致不同关键字的元素对同一散列地址进行争夺的现象。用线性探查法时，容易引发聚集现象。

正确答案：D

————————————————————

————————————————————

解析：“下一个空位”可以大于或小于但不等于原散列地址。等于原散列地址是没有意义的。

正确答案：C

————————————————————

————————————————————

解析：由散列函数计算可知，14,1,27,79散列后的地址都是1，所以有4个记录。

正确答案：D

————————————————————

————————————————————

解析：因为在链地址法中，映射到同一地址的关键字都会链到与此地址相对应的链表上，所以探测过程一定是在此链表上进行的，从而这些位置上的关键字均为同义词;但在线性探测法中出现两个同义关键字时，会把该关键字对应地址的下一个地址也占用掉，两个地址分别记为Addr、Addr+1，查找一个满足H(key)=Addr+1的关键字key时，显然首次探测到的不是key的同义词。

正确答案：A、B

————————————————————

————————————————————

解析：H的取值有17种可能，对应到不同的链表中，所以链表的个数应为17。由于H(key)的取值范围是0～16，所以数组下标为0～16。

正确答案：A、C

————————————————————

————————————————————

解析：

正确答案：A

————————————————————

————————————————————

解析：

正确答案：C

————————————————————

————————————————————

解析：

正确答案：B

————————————————————

————————————————————

解析：由于散列函数的选取，仍然有可能产生地址冲突，冲突不能绝对地避免。

正确答案：C

————————————————————

————————————————————

解析：

正确答案：D

————————————————————

————————————————————

解析：堆积现象因冲突而产生，它对存储效率、散列函数和装填因子均不会有影响而平均查找长度会因为堆积现象而增大。散列函数是指将关键字映射到哈希地址的函数。存储效率和装填(装
载)因子的定义相同，指哈希表中已存储的元素个数与哈希表长度的比值。这些因素都与堆积象无关,而只与哈希表的结构和设计有关。

正确答案：D

————————————————————

————————————————————

解析：

正确答案：C

————————————————————

————————————————————

解析：

正确答案：C

————————————————————

————————————————————

解析：原题再现。填装因子越大，说明哈希表中存储的元素越满，发生冲突的可能性就越高，导致平均查找长度越大。散列函数、冲突解决策略也会影响发生冲突的可能性。Ⅰ、Ⅱ、Ⅲ都正确。

正确答案：D

————————————————————

————————————————————

解析：

正确答案：C

二、综合应用题

————————————————————

————————————————————

解答：在散列表中删除一个记录，在拉链法情况下可以物理地删除。但在开放定址法情况下，不能物理地删除，只能做删除标记。该地址可能是该记录的同义词查找路径上的地址，物理地删除就中断了查找路径，因为查找时碰到空地址就认为是查找失败。

————————————————————

————————————————————

解答：

————————————————————

————————————————————

解答：

————————————————————

————————————————————

解答：

————————————————————

————————————————————

解答：

————————————————————

————————————————————

解答：