文档内容
数据结构知识点总结
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
内容概要：
基本概念——线性表——栈与队列——树与二叉树——图——查找算法——排序算法
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
一、 基本概念
1、数据元素是数据的基本单位。
2、数据项是数据不可分割的最小单位。
3、数据结构的
逻辑结构（抽象的，与实现无关）
物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻”
非顺序映像（链式存储结构）指针表示关系
4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出
正确性：能按设计要求解决具体问题，并得到正确的结果。
有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。
确定性：算法中每条指令的含义必须明确，不允许由二义性
可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。
输入：一个算法的输入可以包含零个或多个数据。
银行笔试助攻加微信：qitd
输
2
出
6
：
8
算
8
法有一个或
银
多个
行
输出
笔 试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
5、算法设计的要求：
（1）正 确 性：算法应能满足设定的功能和要求 。
（2）可 读 性：思路清晰、层次分明、易读易懂 。
（3）健 壮 性：输入非法数据时应能作适当的反应和处理。
（4）高 效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。
（5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。
二、 线性表
1、线性表 List：最常用且最简单的数据结构。
含有大量记录的线性表称为文件。
2、线性表是n个数据元素的有限序列。
线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。
3、顺序表——线性表的顺序存储结构
特点a) 逻辑上相邻的元素在物理位置上相邻。
b) 随机访问。
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、顺序存储：优点：存储密度大，可随机存储
银行笔试助攻加微信：qitd 2 6 8 8 缺点：大银小固行定；笔不利试于增助减节攻点;存加储空微间不信能充：分利q用；it容d量2难扩6充8 8 银行笔试助攻加微信：qitd2688
链式存储：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限制
缺点：增加了存储空间的开销；不可以随机存储元素
三、 栈与队列
1、栈
栈：限定仅在表尾进行插入或删除操作的线性表。
栈顶：表尾端
栈底：表头
栈是先进后出的线性表。
插入栈顶元素称为入栈，删除栈顶元素称为出栈。
2、栈分为链栈和顺序栈
·链栈
用不带头结点的单链表实现。
S a a ... a /\
n n-1 1
·顺序栈类似于顺序表，插入和删除操作固定于表尾。
进栈:进栈运算是在栈顶位置插入一个新元素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;
银行笔试助攻加微信：qitd2688
s->data
银
[s->to
行
p]=x
笔；// 栈试不满助，则攻压入加元素x 微信：
if
q
(S
i
E
t
m
d
pty
2
( s
6
) )
88 银行笔试助攻加微信：qitd2688
return 1；} // 进栈成功，返回1 return 0；// 若栈空不能出栈，且返回0
} else { x=s->data[s->top]；
// 栈不空则栈顶元素存入*x
s->top --；
return x；} // 出栈成功，返回1
}
3、队列
先进先出的线性表。
队尾入队 对头出队
允许插入的一端叫做队尾
允许删除的一端叫做对头
4、链队列
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688typedef struct queuenode
{datatype data;
struct queuenode *next;
}queuenode; // 链队结点的类型datatype
typedef struct
{queuenode *front,*rear;
}linkqueue; // 将头指针、尾指针封装在一起的链队
ffrroonntt AAA BBB …… JJJ ^^^
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
pp
rreeaarr
· 图4-6 链队列示意图
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
5、 循环队列
typedef struct {
DataType elem[MAXSIZE];
int front, rear; // 队头、队尾位置
} SqQueue;
·循环队列判断队空的条件为 front=rear
循环队列判断队满的条件为 （rear+1）%m=front在一个循环队列中删除元素时，首先需要后移队首指针。
6、栈与队列比较：都是线形结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。
四、 树和二叉树
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
1. 树的定义
树（Tree）：是 n（n≥0）个有限数据元素的集合。
在任意一棵非空树T中：
（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点；
（2）当 n>1 时，除根结点之外的其余结点被分成 m(m>0)个互不相交的集合 T1，T2，…，Tm，其中每
一个集合Ti（1≤ i ≤m）本身又是一棵树，并且称为根的子树。
2. 基本术语：
结点的度数：结点的非空子树（即后缀）个数叫作结点的度数
树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否则称作分支结点。
结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
孩子和双亲：
树的深度：
树的度数：树中度数最大的结点度数叫作树的度数
树林：是由零个或多个不相交的树所组成的集合。
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个结点的完全二叉树深度为 。
5) n个结点的完全二叉树，结点按层次编号
有： i的双亲是n/2，如果i = 1时为根（无双亲）；
i的左孩子是2i，如果2i>n，则无左孩子；
i的右孩子是2i + 1，如果2i + 1>n则无右孩子。
4. 二叉树的存储结构
·顺序存储结构
用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。
银行笔试助攻加微信：qitd26
·
8
链
8
式存储结构
银 行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
二叉链表：
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 lchild data parent rchild
在链式存储结构中，含有n个结点的二叉链表有n+1个空链域。
5. 遍历二叉树（先序DLR、中序LDR、后序LRD）方法与C语言描述
由二叉树的递归定义可知，一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。一般有三种方法：先序(前序)遍历DLR（根
左右）、中序遍历LDR（左根右）、 后序遍历LRD（左右根）。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); // 输出结点的数据域
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
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；
银行笔试助攻加微信：qitd 2688 没有 银 左子 行 树， 笔 可作 试 为前 助 驱线 攻 索， 加 标志 微ltag =信= 1。 ： qitd2688 银行笔试助攻加微信：qitd2688
rchild 有右子树，则指向右子树，标志rtag == 0；
没有右子树，可作为后继线索，标志rtag == 1。
7. 树和森林
树的存储结构
双亲表示法，孩子表示法，孩子兄弟表示法。
特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以
结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。树与二叉树的转换
表 5.1 树和二叉树的对应关系
树 对应的二叉树
根 根
第一个孩子 左孩子
下一个兄弟 右孩子
树的遍历
树的结构：①根，②根的子树。
先根遍历：①②。例：ABCDEFGHIJK。
后根遍历：②①。例：CEDFBHGJKIA。
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
遍历森林
森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。
先序遍历：①②③。例：ABCDEFGHIJ。
中序遍历：②①③。例：BDCEAGFIJH。
注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。
A
① ① ③
A F H
B G I
②
B C E G I J
C D F H J K
D
②
E
树的结构划 森林的结构划分
遍历树、森林与遍历二叉树的关系
遍历树、森林和二叉树的关系
树 森林 二叉树
先根遍历 先序遍历 先序遍历
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
后根遍历 中序遍历 中序遍历
8. 哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树
构造赫夫曼树
每次取两个最小的树组成二叉树
赫夫曼编码(前缀码)
向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。五、 图
1．
完全图：有1\2 n(n-1)条变得无向图
有向完全图：具有n（n-1）条弧的有向图。
权：与图的边或弧相关的数。
顶点v的度：和v相关联的边的数目。
入度：以顶点v为头的弧的数目
出度：以顶点v为尾的弧的数目
回路或环：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
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 data; // 顶点信息
ArcNode *firstarc; // 第一个邻接点
银行笔试助攻加微信：qitd}2 Ve6xN8ode8; 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
const int MAX_VERTEX = 最大顶点个数;
typedef struct Graph { // 图
VexNode vexs[MAX_VERTEX]; // 顶点向量
int vexnum, arcnum; // 顶点和弧的个数
} Graph;
边(弧)多则需要存储空间多。
0 A 1 2 /\
1 B 2 3 / \
2 C 3 /\
3 D 0 /\
4 E 0 3 /\·十字链表：
十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。
在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。
·邻接多重表
3. 图的遍历
1) 深度优先（DFS）搜索
访问方式：从图中某顶点v出发：
a）访问顶点v；
b）从 v 的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退
回前一个点继续上述过程，若退回开始点，结束。
2) 广度（宽度，BFS）优先搜索
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
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
3 3 3
1 7 1 7 1 7
C (a) C (b) C (c)
A A A
银行笔试助攻加微信：qitd2685 8 2 银行笔试5 助攻2 加微信5： qi2t d2688 银行笔试助攻加微信：qitd2688
3 3 3
6 6 6
B E D B E D B E D
3 3 3
3 3 3
1 7 1 7 1 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。
普里姆算法和克鲁斯卡尔算法的比较
算法 普里姆算法 克鲁斯卡尔算法
时间复杂 O(n2) O(e loge)度
特点 只与顶点个数n有关 只与边的数目e有关
与边的数目e无关 与顶点个数n无关
适用于稠密图 适用于稀疏图
5. AOV-网
用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。
拓扑排序的方法
(1)在有向图中选一个没有前驱的顶点且输出之
(2)从图中删除该顶点和所有以它为尾的弧
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
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)代替。
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
(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. 二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递
增或递减）排列。
5. 索引顺序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高
6. 动态查找表：二叉排序树查找：二叉排序树的生成
二叉排序树(二叉查找树)：或者是一颗空树。或者如下 1 若它的左子树不空，则左子树上所有的结点的
值均小于他的根结点的值。2若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子
树也分别为二叉排序树。
7. 哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法， 数字分析法
冲突解决方法：开放定址法、拉链法、公共溢出区法
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
七、 排序
1.插入类排序：
·直接插入排序
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待
排序数据元素全部插入完为止。
·折半插入排序
·希尔排序
基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录 基
本有序 时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量
的记录组成一个子序列。
2.交换类排序
·起泡排序
也称冒泡法，每相邻两个记录关键字比大小,大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉
的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记
银行笔试助攻加微信：qitd
录
2
减
6
少
8
一
8
个反序数）
银
。
行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
·快速排序
在当前无序区 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.归并类排序
·二路归并排序
5.基数类排序
·基数排序
主要特点不需要进行关键字间的比较。
多关键字排序：
最高为优先（MSD法）从主关键字开始排序，再从次高位排序，一次类推，最后将所有子序列依次连接在一
起成为一个有序序列。
银行笔试助攻加微信：qitd
最
2
低
6
位
8
优
8
先（LSD法
银
）从
行
最次
笔
位关
试
键字
助
开始
攻
排序，
加
在对
微
高一
信
位的
：
进行
q
排
i
序
t
，
d
直
2
到
6
成
8
为一
8
个有序序
银
列。
行 笔试助攻加微信：qitd2688
排序方法 稳定性 平均时间 最坏情况 辅助存储
直接插入排序 稳定 O（n*n） O（n*n） O（1）
快速排序 不稳定 O（nlbn） O（n*n） O（lbn）
归并排序 稳定 O(nlbn) O（nlbn） O（n）
简单选择排序 稳定 O（n*n） O（n*n） O（1）
堆排序 不稳定 O（nlbn） O（nlbn） O(1)
基数排序 稳定 O（d（n+rd）） O（d（n+rd）） O（rd）
选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动
操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
银行笔试助攻加微信：qitd26(38) 若8n较大，银则应行采用笔时间试复杂助度为攻O(nl加og2n微)的排信序方：法：q快速it排d序2、6堆排8序8或归并排银序。行 笔试助攻加微信：qitd2688
快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(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)低阶。
多项式算法时间：
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)
{
if (n > 0) {
Hanoi(n–1, A, C, B);
Move(A, B);
银行笔试助攻加微信：qitd 2 6 8 8 银 Ha行noi(n笔–1, C试, B, A助)} 攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
}
4、二分查找代码
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
贪心算法（旅行商问题、单源最短路径问题）
以下两种算法都是为了查找最小生成树问题的算法：
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 。设T为G的最小生成树，e ∉T。于是T+e 是一个有回路的图且该回路中
1 1 1
包含e 。该回路中必有条不是e的边e。令T’={T+e }–e。T’也是G的生成树。又c(T’) = c(T) + c(e ) – c(e)，c(e )
1 i 1 i 1 i 1
≤ c(e)，从而 c(T’)≤c(T)，T’是G的最小生成树且含有边e 。矛盾。故必定有图G的最小生成树包含了e 。
i 1 1
=============================================================================
银行笔试助攻加微信：qitd2、 2K6rus8kal8 算法的基本 银 思想 行 ：基 笔 本思 试 想： 助 在保 攻 证无 加 回路 微 的前 信 提下依 ： 次选 q 出 i 权 td 重较 2 小 6 的 8n 8– 1条边。 银 如果 行(i, j)是 笔E 试助攻加微信：qitd2688
中尚未被选中的边中权重最小的，并且(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、活动安排问题、最优装载问题，贪心算法可以找到最优解。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]最小；
银行笔试助攻加微信：qitd2(66) 8 8 将u加入到 银S中 行 ；//笔 将新 试 的最 助 近者加 攻 入 加S 微信：qitd2688 银行笔试助攻加微信：qitd2688
(7) for w∈V-S do //依据最近者u修订dis[w]
(8) dis[w] := min(dis[w] , dis[u]+C[u ,w])
}
}
银行笔试助攻加微信：qitd8、
2
活
6
动
8
安排
8
问题:先把
银
活动
行
按结
笔
束时
试
间早
助
晚排
攻
序。
加
然后
微
选取最
信
早结
：
束的
q
。
i
然
t
后
d
选
2
取
6
第
8
一个
8
开始时间
银
比上
行
一个
笔
结
试助攻加微信：qitd2688
束时间大的再用这个原则选取。总的时间复杂度为O(nlogn)
==============================代码===================================
typedef struct {
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;
return count; }
9、为什么贪心算法不能求得旅行商问题的最优解：最临近法不保证求得旅行商问题的精确解，只能得到问题
地近似解。一般地，贪心选择只依赖于前面选择步骤地最优性，因此是局部最优的，所以贪心法不能够确
保求出问题的最优解。
10、最优装载问题：基本思想：这个题目比较简单，可以用贪心法求解。每次采用重量最轻者优先装入的贪
心选择策略
11、贪心算法的特点是什么？怎么样知道一个问题是否能用贪心算法呢？
贪心算法每次选择目前最优的解，即通过一系列局部最优来获得整体最优。贪心算法只有在具有贪心选
银行笔试助攻加微信：qitd26
择性
8
质
8
时才能保
银
证获
行
得整体
笔
最优
试
。
助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
证明贪心选择性质：⑴第一个选择是对的；⑵在作出贪心选择后原问题转化为同样的子问题；⑶由归纳法知
问题具有贪心选择性质。
若原问题是求带权拟阵的最优独立子集问题，则必满足贪心选择性质。
动态规划
1、最短路径问题:
银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
如果是从源点往后推:
阶段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）重叠子问题：
子问题之间并非相互独立的，而是彼此有重叠的。
4、动态规划算法的步骤：1.找出最优解的性质，并刻画其结构特性。2.递归地定义最优解。3.以自底向上的方
式计算出各子结构的最优值，并流入表格中保存。4.根据计算最优值时得到的信息，
构造最优解。
5、在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦，n-2个三角形。
银行笔试助攻加微信：qitd回2溯6法8 8 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
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 中满足约束条件的所有解，而分支限界法的求解目标
则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，
即在某种意义下的最优解。
银行笔试助攻加微信：qitd 由 2 于 6 求解 8 目 8 标不同， 银 导致 行 分支限 笔 界法 试 与回 助 溯法 攻 在解 加 空间 微 树 T信 上的 ： 搜索 q 方 i 式 t 也 d 不 2 相 6 同 8 。回 8 溯法以深 银 度优 行 先的 笔 方 试助攻加微信：qitd2688
式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索
策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。
为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些
已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优
解的分支推进，以便尽快地找出一个最优解。
分支界限法
1、分支界限法德两个要点：（1）评价函数的构造。（2）搜索路径的构造。
2、所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，
减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：q itd2688 银行笔试助攻加微信：qitd2688
字符串
1、几个名词的定义：串的长度，子串，位置，串相等，模式匹配。简单模式匹配算法在正文设置一个指针指
向第一个然后跟模式串匹配。不行就指针加一直到匹配成功或者正文结束。时间复杂度为O(m+n)最坏为O(mn)
2、KMP算法：时间复杂度为O(m+n)。next(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函数的计算======================================
银行笔试助攻加微信：qitdvo2id g6et8_ne8wnext(){ 银行笔试助攻加微信：qitd2688 银行笔试助攻加微信：qitd2688
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)
其思想是在匹配过程中，一旦发现在正文中出现模式中没有的字符时就可以将模式、正文大幅度地“滑过”
一段距离。
同时考虑到多数不匹配的情形是发生在最后的若干个字符，采用从左到右的方式扫描将浪费很多时间，因此
改自右到左的方式扫描模式和正文========================dist函数的计算====================================
m c∉P, 或c= p 且c≠ p(0
