凑数

顺序查找的平均查找长度

4．对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找任一元素的平均查找长度为()。

A. 5/3

B.2

C.7/3

D.4/3

解析

$\color{green}{\text{A}}$. 5/3

这题指的是查找成功的时候的平均查找长度

总结

题型	错因	教训	视频讲解
	None		nan

折半查找和顺序查找的速度比较

在一个顺序存储的有序线性表上查找一个数据时，既可以采用折半查找，也可以采用顺序查找，但前者比后者的查找速度()。

A．必然快

B.取决于表是递增还是递减

C.在大部分情况下要快

D.必然不快

解析

$\color{green}{\text{C}}$.在大部分情况下要快

如果位于前面的话顺序查找显然查找长度小于二叉查找

总结

题型	错因	教训	视频讲解
	None		nan

二分查找查找不存在的元素查找长度的计算

8.【2010统考真题】已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是()。

A.4

B.5

C. 6

D.7

解析

折半查找法在查找不成功时和给定值进行关键字的比较次数最多为树的高度，$\lfloor log_2 (n) \rfloor + 1$或$\lceil log_2 (n + 1) \rceil $

总结

题型	错因	教训	视频讲解
			nan

二分查找的细节

在有11个元素的有序表$A[1,2….,11]$中进行折半查找($\lfloor (low+high)/2 \rfloor$)，查找元素$A[11]$时，被比较的元素下标依次是()。

A.6,8,10,11

B.6,9,10,11

C.6,7,9,11

D.6,8,9,11

解析

$\color{green}{\text{B}}$.6,9,10,11

脑里面走一个流程就行

总结

题型	错因	教训	视频讲解
	Null		nan

折半查找查找不成功最多和最少的比较次数

13．已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找算法查找一个不存在的元素，则比较的次数至少是()，至多是()。

A.4

B. 5

C. 6

D.7

解析

法1：画判定树
画判定树的技巧，像走程序流程一般，$[16] > [[7] , [8]] > [[[3],[3]],[[3],4]]$, 依次类推分化，再加上，不存在的节点，看经过边的数量(层数-1)
法2：套公式
是平衡二叉树，高度差为1，实际高度就是最多比较次次数。实际高度减一就是最少比较次数。

总结

题型	错因	教训	视频讲解
	None		nan

算二叉查找的查找长度

具有12个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为（)，折半查找查找失败的平均查找长度为（)。

A.37/12

B.35/12

C.39/13

D.49/13

解析

$\color{green}{\text{A}}$.37/12

$\color{green}{\text{D}}$.49/13

画出判定树

总结

题型	错因	教训	视频讲解
	None		nan

分块查找时数据的组织方式

16．采用分块查找时，数据的组织方式为()。

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小)的数据组成索引块

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

解析

分块查找的概念

总结

题型	错因	教训	视频讲解
	None		nan

17．对有2500个记录的索引顺序表（分块表）进行查找，最理想的块长为()。

A.50

B.125

C. 500

D. $log_22500$

解析

$\color{green}{\text{A}}$.50

虽然讲了块间用分块查找
但是实际上这道题需要用严的教材描述的块间块内都是顺序查找，最佳块长的公式为$\sqrt{n}$

总结

题型	错因	教训	视频讲解
	计算	根号多算了一位(C)	nan

19．为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（）次关键字比较。

A.10

B.14

C. 16

D.21

解析

$\color{red}{\text{C}}$. 16

双双折半查找（$\blacktriangleright$($\color{red}{\text{错题}}$？块内无序怎么进行折半查找呢)

总结

题型	错因	教训	视频讲解
	因素考虑完全	猜测题意	nan

1．若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同。

1)查找失败。

2）查找成功，且表中只有一个关键字等于给定值k的元素。

3)查找成功，且表中有若干关键字等于给定值k的元素，要求一次查找能找出所有元素。

解析

1）平均查找长度不同。因为有序顺序表查找到其关键字值比要查找值大的元素时就停止

答案应该是错的，正解应该是相同的，见我对王道算法的质疑，这个地方算出来应该是相同的

查找，并报告失败信息，不必查找到表尾;而无序顺序表必须查找到表尾才能确定查找失败。

2）平均查找长度相同。两者查找到表中元素的关键字值等于给定值时就停止查找。

3)平均查找长度不同。有序顺序表中关键字相等的元素相继排列在一起，只要查找到第一个就可以连续查找到其他关键字相同的元素。而无序顺序表必须查找全部表中的元素才能找出相同关键字的元素，因此所需的时间不同。

n-k

总结

题型	错因	教训	视频讲解
	None		nan

2．设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765, 897,908。

1)试画出对其进行折半查找的判定树。

2)若查找275或684的元素，将依次与表中的哪些元素比较?3）计算查找成功的平均查找长度和查找不成功的平均查找长度。

解析

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710114900.png)

总结

题型	错因	教训	视频讲解
	None		nan

k分查找的时间复杂度

