数据结构题目收录（二十一）

1、在开放定址法中散列到同一个地址而引起的“堆积”问题是由于（）引起的。

• A：同义词之间发生冲突
• B：非同义词之间发生冲突
• C：同义词之间或非同义词之间发生冲突
• D：散列表“溢出”

解析

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

答案：C

2、 下列关于散列冲突处理方法的说法中，正确的有（）。

Ⅰ、采用再散列法处理冲突时不易产生聚集
Ⅱ、采用线性探测法处理冲突时，所有同义词在散列表中一定相邻
Ⅲ、采用链地址法处理冲突时，若限定在链首插入，则插入任一个元素的时间是相同的
Ⅳ、采用链地址法处理冲突易引起聚集现象

• A：Ⅰ和Ⅲ
• B：Ⅰ、Ⅱ和Ⅲ
• C： Ⅲ和Ⅳ
• D： Ⅰ和Ⅳ

解析

• 利用再散列法处理冲突时，按一定的距离，跳跃式地寻找“下一个”空闲位置，减少了发生聚集的可能，Ⅰ正确。
• 散列地址i的关键字，和为解决冲突形成的某次探测地址为i的关键字，都争夺地址i，i+1，…，因此不一定相邻，Ⅱ错误。Ⅲ正确。
• 同义词冲突不等于聚集，链地址法处理冲突时将同义词放在同一个链表中，不会引起聚集现象，Ⅳ错误。

答案：A

3、 设有一个含有200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过1.5，则散列表应能够容纳（）个表项（设查找成功的平均查找长度为ASL=[1+1/(1-$\alpha$)]/2，其中$\alpha$为装填因子）。

• A：400
• B：526
• C：624
• D：676

解析

若有200个表项要放入散列表，采用线性探测法解决冲突，限定查找成功的平均查找长度不超过1.5，则

答案：A

4、 假定有K个关键字互为同义词，若用线性探测法把这K个关键字填入散列表，至少要进行（）次探测。

• A：K-1
• B：K
• C：K+1
• D：K(K+1)/2

解析

K个关键字在依次填入的过程中，只有第一个不会发生冲突，故探测次数为（1+2+3+…+K）=K(K+1)/2，即选D。

答案：D

5、 对包含n个元素的散列表进行查找，平均查找长度（）。

• A：为O(${\log }_2$n)
• B：为O(1)
• C：不直接依赖于n
• D：直接依赖于表长m

解析

在散列表中，平均查找长度与装填因子$\alpha$直接相关，表的查找效率不直接依赖于表中已有表项个数n或表长m。若散列表中存放的记录全部是某个地址的同义词，则平均查找长度为O(n)而非O(1)。

答案：C

6、 采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（）。

• A：数据元素过多
• B：负载因子过大
• C：散列函数选择不当
• D：解决冲突的方法选择不当

解析

聚集是因为选取不当的处理冲突的方法，而导致不同关键字的元素对同一散列地址进行争夺的现象。用线性再探测法，容易引发聚集现象。

答案：D

7、在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值（）；若采用线性探测法，则（）。

• A：一定都是同义词
• B：不一定都是同义词
• C：都相同
• D：一定都不是同义词

解析

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

答案：A，B

8、用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（）。

• A：存储效率
• B：散列函数
• C：装填（装载）因子
• D：平均查找长度

解析

产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选D。

答案：D

9、现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列87,40,30,6，11,22,98,20依次插入HT后，HT查找失败的平均查找长度是（）。

• A：4
• B：5.35
• C：6
• D：6.29

解析

采用线性探查法计算每个关键字的存放情况如下表所示。

由于H(key)=0~6，查找失败时可能对应的地址有7个，对于计算出地址为0的关键字key0，只有比较完0~8号地址后才能确定该关键字不在表中，比较次数为9；对于计算出地址为1的关键字key1，只有比较完1~8号地址后才能确定该关键字不在表中，比较次数为8；以此类推。需要特别注意的是，散列函数不可能计算出地址7，因此有

答案：C

10、对任意7个关键字进行基于比较的排序，至少要进行（）次关键字之间的两两比较。

• A：13
• B：14
• C：15
• D：6

解析

对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。对于任意n个关键字排序的比较次数至少为$┌$${\log }_2$(n!)$┐$。将n=7代入公式，答案为13。

答案：A