线性探测再散列查找成功和不成功的相关问题

数据结构第九、⼗章作业答案第九章查找⼀、填空题1. 在数据的存放⽆规律⽽⾔的线性表中进⾏检索的最佳⽅法是顺序查找（线性查找）。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从⼩到⼤排列的，对⼀个给定的值k ，⽤⼆分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，⽤⼆分法查找时，最⼤⽐较次数是 7 。

3. 假设在有序线性表a[1..20]上进⾏折半查找，则⽐较⼀次查找成功的结点数为1；⽐较两次查找成功的结点数为 2 ；⽐较四次查找成功的结点数为 8 ,其下标从⼩到⼤依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当⽤穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.74．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 ⽐较⼤⼩。

5. 在各种查找⽅法中，平均查找长度与结点个数n ⽆关的查找⽅法是散列查找。

6. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

7. 有⼀个表长为m 的散列表，初始状态为空，现将n （n8、设⼀哈希表表长M 为100 ，⽤除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找⽅法中，平均查找长度与结点个数⽆关的是哈希查找法10、对线性表进⾏⼆分查找时，要求线性表必须以顺序⽅式存储，且结点按关键字有序排列。

计算机学科专业基础综合数据结构-7(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：28，分数：74.00)1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为______。

（分数：2.00）A.(n-1)/2B.n/2C.(n+1)/2 √D..n解析：[解析] 此结论需要考生当作定理一样的牢记。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为______，二分法查找只适用于查找顺序存储的有序表，平均比较次数为______。

在此假定N为线性表中结点数，且每次查找都是成功的。

（分数：4.00）A.N+1B.2log2NC.log2ND.N/2 √E.Nlog2NF..N2解析：A.N+1B.2log2NC.log2N √D.N/2E.Nlog2NF..N2解析：2.下面关于二分查找的叙述正确的是______。

（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储√解析：二叉查找树的查找效率与二叉树的______有天，在______时查找效率最低。

（分数：4.00）A.高度B.结点的多少C.树形√D.结点的位置解析：A.结点太多B.完全二叉树C.呈单枝树√D.结点太复杂解析：3.当采用分块查找时，数据的组织方式为______。

（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块√C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同解析：[解析] 本题主要考查分块查找的相关概念。

4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法?______ （分数：2.00）A.分块√B.顺序C.二分法D.哈希解析：[解析] 由于题目只说明是线性表，因此排除二分法。

哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度⼀、哈希表1、概念哈希表(Hash Table)也叫散列表，是根据关键码值（Key Value）⽽直接进⾏访问的数据结构。

它通过把关键码值映射到哈希表中的⼀个位置来访问记录，以加快查找的速度。

这个映射函数就做散列函数，存放记录的数组叫做散列表。

2、散列存储的基本思路以数据中每个元素的关键字K为⾃变量，通过散列函数H（k）计算出函数值，以该函数值作为⼀块连续存储空间的的单元地址，将该元素存储到函数值对应的单元中。

3、哈希表查找的时间复杂度哈希表存储的是键值对，其查找的时间复杂度与元素数量多少⽆关，哈希表在查找元素时是通过计算哈希码值来定位元素的位置从⽽直接访问元素的，因此，哈希表查找的时间复杂度为O（1）。

⼆、常⽤的哈希函数1. 直接寻址法取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做⾃⾝函数.如果H(Key)的哈希地址上已经有值了,那么就往下⼀个位置找,知道找到H(Key)的位置没有值了就把元素放进去.2. 数字分析法分析⼀组数据,⽐如⼀组员⼯的出⽣年⽉,这时我们发现出⽣年⽉的前⼏位数字⼀般都相同,因此,出现冲突的概率就会很⼤,但是我们发现年⽉⽇的后⼏位表⽰⽉份和具体⽇期的数字差别很⼤,如果利⽤后⾯的⼏位数字来构造散列地址,则冲突的⼏率则会明显降低.因此数字分析法就是找出数字的规律,尽可能利⽤这些数据来构造冲突⼏率较低的散列地址.3. 平⽅取中法取关键字平⽅后的中间⼏位作为散列地址.⼀个数的平⽅值的中间⼏位和数的每⼀位都有关。

