折半查找判定树及平均查找长度

二分法查找1、二分查找(Binary Search)二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。

不妨设有序表是递增有序的。

2、二分查找的基本思想二分查找的基本思想是：（设R[low..high]是当前的查找区间）（1）首先确定该区间的中点位置：（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。

②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。

下一次查找是针对新的查找区间进行的。

因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。

这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

3、二分查找算法int BinSearch(SeqList R，KeyType K){ //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零int low=1，high=n，mid；//置当前查找区间上、下界的初值while(low<=high){ //当前查找区间R[low..high]非空mid=(low+high)/2；if(R[mid].key==K) return mid；//查找成功返回if(R[mid].kdy>K)high=mid-1; //继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}return 0；//当low>high时表示查找区间为空，查找失败} //BinSeareh二分查找算法亦很容易给出其递归程序【参见练习】4、二分查找算法的执行过程设算法的输入实例中有序的关键字序列为(05，13，19，21，37，56，64，75，80，88，92)要查找的关键字K分别是21和85。

折半查找判定树的特点
折半查找（Binary Search）判定树是一种用于分析二分查找算法的数据结构。

以下是折半查找判定树的一些特点：
1.平衡性：折半查找判定树是一棵平衡二叉树。

在最坏情况下，每一层的节点数量都接近于对数的底数为2，这保证了查找的效率。

2.查找时间复杂度：对于包含n个元素的有序数组，折半查找的时间复杂度为O(log n)。

这是因为每一次比较都会将搜索范围缩小一半。

3.插入和删除的复杂度：插入和删除操作不如查找高效。

由于需要保持有序性，插入和删除的平均时间复杂度为O(log n)，但在最坏情况下可能需要O(n)的时间来调整平衡。

4.节点结构：每个节点表示一个比较操作，包含有关元素和比较值的信息。

树的叶子节点表示查找成功的结束点，而非叶子节点表示查找的比较过程。

5.路径长度：对于n个元素的有序数组，折半查找判定树的路径长度为log₂(n)+1。

路径长度是指从根节点到达叶子节点的最短路径的长度。

6.对数性质：折半查找的效率主要依赖于对数的性质。

每一次比较都将搜索范围缩小一半，因此查找的时间复杂度是对数级别的。

7.适用性：折半查找适用于有序数组，因为它依赖于元素的有序性。

如果数据经常需要进行查找而不是插入和删除，折半查找是一种高效的算法。

总的来说，折半查找判定树是一种用于分析二分查找算法行为的有用工具，它展示了查找过程中关键比较的次数和顺序。

折半查找判定树的规则一、折半查找的原理折半查找，也称为二分查找，是一种高效的查找算法。

它的基本思想是将待查找的区间不断二分，直到找到目标元素或确定目标元素不存在。

具体步骤如下：1. 首先，将待查找的区间的左右边界确定为列表的起始位置和结束位置。

2. 然后，计算区间的中间位置，即将左右边界相加除以2得到的整数。

3. 接下来，将中间位置的元素与目标元素进行比较。

4. 如果中间位置的元素等于目标元素，则查找成功，返回该元素的位置。

5. 如果中间位置的元素大于目标元素，则将区间的右边界更新为中间位置减1，并继续查找。

6. 如果中间位置的元素小于目标元素，则将区间的左边界更新为中间位置加1，并继续查找。

7. 重复步骤2至6，直到找到目标元素或确定目标元素不存在。

二、折半查找判定树的规则折半查找判定树是一种用来描述折半查找过程的树状结构。

它由若干个节点组成，每个节点表示一个子问题的解决过程。

根据折半查找的原理，我们可以总结出折半查找判定树的规则如下：1. 根节点表示待查找的区间。

2. 若当前区间为空，则查找失败，返回-1。

3. 若当前区间只包含一个元素，且该元素等于目标元素，则查找成功，返回该元素的位置。

4. 若当前区间只包含一个元素，且该元素不等于目标元素，则查找失败，返回-1。

5. 若当前区间包含多个元素，则按照中间位置划分左右子区间。

6. 若中间位置的元素等于目标元素，则查找成功，返回该元素的位置。

7. 若中间位置的元素大于目标元素，则在左子区间中继续查找，否则在右子区间中继续查找。

三、折半查找的应用折半查找是一种非常高效的查找算法，因此在实际应用中被广泛使用。

它主要应用于以下场景：1. 有序列表的查找：折半查找适用于已经排序的列表，通过不断二分查找的方式可以快速定位目标元素。

2. 数据库索引的实现：数据库中的索引通常采用B+树结构，而B+树的查找过程就是基于折半查找的。

3. 数组中的查找：对于有序数组，折半查找可以在O(logn)的时间复杂度下找到目标元素。

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

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

【＊，★】A.nB. ⌊log2n⌋C. ⌊log2(n+1)⌋D. ⌈log2(n+1)⌉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，则该树共有（）个结点。

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

解：判定树应当描述每次查找的位置：9.9已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

解：9.19解：H(22)=(3×22) mod 11=0 H(41)=(3×41) mod 11=2 H(53)=(3×53) mod 11=5 H(46)=(3×46) mod 11=6H(30)=(3×30) mod 11=2 冲突d1=(7×30) mod 10+1=1 H1（30）=(2+1)/11=3 H(13)=(3×13) mod 11=6 冲突d1=(7×13) mod 10+1=2 H1（13）=(6+2)/11=8 H(01)=(3×01) mod 11=3冲突d1=(7×1) mod 10+1=8 H1（01）=(3+8)/11=0冲突d2=2*（(7×1) mod 10+1）=16 H2（01）=（3+16）/11=8冲突d3=3*（(7×1) mod 10+1）=24 H3（01）=（3+24）/11=5冲突d4=4*（(7×1) mod 10+1）=32 H4（01）=（3+32）/11=2冲突d5=5*（(7×1) mod 10+1）=40 H5（01）=（3+40）/11=10H(67)=(3×67) mod 11=3冲突d1=(7×67) mod 10+1=10 H1（67）=（3+10）/11=2冲突d2=2*((7×67) mod 10+1)=20 H2（67）=（3+20）/11=1哈希表：ASL=(1+1+1+1+2+2+6+3)/8=17/8X。

具有12个关键字的有序表,折半查找的平均查
找长度
折半查找是一种在有序序列中查找某个给定值的方法，它是一种加速搜索的算法，并且有着高效、可靠的特点，在每次搜索次数减半的情况下，无论序列的长度多大，其查找代价是固定的，能大大减少存储器和 CPU 占用，节省时间和空间。

折半查找时，先取出中间位置记录，将查找值和中间位置记录进行比较，子表长度缩小，重复上述查找操作，直到找到等于查找值的记录，或子表不存在为止。

如果有12个关键字的有序表，用折半查找方法来查找，那么平均查找长度(ASL)是[log2(n)]+1=4。

从0开始计数，折半查找找到元素最多需要3步：第一步，查找中间位置的元素；第二步，比较查找元素与中间位置的元素的大小，如果查找元素小于中间位
置的元素，就在中间位置的左半边的子序列中继续查找；如果查找元素大于中间位置的元素，就在中间位置的右半边的子序列中继续查找；第三步，不断进行折半查找，直到找到查找元素，或者查找范围为空，则查找失败，结束。

总的来说，折半查找是一种非常有效的搜索算法
它可以在有序表中大大加快搜索速度，在12个关键字有序表中，折半查找的平均查找长度是4，在节省时间和空间的同时，能够很好地用于搜索、匹配等需要的操作中。

数据结构中的查找算法总结静态查找是数据集合稳定不需要添加删除元素的查找包括：1. 顺序查找2. 折半查找3. Fibonacci4. 分块查找静态查找可以⽤线性表结构组织数据，这样可以使⽤顺序查找算法，再对关键字进⾏排序就可以使⽤折半查找或斐波那契查找等算法提⾼查找效率，平均查找长度：折半查找最⼩，分块次之，顺序查找最⼤。

顺序查找对有序⽆序表均适⽤，折半查找适⽤于有序表，分块查找要求表中元素是块与块之间的记录按关键字有序动态查找是数据集合需要添加删除元素的查找包括： 1. ⼆叉排序树 2. 平衡⼆叉树 3. 散列表 顺序查找适合于存储结构为顺序存储或链接存储的线性表。

顺序查找属于⽆序查找算法。

从数据结构线形表的⼀端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相⽐较，若相等则表⽰查找成功 查找成功时的平均查找长度为： ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 顺序查找的时间复杂度为O(n)。

元素必须是有序的，如果是⽆序的则要先进⾏排序操作。

⼆分查找即折半查找，属于有序查找算法。

⽤给定值value与中间结点mid的关键字⽐较，若相等则查找成功；若不相等，再根据value 与该中间结点关键字的⽐较结果确定下⼀步查找的⼦表 将数组的查找过程绘制成⼀棵⼆叉树排序树，如果查找的关键字不是中间记录的话，折半查找等于是把静态有序查找表分成了两棵⼦树，即查找结果只需要找其中的⼀半数据记录即可，等于⼯作量少了⼀半，然后继续折半查找，效率⾼。

根据⼆叉树的性质，具有n个结点的完全⼆叉树的深度为[log2n]+1。

尽管折半查找判定⼆叉树并不是完全⼆叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为[log2n]+1，最好的情况是1次。

时间复杂度为O(log2n)； 折半计算mid的公式 mid = (low+high)/2;if(a[mid]==value)return mid;if(a[mid]>value)high = mid-1;if(a[mid]<value)low = mid+1; 折半查找判定数中的结点都是查找成功的情况，将每个结点的空指针指向⼀个实际上不存在的结点——外结点，所有外界点都是查找不成功的情况，如图所⽰。

第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。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n—1)/2 B. n/2 C。

