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。

由 12(1+11−α)≤1.5\frac12(1+\frac1{1-\alpha})\le1.5,得 α=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. 为 O(log⁡2n)O(\log_2n)

B. 为 O(1)O(1)

C. 不直接依赖于 n

D. 直接依赖于表长 m

查看答案与解析

答案:C。

平均查找长度与装填因子 α 直接相关,不直接依赖元素数 n 或表长 m。若所有记录均为同一地址的同义词,平均查找长度为 O(n)O(n),并非总为 O(1)O(1)。

单项选择题 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。

地址012345678910111213141516
元素232267269

单项选择题 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。

地址0123456
关键字224315

成功 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。

地址012345678910
关键字982230871140620

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。

开放定址不能随便物理删除元素,否则可能截断同义词的查找地址,应作删除标记。

地址01234
关键字20221225(删除标记)
失败探查次数13212

遇删除标记继续往后查找。失败 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 内的随机整数。

  1. H(key)=key/n。
  2. H(key)=1。
  3. H(key)=(key+random(n))%n。
  4. H(key)=key%p(n),其中 p(n) 是不大于 n 的最大素数。
查看答案与解析
  1. 不能,key/n 可能大于 n,无法找到合适位置。
  2. 能,但不好,所有关键字映射到同一位置,造成大量冲突。
  3. 不能,返回值不确定,无法正常查找。
  4. 能,是好的散列函数。

综合应用题 03

原书题目P329 · 解析P333 · 目视转录

使用 H(key)=key%11,将整数转换成散列表下标。表长 11,依次插入 {1,13,12,34,38,33,27,22}。

  1. 使用线性探测法构造散列表。
  2. 使用链地址法构造散列表。

分别确定查找成功和失败的平均查找长度。

查看答案与解析

散列地址范围为 0~10。线性探测先计算初始地址,若空则存入,否则逐个探查下一空地址。链地址法先计算地址,再将结点插入对应链表。

  1. 线性探测:H(1)=1,直接存 1;H(13)=2,直接存 2;H(12)=1 冲突,地址 2 也冲突,放 3;H(34)=1,依次与 1、2、3 冲突,放 4;其余同理。
地址012345678910
关键字331131234382722
冲突次数00023017

每个已有元素查找概率为 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。

  1. 链地址法,按原书顺序在链尾插入:
地址链表
033→22→NULL
11→12→34→NULL
213→NULL
3NULL
4NULL
538→27→NULL
6~10NULL

成功查找 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 为不大于表长的最大素数。要求:

  1. 构造散列函数。
  2. 计算等概率下成功、失败 ASL(失败只计关键字之间的比较次数)。
查看答案与解析

由 α=n/N,可得 N=n/α≈15,因此 P=13,H(key)=key%13。

关键字263641384415681265125
散列地址0102125231261212

构造出的链表为: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,采用双散列法:

H0(key)=key%13,H_0(key)=key\%13, Hi=(Hi−1+REV⁡(key+1)%11+1)%13,i=1,2,…,m−1.H_i=(H_{i-1}+\operatorname{REV}(key+1)\%11+1)\%13,\quad i=1,2,\ldots,m-1.

REV(x) 颠倒十进制数的各位,例如 REV(37)=73、REV(7)=7。依次插入 (2,8,31,20,19,18,53,27)。

  1. 给出插入后的表。
  2. 计算成功 ASL。
查看答案与解析
  1. 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,无冲突。
地址0123456789101112
关键字27532311920818
比较次数31111112
  1. 成功 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。

  1. 画出构造的散列表。
  2. 计算等概率下成功和失败 ASL。
查看答案与解析
  1. 数组大小 7/0.7=10,下标 0~9。
key78301118914
H(key)0365560
地址0123456789
关键字71481130189
  1. 成功查找各元素概率相同。
key78301118914
比较次数1111332

成功 ASL=(1+2+1+1+1+3+3)/7=12/7。

失败 ASL 的分母既不按元素数也不按表长,而按散列函数可能产生的初始地址数。本题只映射到 0~6,且等概率。

H(key)0123456
比较次数3212154

失败 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,…。

  1. 画出构造后的 HT,计算装填因子。
  2. 给出查找 14 的关键字比较序列。
  3. 查找 8 时,确认失败的散列地址是多少?
查看答案与解析
  1. 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。
地址012345678910
关键字11147209318

装填因子 α=7/11。

  1. H(14)=9,与 3 比较;H₁=10,与 18 比较;H₂=2,与 14 比较,命中。序列为 3,18,14。
  2. 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。