第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
天勤考研高分笔记 个人笔记.pdf
一、绪论
三、栈 队列和数组
数据的物理结构：顺序、链接、索引、散列
链式存储结点内的存储单元地址：一定连续
算法五特性：有穷、确定、可行、输入、输出
C/C++语法注意点：
1.指针的引用 int *&x
2.malloc()函数分配的内存在堆上，用完要 free
3.二位数组 int a[4][5] 有：四行（0123）五列（01234）
栈允许插入删除的一端为栈顶。特点 FILO 有记忆功能。队列是队尾（rear）
插入，队头（front）删除，特点 FIFO。
卡特兰数：n 个不同元素进栈，出栈序列的个数
1
n
C
21
n
n
时间复杂度：
（顺序栈）
（链栈）
4.遍历字符数组 (char f[])的方法：char *p=f;while(*p!=’\0’){p++}
5.switch(a){ case 1: break; case 2:break; }
6.字符串定义 char str[] = “abcdef”; //串长 6 数组长 7 ‘\0’结束标
算法的复杂度
7.int *a[max]指针数组(元素是指针)和 int (*a)[max]指向数组的指针
算法中最基本运算的频度(重复执行次数 f(n))的数量级(O)，记为问题
规模 n 的函数：T(n) = O(f(n))
时间复杂度依赖于：问题规模 n、输入数据的初始状态
O(1)next==NULL 时链表空
2.双链表 （head 指针 头结点 开始结点 终端结点） head==NULL /
head->next==NULL 时链表空
1.几种重要的栈
（1）顺序栈
数组下标从 0 开始 （*与顺序表区别）元素最大个数 maxsize
栈空：st.top= -1 （top==0 数组也能存数据）
栈满：st.top =maxsize - 1 (因为数组从 0 开始)
进栈：st.top++; st.data[st.top]= x; 或 st.data[++st.top]=x;
出栈：x=st.data[st.top]; --(st.top);或 x=st.data[st.top--];
常用简单写法：
int stack[maxsize];int top=-1; //初始化
stack[++top]=a; x=stack[top--];//进栈 出栈
（2）链栈
栈空： lst->next==NULL 内存满时栈满
进栈：（p 元素）：p->next=lst->next; lst->next=p; //即头插
出栈：p=lst->next;lst->next=p->next;free(p); //即单链表删除
初始化：lst=(LNode*)malloc(sizeof(LNode)); lst->next=NULL;
（3）共享栈
栈空：top0==-1（左空） top1==maxsize（右空）
栈满：top1-top0=1
2.几种重要的队列
（1）循环顺序队（顺序队的改进）
循环执行语句 front=(front+1)%8 (数组长度 maxsize=8)
进队：qu.rear=(qu.rear+1)%8; qu.data[qu.rear]=x;
出队：qu.front=(qu.front+1)%8; x= qu.data[qu.front];
（*无论进队、出队，都是先移动指针）
初始化：qu.front=qu.rear=0
3、循环单链表 / 循环双链表
4、静态链表
(2) 链队
队空：lqu->rear==NULL 或 lqu->front==NULL
进队：lqu->rear->next=p; lqu->rear=p (拼接元素移指针)
出队：p=lqu->front;lqu->front=p->next; x=p->data ;free(p);
初始化：LiQueue lqu = (LiQueue*)malloc(sizeof(LiQueue));
lqu->front=lqu->rear=NULL;
4.十字链表法（链式）：特点①含头结点、普通结点 ②每行一链带头，
*链队为空（lqu->rear==NULL）进队还要赋新结点给 front
*链队仅有一元素（lqu->front==lqu->rear）出队还要置 rear 为空
每列一链带头 ③结点 5 分量（行、列、值、下指针、右指针）。
(3) 双端队
六、树与二叉树
1.树的定义是递归的（树的定义中用到树），结点为 0 的树为空树。结点拥
有的分支个数为结点的度。叶结点：即终端结点，即度为零的结点。分支
结点即非终端结点即分支不为 0 的结点。根为树的第一层，树的高度为结
点的最大层次。结点的子树有序不可换为有序树，可换则为无序树。丰满
树（理想平衡树）即除最底层外其他层皆满。
3.栈在表达式求值中的应用
*中缀转前缀后缀结果不唯一，前缀后缀式都有唯一的运算次序，后缀式运
*平衡二叉树：任意结点左右子树高度差的绝对值不超过 1。
2.树的双亲存储结构（顺序树） int tree[maxsize] 根结点的双亲为-1
算符在操作数后，且已考虑了优先级，无括号。
4.特殊矩阵的压缩
四、串
存储从 0 开始。Str.length 串长 =maxsize = 数组长-1。分配内存勿忘+1
串赋值需“逐元素赋值”不能直接=。
两字符直接相减，得到的是 ASCII 码之差。
串的子串数目（含空串）为：n(n+1)/2+1
链串：只需把链表的结点的 data 数据类型改为 char
串的基本操作：
串赋值 strassign(str,”abcdef”);
串比较 int strcompare(str s1,str s2)
串连接 int concat(str &s,str s1,str s2)
求子串 int substring(str &substr,str s,int pos,int len)
串的模式匹配：
1.简单模式匹配 比较次数=模式串*主串
2.KMP 算法。
关键：S 串（模式串不匹配位置之前的子串）头 K 尾 K 可匹配
3.二叉树
二叉树结点度∈[0,2]，均有序树，五大形态：空、根、仅左、仅右、皆有。
完全二叉树由满二叉树由右至左由下至上挨个删除结点所得到。
二叉树性质
0.总分支数=总结点数-1 （所有二叉树）
1.叶结点=双分支结点+1 （非空二叉树）
2.空指针数=总结点数+1
3.第 i 层最多有 2^(i-1)个结点（满二叉树构成首项 1 公比 2 的等比数列）
高度 k 的二叉树最多 2^k-1 个结点
4.完全二叉树从 1~n 编号，则 ①双亲为
2/i
②若 2i≤n a 的左孩为
2i 若 2i≥n 无左孩 ③若 2i+1≤n 右孩 2i+1 若 2i+1≥n 无右孩
5.完全二叉树高度
log
N
1
2
log
or）（
2
N
1
则得候选串，依此可预处理模式串。候选串要选长的（失败后不错过
后续的）。next[j]表示模式串 j 处不匹配时主串 i 应与模式串 next[j]
6.卡特兰数：n 个结点，构成
种不同的二叉树。
1
n
C
21
n
n
继续比较。
*7.（重要思想）
*候选串的长度==next[j]（即候选串为 S 串的 0~k-1 字串、n-1~n-k
子串，则 next[j]=k）。滑动长度为 S 串长度-候选串长度，至少节省比
较次数=候选串长度+滑动长度-1。
由next[n]求next[n+1]分两种情况：①模式串k 处与n 处匹配（0~k
与 n-k~n 匹配）则 next[n+1]=k+1=next[n]+1 ②不匹配时，利用已有的
next 数组寻找...
*KMP 算法稍做改进可在匹配成功后继续寻找（置 j 零，计数）
①根据前中、中后两对遍历序列均可唯一确定二叉树，而根据前后这
对遍历序列不能确定二叉树。
②前中后序遍历叶子结点在序列的先后都相同（从左到右）。
二叉树的存储
8.数的叶子结点数 n=1+n2+2n3+... （n3 即度 3 的结点数）
1.顺序二叉树 BTree[] 适合完全二叉树 ，必须从下标 1 开始存储，利
用二叉树性质求孩子
五、数组、稀疏矩阵和广义表
Amn 二维数组也称矩阵 A[m][n],其转置矩阵为 B[n][m]且 B[i][j]=B[j][i]
2.链式二叉树
矩阵转置（二重循环）、相加（二重循环相加）、相乘（三重循环，最内
4.线索二叉树（TBT:Thread-BT）
层累加）
稀疏矩阵：
1.三元组法 Trimat[maxterms]为线性表，每个 trimat 三个分量（val、i、
j）或表示为 int trimat[maxterms][3] 约定 trimat[0][3]存储原矩阵非零元素个
数、行数、列数。
2.伪地址法 A[i][j]的伪地址 n(i-1)+j 若已知伪地址 x 则 i=x/n j=x%n
3.邻接表法（链式）：每一行的非零元素串成链表，链表结点含两个
分量即值、列号。*与图的邻接表类似
思想：利用空链域添加某种遍历方式下的直接前驱或直接后继（线索）。
添加 tag，=0 孩子，=1 线索。前（中/后）序线索二叉树，线索化过程即遍
历并修改指针，遍历时设 pre 指针指向刚访问过的结点。
5.树和森林
1).孩子兄弟存储结构：“串孩子、留左枝”“左孩子、右兄弟”
②对于有向图，1 个数=总边数，第 i 行元素之和为 i 的出度，第 j 列
元素之和为 j 的入度。
有权图：1 改权值、0 改无穷。
2).森林与二叉树的转换：此时，根结点一定没有右孩子，可将森林中
第二棵树作为右子树，第三棵树转二叉树后当第二棵树的右子树...反之可将
一棵二叉树还原为森林。
3).树与森林的遍历：先根遍历（对应二叉树的先序遍历）、后根遍历
（2）邻接表（图的链式存储结构）
（对应二叉树的中序遍历）。可将树转二叉树再用二叉树方法遍历，如先
每个顶点 i 建立一个单链表，链表首结点为表头存放结点顶点信息，
根遍历序列=（转完后）先序遍历二叉树。森林的遍历亦同（先序、中序）。
6.赫夫曼树（最优二叉树）特点：WPL 最小。
其余结点存放有关边的信息。邻接表是由单链表表头形成的顶点表和单链
表其余结点形成的边表组成。
构建方法：两小结合成二叉树。同一组结点构成的赫夫曼树可能不唯一但
*图的邻接表对顶点的邻接点进行了次序的规定（不同于画图）即邻
wpl 相同。
赫夫曼树特点：①权值大离根近②没有度为 1 的结点（正则二叉树）
带权路径长度：从结点到根的路径长度 * 结点权值。
树的带权路径长度（WPL）：所有叶子结点的带权路径长度之和。
前缀编码：任一字符编码都不是另一字符编码的前缀。
赫夫曼编码：长度最短的前缀编码
接表存储的图其 DFS 序列是唯一的（一般的图 DFS 序列不唯一）
（3）邻接多重表
3.图的遍历
深度优先遍历（DFS）。类似于二叉树的先序遍历。广度优先（BFS）。
4.最小生成树
（1）Prim 算法
任取一点当成树，找树相接边中最小权的，将其与结点并入树，以此类推
得到最小生成树。构建时需要 vset[]和 lowcost[]，vset[i]=1 表示顶点 i 已并
入生成树，lowcost[]存当前生成树到剩余各顶点最短边的权值。
Prim 算法的时间复杂度为 O(n2)，与顶点有关与边数无关，适合稠密图。
（2）Kruskal 算法
图中边按权由小到大排序，从小到大扫描是否为候选边，即是否该边的并
七、图
1.基本概念
由顶点和边构成，边为顶点的有序偶对，两顶点间存在边则说明两顶
点具有相邻接关系。
有向图：边均有方向。无向图：边均无方向。边记（vi,vj）等价于有
入会产生回路（通过并查集来判断），如不产生回路则并入生成树。
向图中存在和两边
克鲁斯卡尔算法主要时间花费在sort(road[],g.e) 规模由e 决定因此适合稀疏
顶点的度：相关边的条数，指向 v 的为入度，从 v 出发的为出度。
有向完全图：n 个顶点的有向图最多具有 n(n-1)个边，此时为有向完
图。
*所有边的权都不同的图或有相等的边但构建最小生成树的过程中都被并
全图。
入的图，其最小生成树是唯一的
无向完全图：n 个顶点的无向完全图最多具有 n(n-1)/2 个边，为~。
基本概念：路径、路径长度、简单路径（顶点与边不重复出现的路径）、
5.最短路径
（3）Dijkstra 算法
回路（首尾顶点相同）。
三个辅助数组。算法过程：①判断并随后
无向图中：连通、连通图（任意两顶点都连通）、连通分量（非连通
图中的极大连通子图）。
有向图中：连通、强连通图（每对 vi 到 vj，vj 到 vi 都连通）、强连通
分量（非强连通图的极大强连通子图）。
*顶点数大于 1 的强连通图一定有环。
权：边附加的相关的数。网：带权图。
2.图的存储
（1）邻接矩阵（图的顺序存储结构）
N 个顶点的图其邻接矩阵是有如下关系的 N 阶方阵:A[i][j]=1 则 ij 临接
=0 则 ij 不临接。由邻接矩阵的行列数可知顶点数。
①对于无向图，邻接矩阵是对称的，1 个数=2*总边数，第 i 行或第 i
列元素之和为顶点的度。
并之（通过 dist） ②刷新辅助数组（更新 dist 为后续判断提供依据，疑似
待更新点为新进点的出度，path 保存“最优路径”）
dist[vi] 存 v0 到每个终点 vi 的最短长度，每一步从中判断下一步并谁。
path[vi] v0 到 vi 最短路径上 vi 的前一个顶点，
set[vi]=1 表示 vi 已并入最短路径（在 S 中），set 可避免走环路
* Path[]是一个双亲存储结构存储的树，打印可得 v0 到任何一个顶点最短路
径上所经的所有顶点。只能输出叶子到根，逆序需要栈辅助。
*Dist[]存放了 v 到其余顶点的最短路径长度。
* 随着新结点并入，发现更优路径时更新 path 和 dist
（4）弗洛伊德算法 （O（n3））
Dijkstra 算法求某点到其余顶点的最短路径，求任一对顶点的最短路径常用
Floyd 算法。算法过程需要两个矩阵，不断尝试借中间节点缩短路径，分两
步：①初始时将图的邻接矩阵赋给 A，Path 全部置-1 ②以 K∈[0，n-1]为中
间节点，若 A[I][J]>A[i][k]+A[k][j]则 A[I][J=A[i][k]+A[k][j]、path[i][j]=k。 最终
path[][]矩阵可递归求任意两点最短路径上的顶点序列。
A[][] 任意两顶点最短路径长度
Path[][] 两顶点间最短路径要经过的中间节点。
5.拓扑排序
（1）AOV 网
以顶点表示活动，边无权值，以边表示活动的先后次序且没有回路的有向
图。
（2）拓扑排序核心算法
有向无环图 G 的拓扑排序：所有顶点排成线性序列，任意一对 uv，若存在
u 到 v 的路径，则序列中一定是 u 在 v 前面。
有向图找拓扑排序序列的过程：①图中选一个无前驱的顶点输出 ②删除此
顶点和所有此顶点出发的边。重复①②直到图中不存在无前驱顶点。
两个辅助变量：栈用来记录当前图中入度为 0 的顶点，计数器 n 记录已输
出顶点的个数。
* 拓扑排序的结果可能不唯一 算法的时间复杂度为 O(n+e)
（3）AOE 网
活动在边上的网，边表活动有权值，与 AOV 网一样都是针对有向无环图。
AOE 网中，只有一个入度为 0 的点为源点，表工程开始；只有一个出度为 0
的点为汇点表工程结束。
（4）关键路径
AOE 网中从源点到汇点，最长的路径为“关键路径”。（工期最短时间为
关键路径之长）。最早发生时间 ve(k)为 ve(j)+权后结果中最大者。最晚
发生时间 vl(k)=vl(j)-权结果中最小者（思想：k 的发生一定不能推迟所
幅减小，适合记录非常多的场景。
*折半次数与比较次数都确定的（low>high 结束）与初始序列无关，
折半一次比较一次。时间复杂度最好 O(n)，最差 O(n2)，平均 O(n2) 空间复
杂度 O(1)
*掌握求解过程：未排序取一个，已排序确定 low/high 、找比较点 floor(sum/2)
比较、重置 low/high
2、3 两部为精髓，13 的低半区则 hl 都为 l 继续和 l 比继续低半区 h--，最终
落于 h 后；高半区则 hl 都为 h 则和 h 比，若高半区则 l++，落 l 前，低半区
则 h--，落 h 后。
③希尔排序（缩小增量排序）：将待排序列某按规则（增量）分成子
序列，分别对子序列进行直接插入排序。希尔排序的主要思想：每趟希尔排
序会使序列更有序，最后来一趟效率很高的直接插入排序。执行过程：按增量
x 分割子序列，子序列分别直插排序，将结果按”原位置”组合。缩小 n 再来
一趟，直至 n=1（不用分割，直接直插排序）。时间复杂度平均情况 O(nlog2n)
空间复杂度 O(1)。希尔排序是不稳定的
*增量最后一个一定取 1，增量序列需无除 1 以外的公因子（如 8421
这样的序列不能取，有公因子 2）
（2）交换类：（冒泡、快速）
有后继事件的最迟发生时间）。
①冒泡排序：算法结束条件：一趟排序中没有发生元素交换。最好情
* 汇点的最早发生时间=工程结束时间=最迟发生时间 ve=vl
手工求解关键路径：
况：待排序列有序，执行 n-1 次 时间复杂度 O(n)；最坏情况：待排序列逆
序执行 n(n-1)/2 时间复杂度 O(n2)。空间复杂度 O(1)
①拓扑排序，依次求出各顶点最早发生时间（往后推最大者），从
②快速排序：以枢轴为中心将序列分成两部分，一部分比其小一部分
ve(0)=0 开始
②逆拓扑排序，依次求出各顶点最迟发生时间 （往前推最小者），
从 vl(max)=ve(max)=28 开始
*活动的最早发生时间 e(ak) = 发出此活动的事件的最早发生时间
*活动的最迟发生时间 l(ak)= 事件的最迟发生时间减去以它为结束的
活动的持续时间
*关键活动：最早发生时间和最迟发生时间相同的活动
*剩余时间：活动的最迟发生时间-最早发生时间 （松弛度）
大（枢纽取出来，两端指针往中走，左小右大于枢纽，碰头点放枢纽），
递归的对左右部分进行快速排序。最好情况下 O(nlog2n) 待排序列越无序算
法效率越高，最坏 O(n2) 序列越有序效率越低。平均 O(nlog2n),就平均值而
言快速排序是所有算法中最好的，排序趟数和初始序列有关。空间复杂度
O(nlog2n) 递归需要栈辅助。
（3）选择类 （简单选择、堆排序）
①简单选择排序：每扫一遍找 1 最小放入有序（与无序的第一个交换）
最终没有无序。
关键活动组成关键路径，关键路径所持续时间=整个工程持续时间。
②堆排序：堆可以看成一棵完全二叉树且满足非叶结点不大于（不小
八、排序
于）左右孩。父亲大孩子小则大顶堆，反之小顶堆。算法过程：
1) 建堆，无序序列对应的完全二叉树的首个非叶结点开始
排序稳定性：待排序序列中相同的项在排序完成后相对位置有无发生变化。
从左到右、从下至上调整结点构建大顶堆。（找最大孩子和自己换，
若排序结果唯一，则排序方法稳定与否无关紧要
到下一层后重复）
1.排序算法分类
（1）插入类（直插、折半插、希尔）特点：不到最后一刻无记录达最终位置。
2) 排序，堆顶与最后一个交换，放入有序并到达最终位
3) 重新建堆（此时其他都有序，只需调整堆顶）直到树（无
①直接插入 ：从 2 开始前面排好，不断取后面往前面插。最好情况
序序列）只剩一个结点结束。
下 O(n)，最坏情况：逆序，i∈[2,n]，总执行次数 n(n-1)/2，时间复杂度 O(n2)，
空间复杂度 O(1) （只有一个 tmp）。适合基本有序的场景
堆排序时间复杂度恒为 O(nlog2n) 空间复杂度 O(1)，典型应用：从大
数据量记录中挑最小前 10 个。
*插入类排序的特点：不到最后一趟排序，无任一记录已达最终位置。
*交换类和选择类排序每一趟都有一个元素到位（冒泡、快速、简单、堆）
②折半插入：记录移动次数与直插排序一样，每次在未有序中选记录
*交换类排序，其排序趟数和初始序列有关。
插入到已有序的序列中，插入位置可用折半查找。寻找插入位置的时间大
（4）并归类：（二路归并）
①二路并归排序：序列划分成 n 个有序 1 元组，两两并归成若干有序
二元组、四元组... 最后剩两个 子序列并归。此算法需进行 log2n 趟，每趟
执行总“并归操作”均为 n 次（*根据线性表一章知：并归操作执行次数为
亲结点 floor(i/2)。败者树中包括：
a) 叶子结点：叶子结点个数（k）为待归并文件数。类型为记录型，
值为从相应有序子序列中读出的当前记录。
两待并归子序列元素之和 ，每趟两序列元素和增多但序列队对数减小）如
b) 非叶子结点：度为 2，整型，存储叶子结点序号，非叶数=叶数
第 k 趟并归执行次数=两子序列元素和*序列对对数= 2K(n/2K) 。综上算法基本操作执行
次数 nlog2n 时间复杂度恒为 O(nlog2n )空间复杂度 O(n) （归并需转存整个
(k) - 1
胜出者存于根在输出，用胜者所在有序子文件的下一个数据取代胜者
待排序列）
（5）基数类：（基数排序）
①基数排序思想是多关键字排序，一种叫最高位优先，即先按最高位
在叶子结点中的位置，继续求新胜者，此时只需沿着叶到根的路径调整败
者树。K 路归并的败者树高度为 ceil（log2k），利用败者树查找下一个最小
关键字时，最多做 ceil（log2k）次比较。（败者树和其他选择树的核心思想
排成若干子序列，再对子序列按次高位排（如扑克牌按花色分组后再按编
一样，用较大时间复杂度将元素排成特定要求的树，取满足要求的元素，
号排）；第二种叫最低位优先，先分配再收集，再分配再收集（先编号分
新来的元素放在刚取出元素的位置上，这样变成点破坏而不是全局破坏，
13 桶，每桶收集花色分至 4 桶再收集）
*低位优先基数排序，有几位数据就要分配收集几轮，每轮分配收集后，相
应位有序，且该位相同的元素其低位仍有序，当最高位经过分配收集后整
体有序。 当关键字取值范围很大时要考虑用最高位优先法。
时间复杂度：平均和最坏情况下都是 O(d(n+rd)) d 关键字位数 n 元素个数 rd
关键字取值范围
空间复杂度：O(rd) （共有 rd 个桶）
（6）外部排序：（归并排序法）
花费较少时间可将结构恢复正常，从而降低时间复杂度）
2.算法比较
（1）时间复杂度：
平均情况下，快速、希尔、并归、堆都是 O(nlog2n )
最坏情况下，快速为 O(n2)，其他都与平均相同。
* 特例：基数排序 O(d(n+rd)) 初始序列有序时 直接插和冒泡 均为 O(n)
（2）空间复杂度
以内存为工作空间来对外存进行排序。三个要点：外存组织、内存排
快速：O(log2n) 、归并：O(n)、基数：O(rd) 、其他均 O(1)
序、内外交换。
①归并排序法 流程：
a) 置换选择排序法。
（3）稳定性
（重要！）不稳定：快速、希尔、简单、堆 其余都稳定
（4）其他特性
写入内存排序后溢写回外存形成初始并归段。
一趟排序某一元素就位：冒泡、快速 、简单选择、堆
输出缓冲区内最小记录并用文件中的树替换，直到所有新输入记录均
元素比较次数与原始序列无关：简单选择排序、折半插入排序
小于最后输出记录时，完成一个初始归并段。重复以上生成下一个。（关键：
排序趟数与原始序列有关：交换类排序
每次必须输出一个最小且输出结果必须保持递增！）
b) 最佳归并树建立。（选择树法）
多个初始并归段多遍并归形成单一并归段。设法建立总 IO 次数最少的
最佳归并树，即让记录少的初始段最先归并。
* 建 N 路最佳归并树即每次挑长度最短的 N 个初始段归并，迭代。（赫
九、查找
夫曼树扩展到 K 叉的情况）。
*（关键！） IO 次数=带权路径长度*2 （权=初始段的长 、路径长=归
1.基本概念
（1）确定查找方法的因素：①查找表采用何种数据结构存储 ②查找表中关
并次数、每次归并有一进一出两次 IO）
键字次序（查找表用链表还是顺序表？数据是有序还是无序？）
* m 个有序段进行 k 路归并，归并的遍数为
* 归并排序算法的时间复杂度 O(nlog2m) （n 元素 m 初始段 根几路归
mk
log
无关）
* 外部排序所需总时间=内部排序时间 m*tIS（产生初始归并段）+外存信息
读写时间 d*tIO+内部归并所需时间 utmg。
*比较内部排序归并和外部排序归并：内是内存中进行，辅助空间 O(n)
（2）查找中对关键字比较的平均次数即平均查找长度作为衡量一个算法效
率优劣的标准
（n 是查找表中记录个数、 p 常取 1/n、 ci 是
找到第 i 个记录需要比较的次数即查找长度 ）。对查找算法的性能分析重
点在 ASL
2.常见查找法
（1）顺序查找法（从头到尾遍历一遍）
外部的是将外存中的多个有序子文件合并为一个有序子文件，子文件
ASL 分两种情况：成功的 ASL1=(n+1)/2 失败的 ASL2=n
中的记录读入内存后可采用多种内部排序方法。外部排序的效率瓶颈主要
（2）折半查找法
在外存读写次数，即归并趟数 s=ceil(logkm)，（m 归并段个数，k 归并路数），
应用中可选用败者树进行多路平衡归并和置换选择排序来减少 m 提高外部
要求表中记录按关键字有序。基本过程：求 mid=(low+high)/2 待查值
k 与 R[mid]比较相等则查找成功否则需确定新查找空间根据 R[mid]与 k 比较
排序效率。
判断落点于左还是右，重复上述过程。
选择树：置换选择排序里选出最小关键字的方法。
败者树：k 个元素构造成败者树，选择树的一种，完全二叉树，顺序
存储结构。数组下标 0 存储胜者，结点从下标 1 开始存储，所以 i 结点的双
描述折半查找的判定树，折半查找的比较次数=根到待查元素所经结
点数，查找的时间复杂度 O(t)=O( log2n) , ASL≈log2(n+1)-1。根据
mid=(low+high)/2 可画出判定树，空指针即查找不成功的位置，查找成功时
结点比较次数为其层数，可分别求 ASL1 和 ASL2
(*要会求 ASL1 ASL2)
5.B 树（多路搜索树，并非二叉）
（1）概念：
孩子结点数最大值为 B 树的阶（其实就是树的度）。
结点最多有 m 个分支，根最少 2 个分支，非根至少有
有 n 个分支的结点有 n-1 个关键字，自增排列。结点结构为：
2/m 个分支。
* 折半查找判定树的树型与序列关键字值无关，只与原始序列中关键
各底层结点是同层叶结点，叶结点下面是失败结点（空指针）
字个数有关系。关键字个数相同的有序表可产生同形判定树
*B 树是平衡 m 叉查找树但限制性更强要求叶结点同层。
n 为关键字个数，k 是关键字且 kiki 且kn
（3）分块查找法（索引顺序查找）
块内随意，块间有序。顺序表进行分块查找需格外建索引表，每项对
应一块，每个索引项由键值分量与链值分量构成，键存每块最大关键字，
链值分量存放指向本块第一个元素和最后一个元素的指针。索引表中所有
项按关键字递增排序。分块查找进行两次查找第一次二分，第二次顺序，
ASL=二分查找平均查找长度+顺序查找平均查找长度。
3.二叉排序树
（1）特点：左小于根，右大于根左右子树各是二叉排序树。中序遍
说明: （1）最大的分支数 m=5
（举个例子）
历序列递增有序。常采用二叉链表存储。
（2）二叉排序树的基本算法
2/m
=3 所以非根结点分支数∈[3,5]
（2）
（3）分支数=关键字数+1 非根结点关键字数∈[2,4]
a）查找：找到空指针域说明查找失败。折半查找的判定树是一
（4）关键字有序且同层，左结点关键字均小于右结点
棵二叉排序树。
*（5）下层结点关键字取值总落于上层结点关键字划分内区间，
b）插入：查找不成功的位置即该关键字的插入位置。已经存在
则返回 0。插入的关键字均存储新建叶结点上
c）构造： 逐个插入即可
d）删除 （掌握手工删除过程）
例如
划分了(-oo,15),(15,26),(26,+oo)
*（6）叶均在第三层叶下均是空指针
（2）B 树的基本操作
不能整子树都删只删一结点并保持二叉排序树特性，删除结点
a）B 树查找：为二叉排序树的扩展，二叉排序树是二路查找，B 树是多路
p 的三种情况：1.p 是叶子直接删即可 2.p 只有一个子树时 p 删掉，子
树接 p 位置。3.p 左右子树均有时：沿着 p 的左子树根右指针一直往
右，或沿着 p 的右子树根结点左指针一直往左到头 r，然后 r 替代 p，
最后按 1.2 中的原则删去 r（此时不可能是有两子树的结点）
4.平衡二叉树（AVL 树）
查找。结点内查找可用折半查找（因为有序）。
过程：1.key 进根结点比较找到则成功 2.keyk[n]
去 p[n]指的子树查找 ，若 K[i]非
树），调整使之成为平衡子树，失衡的最小子树被调整完后整个树就会平
衡。平衡调整的四种情况 LL RR LR RL。
根分支∈[3,5]、关键字个数∈[2,4]，插入，根最多容纳 4 关键字
超范围后拆分
继续插
继续出现关键字个数超限继续拆分
继续插入然后超限
拆分
继续插
此时插入 15，超限拆分，15 进根，再次超限拆分（连锁反应）：
B）结点的删除：8 可直接删，16 删可用 17 替换（与孩子进行关键字交换）
区别：1.n 关键字结点有 n 个分支 （B 树为 n+1）
删 15 时直接删不行借左兄弟不行借
2.非根结点关键字个数范围∈[
2/m ≤n≤m] 根结点为
（B 树分别为
，
）
3.B+树的非叶结点只是索引不含关键字对应的存储地址，而 B 树每个关键
右兄弟则 17<18,所以用 17 覆盖 15,18 覆盖 17。
字对应一个记录的存储地址。
删 4 直接删借左借有都不行需关键字合并：
精髓：根据关键字来计算关键字在表中的地址。H(key)称关键字 Key 的 Hash
4.B+树上有个指向最小叶结点的指针，所有叶连城链表，B 树没有。
7. 散列表（Hash）
出现非根双分支结点，继续合并
，结束！
典型题：给定序列和哈希函数，求哈希表。
地址，即 key 在查找表中的地址。
（1）Hash 表的建立及冲突解决
※几种特殊情况：
1.删除 a 使父亲结点关键字少一个，有可能少于规定数，此时要对
父亲结点继续合并，即删除结点引发的连锁反应。
2.相邻关键字。要删的关键字不在最底层非叶结点上需将其转化成在最底
层叶子结点上的情况。对于不在最底层非叶子结点上的关键字 a，其相邻关键字
为左子树最大关键字或右子树最小关键字（类似于二叉树找前驱后继）
6. B+树
从冲突发生的地址 d 开始探测 d 的下一个地址直至找到空闲单元并将关键字保
存于此，通常边建表边检测冲突解决冲突。
，解决冲突的方法：
根据关键字计算成功 ASL1
根据地址计算失败ASL2
装载因子是指所填充哈希表后饱和的程度，它等于 关键字总数/哈希表的
长度。
查找成功的比较次数=按照哈希后得到的位置去找找到时需比较的次数，
查找不成功的次数（即比较几次才知道不存在）=到第一个地址上关键字为空的
距离
Key 查找过程为：hash 函数算地址，key 与地址上关键字比较，空则失败，同则
成功。不同则遵循冲突处理方法去下一地址比较直到相同（成功）或空（失败）。
（2）常见的 Hash 函数构造法
1.直接定址：取 key 的线性函数为 hash 地址即 H(key)=a*key+b
2.数字分析、3.平方取中（key2 的中间几位做地址）、4.除留余数法
H(key)=key mod p 其中 p 通常选小于等于表长的最大素数以减少冲突。
（3）冲突处理法
1.开放定址法 ：新 hash=冲突解决函数 f（冲突的 hash 地址）
A)线性探查法。递推公式
B)平方探查法
2.链地址法：所有同义词用单链表串起来。Hash 表中存放的不再是记录本
身而是同义词链表的表头。
（4）哈希表的性能分析
查找成功 ASL =找到表中已有表项的平均比较次数
查找失败 ASL=没找到待查项但找到插入位置的平均比较次数（在所有可
能散列到的地址上插入新元素时为找到空位置而进行探查的平均次数）
哈希表的 ASL 与关键字个数 n 无关，与装填因子 a 有关，a=关键字个数
n/表长 m。
典型题：根据关键字序列、装填因子确定表长，采用除留余数法构造函数，
链地址法处理冲突，计算成功与不成功的ASL
a=关键字个数 n/表长 m 除留余数法 HASH 函数 H(key)=key mod p （p 取
不大于 m 的最大素数），各序列值依次 HASH 映射得
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
