文档内容
金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
数据结构知识点总结
-----本资料属www.wuyouqiuzhi.com及旗下天天向上求职工作室&职场精英工作室独家所有，仅限购买者个人
使用，不得分享/转赠/转卖；版权所有，盗版可耻
-----除历年真题外，整套资料还包括了红宝书讲义，完整讲义知识点，在线考试系统（电脑版网址为
www.wuyouqiuzhi.com），移动端刷题软件（名称为：笔试通，苹果商店及安卓各大市场搜索即可下载安装），
在线考试系统和移动端刷题软件购买时会配备账号密码，不会另付费。如缺失以上任何一项，说明资料不是正版，
请从正版处购买
使
天
-----唯一公众账号为 金融业招聘资讯（yinhangqiuzhi），用于更新每月小时政，招聘资讯等。绝对没有通过其他任
小
何公众账号出售资料，任何公众账号出售本资料的均为无良盗版，请从正版处购买 使
蓝
天
蔚
小
：
-----正版购买地址：官网www.wuyouqiuzhi.com及旗下淘宝店：天天向上求小职工作室（唯一客服：galerjim）
服 使
或职场精英工作室（唯一客服：蔚蓝小小天使），或者下载移动端刷题软件蓝（名称为：笔试通）亦可购买
客 天
蔚
旺 小
：
内容概要： 旺 服 小
宝 蓝
基本概念——线性表——栈与队列——树与二淘叉树——图——查客找算法——排序算
蔚
法
旺
一 ：
旺
唯 服
宝
， 客
淘
品 旺
一
出 旺
唯
室 宝
，
作 淘
品
工 一
出
英 唯
室
精 ，
作
场 品
工
职 出
英
室
精
作
场
工
职
英
精
场
职
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
使
天
小
小
使
蓝
天
蔚
小
：
小
服 使
蓝
客 天
蔚
旺 小
：
旺 小
服
宝 蓝
客
淘 蔚
旺
一 ：
旺
唯 服
宝
， 客
淘
品 旺
一
出 旺
唯
室 宝
，
作 淘
品
工 一
出
英 唯
室
精 ，
作
场 品
工
职 出
英
室
精
作
场
工
职
英
精
场
职
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
使
天
小
小
使
蓝
天
蔚
小
一、 基本概念 ：
小
服 使
1、数据元素是数据的基本单位。
客
蓝
天
蔚
2、数据项是数据不可分割的最小单位。 旺 小
：
3、数据结构的 旺 服 小
宝 蓝
逻辑结构（抽象的，与实现无关） 淘 客 蔚
旺
物理结构（存储结构） 顺序映像（顺一序存储结构）位置“相邻” ：
旺
唯 服
非顺序映像（链式存储结构）宝指针表示关系
， 客
淘
4、算法特性：算法具有正确性、品有穷性，确定性，（可行性）、输入，
旺
输出
一
正确性：能按设计要求解决具体 出 问题，并得到正
唯
确的结果。 旺
室 宝
有穷性：任何一条指令都只
作
能执行有限次，即，算法必须在执行
淘
有限步后结束。
品
确定性：算法中每条指令工的含义必须明确，不允许由二义性一
出
可行性：算法中待执 英 行的操作都十分基室本，算法应该在有唯限时间内执行完毕。
精 ，
输入：一个算法场的输入可以包含零作个或多个数据。
品
工
输出：算法有职一个或多个输出 出
英
室
5、算法设计的要求： 精
作
场
（1）正 确 性：算法应能满足设定的功
工
能和要求 。
职
（2）可 读 性：思路清晰、层次分英明、易读易懂 。
精
（3）健 壮 性：输入非法数据时应能作适当的反应和处理。
场
（4）高 效 性（时间复杂职度）：解决问题时间越短，算法的效率就越高。
（5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。
二、 线性表
1、线性表 List：最常用且最简单的数据结构。
含有大量记录的线性表称为文件。
2、线性表是n个数据元素的有限序列。
线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。
3、顺序表——线性表的顺序存储结构
特点
a) 逻辑上相邻的元素在物理位置上相邻。
b) 随机访问。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
0 1 ... MAXSIZE-1
1) typedef struct{ L.elem[] L.length==0
DataType elem[MAXSIZE];
L.elem[] L.length==MAXSIZE
int length;
} SqList;
L.elem[] 0next= =null 旺 小
：
循环单链表为空的判定条件为 L.next= =L 旺 服 小
宝 蓝
线性链表的最后一个结点的指针为NULL 淘 客 蔚
旺
头结点的数据域为空，指针域指向第一个一元素的指针。 ：
旺
唯 服
5、顺序表和单链表的比较
，
宝
客
淘
顺序表 品 单链旺表
一
址相邻表示关系 出 唯针表示关系 旺
室 宝
访问，取元素O(1) 作 ，访问，取元素 淘O(n)
品
删除需要移动元素工 O(n) 出 删除不用一移动元素O(n)(用于查找位置)
英 唯
6、顺序存储：优点
精
：存储密度大，可室随机存储
，
作
缺点场：大小固定；不利于增减节点;存储品空间不能充分利用；容量难扩充
工
链式存储：优 职 点：易于插入删英除；可动态申请空间出；表容量仅受内存空间限制
室
缺点：精增加了存储空间的开销；不可以随机存储元素
作
场
三、 栈与队列
职
工
英
1、栈
精
栈：限定仅在表尾进行插入或删除
场
操作的线性表。
栈顶：表尾端 职
栈底：表头
栈是先进后出的线性表。
插入栈顶元素称为入栈，删除栈顶元素称为出栈。
2、栈分为链栈和顺序栈
·链栈
用不带头结点的单链表实现。
S a a ... a /\
n n-1 1
·顺序栈
类似于顺序表，插入和删除操作固定于表尾。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
进栈:进栈运算是在栈顶位置插入一个新元素x。 出栈:出栈运算是指取出栈顶元素，赋给某一个指定变量x。
算法思想：
算法步骤：
(a)判栈是否为满，若栈满，作溢出处理，并返回0；
(a) 判栈是否为空，若栈空，作下溢处理，并返回0；
(b)若栈未满，栈顶指针top加1；
(c)将新元素x送入栈顶，并返回1。 (b) 若栈非空，将栈顶元素赋给变量x；
算法实现：
(c) 指针top减1，并返回1。
int Push (SeqStack *s，datatype x)
{ if （s->top= =MAXLEN–1） 算法实现：
return 0； // 栈满不能入栈，且返回0 datatype Pop（SeqStack *s）
else { s->top++； { datatypex;
s->data[s->top]=x；// 栈不满，则压入元素x if (SEmpty( s ) )
使
return 1；} // 进栈成功，返回1 return 0；// 若栈空不能出栈，且返回0
天
} else { 小x=s->data[s->top]；
小
// 栈不空则栈顶元素存入*x 使
蓝
蔚s->top --； 天
小
： return x；} // 出栈成功，返回1
小
服 使
} 蓝
客 天
蔚
旺 小
：
3、队列 旺 服 小
宝 蓝
先进先出的线性表。 淘 客 蔚
旺
队尾入队 对头出队 一 ：
旺
唯 服
允许插入的一端叫做队尾 宝
， 客
淘
允许删除的一端叫做对头 品 旺
一
出
唯
旺
室 宝
4、链队列
作
，
淘
品
工 一
出
英 唯
室
typed精ef struct queuenode
，
作
{d 场 atatype data工; 品
职 出
英
struct queuenode *next;
室
精
}queuen场ode; // 链队作结点的类型datatype
工
职
typedef struct
英
{queuenode *fron精t,*rear;
场
}linkqueue; 职 // 将头指针、尾指针封装在一起的链队
ffrroonntt AAA BBB …… JJJ ^^^
pp
rreeaarr
· 图4-6 链队列示意图
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
使
天
小
小
使
蓝
天
蔚
小
：
小
服 使
客
蓝
天
蔚
5、 循环队列 旺 小
：
旺 小
typedef struct { 服
宝 蓝
客
DataType elem[MAXSIZE]; 淘 蔚
旺
int front, rear; // 一 队头、队尾位置 ：
旺
唯 服
} SqQueue; 宝
， 客
淘
品 旺
一
·循环队列判断队空的条件 出 为 front=rear 唯 旺
室 宝
循环队列判断队满的条件为
作
（rear+1）%m=f，ront
淘
品
在一个循环队列中删除工元素时，首先需要后移队首指针。 一
出
6、栈与队列比较：都 英 是线形结构，栈室的操作LIFO（后进唯先出），队列操作FIFO（先进先出）。
精 ，
四、 树和二叉场树 作
品
工
职 出
英
室
精
作
场
工
职
英
精
场
职
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
使
天
小
小
使
蓝
天
蔚
小
：
小
服 使
蓝
客 天
蔚
旺 小
：
1. 树的定义 旺 服 小
宝 蓝
树（Tree）：是 n（n≥0）个有限数据元淘素的集合。 客
蔚
旺
在任意一棵非空树T中： 一 ：
旺
唯 服
（1）有且仅有一个特定的称为树根（Root）的结宝点，根结点无前趋结点；
， 客
淘
（2）当 n>1 时，除根结点之品外的其余结点被分成 m(m>0)个互不
旺
相交的集合 T1，T2，…，Tm，其中每
一
一个集合Ti（1≤ i ≤m）本身 出 又是一棵树，并且称为根的子树。旺
唯
室 宝
2. 基本术语： 作 ， 淘
品
结点的度数：结点的非空工子树（即后缀）个数叫作结点的度一数
出
树叶、分支结点：左 英 （右）子树均为空室二叉树的结点称作唯树叶否则称作分支结点。
精 ，
结点的层数：规场定根的层数是0，其作余结点的层数等
品
于其父结点的层数加1
工
孩子和双亲：职 出
英
室
树的深度： 精
作
场
树的度数：树中度数最大的结点度数叫作树的度数
工
职
树林：是由零个或多个不相交的树所组英成的集合。
精
场
3. 二叉树性质： 职
1) 二叉树的第i层上至多有2i-1个结点。
2) 深度为k的二叉树至多有2k-1个结点。
满二叉树：深度为k，有2k-1个结点。
完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n 个结点的完全二叉树中结点在对应满二叉
树中的编号正好是从1到n。
3) 叶子结点n ，度为2的结点为n ，则n = n +1。
0 2 0 2
考虑结点个数：n = n + n + n
0 1 2
考虑分支个数：n-1 = 2n + n
2 1
可得n = n +1
0 2
logn+1
4) n个结点的完全二叉树深度为 。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
5) n个结点的完全二叉树，结点按层次编号
有： i的双亲是n/2，如果i = 1时为根（无双亲）；
i的左孩子是2i，如果2i>n，则无左孩子；
i的右孩子是2i + 1，如果2i + 1>n则无右孩子。
4. 二叉树的存储结构
·顺序存储结构
用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。
·链式存储结构
二叉链表：
typedef struct BTNode {
使
DataType data; 天
struct BTNode *lchild, *rchild; 小
小
} BTNode, *BinTree; 使
蓝
三叉链表： 蔚 天
小
：
typedef struct BTNode { 小
服 使
DataType data; 客 蓝 天
蔚
struct BTNode *lchild, *rchild, *parent; 旺 小
：
旺 小
} BTNode, *BinTree; 服
宝 蓝
客
淘 蔚
旺
一 ：
旺
唯 服
宝
， 客
lchild data rchild lc品hild data parent 淘rchild
旺
一
在链式存储结构中，含有n个结 出 点的二叉链表有 唯n+1个空链域。 旺
室 宝
作
，
淘
品
5. 遍历二叉树工（先序DLR、中序LDR、后序LRD）一方法与C语言描述
出
由二叉树的递归定义 英 可知，一棵二叉树室由根结点（D）、根唯结点的左子树（L）和根结点的右子树（R）三部分
精 ，
组成。因此，只场要依次遍历这三部作分，就可以遍历整
品
个二叉树。一般有三种方法：先序(前序)遍历DLR（根
工
左右）、中序遍职历LDR（左根右）、 后序遍历LRD（出左右根）。
英
室
精
作
场
工
职
英
精
场
职
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
1．先序遍历（DLR）的递归过程
void Preorder(BT*T) // 先序遍历二叉树BT
{ if (T= =NULL) return; // 递归调用的结束条件
{ printf(T->data); // 输出结点的数据域
Preorder(T->lchild); // 先序递归遍历左子树
Preorder(T->rchild); // 先序递归遍历右子树
}
}
2．中序遍历（LDR）的递归过程
void Inorder(BT*T) // 中序遍历二叉树BT
{ if (T= =NULL) return; // 递归调用的结束条件
{ Inorder(T->lchild); // 中序递归遍历左子树
printf(T->data); // 输出结点的数据域
Inorder(T->rchild); // 中序递归遍历右子使树
天
}
3．后序遍历（LRD）的递归过程 小
}
void Postorder(BT*T) // 后序遍历二小叉树BT
使
{ if (T= =NULL) return; // 递归调用蓝的结束条件
天
{ Postorder(T->lchild); // 后序递归蔚遍历左子树
小
：
Postorder(T->rchild); // 后序递归遍历右子小树
服 使
printf(T->data); // 输出结点的数据域蓝
客 天
} 蔚
旺 小
} 旺 ： 小
服
宝 蓝
客
淘 蔚
旺
6. 线索二叉树 一 旺 ：
唯 服
n个结点的二叉链表中有n+1个空指针，可以利用其指宝向前驱或后继结点，叫线索，同时需附加一个标志，
， 客
淘
区分是子树还是线索。 品 旺
一
出 旺
lchild ltag data rtag rchild唯
室 宝
作0/1 0/1 ，
淘
品
lchild 有左子树工，则指向左子树，标志ltag == 0；一
出
没有左 英 子树，可作为前室驱线索，标志ltag 唯 == 1。
精 ，
rchild 场有右子树，则指向右作子树，标志rta品g == 0；
工
职没有右子树，可作为后继线索，标出志rtag == 1。
英
室
精
作
场
7. 树和森林 工
职
英
精
场
树的存储结构
职
双亲表示法，孩子表示法，孩子兄弟表示法。
特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以
结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。
树与二叉树的转换
表 5.1 树和二叉树的对应关系
树 对应的二叉树
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
个孩子 子
个兄弟 子
树的遍历
树的结构：①根，②根的子树。
先根遍历：①②。例：ABCDEFGHIJK。
后根遍历：②①。例：CEDFBHGJKIA。
遍历森林
森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。
先序遍历：①②③。例：ABCDEFGHIJ。 使
中序遍历：②①③。例：BDCEAGFIJH。 天
小
注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。
小
使
A
① ① 蓝
天
③
蔚
A F H
小
：
B G I
②
小
服 B C E 蓝G I J 使
客 天
C D F H J K 旺 旺 ② D ： 蔚 小 小
E 宝 服 蓝
客
淘 蔚
树的结构划 旺 森林的结构划分
一 ：
旺
唯 服
宝
， 客
淘
遍历树、森林与遍历二叉树的关系品 旺
一
出 旺
遍历树、森林和二叉树的关系
室
唯
宝
，
树 作森林 二叉树 淘
品
工 一
遍历 遍历 遍出历
英 唯
遍历 精遍历 室遍历
，
作
场
工
品
职 出
8. 哈夫曼树：叶子结英点带有权值的最 室 小带权路径长度的最优二叉树
精
作
场
工
职
英
精
场
构造赫夫曼树 职
每次取两个最小的树组成二叉树
赫夫曼编码(前缀码)
向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。
五、 图
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
1．
完全图：有1\2 n(n-1)条变得无向图
有向完全图：具有n（n-1）条弧的有向图。
权：与图的边或弧相关的数。
顶点v的度：和v相关联的边的数目。
入度：以顶点v为头的弧的数目
出度：以顶点v为尾的弧的数目
回路或环：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
使
2. 图的存储结构 天
小
·邻接矩阵：
小
使
A 0 1 1 0 0 蓝
天
蔚
B 0 0 1 1 0 小
：
C 0 0 0 1 0 服 小 使
蓝
D 1 0 0 0 0 客 天
蔚
E 1 0 0 1 0
旺
旺 ：
小
小
·邻接表：
宝
服
蓝
客
typedef struct ArcNode { // 弧结点 淘 蔚
旺
int adjvex; 一 旺// 邻接点 ：
唯 服
struct ArcNode *nextarc; ， 宝 // 下一个邻接 客 点
淘
} ArcNode; 品 一 旺
出 旺
唯
室 宝
，
typedef struct VexNode { 作// 顶点结点 淘
品
VertexType da 工 ta; 出 // 一 顶点信息
英 唯
ArcNode *firstarc精; //
第一个邻接点室
，
作
} VexNode; 场 品
工
职 出
英
室
const int MAX_VE RTEX = 最大
精
顶点个数; 作
场
typedef struct Graph { 职// 图 工
英
VexNode vexs[MAX_VERTEX]; // 顶点向量
精
int vexnum, arcn场um; // 顶点和弧的个数
职
} Graph;
边(弧)多则需要存储空间多。
0 A 1 2 /\
1 B 2 3 / \
2 C 3 /\
3 D 0 /\
4 E 0 3 /\
·十字链表：
十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。
在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
·邻接多重表
3. 图的遍历
1) 深度优先（DFS）搜索
访问方式：从图中某顶点v出发：
a）访问顶点v；
b）从 v 的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退
回前一个点继续上述过程，若退回开始点，结束。
2) 广度（宽度，BFS）优先搜索
a）访问顶点v ；
b）访问同v相邻的所有未被访问的邻接点w ,w , …w ； 使
1 2 k
天
c）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻
小
接点都被访问； 小
使
蓝
天
蔚
4. 生成树和最小生成树 ： 小
小
服 使
每次遍历一个连通图将图的边分成遍历所经过的边
客
和没有经过的边两蓝部分，将遍历经
天
过的边同图的顶点
蔚
构成一个子图，该子图称为生成树。因此有DFS生旺成树和BFS生成树。 小
：
1) 最小生成树 旺 服 小
宝 蓝
·Kruskal算法 淘 客 蔚
旺
一句话，“不构成环的情况下，每次选取最一小边”。 ：
旺
唯 服
宝
A ，A A
客
5 2 5 2 淘 5 2
3 品3 3 旺
一
6 出 6 旺6
B E D B E 唯D B E D
3 室 3 3 宝
1 3 7 作 1 3 ， 7 1淘 3 7
品
C (a工) C出 (b) 一 C (c)
英 唯
室
精 ，
A 作A A
5 场2 5 2 品 5 2
3 职 工 3 出 3
6 英 6 6
B E D B E 室D B E D
3 精 3 3
1 3 7 场 1 3 作 7 1 3 7
工
C (d)职 英C (e) C (f)
精
·普里姆算法
场
记V是连通网的顶点集，U是求职得生成树的顶点集，TE是求得生成树的边集。
普里姆算法：
(a) 开始时，U={v }，TE=Φ；
0
(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE；
(c) 重复(b)直到U=V。
普里姆算法和克鲁斯卡尔算法的比较
姆算法 斯卡尔算法
复杂度 ge)
顶点个数n有关 边的数目e有关
的数目e无关 点个数n无关
于稠密图 于稀疏图
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
5. AOV-网
用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。
拓扑排序的方法
(1)在有向图中选一个没有前驱的顶点且输出之
(2)从图中删除该顶点和所有以它为尾的弧
6. 关键路径
使
AOE网，关键路径 天
小
AOE网(Activity On Edge)——带权的有向无环图，其中顶点表示事件小，弧表示活动，权 表示活动持续时间。在
使
蓝
工程上常用来表示工程进度计划。 天
蔚
关键路径：从源点到汇点的最长的一条路径，或者全部由关：键活动构成的路径小。
小
服 使
蓝
客 天
蔚
旺 小
：
7. 最短路径 旺 服 小
宝 蓝
客
淘 蔚
旺
一 ：
(1) 迪杰斯特拉算法 唯 旺 服
宝
， 客
求一个顶点到其他各顶点的最短路径。 淘
品 旺
一
算法：(a) 初始化：用起点v到出该顶点w的直接边(弧)初始化最短路旺径，否则设为∞；
唯
(b) 从未求得最短路径的终点 室 中选择路径长度 ， 最小的终点u：即求宝得v到u的最短路径；
作 淘
(c) 修改最短路径：计算 工u的邻接点的最短品路径，若(v,…,u)+
一
(u,w)<(v,…,w)，则以(v,…,u,w)代替。
出
(d) 重复(b)-(c)，直到英求得v到其余所有顶点的最短路径。唯
室
特点：总是按照从 精 小到大的顺序求作得最短路径。 ，
场 品
工
职 出
英
室
精
作
场
(2) 弗洛伊德算法 工
职
英
求每对顶点之间的最短路径。
精
依次计算A(0)，A(1)，…，A(n)。 A(0)为场邻接矩阵，计算A(k)时，A(k)(i,j)=min{A(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)}。
技巧：计算A(k)的技巧。第k行、 职 第k列、对角线的元素保持不变，对其余元素，考查A(i,j)与A(i,k)+A(k,j) （“行
+列”），如果后者更小则替换A(i,j)，同时修改路径。
六、 查找
1. 查找分为：静态查找表、动态查找表、哈希查找表
2. 静态查找表：对查找表只作查找操作的查找表。
动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。
3. 顺序查找：顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链
表。
4. 二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
增或递减）排列。
5. 索引顺序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高
6. 动态查找表：二叉排序树查找：二叉排序树的生成
二叉排序树(二叉查找树)：或者是一颗空树。或者如下 1 若它的左子树不空，则左子树上所有的结点的
值均小于他的根结点的值。2若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子
树也分别为二叉排序树。
7. 哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法， 数字分析法
冲突解决方法：开放定址法、拉链法、公共溢出区法
七、 排序
1.插入类排序：
使
天
·直接插入排序
小
每次将一个待排序的数据元素，插入到前面已经排好序的数列小中的适当位置，使 数列依然有序；直到待
使
排序数据元素全部插入完为止。 蓝
天
蔚
·折半插入排序 小
：
小
·希尔排序 服 使
蓝
基本思想：先将整个待排序记录序列分成为若干个子 客 序列分别进行直
蔚
接插入排序，待整个天序列中的记录 基
旺 小
本有序 时在对全体序列进行一次直接插入排序，
旺
子序列的构成不是：简单的逐段分割
小
，而是将像个某个增量
服
的记录组成一个子序列。 宝 蓝
客
淘 蔚
旺
一 ：
旺
2.交换类排序 唯 服
宝
， 客
淘
·起泡排序 品 旺
一
也称冒泡法，每相邻两个记录关 出 键字比大小,大的记录往下沉（也可旺以小的往上浮）。每一遍把最后一个下沉
唯
室 宝
的位置记下，下一遍只需检查比较到此为止；，到所有记录都不发生下沉时，整个过程结束（每交换一次，记
作 淘
品
录减少一个反序数）。 工 一
出
·快速排序 英 室 唯
精 ，
在当前无序区 R场[1..H]中任取一个数作据元素作为比较
品
的"基准"(不妨记为 X)，用此基准将当前无序区划分为左
工
右两个较小的职无序区：R[1..I-1英]和R[I+1..H]，且左出边的无序子区中数据元素均小于等于基准元素，右边的无
室
序 子 区 中 数 据 元 素 均精大 于 等 于 基 准 元 素 ， 而 基 准 X 则 位 于 最 终 排 序 的 位 置 上 ， 即
作
场
R[1..I-1]≤X.Key≤R[ I+1..H](1≤I≤H)，当 R[工1..I-1]和 R[I+1..H]均非空时，分别对它们进行上述的划分过程，直
职
至所有无序子区中的数据元素均已排序英为止。
精
场
3.选择类排序 职
·简单选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到
全部待排序的数据元素排完。
·堆排序
堆排序是一树形选择排序，在排序过程中，将 R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全
二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
4.归并类排序
·二路归并排序
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
5.基数类排序
·基数排序
主要特点不需要进行关键字间的比较。
多关键字排序：
最高为优先（MSD法）从主关键字开始排序，再从次高位排序，一次类推，最后将所有子序列依次连接在一
起成为一个有序序列。
最低位优先（LSD法）从最次位关键字开始排序，在对高一位的进行排序，直到成为一个有序序列。
排序方法 稳定性 平均时间 最坏情况 辅助存储
直接插入排序 稳定 O（n*n） O（n*n） O（1）
使
快速排序 不稳定 O（nlbn） O（n*n） O（lbn）
天
归并排序 稳定 O(nlbn) O（n小lbn） O（n）
简单选择排序 稳定 O（n*n） O（
小
n*n） 使O （1）
蓝
堆排序 不稳定 O（nlbn） 蔚O（nlbn） 天 O(1)
小
基数排序 稳定 （d（n+rd）） ：（d（n+rd））
小
O（rd）
服 使
选取排序方法需要考虑的因素：
客
蓝
天
蔚
(1) 待排序的元素数目n； 旺 小
：
(2) 元素本身信息量的大小； 旺 服 小
宝 蓝
(3) 关键字的结构及其分布情况； 淘 客 蔚
旺
(4) 语言工具的条件，辅助空间的大一小等。 ：
旺
唯 服
小结： 宝
， 客
淘
(1) 若n较小(n <= 50)，则可品以采用直接插入排序或直接选择排 旺 序。由于直接插入排序所需的记录移动
一
操作较直接选择排序多，因出而当记录本身信
唯
息量较大时，用直旺接选择排序较好。
室 宝
(2) 若文件的初始状态 作 已按关键字基本有，序，则选用直接 淘 插入或冒泡排序为宜。
品
(3) 若n较大，则应工采用时间复杂度为O(nlog2n)的排一序方法：快速排序、堆排序或归并排序。
出
快速排序是目前 英 基于比较的内部排室序法中被认为是最唯好的方法。
精 ，
(4) 在基于比场较排序方法中，每作次比较两个关键 品 字的大小之后，仅仅出现两种可能的转移，因此可以用
工
一棵二叉职树来描述比较判定过程，由此可以出证明：当文件的n个关键字随机分布时，任何借助于"比较"
英
室
的排序算法 ，至少需要精O(nlog2n)的时间。
作
场
工
职
英
算法分析知识点总结
精
场
职
算法概述
1、算法的五个性质：有穷性、确定性、能行性、输入、输出。
2、算法的复杂性取决于：（1）求解问题的规模（N）,（2）具体的输入数据（I），（3）算法本身的设
计（A），C=F(N,I,A)。
3、算法的时间复杂度的上界记号O，
下界记号Ω(记为f(N) = Ω(g(N))。 即算法的实际运行时间至少需要g(n)的某个常数倍时间)，
同阶记号Θ：f(N)= Θ(g(N))表示f(N)和g(N)同阶 。
即算法的实际运行时间大约为g(n)的某个常数倍时间。
低阶记号o：f(N)=o(g(N))表示f(N)比g(N)低阶。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
多项式算法时间：
O(1) b1 (D(n) = n) ∴ T(n) = O(n2)；
对⑵，∵ a = b2 (D(n) = n2)∴ T(n) = O(n2log n)；
对⑶，∵ a < b3 (D(n) = n3)∴ T(n) = O(n3)；
证明一个算法的正确性需要证明两点：1、算法的部分正确性。2、算法的终止性。
3、汉诺塔问题：
void Hanoi(int n, int Fr, int To, int As)
{
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
if (n > 0) {
Hanoi(n–1, A, C, B);
Move(A, B);
Hanoi(n–1, C, B, A)}
}
4、二分查找代码
使
天
小
小
使
蓝
天
蔚
小
：
小
服 使
蓝
客 天
蔚
旺 小
：
旺 小
服
宝 蓝
客
淘 蔚
旺
一 ：
旺
唯 服
宝
， 客
淘
品 旺
一
出 旺
唯
室 宝
，
作 淘
品
工 一
出
英 唯
室
精 ，
作
场 品
工
职 出
英
室
精
作
场
工
职
英
精
场
职
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
使
天
小
贪心算法（旅行商问题、单源最短路径问题）
小
使
蓝
以下两种算法都是为了查找最小生成树问题的算法：蔚 天
小
1、Prim算法的基本思想：在保证连通的前提下依次：选出权重较小的 小n – 1条边。
服 使
（在实现中体现为n个顶点的选择）。
客
蓝
天
蔚
G=(V, E)为无向连通带权图，令V={1, 2, 旺…, n}。 小
：
设置一个集合S ，初始化S = {1}，T = 旺 Φ。 服 小
宝 蓝
贪心策略：如果V–S中的顶点淘j与S中的某个点i 客连接且(i, j) 的权
蔚
重最小，于是就选择j(将j加
旺
入S)，并将(i, j) 加入T中 。 一 ：
旺
唯 服
重复执行贪心策略，直至V–S为空。 宝
， 客
淘
=======================品======证明最小生成树必然包含最
旺
小权值边=================
一
若G的任何最小生成
室
树 出 都不包含e
1
。设 唯T为G的最小生
宝
成旺树，e
1
∉T。于是T+e
1
是一个有回路的图且
该回路中包含e 1 。 作 该回路中必有条不，是e的边e i 。令 淘 T’={T+e 1 }–e i 。T’也是G的生成树。又c(T’) = c(T)
品
+ c(e ) – c(e)，c工(e ) ≤ c(e)，从而 c(T’)≤c(T)，T’是G一的最小生成树且含有边e 。矛盾。故必定有图G
1 i 1 i 出 1
的最小生成树 英 包含了e 。 室 唯
精 1 ，
作
=======场===============================
品
=======================================
工
2、Kr 职 uskal算法的基本
英
思想：基本思想：出在保证无回路的前提下依次选出权重较小的n – 1条边。如
室
果(i, j )是E中尚未精被选中的边中权重最小的，并且(i, j)不会与已经选择的边构成回路，于是就选择
作
场
(i, j)。具 体做法:先把所有n个点 工 画出来。不画边。然后把权值最小的那条边画上去。然后再把当
职
前权值最小的边(不算画了的英边)画上去。如果构成回路则舍弃这条边。然后一直直到画了 n-1 条
精
边
场
3、 Prim与Kruskal两算职法的复杂性：
Prim算法为两重循环，外层循环为n次，内层循环为O(n)，因此其复杂性为O(n2)。
Kruskal算法中，设边数为e，则边排序的时间为O(eloge)，最多对e条边各扫描一次，每次确定边
的时间为O(loge)，所以整个时间复杂性为O(eloge)。
当e = Ω(n2)时，Kruskal算法要比Prim算法差；
当e = ο(n2)时，Kruskal算法比Prim算法好得多。
4、贪心算法的基本要素是：贪心选择性质。
5、最小生成树问题、单源最短路径问题、旅行商问题、0—1背包问题，贪心算法不能够找到最优解。
6、活动安排问题、最优装载问题，贪心算法可以找到最优解。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
7、Dijkstra 算法
Procedure Dijkstra {
( 1) S:={1}; //初始化S
(2) for i:= 2 to n do //初始化dis[]
(3) dis[i] =C[1, i] ; //初始时为源到顶点i一步的距离。不能一步到达就是无穷
(4) for i :=1 to n do {
(5) 从V-S中选取一个顶点u使得dis[u]最小；
使
(6) 将u加入到S中；//将新的最近者加入S 天
(7) for w∈V-S do //依据最近者u修订dis[w] 小
小
(8) dis[w] := min(dis[w] , dis[u]+C[u ,w]) 使
蓝
天
} 蔚
小
：
} 小
服 使
蓝
客 天
蔚
旺 小
：
旺 小
服
宝 蓝
客
淘 蔚
旺
一 ：
旺
唯 服
宝
， 客
淘
品 旺
一
出 旺
唯
室 宝
，
作 淘
品
工 一
出
英 唯
精
室
，
8、活动安场排问题:先把活动作按结束时间早晚排
品
序。然后选取最早结束的。然后选取第一个开始时间比
工
上一职个结束时间大的再用这个原则选取出。总的时间复杂度为O(nlogn)
英
室
====== =========精===============代码===================================
作
场
typedef st ruct { 工
职
int number; //活动的编号 英
精
float start; //活动开始的时间
场
float end; //活动结职束的时间
Bool selected; //标记活动是否被选择
}Active;
int greedySelector(Active activity[], int n)
{QuitckSort(activity,n); //将活动按结束时间排序
activity[1].selected=true; j=1;count=1;
for(i=2;i<=n;i++)
if(activity[i].start>=activity[j].end)
{activity[i].selected=true;
j=i; count++; }
else activity[i].selected=false;
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
return count; }
9、为什么贪心算法不能求得旅行商问题的最优解：最临近法不保证求得旅行商问题的精确解，只能
得到问题地近似解。一般地，贪心选择只依赖于前面选择步骤地最优性，因此是局部最优的，所
以贪心法不能够确保求出问题的最优解。
10、最优装载问题：基本思想：这个题目比较简单，可以用贪心法求解。每次采用重量最轻者优先
装入的贪心选择策略
11、贪心算法的特点是什么？怎么样知道一个问题是否能用贪心算法呢？
贪心算法每次选择目前最优的解，即通过一系列局部最优来获得整体最优。贪心算法只有在具
有贪心选择性质时才能保证获得整体最优。
证明贪心选择性质：⑴第一个选择是对的；⑵在作出贪心选择后 原问题转化为同样的子问题；
使
⑶由归纳法知问题具有贪心选择性质。
天
若原问题是求带权拟阵的最优独立子集问题，则必满足贪小心选择性质。
小
使
动态规划 蓝
天
蔚
小
1、最短路径问题: ：
小
服 使
蓝
客 天
蔚
旺 小
：
旺 小
服
宝 蓝
客
淘 蔚
旺
一 ：
旺
唯 服
宝
， 客
淘
品 旺
一
出 旺
唯
室 宝
，
作 淘
品
工 一
出
英 唯
室
精 ，
作
场 品
职
工
出
如果是从源点往后推:
英
室
阶段1 : 精
作
场
C(s,1)=w(s,1 )=4， C(s,2)=w(s,2)=2, 工 C(s,3)=w(s,3)=3
职
阶段2: 英
精
C(s,4)=min{w(1,4)+C(s,1), w(2,4)+C(s,2)}=min{14,8}= 8
场
C(s,5)=min{w(1,5)+C(s,1),职 w(2,5)+C(s,2), w(3,5)+C(s,3)} =min{13,9,6}= 6
C(s,6)=min{w(2,6)+C(s,2), w(3,6)+C(s,3)}=min{12,11}= 11
阶段3:
C(s,7)=min{w(4,7)+C(s,4), w(5,7)+C(s,5), w(6,7)+C(s,6)} =min{12,15,16}= 12
C(s,8)=min{w(4,8)+C(s,4), w(5,8)+C(s,5), w(6,8)+C(s,6)} =min{16,12,15}= 12
阶段4:
C(s,t)=min{w(7,t)+C(s,7), w(8,t)+C(s,8)}=min{20,16}= 16
2、最有子结构的性质：最优解的子结构也是最优的。
3、动态规划的基本要素：（1）最优子结构：问题的最优解是由其子问题的最优解所构成的。（2）重
叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
4、动态规划算法的步骤：1.找出最优解的性质，并刻画其结构特性。2.递归地定义最优解。3.以自底
向上的方式计算出各子结构的最优值，并流入表格中保存。4.根据计算最
优值时得到的信息，构造最优解。
5、在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦，n-2个三角形。
回溯法
1、三种搜索方法：（1）广度优先搜索的优点是一定能找到解；缺点是空间复杂性和时间复杂性都大。
（2）深度优先搜索的优点是空间复杂性和时间复杂性较小；缺点是不一定能找到解。（3）启发式搜
索是最好优先的搜索，优点是一般来说能较快地找到解，即其时间复杂性更小；缺点是需要设计一
个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。
2、 回溯法是一种通用的算法，实为深度优先的搜索方法。
使
回溯法可以递归实现，也可以迭代实现。
天
回溯法通常求解三类问题： 小
小
(1)求排列：时间复杂性为O(f(n)n!)； 使
蓝
(2)求子集：时间复杂性为O(f(n)2n)； 蔚 天
小
(3)求路径：时间复杂性为O(f(n)kn)。 ：
小
服 使
这里f(n)为处理一个结点的时间复杂性。
客
蓝
天
蔚
3、分支限界法回溯法联系与区别： 旺 小
：
支限界法类似于回溯法，也是一种在 旺 问题的解空间树服T上搜索问题解的算小法。但在一般情况下，
宝 蓝
分支限界法与回溯法的求解目标淘不同。回溯法的求解客目标是找出T中
蔚
满足约束条件的所有解，而
旺
分支限界法的求解目标则是找一出满足约束条件的一个解，或是在满：足约束条件的解中找出使某一
旺
唯 服
目标函数值达到极大或极小的解，即在某种宝意义下的最优解。
， 客
淘
由于求解目标不同，导品致分支限界法与回溯法在解空间树 旺T上的搜索方式也不相同。回溯法以深
一
度优先的方式搜索解 出 空间树 T，而分
唯
支限界法则以广度旺优先或以最小耗费优先的方式搜索解空间
室 宝
树T。分支限界
作
法的搜索策略是：，在扩展结点处，
淘
先生成其所有的儿子结点（分支），然后再从当
品
前的活结点表工中选择下一个扩展对点。为了有效一地选择下一扩展结点，以加速搜索的进程，在每
出
一活结点处 英 ，计算一个函数室值（限界），并根唯据这些已计算出的函数值，从当前活结点表中选择
精 ，
一个场最有利的结点作为扩作展结点，使搜索
品
朝着解空间树上有最优解的分支推进，以便尽快地找出
工
一职个最优解。 出
英
室
精
分支界限法
场
作
工
职
1、分支界限法德两个要点：（1 英）评价函数的构造。（2）搜索路径的构造。
精
2、所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子
场
树剪去，减少搜索的范围职，提高效率。因而更准确的称呼应是“界限剪支法”
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
使
天
小
字符串
小
使
蓝
1、几个名词的定义：串的长度，子串，位置，串相等蔚，模式匹配。简单天模式匹配算法在正文设置一
小
个指针指向第一个然后跟模式串匹配。不行就指针：加一直到匹配成功或者正文结束。时间复杂度为
小
服 使
O(m+n)最坏为O(mn)
客
蓝
天
蔚
旺 小
：
2、KMP算法：时间复杂度为O(m+n)。n 旺 ext(j)函数的计算服(计算到第j个就是小从1到j-1这个子串首位
宝 蓝
分别截取尽可能长的相同子串。从尾淘巴那里截取的子串客不用倒过来。得
蔚
到的最长相同子串长+1 就是
旺
next(j)的值啦。Next(1)固定等于0 一。 恒有next(2) = 1)， ：
旺
唯 服
int KMP_StrMatch(SString S, SString P)｛ 宝
， 客
淘
int i = 1, j = 1, m = 品0; 旺
一
while(i <= S[0] & 出 & j <= P[0]) 唯 旺
室 宝
if (j =作 0 || S[i] = P[j])｛i+，+; j++;｝
淘
品
else j工 = next[j]; //失配时从next[j]重新比较一
出
英 唯
if(j > P[0]) m = i – j + 室1;
精 ，
场return(m); 作 品
工
职 ｝ 出
英
室
======== =========精Newnext函数的计算======================================
作
场
void get_new next(){ 工
职
int k,j; 英
精
newnext[1]=0; j=2;
场
while(j<=P[0]){ k=next[j职];
if(k==0||p[k]!=p[j])
newnext[j]=k;
else newnext[j]=newnext[k];
j=j+1;}}
3、BM算法：Boyer-Moore串匹配算法(简称BM算法)。最坏时间复杂度O(mn)
其思想是在匹配过程中，一旦发现在正文中出现模式中没有的字符时就可以将模式、正文大幅度地
“滑过”一段距离。
同时考虑到多数不匹配的情形是发生在最后的若干个字符，采用从左到右的方式扫描将浪费很多时
间，因此改自右到左的方式扫描模式和正文
本资料仅限购买者一个人使用，不得分享/转赠/转卖；祝各位获得心仪offer。版权所有，违者必究。金融/四大/国企/名企求职笔试面试教育-职场精英工作室，店址：https://huntjob.taobao.com/ 唯一旺旺客服：蔚蓝小小天使
========================dist函数的计算====================================
m c∉P, 或c= p 且c≠ p(0
