考研帮 > 数学 > 每日一练

5.3 散列(Hash)表及其查找

5.3 散列(Hash)表及其查找

  考试大纲涉及本节的知识点有:哈希函数构造方法、冲突解决办法(开放定址法、再哈希法、链地址法)、哈希表的查找及其性能分析。

一、选择题

  1.选择题题目部分
  ● 散列法存储的基本思想是根据 (1) 来决定 (2) ,碰撞(冲突)指的是 (3) (4) 越大,发生碰撞的可能性也越大。处理碰撞的两类主要方法是 (5)
  (1)A.存储地址 B.元素的序号 C.元素个数 D.关键码值
  (2)A.存储地址 B.元素的序号 C.元素个数 D.关键码值
  (3)A.两个元素具有相同序号
     B.两个元素的关键码值不同,而非码属性相同
     C.不同关键码值对应到相同的存储地址
     D.负载因子过大
  (4)A.非码属性 B.平均检索长度 C.负载因子 D.散列表空间
  (5)A.线性探查法和双散列函数法 B.建溢出区法和不建溢出区法
     C.除余法和折叠法 D.拉链法和开地址法
  ● 散列(Hash)文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系,所以选择好的 (6) 法是散列文件的关键。
  (6)A.散列函数 B.除余法中质数
     C.冲突处理 D.散列函数和冲突处理
  ● 设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15、38、61、84共4个,现要将关键字为49的节点加到表中,用二次探测再散列法解决冲突,则放入的位置是 (7)
  (7)A.8 B.3 C.5 D.9
  ● 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行 (8) 次探测。
  (8)A.k-1次 B.k次 C.k+1次 D.k(k+1)/2次
  ● 关于杂凑查找说法不正确的有 (9) 个。
  (a)采用链地址法解决冲突时,查找任一个元素的时间是相同的
  (b)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的
  (c)用链地址法解决冲突易引起聚集现象
  (d)再哈希法不易产生聚集
  (9)A.1 B.2 C.3 D.4
  ● 已知一个线性表(38,25,74,63,52,48),采用的散列函数为H(Key)=Key mod 7,将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为 (10)
  (10)A.1.5 B.1.7 C.2.0 D.2.3
  2.选择题练习的答案与分析
  题号 (1) (2) (3) (4) (5)
  答案  D   A   C   C   D
  习题分析:
  散列表又称杂凑表,是一种十分实用的查找技术,具有极高的查找效率。其基本思想是根据关键码值(查找码)与表项存储地址的映射关系,进行高效、精确地查找。查找效率与散列函数的计算复杂度、冲突解决方案的使用有直接的关系。
  当关键码比较多时,很可能出现散列函数值相同的情况,这就是冲突。通常也称为冲突的两个关键是该散列函数的同义词,负载因子越大发生碰撞的可能性也越大。通常解决冲突的方法是设法在散列表中找一个空位,而常见的方法有两种:开放定址法和拉链法。
  题号 (6)
  答案 D
  习题分析:
  大多数散列函数都不是一一对应的关系,当两个不同的记录被散列函数映射到同一个地址时,称为冲突,冲突会降低效率。为了尽可能避免冲突,应选择列好的散列函数,使用同等概念取值域。
  题号 (7)
  答案 D
  习题分析:
  在加入49前,哈希表中的地址4、5、6、7已经占用,H(49)=5冲突;第1次冲突后计算哈希地址为6((H(49)+1)%11=6)还是冲突;第2次冲突后计算哈希地址为4((H(49)-1)%11=4)仍然冲突;第3次冲突后计算哈希地址为9((H(49)+4)%11=9)存入。
  题号 (8)
  答案 D
  习题分析:
  第1个直接存入(探测1次),第2个冲突1次(探测2次),…,第k个冲突(k-1)次(探测k次)。共需要探测
  题号 (9)
  答案 B
  习题分析:
  (1)、(3)不正确。链地址法解决冲突时,主要变成在链表中顺序查找,因此查找元素的时间长。(3)链地址法不会产生聚集现象。
  题号 (10)
  答案 C
  习题分析:
  根据题意的要求,可以先求出其散列地址,如表5-4所示。

表5-4 散列地址

关键字 38 25 74 63 52 48
散列地址(关键字%7) 3 4 4 0 3 6

  首先,如果采用线性探测开放定址法解决冲突,那么得到:

63 48   38 25 74 52
  成功比较次数:  1   3       1    1   2   4
  可以看出,其成功比较次数分别为1、3、1、1、2、4,因此其平均查找长度就是(1+3+1+1+2+4)/6=2.0。
  3.训练自测表(如表5-5所示)

表5-5 选择题练习自测表

题    号 考  查  点 得    分
(1)~(5) 散列法存储的基本思想  
(6) 散列函数  
(7) 二次探测再散列法  
(8) 线性探测法  
(9) 散列查找的应用  
(10) 开放定址法  

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