（n+1）/2 D。

n2. 下面关于二分查找的叙述正确的是（ )A。

表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B。

表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分(对半）查找表的元素的速度比用顺序法（ )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度( ）A. 3。

1 B。

4 C. 2。

5 D. 55．当采用分块查找时,数据的组织方式为 ( ）A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序,但块间必须有序，每块内最大(或最小）的数据组成索引块C。

数据分成若干块，每块内数据有序，每块内最大(或最小）的数据组成索引块D. 数据分成若干块,每块（除最后一块外)中数据个数需相同6。

二叉查找树的查找效率与二叉树的( （1）)有关, 在（（2）)时其查找效率最低（1）: A。

高度 B。

结点的多少 C. 树型 D. 结点的位置(2）: A。

结点太多 B. 完全二叉树 C。

呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败，它们的平均查找长度是((1）） ,对于查找成功，他们的平均查找长度是（（2））供选择的答案：A。

相同的 B。

不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A．(100,80， 90， 60， 120，110，130） B。

（100，120，110,130，80， 60, 90) C。

（100，60, 80， 90, 120，110，130） D。

第八章选择题1. C2.A3.B4.C5.D6.B7.B8.A9.D 10.D 11.C 12.C填空题1.n、n+12. 43.8.25( 折半查找所在块 )4.左子树、右子树5.266.顺序、(n+1)/2、O(log2n)7.m-1、[m/2]-18.直接定址应用题1.进行折半查找时，判定树是唯一的，折半查找过程是走了一条从根节点到末端节点的路径，所以其最大查找长度为判定树深度[log2n]+1.其平均查找长度约为[log2n+1]-1.在二叉排序树上查找时，其最大查找长度也是与二叉树的深度相关，但是含有n个节点的二叉排序树不是唯一的，当对n个元素的有序序列构造一棵二叉排序树时，得到的二叉排序树的深度也为n，在该二叉树上查找就演变成顺序查找，此时的最大查找长度为n；在随机情况下二叉排序树的平均查找长度为1+4log2n。

因此就查找效率而言，二分查找的效率优于二叉排序树查找，但是二叉排序树便于插入和删除，在该方面性能更优。

3. 评价哈希函数优劣的因素有：能否将关键字均匀的映射到哈希表中，有无好的处理冲突的方法，哈希函数的计算是否简单等。

冲突的概念：若两个不同的关键字Ki和Kj，其对应的哈希地址Hash(Ki) =Hash(Kj)，则称为地址冲突，称Ki和K,j为同义词。

（1）开放定址法（2）重哈希法（3）链接地址法4.（1）构造的二叉排序树，如图（2）中序遍历结果如下：10 12 15 20 24 28 30 35 46 50 55 68（4）平均查找长度如下：ASLsucc = （1x1+2x2+3x3+4x3+5x3）/12 = 41/128.哈希地址如下：H(35) = 35%11 = 2H(67) = 67%11 = 1H(42) = 42%11 = 9H(21) = 21%11 = 10H(29) = 29%11 = 7H(86) = 86%11 = 9H(95) = 95%11 = 7H(47) = 47%11 = 3H(50) = 50%11 = 6H(36) = 36%11 = 3H(91) = 91%11 = 3第九章选择题1. D2.C3.B4.D5.C6.B7.A8.A9.D 10.D填空题1.插入排序、交换排序、选择排序、归并排序2.移动（或者交换）3.归并排序、快速排序、堆排序4.保存当前要插入的记录，可以省去在查找插入位置时的对是否出界的判断5.O(n)、O(log2n)6.直接插入排序或者改进了的冒泡排序、快速排序7.Log2n、n8.完全二叉树、n/29.1510.{12 38 25 35 50 74 63 90}应用题11.（1）Shell排序(步长为5 3 1)每趟的排序结果初始序列为100 87 52 61 27 170 37 45 61 118 14 88 32步长为5的排序14 37 32 61 27 100 87 45 61 118 170 88 52步长为3的排序结果14 27 32 52 37 61 61 45 88 87 170 100 118步长为1的排序结果14 27 32 37 45 52 61 61 87 88 100 118最后结果14 27 32 37 45 52 61 61 87 88 100 118 170（2）快速排序每趟的排序结果如图初始序列100 87 52 61 27 170 37 45 61 118 14 88 32第一趟排序[32 87 52 61 27 88 37 45 61 14]100[118 170]第二趟排序[14 27]32[61 52 88 37 45 61 87]100 118[170]第三趟排序14[27]32[45 52 37]61[88 61 87]100 118[170]第四趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]第五趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]最后结果14[27]32[37]45[52]61[61]87 88 100 118[170]（3）二路归并排序每趟的排序结果初始序列[100][87][52][61][27][170][37][45][61][118][14][88][32]第一趟归并[87 100][52 61][27 170][37 45][61 118][14 88][32]第二趟归并[52 61 87 100][27 37 45 170][14 61 88 118][32]第三趟归并排序[27 37 45 52 61 87 100 170][14 32 61 88 118]第四趟归并排序[14 27 32 37 45 52 61 61 87 88 100 118 170]最后结果14 27 32 37 45 52 61 61 87 88 100 118 17012.采用快速排序时，第一趟排序过程中的数据移动如图：算法设计题1.分析：为讨论方便，待排序记录的定义为（后面各算法都采用此定义）：#define MAXSIZE 100 /* 顺序表的最大长度，假定顺序表的长度为100 */ typedef int KeyType; /* 假定关键字类型为整数类型 */typedef struct {KeyType key; /* 关键字项 */OtherType other; /* 其他项 */}DataType; /* 数据元素类型 */typedef struct {DataType R[MAXSIZE+1]; /* R[0]闲置或者充当哨站 */int length; /* 顺序表长度 */}sqList; /* 顺序表类型 */设n个整数存储在R[1..n]中，因为前n-2个元素有序，若采用直接插入算法，共要比较和移动n-2次，如果最后两个元素做一个批处理，那么比较次数和移动次数将大大减小。

⼆分法查找# ⼆分查找(折半查找)title: ⼆分查找tags: 数据结构与算法之美author: ⾠砂⼀、简介⼆分查找也称折半查找（Binary Search），它是⼀种效率较⾼的查找⽅法。

但是，折半查找要求线性表必须采⽤顺序存储结构，⽽且表中元素按关键字有序排列（解释：所以⼆分查找的时候⼀定要是有序的数组）⼆、过程若k==R[mid].key，查找成功若k<R[mid].key，则high=mid-1若k>R[mid].key，则low=mid+11.查找 212.查找70三、算法描述1.⾮递归设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录⽐较若k==R[mid].key，查找成功若k<R[mid].key，则high=mid-1若k>R[mid].key，则low=mid+1重复上述操作，直⾄low>high时，查找失败int Search_Bin(SSTable ST,KeyType key){//若找到，则函数值为该元素在表中的位置，否则为0low=1;high=ST.length; while(low<=high){mid=(low+high)/2;if(key==ST.R[mid].key) return mid;else if(key<ST.R[mid].key) high=mid-1;//前⼀⼦表查找else low=mid+1; //后⼀⼦表查找} return0; //表中不存在待查元素}2.递归int Search_Bin (SSTable ST, keyType key, int low, int high){if(low>high) return0; //查找不到时返回0mid=(low+high)/2;if(key==ST.elem[mid].key) return mid;else if(key<ST.elem[mid].key)return search_Bin(ST,key,low,mid-1);//递归else return search_Bin(ST,key,mid+1,high); //递归}3、完整代码public class BinarySearch {public static void main(String[] args) {int[] nums = {1, 4, 5, 8, 9};System.out.println(binarySearch(nums, 1));System.out.println(binarySearchRecursion(nums, 1, 0, nums.length - 1));}/*** 循环** @param nums* @param target** @return*/public static int binarySearch(int[] nums, int target) {if (nums.length < 0) {return -1;}int left = 0;int right = nums.length - 1;while (left <= right) {int mid = (left - right) / 2 + right;if (target == nums[mid]) {return mid;} else if (target > nums[mid]) {left = mid + 1;} else {right = mid - 1;}}return -1;}/*** 递归** @param nums* @param target* @param left* @param right** @return*/public static int binarySearchRecursion(int[] nums, int target, int left, int right) {if (nums.length < 0 || left < 0 || right > nums.length - 1) {return -1;}int mid = (left - right) / 2 + right;if (left <= right) {if (target == nums[mid]) {return mid;} else if (target > nums[mid]) {return binarySearchRecursion(nums, target, mid + 1, right);} else {return binarySearchRecursion(nums, target, left, mid - 1);}}return -1;}四、折半查找的性能分析判定树：树中每个结点表⽰表中⼀个记录，结点中的值为该记录在表中的位置，通常称这个查找过程的⼆叉树称为判定树。

第六章 查找填空题1.折半查找的要求是，并且 。

2.折半查找判定树既是一种 ，也是一种 。

3.假定在有序表R[0…19]上进行折半查找，则比较一次查找成功的结点数为 个，比较两次查找成功的结点数为 ，比较三次查找成功的结点数为 ，比较四次查找成功的结点数为 ，比较五次查找成功的结点数为 ，折半查找的平均查找长度为 。

4.假定查找有序表R[0…ll]中每个元素的概率相等，则进行顺序查找的平均查找长度为 ，进行折半查找时的平均查找长度为 。

5.对线性表R[0…59]进行分块查找，共分为10块，每块长度等于6，若假定查找索引表和块均用顺序查找的方法，查找每一个元素的平均查找长度为 。

6.在分块查找中，首先查找 ，然后再查找相应的 ，整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应于表的平均查找长度的 。

7.对于长度为n的线性表，若进行顺序查找，则时间复杂度为 ，若进行折半查找，则时间复杂度为 ，若进行分块查找，则时间复杂度为 (假定总块数和每块长度均接近n^1/2值)。

8.若一个待散列存储的线性表长度为n，用于散列的散列表长度为m，则m应为 。

装填因子为 。

9.在散列存储中，装填因子的值越大，存取元素时发生冲突的可能性就 ，当的值越小，存取元素时发生冲突的可能性就 。

10.在线性表的散列存储中，处理冲突有 和 两类。

当装填因子一定时，采用链地址法解决冲突比采用开放定址法处理冲突的平均查找长度要 。

11. 已知一个待散列存储的线性表为(18、34、58、26、75、67、48、93、81)，散列函数为h(k)=k％11，若采用线性探查法解决冲突，则平均查找长度为 ；若采用链地址法解决冲突，则平均查找长度为 。

12.折半查找的查找速度 比顺序查找的速度快，假设有100个元素，用折半折半查找时，最大查找比较次数是 ，最小比较次数是 。

选择题13.采用顺序查找的方法查找长度为n的线性表，则查找每个元素的平均比较次数为( )。

计算机学科专业基础综合数据结构-查找(一)(总分：100.00，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：38，分数：38.00)1.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素查找成功的平均查找长度为______。

∙ A.n/2∙ B.(n+1)/2∙ C.(n-1)/2∙ D.n/4（分数：1.00）A.B. √C.D.解析：[解析] 对单链表和顺序表进行顺序查找，都需要逐个扫描表中元素，因此其平均查找长度相同，都是(n+1)/2。

2.对线性表进行折半查找时，要求线性表必须______。

∙ A.以顺序方式存储∙ B.以链接方式存储∙ C.以顺序方式存储，且结点按关键字有序排序∙ D.以链接方式存储，且结点按关键字有序排序（分数：1.00）A.B.C. √D.解析：[解析] 折半查找要求表的存储结构有随机存储特性，且表中元素要有序，因此本题选C。

3.采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为______。

∙ A.O(n)∙ B.O(log2n)∙ C.O(n2)∙ D.O(nlog2n)（分数：1.00）A.B. √C.D.解析：[解析] 对长度为n的有序顺序表进行折半查找，其平均查找长度与有n个结点的完全二叉树同数量级，即O(log2n)，因此本题选B。

4.在对长度为n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为______。

A．n B．C． D（分数：1.00）A.B.C.D. √解析：[解析] 折半查找的平均查找长度可用二叉判定树分析，其高度与完全二叉树相同，根据完全二叉树的性质，有[*]。

5.采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数______对应二叉判定树的高度(设高度≥2)。

∙ A.小于∙ B.大于∙ C.等于∙ D.小于等于（分数：1.00）A.B.C.D. √解析：[解析] 对有序顺序表中的元素进行查找所需要的总比较次数与对应元素在表中的位置有关，最多不会超出该表对应二叉判定树的高度，因此本题选D。

《数据结构提高》试卷考查复习题面①单选题②判断题③填空题④简答题⑤画图题⑥计算题目录《数据结构提高》试卷考查复习题 (1)一、单项选择题（抽考10小题，每小题2分，共20分） (1)二、判断题（共10小题，每小题1分，共10分） (4)三、填空题（每小题1分，共12分） (4)四、简答题（共2小题，每小题5分，共10分。

） (5)五、画图题（抽考2小题，每小题6分，共12分。

） (6)六、计算题（共3小题，每小题12分，共36分。

） (7)七、算法设计题（抽考1题，共12分。

） (9)《数据结构提高》试卷考查复习题一、单项选择题（抽考10小题，每小题2分，共20分）1．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的右孩子结点的编号为（C）。

左孩子节点编号为2iA 2i+1B 2iC i/2D 2i-12．下面程序段的时间复杂度是（C）。

for（i ＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）A[i][j] ＝0；A O(n)B O(nlog2n)C O(n2)D O(n3/2)3．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（C）。

A head==nullB head->next==nullC head->next==headD head!=null4．设某棵二叉树的高度为8，则该二叉树上叶子结点最多有（ B ）。

2^(8-1)A 64B 128C 512D 10245.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作为__D__。

**********注意：是链式栈选D，顺序栈选B**********A top=top+1;B top=top-1;C top->next=top;D top=top->next;6.以下数据结构中哪一个是线性结构？__B__A 树B 栈C 图D 二叉树7. 设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是__C__。

二叉树完全二叉树：若二叉树的高度是h，除第h层之外，其他（1~h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。

想到点什么没？实际上堆也是完全二叉树满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。

哈夫曼树：又称为最优树，这是一种带权路径长度最短的树。

哈夫曼编码就是哈夫曼树的应用。

构造如下：1、将所有节点集合看成独立的树，且左右子树都为空，没有父节点；2、挑选两棵根节点权值最小的没有父节点的树，生成一个节点作为它们的父节点，父节点的权值等于他们的权值之和，集合中删除这两个子节点，将父节点加入到节点集合3、重复第2步，直到最后变成一棵树。

平衡二叉树（插入、删除！！如何平衡！！）：所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过1。

红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。

红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。

对于红黑树，插入，删除，查找的复杂度都是O （log N）--------------------------二叉树操作：树的高度= max(左子树的高度，右子树的高度) + 1树中的叶子节点的个数= 左子树中叶子节点的个数+ 右子树中叶子节点的个数交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换求两个节点的最近公共祖先求两个节点的公共祖先可以用到上面的判断一个节点是否在一颗子树中。

（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。

（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。

（3）如果两个节点一个在根节点的右子树中，一个在根节点的左子树中，则最近公共祖先一定是根节点。

当然，要注意的是：可能一个节点pNode1在以另一个节点pNode2为根的子树中，这时pNode2就是这两个节点的最近公共祖先了。

数据结构50：⼆分查找法（折半查找法）折半查找，也称⼆分查找，在某些情况下相⽐于顺序查找，使⽤折半查找算法的效率更⾼。

但是该算法的使⽤的前提是静态查找表中的数据必须是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使⽤折半查找算法查找数据之前，需要⾸先对该表中的数据按照所查的关键字进⾏排序：{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进⾏排序的意思是：若查找表中存储的数据元素含有多个关键字时，使⽤哪种关键字做折半查找，就需要提前以该关键字对所有数据进⾏排序。

折半查找算法对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采⽤折半查找算法查找关键字为 21 的过程为：图 1 折半查找的过程（a）如上图 1 所⽰，指针 low 和 high 分别指向查找表的第⼀个关键字和最后⼀个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。

在查找的过程中每次都同 mid 指向的关键字进⾏⽐较，由于整个表中的数据是有序的，因此在⽐较之后就可以知道要查找的关键字的⼤致位置。

例如在查找关键字 21 时，⾸先同 56 作⽐较，由于21 < 56，⽽且这个查找表是按照升序进⾏排序的，所以可以判定如果静态查找表中有 21这个关键字，就⼀定存在于 low 和 mid 指向的区域中间。

因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧⼀个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。

如图 2 所⽰：图 2 折半查找的过程（b）同样，⽤ 21 同 mid 指针指向的 19 作⽐较，19 < 21，所以可以判定 21 如果存在，肯定处于 mid 和 high 指向的区域中。

所以令 low 指向 mid 右侧⼀个位置上，同时更新 mid 的位置。

平均查找长度平均查找长度（AverageSearchLength，ASL）是统计学中相对特定结构而言一种术语，用以指定该结构中某一元素的查找所需的平均步数，也就是说，通过给定的结构，寻找某元素的平均步数是该结构的平均查找长度。

平均查找长度可以用来衡量一种数据结构的性能，可以用来比较不同的查找算法，也可用来确定某个算法的时间复杂度。

在统计学中，平均查找长度是一个常用的量度，用它可以比较不同的查找算法，从而确定算法的优劣。

比如，假设已知的结构有两种查找算法，A和B，那么可以分别计算它们的平均查找长度，并把它们进行比较，从而确定哪种算法更优秀。

如何计算平均查找长度计算平均查找长度的方法有很多，其中最常用的方法是使用枚举法（Enumeration）。

使用枚举方法，首先需要确定数据结构中所有元素的键值（key），然后算出每种键值的查找步数，最后把所有元素的查找步数求和，并除以总元素数，从而得出该数据结构的平均查找长度。

另外，还有一种非常简单的方法来计算平均查找长度，这种方法称为随机查找法（Random Search）。

按照这种方法，对于每一个要查找的元素，使用随机折半查找法（Binary Search），最后求和所有查找步数，除以总元素数，从而得出平均查找长度。

平均查找长度的应用平均查找长度可以应用于数据结构和算法，用来确定不同数据结构和算法之间的优劣势。

其中，对于同一种数据结构，不同的查找算法之间的性能可以用平均查找长度来比较；而对于不同的数据结构，使用相同的查找算法的性能也可以用平均查找长度来比较。

此外，平均查找长度也可以用于确定某种算法的时间复杂度，因为知道了算法的平均查找长度，可以把它与对应的时间复杂度建立联系，这样就能大致估算出算法的时间复杂度了。

总结平均查找长度（Average Search Length，ASL）是统计学中相对特定结构而言一种术语，可以用它来衡量一种数据结构的性能，可以比较不同的查找算法，也可用来确定某个算法的时间复杂度。

数据结构简答题1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.7 在程序设计中，可采用下列三种方法实现输出和输入：(1) 通过scanf和printf语句；(2) 通过函数的参数显式传递；(3) 通过全局变量隐式传递。

试讨论这三种方法的优缺点。

解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。

(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。

(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。