凑数
凑数
凑数
凑数
ch1.绪论
ch2.线性表
ch3.栈和队列
中缀转后缀
解析
$\color{yellow}{\text{问题:为什么和课本的优先级不一样}}$
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| nan |
ch4.串
ch5.树和二叉树
求解完全二叉树的叶子节点的个数
- 结论1是怎么来的？
求解二叉树无右孩子的节点的个数
- ？？？按题目的意思为什么不是C
中序遍历和先序遍历
后序遍历的前后次序
解析
题型：性质题
错因: 因素考虑完全
路径与遍历顺序的关系
解析
我感觉错误的解释
知乎讨论：结论-重点在于非递归也能找到，所以是后序
题型: 超越理解范围
错因: 超越理解范围
叶子结点的性质
解析
题型: 性质题
错因: None
已知前序，后序序列，求二叉树的种类
解析
题型: 性质题
前序和后序序列相反的二叉树的性质
错因: Null
前序，后序序列相反的二叉树的性质
解析
题型: 性质题
错因: None
前序，中序，后序序列互求例题
解析
题型: 纯知识点运用题
错因: None
$\bigstar$ n，l，r归纳的基本应用
解析
题型: 性质题
错因: 数据乱码
线索二叉树的结构
解析
题型: 概念题
错因: 概念不清
线索化之后空域的个数
解析
题型: 性质题
错因: 性质不清
一开始直接以为是所有的链域都用掉了，但其实并不是这样。
越过上面的思维误区之后，算出来是1个。
但其实是没有算进去根节点。
二叉树的遍历与栈
解析
题型: 超越理解范围
错因: 超越理解范围
中序线索化
解析
题型: 概念题
错因: None
$\bigstar$ 二叉树的种类+栈方法解决
解析
题型: 综合运用题,超越理解范围
错因: 因素考虑完全
- 标准答案的解题方法有点花？没怎么看懂
- 直接枚举也能出来
先序后序正好相反
解析
题型: 性质题
错因: 性质不清
由森林转换的二叉树，右指针为空的结点个数
设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（)个。
A. n-1
B.n
C. n+1
D. n+2
解析
根据森林与二叉树转换规则“左孩子右兄弟”。二叉树B中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，故树B中右指针域为空的结点有n+1个。
题型: 概念题,性质题
错因: 超越理解范围
由森林转换的二叉树，右指针为空的结点个数2
【2011统考真题】已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（ )。
A. 115
B. 116
c. 1895
D.1896
解析
树转换为二叉树时，树的每个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应二叉树中无右孩子的结点个数=分支结点数＋1 = 2011 -116+1= 1896。
题型: 概念题,性质题
错因: 超越理解范围
按（)遍历二叉排序树得到的序列是一个有序序列。
A．先序
B.中序
C．后序
D.层次
解析
$\color{green}{\text{B}}$.中序
关于这点的理解，可以用函数栈来理解,最先出栈一定是最左边的孩子，最小的节点(多debug几次看几次函数栈就能感受到了,pta中关于二叉树的题目)
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|含有20个结点的平衡二叉树的最大深度为（)。
A.4
B.5
C. 6
D.7
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|ch6.图
图中有关路径的定义是
A.由顶点和相邻顶点序偶构成的边所形成的序列
B.由不同顶点所形成的序列
C.由不同边所形成的序列
D.上述定义都不是
解析
$\color{red}{\text{A.}}$由顶点和相邻顶点序偶构成的边所形成的序列
注意$\color{red}{\text{图}}$中$\color{green}{\text{路径}}$是$\color{red}{\text{顶点序列}}$，不是边序列
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 定义题 | None | nan |
一个有n个顶点和n条边的无向图一定是
A.连通的
B.不连通的
C．无环的
D.有环的
解析
$\color{red}{\text{D.有环的}}$
若一个无向图有n个顶点和n-1条边，可以使它连通但没有环(即生成树)，但再加一条边，在不考虑重边的情形下，则必然会构成环。
关于A选项，一个环+一个单独节点，不连通
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | 举例子永远的神 | nan |
若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是
A.强连通图
B.连通图
C．有回路
D.一棵树
解析
$\color{red}{\text{B.连通图}}$
$\color{red}{\text{强连通图是有向图}}$，与题意矛盾，选项A错误;
对无向连通图做一次深度优先搜索，可以访问到该连通图的所有顶点，选项B正确;
有回路的无向图不一定是连通图，因为回路不一定包含图的所有结点，选项C错误;
连通图可能是$\color{red}{\text{树}}$，也可能存在$\color{red}{\text{环}}$，选项D错误。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| None | 性质题 | 强连通图是对于有向图而言的 | nan |
$\color{red}{\text{【2011统考真题】下列关于图的叙述中，正确的是（)。}}$
I回路是简单路径
II．存储稀疏图，用邻接矩阵比邻接表更省空间
III．若有向图中存在拓扑序列，则该图不存在回路
A.仅II
B.仅I、II
C．仅I
D.仅I、III
解析
$\color{red}{\text{C．仅I}}$
回路对应于路径，简单回路对应于简单路径，故Ⅰ错误;
稀疏图是边比较少的情况，此时用邻接矩阵必将浪费大量的空间，应选用邻接表，故Ⅱ错误。
存在回路的图不存在拓扑序列，Ⅲ正确。
II和Ⅲ中所涉知识点请参阅后面的内容。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
以下关于图的叙述中，正确的是（)。
A.图与树的区别在于图的边数大于等于顶点数
B．假设有图G={V,{E}}，顶点集$V’ \in V$,$E’ \in E$，则$V’$和{$E’$}构成G的子图
C.无向图的连通分量是指无向图中的极大连通子图
D.图的遍历就是从图中某一顶点出发访遍图中其余顶点
解析
$\color{red}{\text{C.}}$无向图的连通分量是指无向图中的极大连通子图
图与树的区别是$\color{red}{\text{逻辑上}}$的区别，而不是边数的区别，图的边数也可能小于树的边数，故选项A错;
若E中的边对应的顶点不是V的元素，V和{E}无法构成图，故选项B错;
无向图的$\color{red}{\text{极大连通子图}}$称为$\color{red}{\text{连通分量}}$，选项C正确;
图的遍历要求每个结点只能被访问一次，且若图$\color{red}{\text{非连通}}$，则从某一顶点出发$\color{red}{\text{无法}}$访问到其他全部顶点，选项D的说法不准确。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | 性质不清 | 考虑非连通的情况 | nan |
【2009统考真题】下列关于无向连通图特性的叙述中，正确的是（)。
I所有顶点的度之和为偶数
II.边数大于顶点个数减1
III.至少有一个顶点的度为1
A．只有Ⅰ
B.只有Ⅱ
C.I和II
D.Ⅰ和III
解析
$\color{red}{\text{A．}}$只有Ⅰ
无向连通图对应的$\color{red}{\text{生成树}}$也是无向连通图，但此时边数等于顶点数$\color{red}{\text{减1}}$，故Ⅱ错误。
考虑一个无向连通图的顶点恰好构成一个$\color{red}{\text{回路}}$的情况，此时每个顶点的度都是2，故Ⅲ错误。
在无向图中，所有顶点的度之和为边数的2倍，故Ⅰ正确。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
【2010统考真题】若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（)。
A. 6
B.15
C. 16
D.21
解析
$\color{red}{\text{C. 16}}$
题干要求在“$\color{red}{\text{任何情况}}$”下都是连通的，考虑最极端的情形，即图G的6个顶点构成一个完全无向图，再加上一条边后，第7个顶点必然与此完全无向图构成一个连通图，所以最少边数=6×5/2+1=16。若边数n小于等于15，可以使这n条边仅连接图G中的某6个顶点，从而导致第7个顶点无法与这6个顶点构成连通图（不满足“任何情况”)。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 计算题 | 因素考虑完全 | 注意又要任何情况又要连通 | nan |
以下关于图的叙述中，正确的是（）。
A．强连通有向图的任何顶点到其他所有顶点都有弧
B．图的任意顶点的入度等于出度
C．有向完全图一定是强连通有向图
D.有向图的边集的子集和顶点集的子集可构成原有向图的子图
解析
$\color{red}{\text{C．}}$有向完全图一定是强连通有向图
强连通有向图的任何顶点到其他所有顶点都有$\color{red}{\text{路径}}$，但未必有$\color{red}{\text{弧}}$;
无向图任意顶点的入度等于出度，但有向图未必满足;
若边集中的某条边对应的某个顶点不在对应的顶点集中，则有向图的边集的子集和顶点集的子集无法构成子图。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | nan |
9.【2013统考真题】设图的邻接矩阵A如下所示，各顶点的度依次是（ )。
A. 1,2,1,2
B.2,2,1,1
C.3,4,2,3
D.4,4,2,2
解析
$\color{red}{\text{C}}$.3,4,2,3
邻接矩阵A为$\color{red}{\text{非对称矩阵}}$，说明图是有向图，度为入度与出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列(对应入度）的非零元素之和。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 定义题 | None | nan |
10.一个有28条边的非连通无向图至少有（)个顶点。
A.7
B.8
C.9
D.10
解析
此题的解题思路和第7题的恰好相反。考查至少有多少个顶点的情形，我们考虑该非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在28=n(n-1)/2=8×7/2条边的完全无向图中，总共有8个顶点，再加上1个不连通的顶点，共9个顶点。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | Null | nan |
11.对于一个有n个顶点的图:若是连通无向图，其边的个数至少为();若是强连通有向图，其边的个数至少为().
A. n -1,n
B. n -1, n(n -1)
C. n, n
D. n, n(n - 1)
解析
对于连通无向图，边最少即构成一棵树的情形;对于强连通有向图，边最少即构成一个有向环的情形。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | 因素考虑完全 | 强连通有向图最少是环 | nan |
12．无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有（)个顶点。
A. 11
B.12
C.15
D.16
解析
$\color{red}{\text{D.}}$16
由于在具有n个顶点、e条边的无向图中，有艺TD(v,)=2e，故可求得度为2的顶点数为7，从而最多有16个顶点。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
13．在有n个顶点的有向图中，每个顶点的度最大可达()。
A. n
B. n -1
C. 2n
D. 2n-2
解析
$\color{red}{\text{D.}}$ 2n-2
在有向图中，顶点的度等于入度与出度之和。n个顶点的有向图中，任意一个顶点最多还可以与其他n-1个顶点有一对指向相反的边相连。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | 因素考虑完全 | 没看清楚题目说的是有向图 | nan |
14．具有6个顶点的无向图，当有（）条边时能确保是一个连通图。
A. 8
B.9
C.10
D. 11
解析
解题思路与第7题类似。5个顶点构成一个完全无向图，需要10条边;再加上1条边后，能保证第6个顶点必然与此完全无向图构成一个连通图，故共需11条边。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
15.【2017统考真题】已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是()。
A. 10
B.11
C.13
D. 15
解析
$\color{red}{\text{B}}$ 11
无向图边数的2倍等于各顶点度数的总和。由于其他顶点的度均小于3，设它们的度都为⒉，设它们的数量是x，列出这方程4×x3+3x4+2x = 16x2，解得x=4。4＋4+3= 11，选项B正确。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 计算 | None | nan |
16.设有无向图G=(V,E)和G’=(V,E’)，若G’是G的生成树，则下列不正确的是()。
I.G’为G的连通分量
II.G’为G的无环子图
III．G’为G的极小连通子图且V’=V
A. I、II
B．只有III
C. II、II
D.只有Ⅰ
解析
$\color{green}{\text{D.}}$ 只有Ⅰ
一个连通图的生成树是一个极小连通子图，显然它是无环的，故II、III 正确。极大连通子图称为连通分量，G’连通但非连通分量。这里再补充一下“$\color{red}{\text{极大连通子图}}$”:如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | 概念不清 | 无向图的连通分量是极大连通子图，点边越多 | nan |
17．若具有n个顶点的图是一个环，则它有（）棵生成树。
A. n2
B. n
C. n-1
D. 1
解析
因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树,所以共有n种情况。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
18．若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有（)棵树。
A. n
B. e
C. n -e
D. 1
解析
n个结点的树有n-1条边，假设森林中有x棵树，将每棵树的根连到一个添加的结点，则成为一棵树，结点数是n+1，边数是e+x，从而可知x =n- e。
另解:设森林中有x棵树，则再用x-1条边就能把所有的树连接成一棵树，此时，边数+1=顶点数，即e +(x - 1)+1=n，故x =n-e。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
图G是一个非连通无向图，共有28条边，该图至少有多少个顶点?
解析
由于图G是一个非连通无向图，在边数固定时，顶点数最少的情况是该图由两个连通子图构成，且其中之一只含一个顶点，另一个为完全图。其中只含一个顶点的子图没有边，另一个完全图的边数为n(n-1)/2 = 28，得n=8。所以该图至少有1+8=9个顶点。
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | None | nan |
如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上?
解析
按各顶点的出度进行排序。n 个顶点的有向图，其顶点的最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即只要存在弧$$，就不管顶点j的出度是否大于顶点i的出度，都把i编号在顶点j的编号之前，因为只有i≤j，弧$$对应的1才能出现在邻接矩阵的上三角。
通过后面小节的学习，会发现采用拓扑排序并依次编号是一种更为简便的方法。
$\color{red}{\text{?????没看懂}}$
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 性质题 | 性质不清 | nan |
破圈法
下面是一种称为“破圈法”的求解最小生成树的方法:
所谓“破圈法”，是指“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
试判断这种方法是否正确。若正确，说明理由;若不正确，举出反例（注:圈就是回路)。
解析
由于经过“破圈法”之后，最终没有回路，故一定可以构造出一棵生成树。
这里的前提是，没有回路就一定是最小生成树
下面证明这棵生成树是最小生成树。记“破圈法”生成的树为T，假设T不是最小生成树，则必然存在最小生成树T，使得它与T的公共边尽可能地多，则将T与T取并集，得到一个图，此图中必然存在回路，由于“破圈法”的定义就是从回路中去除权最大的边，此时生成的T的权必然是最小的，这与原假设T不是最小生成树矛盾，从而T是最小生成树。下图说明了“破圈法”的过程:
因为点是一样的，多了一条边，必然有环，而破圈法已经去掉了最大权值的边？：$\color{red}{\text{还是说不通}}$
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| nan |
c
ch7.查找
顺序查找的平均查找长度
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
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| None | nan |
k分查找的时间复杂度
3．类比二分查找算法，设计k分查找算法(k为大于2的整数）如下:首先检查n/k处(n为查找表的长度）的元素是否等于要搜索的值，然后检查2n/k处的元素……这样，或者找到要查找的元素，或者把集合缩小到原来的1/k，若未找到要查找的元素，则继续在得到的集合上进行k 分查找;如此进行，直到找到要查找的元素或查找失败。试求查找成功和查找失败的时间复杂度。
解析
- 注意这题只要求计算时间复杂度，而不是$ASL$
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| None | nan |
分块查找变种
Details
解析
Details
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 题意 | nan |
2013真题:算法的改进
Details
解析
Details
- 换了一种折半查找的方法，按照长度来二叉查找，明明可以达到1.8
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 计算,题意 | 算错数然后开始乱猜 | nan |
二分查找的递归写法
Details
解析
Details
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| None | nan |
动态查找在顺序表上的实现
Details
解析
Details
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 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
根节点$\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
- 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
- 在B树中$\color{red}{\text{节点}}$相当于$\color{red}{\text{数组}}$，而不是关键字(数组中每一个单元格)！
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| None | nan |
含有n个非叶结点的m阶B树中至少包含()个关键字。
解析
D
Details
- 在B树中$\color{red}{\text{节点}}$相当于$\color{red}{\text{数组}}$，而不是关键字(数组中每一个单元格)！
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 概念不清 | nan |
已知一棵5阶B树中共有53个关键字，则树的最大高度为()，最小高度为（)。
A. 2
B.3
C.4
D. 5
解析
C，B
Details
- 这个公式中，高度$\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
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 计算 | 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
- 红色那一步分裂的时候，忘记拆分成两个了
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| 知识结构不清 | 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 |
ch8.排序
pp.311/pp.313
1．在以下排序算法中，每次从未排序的记录中选取最小关键字的记录，加入已排序记录的末尾,该排序方法是()。
A.简单选择排序
B.冒泡排序
C．堆排序
D、直接插入排序
解析
$\color{green}{\text{A}}$.简单选择排序
总结
| 题型 | 错因 | 教训 | 视频讲解 |
|---|---|---|---|
| nan |
2.简单选择排序算法的比较次数和移动次数分别为（)。
A. O(n),O($log_2n$)
B. O($log_2n$)，O($n^2$)
C. O($n^2$)，O(n)
D. O($nlog_2n$)，O(n)
解析
$\color{green}{\text{C}}$. O($n^2$)，O(n)
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|多属性排序算法的设计
图片详情
解析
图片详情
题目没有限定两个属性都相同的情况下，节点的相对顺序，只是限定了$k_1$相同的情况下$k_2$按小大排序，所以先按照$k_2$排序之后，$k_1$再排序时必须选定稳定的算法,就能满足题目的要求
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|构建堆时插入和删除的时间复杂度
图片详情
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|建堆的时间复杂度
图片详情
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|比较次数与序列初始状态无关的是
图片详情
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|图片详情
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|图片详情
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|图片详情
解析
图片详情
题目tag详情
###### 总结 |题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|1．以下排序方法中，()在一趟结束后不一定能选出一个元素放在其最终位置上。
A.简单选择排序
B．冒泡排序
C.归并排序
D.堆排序
解析
$\color{green}{\text{C}}$.归并排序
图片详情
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|算法的空间复杂度
图片详情
解析
图片详情
$\color{red}{\text{Q}}$: 快排的时间复杂度的理解
$\color{red}{\text{Q}}$: 基于递归的时间复杂度和空间复杂度
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|【2016统考真题】对10TB的数据文件进行排序，应使用的方法是()。
A.希尔排序
B.堆排序
C．快速排序
D.归并排序
解析
$\color{green}{\text{D}}$.归并排序
外部排序指待排序文件较大，内存一次性放不下，需存放在外部介质中。外部排序通常采用归并排序法。选项A、B、C都是内部排序的方法。
归并算法最后不是还要全部读到内存里面？
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|内部排序算法中归并排序和选择插入排序的比较
图片详情
解析
图片详情
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|外部排序需要的总的比较次数
图片详情
解析
图片详情
外部排序的特性：有多少个归并段内存中就有多少个元素需要比较
$\color{red}{\text{Q}}$: 败者树的构建
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|外部排序的输入输出缓冲区的作用
图片详情
解析
题目理解的工作区
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|外部排序实现并行处理的条件
图片详情
解析
图片详情
题目理解的并行
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|构建带权路径最小的三叉树
图片详情
解析
图片详情
- 由哈夫曼树推导三叉树节点数量之间的关系：$3n_3 + 1 = n_0 + n_3$
- 然后又已知$n_0$的数量就是题目描述的叶子节点
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|【2019统考真题】设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是()。
A. 1
B.2
C. 3
D.4
解析
图片详情
- 同上题，不过$\color{red}{\text{Q}}$：为什么需要补了结点之后才是最优的
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|多路平衡归并排序是外部排序的主要方法，试问多路平衡归并排序包括哪两个相对独立的阶段?每个阶段完成何种工作?
解析
多路平衡归并排序由两个相对独立的阶段组成:生成初始归并段阶段和多趟归并排序阶段。生成初始归并段阶段根据内存工作区的大小，将有m个记录的磁盘文件分批输入内存，采用有效的内部排序方法分别进行排序，生成若干有序的子文件，即初始归并段。多趟归并排序阶段采用多路归并方法将这些归并段逐趟归并，最后归并成一个有序文件。
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|打开文件数和最大归并段数之间的关系
图片详情
解析
图片详情
注意输出缓冲也需要打开一个文件
$\color{red}{\text{Q}}$: 打开关闭文件需不需要内核态之间的切换
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|磁盘块大小与初始归并段之间的关系
图片详情
解析
图片详情
$\color{red}{\text{Q}}$：为什么？
图片详情
总结
题目tag详情
|题型|错因|教训|视频讲解| |---|---|---|---| ||||nan|败者树的构建和执行过程
图片详情
解析
图片详情
