【数据结构】——查找、散列表的相关习题

目录

• 一、选择填空判断题
• • 题型一（顺序查找）
  • 题型二（折半查找）
  • 题型三（分块查找）
  • 题型四（树型查找——二叉排序树）
  • 题型五（树型查找——平衡二叉树）
  • 题型六（处理冲突方法）
• 二、应用题
• • 题型一（折半查找判定树）
  • 题型二（散列表——线性探查法）
  • 题型三（散列表——链地址法）
  • 题型四（散列表——平方探查法）
  • 题型五（二叉排序树）

一、选择填空判断题

题型一（顺序查找）

1、顺序查找适用于存储结构为（）的线性表。
A、顺序存储结构或者链式存储结构
B、散列存储结构
C、索引存储结构
D、压缩存储结构

解析：（A）
顺序查找属于线性查找，从线性表的一端开始，依次检查所给定的关键字是否满足条件，若找到符合条件的元素，则查找成功；否则，查找失败。

由于线性表有顺序存储和链式存储两种存储方式，顺序查找对这两种存储方式都适用，若对于顺序表，则通过数组的下标依次查找；对于链表，则通过指针依次查找，在链表中只能进行顺序查找。

题型二（折半查找）

1、使用二分查找方法时，对线性表的存储结构及特性的要求是（）。
A、元素的链表
B、有序的链表
C、无序的顺序表
D、有序的顺序表

解析：（D）
二分查找（折半查找）属于线性查找，每次取中间元素进行比较，一直缩小范围继续进行查找，直到查找到相关元素为止，找到即查找成功；否则，查找失败。

二分查找只适用于有序的顺序表，它要求线性表具有随机存取，前提是查找表中必须是按关键字大小有序排列。

2、在一个顺序存储的有序线性表上查找一个数据时，既可以采用折半查找，也可以采用顺序查找，但前者比后者的查找速度（）。
A、必然快
B、取决于表是递增还是递减
C、在大部分情况下要块
D、必然不快

解析：（C）
顺序查找的优点是对元素的存储没有要求，可以顺序存储和链式存储，且对表内的有序性也没有要求，但其缺点是当n较大时，ASL较大，导致效率低。在平均情况下，折半查找比顺序查找的效率高。

3、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功的比较次数为（）。
A、1
B、2
C、4
D、6

解析：（B）
low指针一开始指向13，high指针一开始指向134，所以mid指向50，第一次比较90>15，所以low+1，high指针不变，此时low指针指向62，high指针指向134，即mid指向90，即第二次比较时找到目标元素，查找成功的比较次数为2。

4、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多为（）。
A、4
B、5
C、6
D、7

解析：（B）
对于顺序查找，查找成功或不成功，关键字的比较次数始终是n+1次，当定位至第i个元素时，关键字的比较次数为n-i+1。（默认代码中采用监视哨，若不采用监视哨，关键字的比较次数为n）

对于折半查找，查找成功和查找失败的最多比较次数相同，均为⌈log₂(n+1)⌉，由于折半判定树不是一棵满二叉树，其各分支高度相差为0或1，且由于最多相差为1，所以查找失败的最少次数为⌈log₂(n+1)⌉。故题中关键字的比较次数最多为⌈log₂(n+1)⌉=⌈log₂(16+1)⌉=⌈log₂(17)⌉= 4.087…，取大于等于该值的最小整数（向上取整），即5。

5、若有序表中有150个元素，采用二分查找方法进行查找，则查找成功的最大查找长度为（）。
A、8
B、7
C、6
D、5

解析：（A）
在折半判定树中，比较次数最多不会超过树的高度h=⌈log₂(n+1)⌉，即最大查找长度不会超过⌈log₂(n+1)⌉，所以查找成功的最大查找长度为⌈log₂151⌉=⌈7.23⌉=8。

题型三（分块查找）