3．类比二分查找算法，设计k分查找算法(k为大于2的整数）如下:首先检查n/k处(n为查找表的长度）的元素是否等于要搜索的值，然后检查2n/k处的元素……这样，或者找到要查找的元素，或者把集合缩小到原来的1/k，若未找到要查找的元素，则继续在得到的集合上进行k 分查找;如此进行，直到找到要查找的元素或查找失败。试求查找成功和查找失败的时间复杂度。

解析

注意这题只要求计算时间复杂度，而不是$ASL$

总结

题型	错因	教训	视频讲解
	None		nan

分块查找变种

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710115205.png)

解析

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710115606.png)

总结

题型	错因	教训	视频讲解
	题意		nan

2013真题:算法的改进

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710115831.png)

解析

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710115959.png)

换了一种折半查找的方法，按照长度来二叉查找，明明可以达到1.8

总结

题型	错因	教训	视频讲解
	计算,题意	算错数然后开始乱猜	nan

二分查找的递归写法

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710120348.png)

解析

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710120245.png)

总结

题型	错因	教训	视频讲解
	None		nan

动态查找在顺序表上的实现

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710120403.png)

解析

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710120440.png)

总结

题型	错因	教训	视频讲解
	None		nan

下列关于m阶B树的说法中，错误的是()。

A．根结点至多有m棵子树

B．所有叶结点都在同一层次上

C．非叶结点至少有m/2 ( m为偶数）或(m + 1)/2 ( m为奇数）棵子树

D.根结点中的数据是有序的

解析

$\color{green}{\text{C．}}$非叶结点至少有m/2 ( m为偶数）或(m + 1)/2 ( m为奇数）棵子树

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710171707.png)

根节点$\color{green}{\text{最少}}$可以只有一个关键字，两棵子树

总结

题型	错因	教训	视频讲解
	概念不清		nan

3.以下关于m阶B树的说法中，正确的是（)。

I.每个结点至少有两棵非空子树

II.树中每个结点至多有m-1个关键字

III．所有叶结点在同一层

IV．插入一个元素引起B树结点分裂后，树长高一层

A. I、II

B.II、III

C.III、IV

D. I、II、IV

解析

$\color{green}{\text{B}}$.II、III

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710172046.png)

I对于根节点，才是「至少有两棵非空子树」，非根的内部节点至少有$\lceil m/2 \rceil$棵子树

总结

题型	错因	教训	视频讲解
	None		nan

7．具有n个关键字的m阶B树，应有（)个叶结点。

A. n+ 1

B. n -1

C. mn

D. nm/2

解析

$\color{green}{\text{A}}$. n+ 1

B树的叶结点对应查找失败的情况，对有$n$个关键字的查找集合进行查找，失败可能性有$n+1$种。

总结

题型	错因	教训	视频讲解
	性质不清		nan

8．高度为5的3阶B树至少有（）个结点，至多有（)个结点。

A.32

B.31

c.120

D.121

解析

B、D

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710173140.png)

在B树中$\color{red}{\text{节点}}$相当于$\color{red}{\text{数组}}$，而不是关键字(数组中每一个单元格)！

总结

题型	错因	教训	视频讲解
	None		nan

含有n个非叶结点的m阶B树中至少包含()个关键字。

解析

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710173601.png)

在B树中$\color{red}{\text{节点}}$相当于$\color{red}{\text{数组}}$，而不是关键字(数组中每一个单元格)！

总结

题型	错因	教训	视频讲解
	概念不清		nan

已知一棵5阶B树中共有53个关键字，则树的最大高度为()，最小高度为（)。

A. 2

B.3

C.4

D. 5

解析

C，B

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710174959.png)

这个公式中，高度$\color{red}{\text{不}}$含叶子节点(推导)
严书中只提到了深度，是包含叶子节点的
对比树的最小高度：树的最小高度会有分母奇奇怪怪的成分，由于B树每个节点是一个数组的性质下面就没有奇奇怪怪的成分了
最大高度：推导过程过于繁琐，这里直接给出记忆方法好了：底可以理解为分支数，除以二理解为，根节点分化出了两个分支，加1理解为加上根节点

总结

题型	错因	教训	视频讲解
	计算	不能将定义和性质好好运用在计算中	nan

下列关于B树和B+树的叙述中，不正确的是()。

A．B树和B+树都能有效地支持顺序查找

B.B树和B+树都能有效地支持随机查找

C．B树和B+树都是平衡的多叉树

D.B树和B+树都可以用于文件索引结构

解析

$\color{red}{\text{A}}$．B树和B+树都能有效地支持顺序查找

顺序查找：数组和链表支持
$\color{red}{\text{随机查找的定义是什么}}$，好像还没有遇到过？

由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找。

总结

题型	错因	教训	视频讲解
	概念不清		nan

【2017 统考真题】下列应用中，适合使用B+树的是（)。

A．编译器中的词法分析

B.关系数据库系统中的索引

C．网络中的路由表快速查找

