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

这篇具有很好参考价值的文章主要介绍了【数据结构】——查找、散列表的相关习题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、选择填空判断题

题型一(顺序查找)

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)

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

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

解析:(A)
在折半判定树中,比较次数最多不会超过树的高度h=⌈log2(n+1)⌉,即最大查找长度不会超过⌈log2(n+1)⌉,所以查找成功的最大查找长度为⌈log2151⌉=⌈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子表=⌈log2(b+1)⌉+⌈log2(b+1)⌉=2⌈log2(b+1)⌉=2⌈log2256⌉=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=⌈log2(n+1)⌉,所以二叉排序树的最小深度为⌈log2(n+1)⌉;而若二叉排序树只是一个单支树(左或右单支树),此时最坏情况,即树的高度为元素的个数,则其最大深度为n。
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找

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

解析:(A)
构造二叉排序树如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
对元素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,如下构造的二叉排序树:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
其中C选项中与用其它三个序列所构造的结果不同。

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

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

题型五(树型查找——平衡二叉树)

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)
构造平衡二叉树,插入过程中保证其条件,若不满足调整:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
插入结点4、5,插入结点5时,不平衡进行调整:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
RR型旋转后:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
插入结点6,不平衡,进行RR型旋转:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
进行RR型旋转:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
插入结点7:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
不平衡,进行调整,RR型旋转,得到最终的AVL树:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
由树可知,平衡因子为0的分支结点的个数为3,分别是结点4、结点2和结点6。

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

已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
解析:(D)
可知,插入的关键字23后,发生不平衡:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
由于插入的位置是结点20的右子树的左子树,所以进行RL型旋转:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找

题型六(处理冲突方法)

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为判定树的根结点,如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
②从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,如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
  • 继续探索左子树,low=1不变,high变为mid-1,mid=3,即high=mid-1=3-1=2,改变后的mid=⌊(low+high)/2 ⌋=⌊3/2⌋=⌊1.5⌋=1,所以结点3的左子树为1,如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
  • 若继续探索左子树,易知结点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,如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
  • 右子树】此时从结点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,如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
  • 若继续探索左子树,易知结点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,如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    mid右子表查找
  • 此时high=12不变,low为mid+1,mid=6,即low=mid+1=6+1=7,改变后的mid=⌊(low+high)/2 ⌋=⌊19/2⌋=⌊9.5⌋=9,如下:已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
  • 此时从结点9开始探索左子树,low=5不变,high为mid+1,mid=9,即high=mid+1=9+1=10,改变后的mid=⌊(low+high)/2 ⌋=⌊15/2⌋=⌊7.5⌋=7,如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
    ……
    最后可以得到如下:
    已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找

(2)查找成功:ASL=(1×1+2×2+4×3+5×4)/12=37/12。
查找失败:判定树中,将其补全,第四行失败的叶结点有3个,第五行失败的叶结点有10个,如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
所以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)画出其二分查找树,如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
由查找树可知,要查找元素81,需要依次与36、53、77、85进行比较:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
(2)查找成功时,ASL=(1×1+2×2+3×4+4×5)/12=37/12
(3)将判定树中失败的结点补全,第四行失败的叶结点有3个,第五行失败的叶结点有10个,如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
所以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;

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 5
冲突次数 0

由于H(31)=31%13=5,出现冲突,进行处理,
m=13,增量序列di=1,所以H31=(H(ki)+di)%m=(H(31)+d1)%13=(5+1)%13=6,发生冲突次数为1;

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 5 31
冲突次数 0 1

由于H(18)=18%13=5,出现冲突,进行处理,
m=13,增量序列di=1,所以H31=(H(ki)+di)%m=(H(18)+d1)%13=(5+1)%13=6,处理后发现仍冲突,继续进行处理,
H31=(H(ki)+di)%m=(H(18)+d2)%13=(5+2)%13=7,得到发生冲突次数为2;

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 5 31 18
冲突次数 0 1 2

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

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 5 31 18 24
冲突次数 0 1 2 0

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

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 27 5 31 18 24
冲突次数 0 0 1 2 0

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

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 27 15 5 31 18 24
冲突次数 0 0 0 1 2 0

由于H(2)=2%13=2,出现冲突,进行处理,m=13,增量序列di=1,所以H2=(H(ki)+di)%m=(H(2)+d1)%13=(2+1)%13=3,发生冲突次数为1;

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 27 15 2 5 31 18 24
冲突次数 0 0 1 0 1 2 0

由于H(3)=3%13=3,出现冲突,进行处理,
m=13,增量序列di=1,所以H3=(H(ki)+di)%m=(H(3)+d1)%13=(3+1)%13=4,发生冲突次数为1;

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 27 15 2 3 5 31 18 24
冲突次数 0 0 1 1 0 1 2 0