1、（填空）长度为7225的有序表，采用分块查找进行查找，为了提高顺序查找索引表和顺序查找相应块的效率，则应将有序表分成_________块，每块长度为_________，此时平均查找长度是_________。

解析：85、85、86
分块查找的平均查找长度等于索引查找和块内查找的平均查找长度之和，即ASL=ASL_索引表+ASL_子表。若查找表长度为n，被均匀地分为b块，且每块有s个记录，则在等概率的情况下，若对块内和索引表内都采用顺序查找的平均查找长度为：ASL=ASL_索引表+ASL_子表=(b+1)/2+(s+1)/2=(s2+2s+n)/2s，且每块有记录为s= √n。

所以被分为85块，每块的最佳长度应该为√7225=85最合适，为每个块建立索引，索引表中索引项的个数为85，即每块长度为85，从85个块中进行顺序查找，即(b+1)/2=(85+1)/2=43；在每个块中进行顺序查找，即(s+1)/2=(85+1)/2=43，故平均查找长度为43+43=86。

2、为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找列表中已有元素最多需要执行（）次关键字比较。
A、10
B、14
C、16
D、21

解析：（C）
每个索引块的大小为 √65025=255，为每个块建立索引，索引表中索引项的个数为b=255，当对索引表和块内都采用折半查找时，查找效率最高，即ASL=ASL_索引表+ASL_子表=⌈log₂(b+1)⌉+⌈log₂(b+1)⌉=2⌈log₂(b+1)⌉=2⌈log₂256⌉=2×8=16。

题型四（树型查找——二叉排序树）

1、按（）遍历二叉排序树得到的序列是一个有序序列。
A、先序
B、中序
C、后序
D、层次

解析：（B）
二叉排序树也称为二叉查找树，其中各结点值的大小关系是：左子树<根结点<右子树，且左、右子树也是一棵二叉排序树满足其条件，若对该树进行中序遍历，可得到一个递增序列。

同样，平衡二叉树是基于二叉排序树来的，平衡二叉树也是一颗二叉排序树，按照中序也可以得到一个递增序列。

2、二叉排序树中进行查找的效率与（）有关。
A、二叉排序树的深度
B、二叉排序树的结点个数
C、被查找结点的度
D、二叉排序树的存储结构

解析：（A）
二叉排序树的查找是由根结点开始，然后沿着二叉树的分支依次向下查找，若要查找的元素与当前根结点相等，则查找成功；若小于根结点，则在当前根结点的左子树上继续查找，若大于，则在当前根结点的右子树上继续查找，依次递归。所以，二叉排序树的查找效率取决于树的高度。

3、构造一棵具有n个结点的二叉排序树，理想情况下和最坏情况下的深度分别为（）。
A、n，⌈log2(n+1)⌉
B、n，n
C、⌈log2(n+1)⌉，n
D、⌈log2(n+1)⌉，⌈log2(nn+1)⌉

解析：（C）
对n个结点构造二叉排序树，理想情况下，即为一棵满二叉树时的高度，类比于完全二叉树，即树的高度为h=⌈log₂(n+1)⌉，所以二叉排序树的最小深度为⌈log₂(n+1)⌉；而若二叉排序树只是一个单支树（左或右单支树），此时最坏情况，即树的高度为元素的个数，则其最大深度为n。

4、对于查找的关键字序列{52，26，14，32，71，60，93，58，24，41}构造二叉排序树，在该树中查找元素60需要进行的比较次数为（）。
A、3
B、4
C、5
D、6

解析：（A）
构造二叉排序树如下：

对元素60进行查找，首先与根结点52进行比较，由于60>52，沿着右子树依次向下比较，60<71，向下元素71的左子树向下继续比较，60=60，查找成功，故比较次数为3。

5、对于查找的关键字序列{52，26，14，32，71，60，93，58，24，41}构造二叉排序树，在该树中查找元素60需要进行的比较的结点依次为（）。
A、52，71
B、52，71，60
C、52，71，93
D、52，71，58

