7.5 散列表·习题
复习入口
7.5 散列表 · 7.5.1 散列表的基本概念 · 7.5.2 散列函数的构造方法 · 7.5.3 处理冲突的方法 · 7.5.3.1 开放定址法 · 7.5.3.2 拉链法 · 7.5.4 散列查找及性能分析
本节共30题:选择题23题,综合应用题7题。每题答案紧接题目折叠显示。
文字转录进度:30/30题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P327 · 解析P330 · 目视转录
只能在顺序存储结构上进行的查找方法是( )。
A. 顺序查找法
B. 折半查找法
C. 树形查找法
D. 散列查找法
查看答案与解析
答案:B。
顺序查找可以顺序或链式存储;折半查找只能顺序存储且要求关键字有序;树形查找要求树的存储结构,可顺序或链式存储;散列查找中的链地址法采用顺序与链式结合。
单项选择题 02
原书题目P327 · 解析P330 · 目视转录
散列查找一般适用于( )情况下的查找。
A. 查找表为链表
B. 查找表为有序表
C. 关键字集合比地址集合大得多
D. 关键字集合与地址集合之间存在对应关系
查看答案与解析
答案:D。
关键字集合与地址集合存在对应关系时,可通过散列函数表示,以计算函数而非逐项比较的方式进行查找。
单项选择题 03
原书题目P327 · 解析P330 · 目视转录
下列关于散列表的说法中,正确的是( )。
Ⅰ.若散列表装填因子 α<1,则可避免碰撞。
Ⅱ.散列查找中不需要任何关键字比较。
Ⅲ.散列表查找成功时平均查找长度仅与表长有关。
Ⅳ.若在散列表中删除一个元素,不能简单地将该元素删除。
A. Ⅰ和Ⅳ
B. Ⅱ和Ⅲ
C. Ⅲ
D. Ⅳ
查看答案与解析
答案:D。
冲突不可避免,α<1 也不能保证无冲突,需设计处理方法,Ⅰ错误。计算散列地址后仍需比较关键字来确认成功,Ⅱ错误。成功 ASL 与装填因子有关,与表长无直接关系,Ⅲ错误。开放定址时不能随便删除元素,否则可能导致查找路径中断,通常在地址处作删除标记,Ⅳ正确。
单项选择题 04
原书题目P327 · 解析P330 · 目视转录
开放定址法中散列到同一地址引起的“堆积”问题是由( )引起的。
A. 同义词之间发生冲突
B. 非同义词之间发生冲突
C. 同义词之间或非同义词之间发生冲突
D. 散列表溢出
查看答案与解析
答案:C。
同义词冲突的探查序列与非同义词之间的探查序列交织,导致查找需要较长探测距离,降低效率。因此要选择好的冲突处理方法避免堆积。
单项选择题 05
原书题目P327 · 解析P330 · 目视转录
下列关于散列冲突处理方法的说法中,正确的有( )。
Ⅰ.采用平方探测法处理冲突时不易产生聚集。
Ⅱ.采用线性探测法处理冲突时,所有同义词在散列表中一定相邻。
Ⅲ.采用链地址法处理冲突,若限定在链首插入,则插入任意元素的时间相同。
Ⅳ.采用链地址法处理冲突易引起聚集。
A. Ⅰ和Ⅲ
B. Ⅰ、Ⅱ和Ⅲ
C. Ⅲ和Ⅳ
D. Ⅰ和Ⅳ
查看答案与解析
答案:A。
平方探测增量非线性,可以跳过部分已占单元,减少聚集,Ⅰ正确。散列地址为 i 的关键字和经探测放到 i 的关键字都可能争夺 i、i+1、…,同义词不一定相邻,Ⅱ错误。链首插入时间相同,Ⅲ正确。冲突不等于聚集,链地址法将同义词放同一链中,不会引起聚集,Ⅳ错误。
单项选择题 06
原书题目P327 · 解析P331 · 目视转录
设有含 200 个元素的散列表,用线性探测法解决冲突。要求按关键字查询找到表项的平均探测次数不超过 1.5,则散列表应能够容纳( )个元素。设成功 ASL=[1+1/(1−α)]/2,α 为装填因子。
A. 400
B. 526
C. 624
D. 676
查看答案与解析
答案:A。
由 ,得 α=200/m≤1/2,因此 m≥400。
单项选择题 07
原书题目P328 · 解析P331 · 目视转录
假定 K 个关键字互为同义词,若用线性探测法填入散列表,至少要进行( )次探测。
A. K−1
B. K
C. K+1
D. K(K+1)/2
查看答案与解析
答案:D。
依次填入时只有第一个不发生冲突,探测次数总和为 1+2+…+K=K(K+1)/2。
单项选择题 08
原书题目P328 · 解析P331 · 目视转录
对包含 n 个元素的散列表进行查找,平均查找长度( )。
A. 为
B. 为
C. 不直接依赖于 n
D. 直接依赖于表长 m
查看答案与解析
答案:C。
平均查找长度与装填因子 α 直接相关,不直接依赖元素数 n 或表长 m。若所有记录均为同一地址的同义词,平均查找长度为 ,并非总为 。
单项选择题 09
原书题目P328 · 解析P331 · 目视转录
开放定址法散列表中发生聚集的主要原因是( )。
A. 数据元素过多
B. 负载因子过大
C. 散列函数选择不当
D. 解决冲突的方法选择不当
查看答案与解析
答案:D。
聚集是选取不当冲突处理方法,导致不同关键字争夺同一地址的现象。线性探测容易引起聚集。
单项选择题 10
原书题目P328 · 解析P331 · 目视转录
用线性探测再散列法处理冲突时,计算出的一系列“下一个空位”的要求是( )。
A. 必须大于或等于原散列地址
B. 必须小于或等于原散列地址
C. 可以大于或小于但不等于原散列地址
D. 对地址何值没有限制
查看答案与解析
答案:C。
下一空位可以大于或小于、但不等于原散列地址;等于原地址没有意义。
单项选择题 11
原书题目P328 · 解析P331 · 目视转录
一组记录关键字为 {19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,H(key)=key mod 13,地址为 1 的链中有( )个记录。
A. 1
B. 2
C. 3
D. 4
查看答案与解析
答案:D。
14、1、27、79 的散列地址都是 1,共 4 个记录。
单项选择题 12
原书题目P328 · 解析P331 · 目视转录
链地址法构成的散列表查找成功时,所探测各位置上的关键字值( );若采用线性探测法,则( )。
A. 一定都是同义词
B. 不一定都是同义词
C. 都相同
D. 一定都不是同义词
查看答案与解析
答案:A、B。
链地址法把映射到同一地址的关键字链接在对应链表中,探测都在该链中,故均为同义词。线性探测时,两个同义词可能占 Addr、Addr+1,再查找原散列地址为 Addr+1 的另一关键字时,会探测到前一个关键字,两者显然不同义。
单项选择题 13
原书题目P328 · 解析P331 · 目视转录
采用链地址法构造散列表,H(key)=key mod 17,则需(①)个链表。各链首指针构成数组,数组下标范围为(②)。
①
A. 17
B. 13
C. 16
D. 任意
②
A. 0~17
B. 1~17
C. 0~16
D. 1~16
查看答案与解析
答案:① A;② C。
H 有 17 种取值,对应 17 个不同链表。取值范围为 0~16,因此数组下标也是 0~16。
单项选择题 14
原书题目P328 · 解析P331 · 目视转录
散列表长 m=14,H(key)=key%11,表中仅 4 个结点,H(15)=4、H(38)=5、H(61)=6、H(84)=7。采用线性探测,关键字 49 的结点地址是( )。
A. 8
B. 3
C. 5
D. 9
查看答案与解析
答案:A。
Hᵢ=(H(key)+dᵢ)%m,dᵢ=1,2,…,m−1。H(49)=5 冲突,接着地址 6、7 均冲突,地址 8 无冲突。
单项选择题 15
原书题目P328 · 解析P331 · 目视转录
长度为 17、初始为空的 HT,H(key)=key%17,线性探查法处理冲突。将 26,25,72,38,8,18,59 依次插入,查找 59 需探查( )次。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:C。
H(26)=9、H(25)=8、H(72)=4,均不冲突;H(38)=4 冲突,放 5;H(8)=8 冲突,放 10;H(18)=1,不冲突;H(59)=8 冲突,放 11。因此查找 59 探查 8、9、10、11,共 4 次。
单项选择题 16
原书题目P328 · 解析P331 · 目视转录
长度为 17、初始为空的 HT,H(key)=key%17,平方探测解决冲突:Hᵢ(key)=(H(key)±i²)%17。依次插入 6,22,7,26,9,23 后,23 存放的位置是( )。
A. 0
B. 2
C. 6
D. 15
查看答案与解析
答案:B。
6、22、7、26 的初始地址分别为 6、5、7、9;9 的初始地址 9 冲突,探测 10 无冲突。23 初始地址 6 冲突,依次探测 7、5、10 都冲突,探测 2 无冲突,故放在 2。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 元素 | 23 | 22 | 6 | 7 | 26 | 9 |
单项选择题 17
原书题目P328 · 解析P332 · 目视转录
将 10 个元素散列到 100000 个单元的散列表中,则( )产生冲突。
A. 一定会
B. 一定不会
C. 仍可能会
D. 不确定
查看答案与解析
答案:C。
由于散列函数选取,仍可能产生地址冲突,冲突不能绝对避免。
单项选择题 18
原书题目P328 · 解析P332 · 目视转录
【2011 统考真题】为提高散列表查找效率,可以采取的正确措施是( )。
Ⅰ.增大装填因子。
Ⅱ.设计冲突少的散列函数。
Ⅲ.处理冲突时避免产生聚集(堆积)。
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅱ
D. 仅Ⅱ、Ⅲ
查看答案与解析
答案:D。
效率取决于散列函数、冲突处理方法和装填因子。装填因子越大,冲突概率通常越高,Ⅰ反向。设计冲突少的函数、采用避免聚集的方法能提高效率,Ⅱ、Ⅲ正确。例如链地址法不聚集,线性探测易聚集。
单项选择题 19
原书题目P329 · 解析P332 · 目视转录
【2014 统考真题】用散列方法处理冲突时可能出现堆积(聚集)现象,下列会受其直接影响的是( )。
A. 存储效率
B. 散列函数
C. 装填因子
D. 平均查找长度
查看答案与解析
答案:D。
堆积由冲突产生,不改变存储效率、散列函数或装填因子,却使平均查找长度增大。散列函数是关键字到地址的映射;装填因子是已有元素数与表长之比,这些与堆积无关,只与表结构、设计有关。
单项选择题 20
原书题目P329 · 解析P332 · 目视转录
【2018 统考真题】长度为 7、初始为空的 HT,H(k)=k%7,用线性探测再散列法处理冲突。依次插入 22,43,15,成功查找的平均查找长度是( )。
A. 1.5
B. 1.6
C. 2
D. 3
查看答案与解析
答案:C。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 关键字 | 22 | 43 | 15 |
成功 ASL=(1+2+3)/3=2。
单项选择题 21
原书题目P329 · 解析P332 · 目视转录
【2019 统考真题】长度 11、初始为空的 HT,H(key)=key%7,线性探查处理冲突。依次插入 87,40,30,6,11,22,98,20,失败查找的平均查找长度是( )。
A. 4
B. 5.25
C. 6
D. 6.29
查看答案与解析
答案:C。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 98 | 22 | 30 | 87 | 11 | 40 | 6 | 20 |
H(key) 只有 0~6 七种取值。初始地址为 0 时要探测 0~8 共 9 次才能确认失败,初始地址 1 时要 8 次,依此类推,失败 ASL=(9+8+7+6+5+4+3)/7=6。注意散列函数不可能直接算出地址 7。
单项选择题 22
原书题目P329 · 解析P332 · 目视转录
【2022 统考真题】下列因素中,影响散列方法平均查找长度的是( )。
Ⅰ.装填因子 Ⅱ.散列函数 Ⅲ.冲突解决策略
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
查看答案与解析
答案:D。
装填因子越大,表越满,冲突概率越高,平均查找长度越大。散列函数和冲突解决策略也会影响冲突概率,三者均影响 ASL。
单项选择题 23
原书题目P329 · 解析P332 · 目视转录
【2023 统考真题】长度 5、初始为空的 HT,H(k)=(k+4)%5,线性探查再散列处理冲突。依次插入 2022,12,25,然后删除 25,失败查找的平均查找长度为( )。
A. 1
B. 1.6
C. 1.8
D. 2.2
查看答案与解析
答案:C。
开放定址不能随便物理删除元素,否则可能截断同义词的查找地址,应作删除标记。
| 地址 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 关键字 | 2022 | 12 | 25(删除标记) | ||
| 失败探查次数 | 1 | 3 | 2 | 1 | 2 |
遇删除标记继续往后查找。失败 ASL=(1+3+2+1+2)/5=1.8。
综合应用题
综合应用题 01
原书题目P329 · 解析P333 · 目视转录
若要在散列表中删除一个记录,应如何操作?为什么?按开放地址法和拉链法分别说明。
查看答案与解析
拉链法可以物理删除记录。开放地址法不能物理删除,只能作删除标记,因为该地址可能在其他同义词的查找路径上;物理删除会中断路径,查找遇空地址便误认为失败。
综合应用题 02
原书题目P329 · 解析P333 · 目视转录
假定把整数关键字 key 散列到有 n 个表项(地址 0~n−1)的表中。下面各 H(key) 能否作散列函数?若能,是否是好函数?说明理由。random(n) 返回 0~n−1 内的随机整数。
- H(key)=key/n。
- H(key)=1。
- H(key)=(key+random(n))%n。
- H(key)=key%p(n),其中 p(n) 是不大于 n 的最大素数。
查看答案与解析
- 不能,key/n 可能大于 n,无法找到合适位置。
- 能,但不好,所有关键字映射到同一位置,造成大量冲突。
- 不能,返回值不确定,无法正常查找。
- 能,是好的散列函数。
综合应用题 03
原书题目P329 · 解析P333 · 目视转录
使用 H(key)=key%11,将整数转换成散列表下标。表长 11,依次插入 {1,13,12,34,38,33,27,22}。
- 使用线性探测法构造散列表。
- 使用链地址法构造散列表。
分别确定查找成功和失败的平均查找长度。
查看答案与解析
散列地址范围为 0~10。线性探测先计算初始地址,若空则存入,否则逐个探查下一空地址。链地址法先计算地址,再将结点插入对应链表。
- 线性探测:H(1)=1,直接存 1;H(13)=2,直接存 2;H(12)=1 冲突,地址 2 也冲突,放 3;H(34)=1,依次与 1、2、3 冲突,放 4;其余同理。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 33 | 1 | 13 | 12 | 34 | 38 | 27 | 22 | |||
| 冲突次数 | 0 | 0 | 0 | 2 | 3 | 0 | 1 | 7 |
每个已有元素查找概率为 1/8。33 无冲突,比较 1 次;22 初始地址 0,比较 8 次;其他同理。成功 ASL=(1+1+1+3+4+1+2+8)/8=21/8。
失败时,初始地址 0 需查完 0~8 共 9 次,初始地址 1 需 8 次,依此类推;8、9、10 为空,各需 1 次。因此失败 ASL=(9+8+7+6+5+4+3+2+1+1+1)/11=47/11。
- 链地址法,按原书顺序在链尾插入:
| 地址 | 链表 |
|---|---|
| 0 | 33→22→NULL |
| 1 | 1→12→34→NULL |
| 2 | 13→NULL |
| 3 | NULL |
| 4 | NULL |
| 5 | 38→27→NULL |
| 6~10 | NULL |
成功查找 33 比较 1 次、22 比较 2 次,其他同理。成功 ASL=(1×4+2×3+3)/8=13/8。
原书本题失败计数包含空指针一次:地址 0 长度 3,地址 1 长度 4,地址 2 长度 2,地址 5 长度 3,空链长度 1,故失败 ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11。
注意:失败 ASL 有两种约定,一种把与空结点比较也计入,比较次数=冲突次数+1;另一种只计算关键字之间的比较。应按题目约定。
综合应用题 04
原书题目P329 · 解析P334 · 目视转录
关键字 {26,36,41,38,44,15,68,12,6,51,25},链地址法解决冲突。装填因子 α=0.73,H(key)=key%P,P 为不大于表长的最大素数。要求:
- 构造散列函数。
- 计算等概率下成功、失败 ASL(失败只计关键字之间的比较次数)。
查看答案与解析
由 α=n/N,可得 N=n/α≈15,因此 P=13,H(key)=key%13。
| 关键字 | 26 | 36 | 41 | 38 | 44 | 15 | 68 | 12 | 6 | 51 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 散列地址 | 0 | 10 | 2 | 12 | 5 | 2 | 3 | 12 | 6 | 12 | 12 |
构造出的链表为:0:26;2:41→15;3:68;5:44;6:6;10:36;12:38→12→51→25;其他地址为空。
成功 ASL=(1×7+2×2+3×1+4×1)/11=18/11。
失败只比较关键字,不计空指针,ASL=(1+0+2+1+0+1+1+0+0+0+1+0+4)/13=11/13。
综合应用题 05
原书题目P330 · 解析P335 · 目视转录
散列表为 HT[0..12],大小 m=13,采用双散列法:
REV(x) 颠倒十进制数的各位,例如 REV(37)=73、REV(7)=7。依次插入 (2,8,31,20,19,18,53,27)。
- 给出插入后的表。
- 计算成功 ASL。
查看答案与解析
- H₀(2)=2、H₀(8)=8、H₀(31)=5、H₀(20)=7、H₀(19)=6,无冲突。H₀(18)=5 冲突,H₁(18)=(5+REV(19)%11+1)%13=(5+3+1)%13=9,无冲突。H₀(53)=1,无冲突。H₀(27)=1 冲突,H₁(27)=(1+REV(28)%11+1)%13=(1+5+1)%13=7,仍冲突;H₂(27)=(7+5+1)%13=0,无冲突。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 27 | 53 | 2 | 31 | 19 | 20 | 8 | 18 | |||||
| 比较次数 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
- 成功 ASL=(3+1+1+1+1+1+1+2)/8=11/8。
综合应用题 06
原书题目P330 · 解析P335 · 目视转录
【2010 统考真题】将 (7,8,30,11,18,9,14) 散列存储,表空间为下标从 0 开始的一维数组,H(key)=(key×3) mod 7,线性探测再散列解决冲突,装填因子为 0.7。
- 画出构造的散列表。
- 计算等概率下成功和失败 ASL。
查看答案与解析
- 数组大小 7/0.7=10,下标 0~9。
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
|---|---|---|---|---|---|---|---|
| H(key) | 0 | 3 | 6 | 5 | 5 | 6 | 0 |
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 7 | 14 | 8 | 11 | 30 | 18 | 9 |
- 成功查找各元素概率相同。
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
|---|---|---|---|---|---|---|---|
| 比较次数 | 1 | 1 | 1 | 1 | 3 | 3 | 2 |
成功 ASL=(1+2+1+1+1+3+3)/7=12/7。
失败 ASL 的分母既不按元素数也不按表长,而按散列函数可能产生的初始地址数。本题只映射到 0~6,且等概率。
| H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 比较次数 | 3 | 2 | 1 | 2 | 1 | 5 | 4 |
失败 ASL=(3+2+1+2+1+5+4)/7=18/7。
综合应用题 07
原书题目P330 · 解析P335 · 目视转录
【2024 统考真题】将 20,3,11,18,9,14,7 依次存入长度 11、初始为空的 HT,H(key)=(key×3)%11。初始地址为 H₀,冲突探查序列为 H₁,H₂,…,其中 Hₖ=(H₀+k²)%11,k=1,2,…。
- 画出构造后的 HT,计算装填因子。
- 给出查找 14 的关键字比较序列。
- 查找 8 时,确认失败的散列地址是多少?
查看答案与解析
- H(20)=5,装入 5;H(3)=9,装入 9;H(11)=0,装入 0;H(18)=10,装入 10;H(9)=5 冲突,探查 (5+1)%11=6,装入 6;H(14)=9 冲突,探查 10 仍冲突,再探查 (9+4)%11=2,装入 2;7 装入 3。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 11 | 14 | 7 | 20 | 9 | 3 | 18 |
装填因子 α=7/11。
- H(14)=9,与 3 比较;H₁=10,与 18 比较;H₂=2,与 14 比较,命中。序列为 3,18,14。
- H(8)=2,与 14 比较;H₁=(2+1)%11=3,与 7 比较;H₂=(2+4)%11=6,与 9 比较;H₃=(2+9)%11=0,与 11 比较;H₄=(2+16)%11=7,为空,确认失败。所以地址为 7。