因此，有平⽅取中法得到的哈希地址同关键字的每⼀位都有关，是的哈希地址具有较好的分散性。

该⽅法适⽤于关键字中的每⼀位取值都不够分散或者较分散的位数⼩于哈希地址所需要的位数的情况。

4. 折叠法折叠法即将关键字分割成位数相同的⼏部分,最后⼀部分位数可以不同,然后取这⼏部分的叠加和(注意:叠加和时去除进位)作为散列地址.数位叠加可以有移位叠加和间界叠加两种⽅法.移位叠加是将分割后的每⼀部分的最低位对齐,然后相加;间界叠加是从⼀端向另⼀端沿分割界来回折叠,然后对齐相加.5. 随机数法选择⼀个随机数,去关键字的随机值作为散列地址,通常⽤于关键字长度不同的场合.6. 除留余数法取关键字被某个不⼤于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平⽅取中等运算之后取模。

第八章习题8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给定值K的记录。

（2）查找成功且表中只有一个关键字等于给定值K的记录。

（3）查找成功且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。

8.2画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

8.3试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。

8.4试从空树开始，画出按以下次序向2-3树(即3阶B-树)中插入关键码的建树过程：20，30，50，52，60，68，70。

如果此后删除50和68，画出每一步执行后2-3树的状态。

8.5选取哈希函数H(k)=(3k)%11，用线性探测再散列法处理冲突。

试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。

8.6试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。

（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）8.7试编写利用折半查找确定记录所在块的分块查找算法。

8.8试写一个判别给定二叉树是否为二叉排序树的算法。

设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。

8.9编写算法，求出指定结点在给定的二叉排序树中所在的层数。

8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。

8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。

8.12 已知长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。

第9章查找一、选择题1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复杂度为（）。

【＊，★】A.O(n)B. O(log2n)C. O(n2)D. O(nlog2n)2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。

【＊，★】A.nB.C.D.3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。

【＊】A.nB. n/2C. (n+1)/2D. (n-1)/24.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。

【＊＊】A.小于B. 大于C. 等于D. 大于等于5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）。

【＊】A. 1B. 2C. 3D. 46.对线性表进行折半查找时，要求线性表必须（）。

【＊】A.以顺序方式存储B. 以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序7.顺序查找法适合于存储结构为（）的查找表。

【＊】A.散列存储B. 顺序或链接存储C. 压缩存储D. 索引存储8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。

【＊＊】A.10B. 25C. 6D. 6259.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（），中序遍历序列为（）。

【＊＊，★】A.abcloprstuB. alcpobsrutC. trbaoclpsuD. trubsaocpl10.折半查找和二叉排序树的时间性能（）。

【＊】A.相同B. 不相同11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. kB.k+lC. k(k+l)／2D. l+k (k+l)/22．下述命题( )是不成立的。

A. m阶B-树中的每一个结点的子树个数都小于或等于mB. m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C. m阶B-树中的每一个结点的子树高度都相等D.m阶B-树具有k个子树的非叶子结点含有(k-l)个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ) 查找方法。

A.分块B. 顺序C. 二分D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( )，最小比较次数是( )。

A.7，1B.6，lC.5，1D. 8，15．散列表长m=15，散列表函数H(key)=key%13。

表中已有4个结点：addr(18)=5；addr(32)=6; addr(59)=7; addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8B. 3C. 5D. 46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A. 15B. 27C. 25D. 307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B. 最大概率C. 最小概率D.平均概率8．设散列地址空间为O..m-1，k为关键字，假定散列函数为h(k)=k%p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A.mB. m-lC.m+lD.[m+1]10．当向一棵m阶的B壤f做删除操作时，若使一个结点中的关键字个数等于( )，则可能需要用它的左兄弟或右兄弟结点合并成一个结点。

计算机学科专业基础综合数据结构-7一、单项选择题(总题数：28，分数：74.00)1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为______。

A.(n-1)/2B.n/2C.(n+1)/2 √D..n此结论需要考生当作定理一样的牢记。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为______，二分法查找只适用于查找顺序存储的有序表，平均比较次数为______。