解析：（B）
由上题可知，一共与三个元素进行比较，且最后一次比较的元素是要查找的元素查找成功，所以依次比较的元素为52、71、60。

6、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。
A、{15，13，14，6，17，16，18}
B、{15，17，16，18，13，6，14}
C、{15，6，13，14，17，16，18}
D、{15，13，6，14，17，18，16}

解析：（C）
选项A、B、D和C，如下构造的二叉排序树：

其中C选项中与用其它三个序列所构造的结果不同。

7、折半查找与二叉排序树的时间性能（）。
A、相同
B、完全不同
C、有时不相同
D、数量级都为O(log₂n)

解析：（C）
折半查找中，查找成功和查找失败的最多比较次数相同，均为⌈log₂(n+1)⌉，所以为O(log₂n)，而二叉排序树只有是平衡二叉树时，其平均查找长度为O(log₂n)，故有时不相同。

题型五（树型查找——平衡二叉树）

1、具有5层结点的AVL至少有（）个结点。
A、10
B、12
C、15
D、17

解析：（B）
由斐波那契数列（Fibonacci），可得最少有f(m) = f(m-1) + f(m-2) + 1个结点，其中f(1) = 1 、f(2) = 2、f(3) = 4。具有5层结点的平衡二叉树，m=5，所以的结点个数至少为f(5) = f(5-1) + f(5-2) + 1= f(4) + f(3) + 1=[f(3) + f(2) + 1]+[f(2) + f(1) + 1]+1=4+2+1+2+1+1+1=12个结点。

2、若将关键字1，2，3，4，5，6，7依次插入初始为空的平衡二叉树T，则T中平衡因子为0的分支结点的个数为（）。
A、0
B、1
C、2
D、3

解析：（D）
构造平衡二叉树，插入过程中保证其条件，若不满足调整：

插入结点4、5，插入结点5时，不平衡进行调整：

RR型旋转后：

插入结点6，不平衡，进行RR型旋转：

进行RR型旋转：

插入结点7：

3、给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是（）
A、16
B、20
C、23
D、25

解析：（D）
可知，插入的关键字23后，发生不平衡：

由于插入的位置是结点20的右子树的左子树，所以进行RL型旋转：

题型六（处理冲突方法）

1、在开放定址法中散列到同一个地址而引起的“堆积”问题是由于（）引起的。
A、同义词之间发生冲突
B、非同义词之间发生冲突
C、同义词之间或非同义词之间发生冲突
D、散列表“溢出”

解析：（C）

（多选）2、为提高散列表的查找效率，可以采取的措施是（）。
A、增大装填因子
B、设计冲突少的散列函数
C、处理冲突时避免产生聚集现象

解析：（BC）
哈希表的查找效率取决于哈希函数、处理冲突的方法和装填因子α，其中装填因子α是一个表的装满程度，它等于表中记录数/哈希表长度，哈希表的平均查找长度依赖于装填因子α，而不直接依赖记录数或哈希表长度，当α越大，表示装填的记录越满，发生冲突的可能性越大，反之可能性越小。

二、应用题

题型一（折半查找判定树）

1、若一个有序顺序表表长为12：
（1）画出对其进行二分查找的二分查找判定树；
（2）在等概率假定条件下，计算对该表进行二分查找时查找成功和查找失败的平均查找长度。

解析：（1）二分查找判定树的求法：
①确定根结点：取low=1，high=12，mid向下取整（小于等于这个数的最大整数），即mid=⌊(low+high)/2 ⌋=⌊6.5⌋=6，即元素6为判定树的根结点，如下：


②从mid的左右子表开始进行查找。
③mid左子表查找：