D.操作系统的磁盘空闲块管理

解析

$\color{green}{\text{B.}}$关系数据库系统中的索引

B+树是应文件系统所需而产生的B树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者的磁盘读写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。所以选项B正确。

总结

题型	错因	教训	视频讲解
	性质不清		nan

17.【2018统考真题】高度为5的3阶B树含有的关键字个数至少是()。

A. 15

B.31

C.62

D.242

解析

$\color{green}{\text{B.}}$31

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710182822.png)

总结

题型	错因	教训	视频讲解
	计算		nan

18.【2020统考真题】依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根结点中包含的关键字是()。

A. 8

B. 6，9

C. 8，13

D. 9，12

解析

$\color{red}{\text{B}}$. 6，9

Details

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710183034.png)

红色那一步分裂的时候，忘记拆分成两个了

总结

题型	错因	教训	视频讲解
	知识结构不清		nan

B树与文件索引

利用B树做文件索引时，若假设磁盘页块的大小是4000B（实际应是2的次幂，此处是为了计算方便)，指示磁盘地址的指针需要5B。现有20000000个记录构成的文件，每个记录为200B，其中包括关键字5B。

试问在这个采用B树作索引的文件中，B树的阶数应为多少?假定文件数据部分未按关键字有序排列，则索引部分需要占用多少磁盘页块?

解析

图片详情

复习完操作系统，重新来看

总结

题型	错因	教训	视频讲解
	知识结构不清		nan

散列查找一般适用于(）的情况下的查找。

A.查找表为链表

B.查找表为有序表

C．关键字集合比地址集合大得多

D.关键字集合与地址集合之间存在对应关系

解析

2.$\color{green}{\text{D}}$

关键字集合与地址集合之间存在对应关系时，通过散列函数表示这种关系。这样，查找以计算散列函数而非比较的方式进行查找。

注意一下概念

总结

题型	错因	教训	视频讲解
	None		nan

下列关于散列表的说法中，正确的是()。

I．若散列表的填装因子α<1，则可避免碰撞的产生

II.散列查找中不需要任何关键字的比较

III.散列表在查找成功时平均查找长度与表长有关

IV.若在散列表中删除-一个元素，不能简单地将该元素删除

A.I和IV

B.II和III

C.III

D.IV

解析

$\color{green}{\text{D}}$.IV

散冲突（碰撞）是不可避免的，与装填因子无关，因此需要设计处理冲突的方法，Ⅰ错误。散列查找的思想是计算出散列地址来进行查找，然后比较关键字以确定是否查找成功，II错误列查找成功的平均查找长度与装填因子有关，与表长无关，Ⅲ错误。在开放定址的情形下，不能随便删除散列表中的某个元素，否则可能会导致搜索路径被中断（因此通常的做法是在要删除的地方做删除标记，而不是直接删除)，Ⅳ正确。

注意一下概念

总结

题型	错因	教训	视频讲解
	None		nan

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

A.同义词之间发生冲突

B.非同义词之间发生冲突

C．同义词之间或非同义词之间发生冲突

D.散列表“溢出”

解析

$\color{green}{\text{C}}$．同义词之间或非同义词之间发生冲突

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

举一个简单的例子，比如除留余数法的线性探查就很容易出现非同义词之间的冲突「1，1，2」，1，2是非同义词但是发生了冲突

总结

题型	错因	教训	视频讲解
	概念不清		nan

下列关于散列冲突处理方法的说法中，正确的有()。

I．采用再散列法处理冲突时不易产生聚集

II．采用线性探测法处理冲突时，所有同义词在散列表中一定相邻

III采用链地址法处理冲突时，若限定在链首插入，则插入任一个元素的时间是相同的

IV．采用链地址法处理冲突易引起聚集现象

A.I和III

B.I、II和III

C.IⅢ和IV

D.Ⅰ和IV

解析

$\color{green}{\text{A}}$.I和III

图片详情

再散列法跳跃式的处理冲突，减少了发生聚集的可能

总结

题型	错因	教训	视频讲解
	None		nan

已知ASL和表项数，线性探查次数，求哈希表总长度

图片详情

解析

图片详情

一种比较有意思的题型

总结

题型	错因	教训	视频讲解
	None		nan

散列表的平均查找长度

图片详情

解析

图片详情

如果全是同义词那么是$O(n)$

总结

题型	错因	教训	视频讲解
	性质不清		nan

2018统考真题-散列表表-ASL

图片详情

解析

图片详情

严的教材包括这道真题都表示，hash之后还需要只是比较一次，才能确定是否找到

总结

题型	错因	教训	视频讲解
			nan

2019统考真题-散列表表-ASL

图片详情

解析

图片详情

答案是不是错了，首先20应该是溢出了的，不会出现在hash表中，其次，不是线性探测，是线性探测再散列解决冲突，答案上是直接用线性探测的解法解了
散列7次回到原位，所以ASL要么是6要么是7

总结

题型	错因	教训	视频讲解
			nan