在此假定N为线性表中结点数，且每次查找都是成功的。

（分数：4.00）A.N+1B.2log2NC.log2ND.N/2 √E.Nlog2NF..N2A.N+1B.2log2NC.log2N √D.N/2E.Nlog2NF..N22.下面关于二分查找的叙述正确的是______。

A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储√二叉查找树的查找效率与二叉树的______有天，在______时查找效率最低。

（分数：4.00）A.高度B.结点的多少C.树形√D.结点的位置A.结点太多B.完全二叉树C.呈单枝树√D.结点太复杂3.当采用分块查找时，数据的组织方式为______。

A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块√C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同本题主要考查分块查找的相关概念。

4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法?______A.分块√B.顺序C.二分法D.哈希由于题目只说明是线性表，因此排除二分法。

哈希算法虽然有最快的查找效率，但建立哈希表无法适应动态变化的要求。

习题9解答判断题：1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

答：FALSE (错。

链表表示的有序表不能用折半查找法。

)2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。

答：FALSE (错。

因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。

)3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。

( )答：TRUE4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。

答：TRUE5.查找表是由同一类型的数据元素(或记录)构成的集合。

答：TRUE单选题：6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。

A. 1、2、3B. 9、5、2、3C. 9、5、3D.9、4、2、3 答：D (第一次⎣⎦2/)181(+ = 9,第二次⎣⎦2/)81(+ = 4，第三次⎣⎦2/)31(+ = 2, (第四次⎣⎦2/)33(+ = 3，故选D.7. 顺序查找法适合于存储结构为____________的线性表。

A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储答：B8.对线性表进行二分查找时，要求线性表必须( )。

A ．以顺序方式存储 B. 以链接方式存储C ．以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序答：C9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。

表中已有4个记录(如下图所示)，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是( )。

答：D (计算H(k)，即H(49)=49 mod 11 = 5,冲突，进行二次探测再散列。

散列表冲突处理方案散列表（Hash Table）是一种重要的数据结构，它能够快速地进行插入、查找和删除等操作。

然而，在实际应用中，冲突（Collision）是散列表中常见的问题之一。

本文将介绍散列表冲突处理的几种常见方案，以及它们的优缺点。

一、开放定址法开放定址法是一种解决冲突的常见方法。

其原理是，当发生冲突时，通过一定的探测序列找到下一个可用的空槽，将待插入的元素放入该槽内。

常用的探测序列有线性探测、二次探测以及双重散列等。

1. 线性探测线性探测是最简单的开放定址法策略。

当发生冲突时，直接往后查找下一个空槽，并将待插入元素放入该槽内。

即使数组中只有少数位置被占用，线性探测也可能导致长时间的查找。

此外，线性探测容易产生一次聚集（Primary Clustering）现象，即冲突后的元素倾向于聚集在一起，进一步影响散列表的性能。

2. 二次探测二次探测对线性探测进行了改进。

当发生冲突时，根据一个二次探测序列进行查找下一个空槽，并将待插入元素放入该槽内。

二次探测的探测序列可以是平方探测、斐波那契探测等。

相比线性探测，二次探测能够减少聚集现象，但仍然存在聚集的问题。

3. 双重散列双重散列是一种更为高效的开放定址法策略。

当发生冲突时，通过计算另一个散列函数的值，并将其与原始散列值相加，得到下一个空槽的位置。

双重散列能够更好地解决聚集问题，提高散列表的性能。

二、链表法链表法是另一种常见的散列表冲突处理方案。

基本思想是，将散列得到的相同索引值的元素存储在同一个链表中。

当插入元素时，只需要将其插入到对应索引位置的链表尾部即可。

链表法对于散列冲突的处理效果较好，但在插入和查找操作上需要额外的链表遍历开销。

三、再散列法再散列法是一种结合链表法和开放定址法的冲突处理方法。

当发生冲突时，使用一个新的散列函数对待插入的元素进行再散列，并将其放入新的散列位置。

再散列法能够在一定程度上减少冲突的概率，提高散列表的性能。

综上所述，散列表冲突处理的方案有开放定址法、链表法以及再散列法等。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。