• 【左子树】此时low=1不变，high变为mid-1，mid=6，即high=mid-1=6-1=5，改变后的mid=⌊(low+high)/2⌋=⌊6/2⌋=⌊3⌋=3，所以根结点6的左子树为3，如下：
  
  
• 继续探索左子树，low=1不变，high变为mid-1，mid=3，即high=mid-1=3-1=2，改变后的mid=⌊(low+high)/2 ⌋=⌊3/2⌋=⌊1.5⌋=1，所以结点3的左子树为1，如下：
  
  
• 若继续探索左子树，易知结点1无左子树。
• 从结点1开始探索右子树，high=2不变，low为mid+1，mid=1，即low=mid+1=1+1=2，改变后的mid=⌊(low+high)/2 ⌋=⌊4/2⌋=⌊2⌋=2，所以结点1的右子树为2，如下：
  
  
• 【右子树】此时从结点3开始探索右子树，high=5不变，low为mid+1，mid=3，即low=mid+1=3+1=4，改变后的mid=⌊(low+high)/2 ⌋=⌊9/2⌋=⌊4.5⌋=4，所以结点3的右子树为4，如下：
  
  
• 若继续探索左子树，易知结点4无左子树。
• 此时从结点4开始探索右子树，high=5不变，low为mid+1，mid=4，即low=mid+1=4+1=5，改变后的mid=⌊(low+high)/2 ⌋=⌊10/2⌋=⌊5⌋=5，所以结点4的右子树为5，如下：
  
  
  ④mid右子表查找：
• 此时high=12不变，low为mid+1，mid=6，即low=mid+1=6+1=7，改变后的mid=⌊(low+high)/2 ⌋=⌊19/2⌋=⌊9.5⌋=9，如下：
  
• 此时从结点9开始探索左子树，low=5不变，high为mid+1，mid=9，即high=mid+1=9+1=10，改变后的mid=⌊(low+high)/2 ⌋=⌊15/2⌋=⌊7.5⌋=7，如下：
  
  
  ……
  最后可以得到如下：
  

（2）查找成功：ASL=（1×1+2×2+4×3+5×4）/12=37/12。
查找失败：判定树中，将其补全，第四行失败的叶结点有3个，第五行失败的叶结点有10个，如下：

所以ASL=（3×3+4×10）/13=49/13。

2、假定对有序表{13，17，21，28，34，36，42，49，53，62，77，85}进行二分查找，根据其二分查找树，回答以下问题：
（1）若查找元素81，则需要依次与哪些元素比较？
（2）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
（3）假定每个元素的查找概率相等，求查找失败时的平均查找长度。

解析：（1）画出其二分查找树，如下：

由查找树可知，要查找元素81，需要依次与36、53、77、85进行比较：

（2）查找成功时，ASL=（1×1+2×2+3×4+4×5）/12=37/12
（3）将判定树中失败的结点补全，第四行失败的叶结点有3个，第五行失败的叶结点有10个，如下：

所以ASL=（3×3+4×10）/13=49/13。

题型二（散列表——线性探查法）

1、设散列函数H(K)=K%13，其表长为13，地址范围为0~12，对关键字序列{5，31，18，24，27，15，2，3，16，4}进行构造散列表，采用线性探查法处理冲突，
（1）画出散列表；
（2）在等概率假定条件下，计算该表查找成功和查找失败的平均查找长度。

解析：（1）由散列函数，将关键字值代入到哈希函数中求得哈希地址：
H(5)=5%13=5，发生冲突次数为0；

由于H(31)=31%13=5，出现冲突，进行处理，
m=13，增量序列d_i=1，所以H₃₁=(H(k_i)+d_i)%m=(H(31)+d₁)%13=(5+1)%13=6，发生冲突次数为1；

由于H(18)=18%13=5，出现冲突，进行处理，
m=13，增量序列d_i=1，所以H₃₁=(H(k_i)+d_i)%m=(H(18)+d₁)%13=(5+1)%13=6，处理后发现仍冲突，继续进行处理，
H₃₁=(H(k_i)+d_i)%m=(H(18)+d₂)%13=(5+2)%13=7，得到发生冲突次数为2；

H(24)=24%13=11，发生冲突次数为0；

H(27)=27%13=1，发生冲突次数为0；

