25版王道数据结构课后习题详细分析第七章 7.5 散列表

本文主要是介绍25版王道数据结构课后习题详细分析第七章 7.5 散列表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、单项选择题

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

解析：

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

解析：线性探测法的公式为H=(H(key)+d;)%m，其中d,=1,2…, m-1。日(49)=49%11=5，有冲突;H=(H(49)+1)%14=6，有冲突;H=(H(49)+2)%14=7，有冲突;H=(H (49)+3)号14=8，无冲突。

正确答案：

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

解析：插入过程如下:H(26)=9，不冲突;日(25)=8，不冲突;H(72)=4，不冲突;H(38)=4,冲突，冲突处理后的地址为5;H(8)=8，冲突，冲突处理后的地址为10;H(18)=l，不冲突;H (59)=8，冲突，冲突处理后的地址为11。因此，在表中查找59需要探查4次。

正确答案：

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

解析：

正确答案：

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

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

正确答案：

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

解析：散列表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子（即表中记录数与表长之比）的大小成正比，Ⅰ与题意相反。I显然正确。采用合适的冲突处理方法可避免聚集现象，也将提高查找效率，Ⅲ正确。例如，用链地址法处理冲突时不存在聚集现象，用线性探测法处理冲突时易引起聚集现象。

正确答案：

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

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

正确答案：

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