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)/6=2.0。
3.训练自测表(如表5-5所示)
表5-5 选择题练习自测表
题 号 | 考 查 点 | 得 分 |
(1)~(5) | 散列法存储的基本思想 | |
(6) | 散列函数 | |
(7) | 二次探测再散列法 | |
(8) | 线性探测法 | |
(9) | 散列查找的应用 | |
(10) | 开放定址法 |
5.3 散列(Hash)表及其查找
评论列表 人参与