H(15)=15%13=2，发生冲突次数为0；

由于H(2)=2%13=2，出现冲突，进行处理，m=13，增量序列d_i=1，所以H₂=(H(k_i)+d_i)%m=(H(2)+d₁)%13=(2+1)%13=3，发生冲突次数为1；

由于H(3)=3%13=3，出现冲突，进行处理，
m=13，增量序列d_i=1，所以H₃=(H(k_i)+d_i)%m=(H(3)+d₁)%13=(3+1)%13=4，发生冲突次数为1；

由于H(16)=3%13=3，出现冲突，进行处理，m=13，增量序列d_i=1，所以H₃=(H(k_i)+d_i)%m=(H(16)+d₁)%13=(3+1)%13=4，仍发生冲突，继续处理，H₃=(H(k_i)+d_i)%m=(H(16)+d₂)%13=(3+2)%13=5，仍发生冲突，继续处理，H₃=(H(k_i)+d_i)%m=(H(16)+d₃)%13=(3+3)%13=6，仍发生冲突，继续处理，H₃=(H(k_i)+d_i)%m=(H(16)+d₄)%13=(3+4)%13=7，仍发生冲突，继续处理，H₃=(H(k_i)+d_i)%m=(H(16)+d₅)%13=(3+5)%13=8，
不发生冲突结束，发生冲突次数为5；

由于H(4)=4%13=4，出现冲突，进行处理，……，同样也冲突5次。
最终，得到的哈希表如下：

（2）在等概率情况下，每个元素的冲突次数加1除以元素个数，即得到查找成功下的平均查找长度，即：

在等概率情况下，表中每个地址本身到下一个非空地址的个数相加除以表长，即得到查找成功下的平均查找长度，而空单元为3，即

2、设散列函数H(K)=K%16，其地址范围为0~17，对关键字序列{10，24，32，17，31，30，46，47，40，63，49}进行构造散列表，采用线性探查法处理冲突，
（1）画出散列表；
（2）若要查找60和63，需要依次与哪些关键字进行比较？
（3）在等概率假定条件下，计算该表查找成功和查找失败的平均查找长度。

解析：（1）由散列函数，将关键字值代入到哈希函数中求得哈希地址：
H(10)=10%16=10，发生冲突次数为0；
H(21)=24%16=8，发生冲突次数为0；
H(32)=32%16=0，发生冲突次数为0；
H(17)=17%16=1，发生冲突次数为0；
H(31)=31%16=15，发生冲突次数为0；
H(30)=30%16=14，发生冲突次数为0；
H(46)=46%16=14，发生冲突，探测下一位置H(46)=15，仍发生冲突，继续探测下一位置16未发生冲突，故H(46)=16，发生冲突次数为2；
H(47)=47%16=15，探测下一位置H(46)=16，仍发生冲突，继续探测下一位置17未发生冲突，故H(46)=17，发生冲突次数为2；
H(40)=40%16=8，发生冲突，探测下一位置9未发生冲突，故H(40)=9，所以发生冲突次数为1；
H(63)=63%16=15，发生冲突，探测下一位置16，仍发生冲突，继续探测下一位置17发生冲突，回到散列表的起始地址继续探测，下一位置0，仍发生冲突，继续探测下一位置1发生冲突，继续探测下一位置2未发生冲突，故H(63)=2，所以发生冲突次数为5；
H(49)=49%16=1，发生冲突，探测下一位置2，仍发生冲突，继续探测下一位置3未发生冲突，故H(49)=3，所以发生冲突次数为2。

（2）查找元素60，H(60)=60%16=12，根据散列表中地址为12的单元为空，所以比较一次即可查找到该元素。
查找元素63，H(63)=63%16=15，由于查找该元素发生5次冲突，需要依次与散列表地址为15、16、17、0、1的元素进行比较，即31、46、47、32、17，另外最后与其本身还有一次比较，所以共需要与31、46、47、32、17、63比较。
（3）在等概率情况下，每个元素的冲突次数加1除以元素个数，即得到查找成功下的平均查找长度，即：