由于H(16)=3%13=3,出现冲突,进行处理,m=13,增量序列di=1,所以H3=(H(ki)+di)%m=(H(16)+d1)%13=(3+1)%13=4,仍发生冲突,继续处理,H3=(H(ki)+di)%m=(H(16)+d2)%13=(3+2)%13=5,仍发生冲突,继续处理,H3=(H(ki)+di)%m=(H(16)+d3)%13=(3+3)%13=6,仍发生冲突,继续处理,H3=(H(ki)+di)%m=(H(16)+d4)%13=(3+4)%13=7,仍发生冲突,继续处理,H3=(H(ki)+di)%m=(H(16)+d5)%13=(3+5)%13=8,
不发生冲突结束,发生冲突次数为5;

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 27 15 2 3 5 31 18 16 24
冲突次数 0 0 1 1 0 1 2 5 0

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

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12
关键字 27 15 2 3 5 31 18 16 4 24
冲突次数 0 0 1 1 0 1 2 5 5 0

(2)在等概率情况下,每个元素的冲突次数加1除以元素个数,即得到查找成功下的平均查找长度,即:
A S L 成功 = ( 1 + 1 + 2 + 2 + 1 + 2 + 3 + 6 + 6 + 1 ) 10 = 25 10 = 5 2 ASL_{成功}=\frac{(1+1+2+2+1+2+3+6+6+1)}{10}=\frac{25}{10} =\frac{5}{2} ASL成功=10(1+1+2+2+1+2+3+6+6+1)=1025=25
在等概率情况下,表中每个地址本身到下一个非空地址的个数相加除以表长,即得到查找成功下的平均查找长度,而空单元为3,即
A S L 失败 = ( 3 × 1 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 2 ) 13 = 59 13 ASL_{失败}=\frac{(3×1+10+9+8+7+6+5+4+3+2+2)}{13}=\frac{59}{13} ASL失败=13(3×1+10+9+8+7+6+5+4+3+2+2)=1359

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。

散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
关键字 32 17 63 49 24 40 10 30 31 46 47
冲突次数 0 0 5 2 0 1 0 0 0 2 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除以元素个数,即得到查找成功下的平均查找长度,即:
A S L 成功 = ( 1 + 1 + 6 + 3 + 1 + 2 + 1 + 1 + 1 + 3 + 3 ) 11 = 23 11 ASL_{成功}=\frac{(1+1+6+3+1+2+1+1+1+3+3)}{11}=\frac{23}{11} ASL成功=11(1+1+6+3+1+2+1+1+1+3+3)=1123
在等概率情况下,表中每个地址本身到下一个非空地址的个数相加除以表长,即得到查找成功下的平均查找长度,由于这里查找关键字中,比较的地址范围和真实地址不一样,即哈希函数中的16不等于表长18,所以查找失败时不计入ASL,只取地址为0~15的元素,即地址为16和17的元素舍去,而空单元为7,即
A S L 失败 = ( 7 × 1 + 5 + 4 + 3 + 2 + 4 + 3 + 2 + 9 + 8 ) 16 = 47 16 ASL_{失败}=\frac{(7×1+5+4+3+2+4+3+2+9+8)}{16}=\frac{47}{16} ASL失败=16(7×1+5+4+3+2+4+3+2+9+8)=1647

题型三(散列表——链地址法)

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。
链地址法表示的哈希表如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
(3)通过链地址法表示的哈希表计算:
查找成功时,ASL等于每行行数乘以元素的个数相加除以元素个数,即
A S L 成功 = ( 1 × 6 + 2 × 2 ) 8 = 10 8 = 5 4 ASL_{成功}=\frac{(1×6+2×2)}{8}=\frac{10}{8} =\frac{5}{4} ASL成功=8(1×6+2×2)=810=45
查找失败时,ASL等于每个单元的个数相加除以表长,即
A S L 失败 = ( 1 + 1 + 1 + 2 + 1 + 2 ) 13 = 8 13 ASL_{失败}=\frac{(1+1+1+2+1+2)}{13}=\frac{8}{13} ASL失败=13(1+1+1+2+1+2)=138

题型四(散列表——平方探查法)

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

解析:由散列函数,将关键字值代入到哈希函数中求得哈希地址:
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+22)%10=4,此时无冲突,放在散列地址4中,冲突次数为2;
27%7=6,与散列地址6冲突,通过平方探查法,即(6+1)%10=7,此时仍有冲突,继续通过平方探查法,即(6+22)%10=0,此时仍有冲突,继续通过平方探查法,即(6+32)%10=5,此时无冲突,放在散列地址5中,冲突次数为3。

散列地址 0 1 2 3 4 5 6 7 8 9
关键字 14 1 9 23 84 27 55 20
冲突次数 0 0 0 1 2 3 0 1

A S L 成功 = ( 1 + 1 + 1 + 2 + 3 + 4 + 1 + 2 ) 8 = 15 8 ASL_{成功}=\frac{(1+1+1+2+3+4+1+2)}{8}=\frac{15}{8} ASL成功=8(1+1+1+2+3+4+1+2)=815
A S L 失败 = ( 2 × 1 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 ) 10 = 46 10 = 23 5 ASL_{失败}=\frac{(2×1+9+8+7+6+5+4+3+2)}{10}=\frac{46}{10} =\frac{23}{5} ASL失败=10(2×1+9+8+7+6+5+4+3+2)=1046=523