在等概率情况下，表中每个地址本身到下一个非空地址的个数相加除以表长，即得到查找成功下的平均查找长度，由于这里查找关键字中，比较的地址范围和真实地址不一样，即哈希函数中的16不等于表长18，所以查找失败时不计入ASL，只取地址为0~15的元素，即地址为16和17的元素舍去，而空单元为7，即

题型三（散列表——链地址法）

1、用关键字序列{1，9，12，11，25，35，17，29}创建一个哈希表，装填因子a=1/2，确定表长m，采用除留余数法构造哈希函数，通过链地址法来处理冲突。
（1）求m的值；
（2）画出哈希表；
（2）求在等概率情况下，查找成功和查找失败的平均查找长度。

解析：（1）n为关键字个数，m为表长，所以装填因子a=n/m=1/2，其中n=8，可得：m=16。
（2）除留余数法构造哈希函数，可得到哈希函数H(K)=K%p，其中p的取值为不大于表长的最大素数（素数：不能被常数1或自己以外的其他整数整除的数），且尽量使哈希地址散落均匀从而减少冲突，由于表长为16，故p的取值为13，即哈希函数为H(K)=K%13。
链地址法表示的哈希表如下：

题型四（散列表——平方探查法）

1、设散列函数H(K)=K mod 7，表长为10，对关键字序列{9，1，23，14，55，20，84，27}进行构造散列表，采用开放地址法的二次探测再散列法Hi=(H(K)+di) mod 10（di=0，1²，2²，3²……）解决冲突，构造哈希表，并计算查找成功和查找失败的平均查找长度。

解析：由散列函数，将关键字值代入到哈希函数中求得哈希地址：
9%7=2，无冲突，放在散列地址2中，冲突次数为0；
1%7=1，无冲突，放在散列地址1中，冲突次数为0；
23%7=2，与散列地址2冲突，通过平方探查法，即（2+1）%10=3，此时无冲突，放在散列地址3中，冲突次数为1；
14%7=0，无冲突，放在散列地址0中，冲突次数为0；
55%7=6，无冲突，放在散列地址6中，冲突次数为0；
20%7=6，与散列地址6冲突，通过平方探查法，即（6+1）%10=7，此时无冲突，放在散列地址7中，冲突次数为1；
84%7=0，与散列地址0冲突，通过平方探查法，即（0+1）%10=1，此时仍有冲突，继续通过平方探查法，即（0+2²）%10=4，此时无冲突，放在散列地址4中，冲突次数为2；
27%7=6，与散列地址6冲突，通过平方探查法，即（6+1）%10=7，此时仍有冲突，继续通过平方探查法，即（6+2²）%10=0，此时仍有冲突，继续通过平方探查法，即（6+3²）%10=5，此时无冲突，放在散列地址5中，冲突次数为3。

题型五（二叉排序树）

1、已知长度为12的表（13，10，19，4，11，26，21，5），按表中的顺序依次插入一棵初始为空的二叉排序树，
（1）画出插入完成后的二叉排序树；
（2）画出在以上二叉排序树中删除值为10的结点后的二叉排序树。

解析：
（1）插入完成后的二叉排序树如下：

（2）删除值为10的结点，该结点有左孩子和右孩子，所以用二叉排序树的中序遍历序列中该结点的前驱/后继代替该结点。
由于二叉排序树的中序遍历序列是一个递增序列，不难得到，中序遍历序列为{4，5，10，11，13，19，26}，这里选择10的前驱结点5代替，所以删除后的二叉排序树可表示为：

2、设依次输入关键码{6，11，3，7，15，5，12，4，9，1}构造二叉搜索树。
（1）画出二叉搜索树；
（2）计算在等概率条件下查找成功的平均查找长度ASL。

解析：
（1）可画出该二叉搜索树：