题型五(二叉排序树)

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

解析:
(1)插入完成后的二叉排序树如下:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找

(2)删除值为10的结点,该结点有左孩子和右孩子,所以用二叉排序树的中序遍历序列中该结点的前驱/后继代替该结点。
由于二叉排序树的中序遍历序列是一个递增序列,不难得到,中序遍历序列为{4,5,10,11,13,19,26},这里选择10的前驱结点5代替,所以删除后的二叉排序树可表示为:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找

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

解析:
(1)可画出该二叉搜索树:
已知一个长度为16的顺序表l,其元素按关键字有序排列。若采用二分查找法查找一个l,数据结构重点习题,数据结构,查找,散列表,二分查找,分块查找
(2)在等概率的情况下,二叉排序树查找成功的平均查找长度ASL成功=每层层数乘以每层结点个数之和除以二叉排序树的结点总个数。
元素总数为10,其中第一层元素个数为1,第二层为2,第三层为4,第四层为3,所以可得查找成功的平均查找长度:
A S L 成功 = ( 1 × 1 + 2 × 2 + 3 × 4 + 4 × 3 ) 10 = 29 10 ASL_{成功}=\frac{(1\times1+2\times2+3\times4+4\times3 )}{10} =\frac{29}{10} ASL成功=10(1×1+2×2+3×4+4×3)=1029文章来源地址https://www.toymoban.com/news/detail-762122.html

到了这里,关于【数据结构】——查找、散列表的相关习题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】——排序算法的相关习题

    1、直接插入排序 1、对n个元素进行直接插入排序,需要进行()趟处理。 A、n B、n+1 C、n-1 D、2n 解析: (C) 直接插入排序是将要排序的序列按照的大小插入至已排好序的子序列中,一直进行直到整个序列有序,所以对n个元素进行直接插入排序,一共插入元素n-1次,

    2024年02月03日
    浏览(28)
  • 【数据结构】——串,数组,矩阵的相关习题

    1、数组通常具有的两种基本操作是()。 A、查找和修改 B、查找和索引 C、索引和修改 D、建立和删除 解析: (A) 基本操作是查找和修改,其中每个元素都可以通过其索引来访问,这是从数组的第一个元素开始计算的。除了访问和修改数组元素之外,还可以执行其他一些操

    2024年02月12日
    浏览(24)
  • 【数据结构】——线性表的相关习题

    1、线性表的顺序存储结构是一种()存储结构。 A、顺序存取 B、随机存取 C、索引存取 D、散列存取 解析: (B) 顺序存储结构 的可以实现 随机存取 ,可以在O(1)内通过首地址和元素序号找到元素,每个元素占用最少的存储空间,其存储密度高,但只能使用相邻的一块存储

    2024年02月14日
    浏览(28)
  • 【数据结构】——树和二叉树的相关习题

    1、设高度为h的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为(),最多为()。 A、h ;2 h -1 B、2h-1 ; 2 h -1 C、2h+1; 2 h-1 -1 D、h+1;2 h -1 解析: (B) 最少的情况下,除了根结点该层为1个结点以外,其余h-1层都有2个结点,得2(h-1),即2(h-1)+1=2h-1。

    2024年02月03日
    浏览(32)
  • 【数据结构】——多维数组、矩阵以及广义表的相关习题

    1、数组通常具有的两种基本操作是()。 A、查找和修改 B、查找和索引 C、索引和修改 D、建立和删除 解析: (A) 基本操作是查找和修改,其中每个元素都可以通过其索引来访问,这是从数组的第一个元素开始计算的。除了访问和修改数组元素之外,还可以执行其他一些操

    2024年02月04日
    浏览(27)
  • 数据结构之索引查找(分块查找)

    活动地址:CSDN21天学习挑战赛   作者简介:大家好我是小唐同学(๑؂๑),为梦想而奋斗的小唐,让我们一起加油!!! 个人主页: 小唐同学(๑؂๑)的博客主页 系列专栏:数据结构 博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已

    2024年02月02日
    浏览(38)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(41)
  • 数据结构10 -查找_树表查找

    二叉搜索树是有数值的了, 二叉搜索树是一个有序树 。 若它的左子树不空,则左子树上所有结点的值均 小于 它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均 大于 它的根结点的值; 它的左、右子树也分别为二叉排序树 下面这两棵树都是搜索树 bstree.c(二

    2024年02月14日
    浏览(27)
  • 数据结构--》掌握数据结构中的查找算法

            当你需要从大量数据中查找某个元素时,查找算法就变得非常重要。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握查找在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据

    2024年02月08日
    浏览(44)
  • 数据结构--6.3查找算法(静态、动态)(插值查找)

    静态查找:数据集合稳定,不需要添加,删除元素的查找操作。 动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作。 对于静态查找来说,我们不妨可以用线性表结构组织数据,这样可以使用顺序查找算法,如果我们在对进行排序,则可以使用折

    2024年02月09日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包