第一章绪论
1.数据结构定义：存在一种或多种特定的关系数据元素的集合。
2.数据逻辑结构的分类：线性结构：线性表，栈，队，串，数组等；非线性结构：树，图
3.两类物理存储方式及特点
顺序存储结构：（特点）借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
链式存储结构：（特点）借助指示元素存储地址的指针表示数据元素之间的逻辑关系
4.时间复杂度的计算
时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
P.S算法中的语句执行次数称为语句频度或时间频度。记为T(n),与时间复杂度要区分。
第二章线性表
1．线性表的定义：线性表是由n≥0个数据元素组成的有限序列。
2.移动元素个数的计算
3.顺序表插入和删除算法时间复杂度计算
插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。
删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）
4.非空循环单链表的特点
表中最后一个结点的指针域指向头结点，整个链表形成一个环。
5.单链表的插入与删除操作
·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O（n）。
·尾插法：head= rear = null；if（head = null）head=s；else r ->next=s；r =s；平均时间复杂度均为O（n）·插入运算：p=GetNode（L，i-1）；s->next=p->next；p->next=s；平均时间复杂度均为O（n）·删除运算：p=GetNode（L，i-1）；r = p->next；p->next = r->next；free（r）；平均时间复杂度均为O（n）6.双向链表的插入操作
后插：s->priou=p; s->next=p->next; p->next->priou=s ; p->next=s;
前插：q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q;
7.单链表中查找某元素的平均比较次数
从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较n个结点
第三章栈和队列
1.栈和队列的逻辑特性
栈：限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈的操作特性：后进先出（LIFO）。
队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。
队列的操作特性：先进先出(FIFO,LILO)
2.顺序栈的出栈、入栈
typedef int SElemType;
typedef struct {
SElemType data[MAXSIZE]; int top;
}SqStack;
//初始化
Status InitStack(SqStack *s){ s->top = -1;
return OK; }
//入栈 if(s->top == MAXSIZE-1)
return ERROR;
s->top++;
s->data[s->top] = e;
return OK;}
//出栈
Status Pop(SqStack *s,SElemType *e){ if(s->top == -1){
return ERROR; }
*e = s->data[s->top];
3.栈的常见应用（详见教材P48）
<1>数制转换<2>括号匹配的检验<3>行编辑程序<4>迷宫求解<5>表达式求值
4.循环顺序队列出队和入队操作时队首队尾指针变化
每插入一新元素，rear = (rear + 1) % maxsize；每删除一元素，front = (front + 1) % maxsize 。5．循环顺序队列如何判队空、判队满、求队中元素个数。
<1>判队空：if(q.front==rear) return ERROR;
<2>判队满：if(q.rear+1)%MAXSIZE)==q.front) return ERROR;
P.S.队空条件：front==rear（初始化时front=rear）；队满条件：front==（rear+1）%N（N=MAXSIZE）<3>求队中元素个数队列长度：L=（N+rear-front）%N
第四章串 1.串的定义：串是零个或多个字符组成的有限序列。
2.空串和空格串的区别
空串：是指长度为零的串，也就是串中不包含任何字符（结点）。空串是任何串的子串。
空格串：指串中包含一个或多个空格字符的串。
3.了解串的模式识别算法。
模式匹配操作的具体含义是：在主串（也称做目标串)S中，从位置start开始查找是否存在子串(也称做模式串)T，如果在主串S中查找到一个与模式串T相同的子串，则称查找成功；如在主串S 中未找到一个与模式串T相同的子串，则称查找失败。当模式匹配成功时,函数返回模式串T的第一个字符在主串S中的位置;当模式匹配失败时,函数返回-1。其中Brute-Force（BF）算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。
BF算法的主要思想是：将主串S的第start个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较，直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值–1。BF算法简单并且容易理解，但是有些情况下时间效率不高，最好情况下（一配就中）时间复杂度为O(m+n)，最坏情况下时间复杂度为O(n×m)。
KMP算法的主要思想是：利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置，重点就在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪里。
这可以分为两种情况来考虑：当前si和tj比较不相等，（1）当模式串中不存在可相互重叠的真子串，下一次可直接比较si和t0；（2）当模式串中存在可相互重叠的真子串时，j要移动的下一个位置为k，k满足：模式串中最前面的k个字符和j之前的最后k个字符是一样的。
所以，问题的重点：计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当S[i] != T[j]时，j指针的下一个位置。时间复杂度为O（m+n）。
第五章数组和广义表
1.数组和广义表的定义
数组：二维数组是一个定长线性表，且它的每个数据元素也是一个定长线性表。
广义表：广义表是线性表的推广。（多层次的线性结构）
2.二维数组按行（列）优先地址的计算
（1）以列序为主序的存储方式的存储地址计算公式：
LOC(i,j) = LOC(0,0) + (m*(j-1)+(i-1))*L
LOC(i,j)是a(i,j)的存储位置； LOC(0,0)是a(0,0)的存储位置（即二维数组的起始存储位置，为称为基地址或基址）；m是数组的总行数，L是单个数据元素占据的存储单元。
（2）以行序为主序的存储方式的存储地址计算公式：
LOC(i,j) = LOC(0,0) + (n*(i-1)+(j-1))*L
LOC(i,j)是a(i,j)的存储位置； LOC(0,0)是a(0,0)的存储位置（即二维数组的起始存储位置，为称为基地址或基址）；n是数组的总列数，L是单个数据元素占据的存储单元。
解题过程：行n=8，列m=10
（1）行优先：A[5,8]=A(0,0)+(m*(i-1)+(j-1))*L = BA+(10 * ( 5-1) + ( 8-1 )) * 3 = BA + 141
3.二维数组按上三角矩阵按列（行）优先存放地址的计算
对于元素处于上三角区域，即元素a ij ，其中i ≤j ，可得如下规律：
第1行有n 个元素，第2行有(n ?1)个元素，第3行有(n ?2)个元素，第i 行有(n ?i +1)个元素，…第n 行有(n ?n +1)(即只有1个元素)个元素；可得对于元素a ij ，第(i ?1)行（即元素a ij 前一行）共有：
=1i
?1(n ?k +1)=(i ?1)(2n ?i +2)/2 个元素，元素a ij ,在第i 行中是第(j ?i +1)个元素，规定：每个元素所占的长度为e ，所以：
address (a ij )=address (a 11
)+((i ?1)(2n ?i +2)/2+j ?i )e 4.广义表求表头、表尾操作
根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是说，广义表的head 操作，取出的元素是什么，那么结果就是什么。但是tail 操作取出的元素外必须加一个表——“ （）“
问题：
已知广义表LS ＝((a,b,c),(d,e,f)),运用head 和tail 函数取出LS 中原子e 的运算是？
已知广义表LS ＝((a,b,c),(d,e,f))
故: tail(LS)＝((d,e,f))
head(tail(LS))=(d,e,f)
tail(head(tail(LS)))=(e,f)
head(tail(head(tail(LS))))=e
第六章 树和二叉树
1.树和二叉树的定义、结点的度、树的度、树的高度（深度）、完全二叉树、满二叉树
树(Tree) : 是具有层次结构的 n(n≥0) 个结点的有限集。
二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 结点的度：分支的个数(拥有的子树数)
树的度：树中所有结点的度的最大值 树的高度（深度）：树中叶子结点所在的最大层次
完全二叉树：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称为完全二叉树。特点: (1)叶子结点只可能在层次最大的两层上出现。(2)对任一结点，若其右分支的子孙的最大层次为 l ，则其左分支下的子孙的最大层次必为 l 或 l +1。
满二叉树：一棵深度为 k 且有 2k -1 个结点的二叉树称为满二叉树。 特点:(1)每一层的结点数都达到最大结点数。(2)叶子结点在最大层。(3)任一结点，其左、右分支下的子孙的最大层次相等。
2.树的性质公式
<1>带有n 个顶点的树含有n-1条边
<2>带有i 个内点的满m 叉树有n=mi+1个顶点
<3>一个满m 叉树若有
1 n 个顶点，则有i=（n-1）/m 个内点和l=[(m-1)n+1]/m 个树叶；
2 i 个内点，则有n=mi+1个顶点和l=(m-1)*i+1个树叶；
3 l 个树叶，则有n=(ml-1)/(m-1)个顶点和i=(l-1)/(m-1)个内点；
<4>在高度为h 的m 叉树中至多有m k 个树叶。
<5>若一棵树高度为h 的m 叉树带有l 个树叶，则h ≥[log m l].若这棵m 叉树是满的且平衡的，则
h=[log m l].(这里[]向上取整)。
2.二叉树的八个性质
<1> n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种
<2> n层二叉树的第n层最多为2^(n-1)个结点
<3>二叉树节点计算公式 N = n0+n1+n2，度为0的叶子节点比度为2的节点数多一个。N=1*n1+2*n2+1
<4> 对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1
<5>具有n个节点的完全二叉树的深度为log2(n) + 1
<6>深度为k 的二叉树上至多含2k-1 个结点（k≥1）<7> 具有n 个结点的完全二叉树的深度为[log2n]+1
<8> 若对含n 个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：
(1) 若i=1，则该结点是二叉树的根，无双亲, 否则，编号为?i/2?的结点为其双亲结点;
(2) 若2i>n，则该结点无左孩子，否则，编号为2i 的结点为其左孩子结点；
(3) 若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点
3.二叉树的先序、中序、后序遍历，树和二叉树、森林和二叉树之间的转换、树和森林遍历方法及对应二叉树遍历关系
先（根）序的遍历算法：
若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。中（根）序的遍历算法:
若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后（根）序的遍历算法：
若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。树转换成二叉树：任何一棵树都可以转换为一棵只有左子树的二叉树。
森林转换成二叉树
把森林中第二棵树的根节点看成是第一棵树的根节点的兄弟，则可得出森林和二叉树的对应关系。树的遍历可有3条搜索路径:
先根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。
后根(次序)遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点
按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。
森林的遍历
先序遍历中序遍历
若森林不空，则访问森林中第一棵树的根结点; 先序遍历森林中第一棵树的子树森林;
先序遍历森林中(除第一棵树之外)其余树构成的森林。
即：依次从左至右对森林中的每一棵树进行先根遍历。若森林不空，则中序遍历森林中第一棵树的子树森林; 访问森林中第一棵树的根结点;
中序遍历森林中(除第一棵树之外)其余树构成的森林。
即：依次从左至右对森林中的每一棵树进行后根遍历。
5.Huffman树的特点、构造方法、利用Huffman树求Huffman编码的方法。Huffman树的特点
(1)没有度为1的结点
(2)n个叶子结点的哈夫曼树共有2n-1个结点
(3)哈夫曼树任意非叶借点的左右树交换后仍是哈夫曼树
构造方法
二叉树 T
i 中只有一个权值为 w
i
的根结点。
(2)在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。
(3)在 F 中删除这两棵树，同时将新得到的二叉树加入集合 F 中。
(4)重复 (2) 和 (3) ，直到 F 中只含一棵树为止。
利用Huffman树求Huffman编码的方法
例， A , B , C , D 前缀编码可以为 0
, 110 , 10 , 111
利用二叉树设计二进制前缀编码。
叶子结点表示 A , B , C , D 这 4 个字符
左分支表示‘0’，右分支表示‘1’
从根结点到叶子结点的路径上经过的二进制符
号串作为该叶子结点字符的编码
路径长度为编码长度
第七章图
1.图的定义、连通图、完全图等概念。
图是由顶点的有穷集合和顶点之间的集合组成，通常表示为：G( V, E),其中，G表示一个图，V是G 中顶点的集合(又穷非空集合),E是图G中边的集合(可以为空集)。并且，图是一种相较线性表和树更加复杂的数据结构。
图的分类：
无向图：图中任意两个顶点之间的边都是无向边(表示方法: (A, D)或者(D, A))
无向完全图：无向图中，任意两个顶点都存在边(边数：count = n*(n - 1)/2 )
有向图：图中任意两个顶点之间的边都是有向边(表示法
有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧，含有e=n(n-1) 条弧
简单图：图中，若不存在顶点到其自身的边，且同一条边不重复出现
稀疏图：有很少条边或者弧的图
稠密图：有很多条边或者弧的图 (相对于稀疏图来说)
网：带权的图
子图：假设两个图G = (V,{E})和G' = (V',{E'}),如果V'属于V，并且E'属于E则称G'为G的子图
图顶点与边之间的关系：
①无向图中，某一顶点的度为该顶点相关联的边的总数目TD(v)
②有向图中，某一顶点的度包括：入度ID(v)和出度OD(v)
③树的根结点和任意结点的路径是唯一的，但是图中顶点和顶点之间的路径是不唯一的
连通图相关定义：
无向图：连通图：任意两个顶点之间有路径
连通分量：无向图中的极大连通子图(子图、子图连通、子图含极大顶点数、含依附于顶点的所有边) 生成树：是一个极小的连通子图，含有图中全部n个顶点，和n-1条边
有向图：强连通图：任意两个顶点V和W之间存在V -> W和W -> V的弧
有向图的强连通分量：有向图中极大连通子图
有向树：有向图恰有一个顶点的入度为0，其余顶点的入度均为1
3.图的深度（DFS）和广度优先（BFS）遍历方法
深度优先遍历，类似于树的先序遍历。假设给定初态是图中所有顶点均未被访问过，从图中某一顶点vi出发遍历图中的定义如下：首先访问出发点vi，并将其访问标志置为1；然后，从vi出发点依次搜索vi的每个邻接点vj。如vj未被访问过，则以vj为新的出发点继续进行深度优先搜索。
广度优先遍历，类似于树的按层次遍历。设图G是连通的，且图G的初态是所有顶点均未被访问过。从图G的任一顶点vi出发按广度优先搜索遍历图的步骤是：访问vi后，依次访问与vi邻接的所有顶点w1,w2,w3......wn，再按w1,w2,w3......wn的顺序访问其中每个顶点的所有未被访问的邻接点，再按此顺序，依次访问它们所有未被访问的邻接点，以此类推，直到图中所有顶点均被访问过为止。
4.图(或网)的存储（邻接表、邻接矩阵）方法及特点
<1>邻接表
邻接链表表示法对图中的每个顶点建立一个带头的边链表；第i条链表代表依附于顶点vi所有边信息，若为有向图，则表示以顶点vi为弧尾的边信息。邻接链接可以分为两部分，表头结点定义了顶点信息，随后的边链表表达了关于此顶点边信息。所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表。
存储空间：对于有n个顶点，e条边的无向图而言，需要n个表头结点和2e个边链表结点。
度、出度和入度：
无向图顶点度的概念是依附于该结点的边的个数。从边链表表示法中可以很容易的计算顶点的度，即对应边链表结点的个数。
有向图顶点的出度是以该顶点为弧尾的弧的个数。同理，入度是以该顶点为弧头的弧的个数。在邻接链表表示法中，有向图顶点的出度为对应边链表结点的数目。有向图顶点的入度计算比较复杂，必须要遍历整个邻接链表才能得出结果。一种解决方法是再建立一个逆邻接表法，或者采用十字链表法。
<2>邻接矩阵法
对于包含n个顶点的图，建立一个n×n的矩阵arc;用arc[i][j]的取值表示弧
的信息。
矩阵中第i行表示图的顶点vi与其他顶点的弧信息;
对于无权图而言，若弧存在则对应元素为1,否则为0；有权图而言，弧存在即为弧的权重，否则为无穷大；
最开始的无向无权图的邻接矩阵表示法如下：
存储空间：
对于无向图而言，邻接矩阵为一个对称矩阵，我们只需要存储矩阵下三角即可，因此对于包含n个顶点的图，只需要n(n?1)2个存储空间。而对于有向图，则需要n2个存储空间。
度、出度与入度：
针对无权图：无向图顶点的度，即为第i行的所有元素和。
有向图顶点的出度，即为第i行的所有元素和；入度为第i列的所有元素和。
5.最小生成树的概念及求法
最小生成树:权值最小的那颗生成树
最小生成树的性质:
<1>最小生成树并不唯一,准确的来说是最小生成树的树形并不唯一
<2>最小生成树的权值之和唯一,并且是最小的
<3>最小生成树的边数=顶点数-1
求最小生成树有两种经典算法:普里姆算法(prim)和克鲁斯卡尔(kruskal)算法
普里姆算法的基本思想：
从连通网络 N = { V, E }中的某一顶点 u
0 出发, 选择与它关联的具有最小权值的边 ( u
, v ),
将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。时间复杂度：邻阶矩阵储存：O(n2)邻接表储存：O（n+e）克鲁斯卡尔算法的基本思想：
先构造一个只含n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。时间复杂度: O(elog e) e为网的边的数目
6.拓扑排序和关键路径。
拓扑排序
1) 无环图：
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。
所有的工程或者某种流程都可以分为若干个小的工程或者阶段，称这些小的工程或阶段为“活动”。
DAG图表示一个工程，其中有向边表示约束关系。这种有向图必须是无环的。如果出现了环（有向环），那么向前递推，环路上的任一子工程开始的先决条件必然是自己，显然矛盾的。如果设计出这样的工程图，工程无法进行。拓扑排序就是测试一个工程能否顺利进行。
若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样的有向图称为AOV(Activity On Vertex network) 网。在 AOV 网中，若从顶点 v i 到顶点 v j 之间存在一条有向路径，称顶点 v i 是顶点 v j 的前趋，或者称顶点 v j 是顶点 v i 的后继。
2）对 AOV 网进行拓扑排序的方法和步骤如下：
（1）从 AOV 网中选择一个没有前趋的顶点（该顶点的入度为 0 ）并且输出它；
（2）从网中删去该顶点，并且删去从该顶点发出的全部有向边；
（3）重复上述两步，直到剩余网中不再存在没有前趋的顶点为止。
3）操作的结果有两种：
一种是网中全部顶点都被输出，这说明网中不存在有向回路，拓扑排序成功；
另一种是网中顶点未被全部输出，剩余的顶点均有前趋顶点，这说明网中存在有向回路，不存在拓扑有序序列。
4）算法：
为了避免在每一步选入度为零的顶点时重复扫描表头数组，利用表头数组中入度为零的顶点域作为链栈域，存放下一个入度为零的顶点序号，零表示栈底，栈顶指针为 top ，寄生在表头数组的入度域中的入度为零的顶点：
拓朴排序算法梗概如下：
（1）扫描顶点表，将入度为零的顶点入栈；
（2）While ( 栈非空 ) { 将栈顶点 v j 弹出并输出之；
在邻接链表中查 v j 的直接后继 v k ，把 v k 的入度减 1 ，若 v k 的入度为零则进栈；}
5）算法的时间复杂度
对一个具有 n 个顶点， e 条边的网来说，初始建立入度为零的顶点栈，要检查所有顶点一次，执行时间为 O(n) ；排序中，若 AOV 网无回路，则每个顶点入、出栈各一次，每个表结点被检查一次，因而执行时间是 O(n+e) 。所以，整个算法的时间复杂度是 O(n+e) 。
关键路径
若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续时间），则此带权的有向图称为边表示活动的网,简称 AOE 网。
1) AOV 网具有的性质
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
（2）只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。（3）表示实际工程计划的 AOE 网应该是无环的，并且存在唯一的入度过为 0 的开始顶点和唯一的出度为 0 的完成顶点。
2）关键活动：
由事件 v j 的最早发生时间和最晚发生时间的定义 , 可以采取如下步骤求得关键活动 :
（1）从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。
Ve(k)=max{ve(j)+dut()} 其中dut(表示顶点Vj到顶点Vk所持续的时间；
j ∈ T 其中 T 是以顶点 v k 为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。
如果得到的拓朴有序序列中顶点的个数小于网中顶点个数 n ，则说明网中有环，不能求出关键路径，算法结束。
（2）从完成顶点 v n 出发，令 vl(n)=ve(n) ，按逆拓朴有序求其余各顶点的允许的最晚发生时间 : vl(j)=min{vl(k)-dut()} k ∈ S 其中 S 是以顶点 v j 是头的所有弧的尾顶点集合(1≤j≤n-1)。（3）求每一项活动 a i (1≤i≤m) 的最早开始时间 e(i)=ve(j) ；最晚开始时间l(i)=vl(k)-dut() 若某条弧满足 e(i)=l(i) ，则它是关键活动。求出 AOE 网中所有关键活动后，只要删去 AOE 网中所有的非关键活动，即可得到 AOE 网的关键路径。这时从开始顶点到达完成顶点的所有路径都是关键路径。一个 AOE 网的关键路径可以不止一条。
3）注意:
并不是加快任何一个关键活动都可以缩短整个工程完成的时间，只有加快那些包括在所有的关键路径上的关键活动才能达到这个目的。只有在不改变 AOE 网的关键路径的前提下，加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间
第九章查找
1.顺序表查找的平均查找长度:ASL=（n+1）/2
2.二分（折半）查找的过程:取中点int（n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N.
3.动态查找和静态查找的概念
查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表。
4.二叉排序树、平衡二叉树的定义及构造
二叉排序树（BST）定义是：二叉排序树是空树或者满足如下性质的二叉树：
<1>若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
<2>若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
<3>左、右子树本身又是一棵二叉排序树。
二叉排序树的插入、建立、删除的算法时间复杂度是O（nlog
n）。
2
构造
(1)二叉排序树的图示
右面面是二叉排序树的图示，通过它可以加深对二
叉排序树的理解。
(2)二叉排序树常见的操作及思路
下面是二叉排序树常见的操作及思路。
(2-1)插入节点
思路：比如我们要插入数字20到这棵二叉排序树中。
那么步骤如下：
（1首先将20与根节点进行比较，发现比根节点小，
所以继续与根节点的左子树30比较。
（2发现20比30也要小，所以继续与30的左子树10
进行比较。
（3发现20比10要大，所以就将20插入到10的右子
树中。
此时的二叉排序树如右图：
(2-2)查找节点
比如我们要查找节点10，那么思路如下：
（1还是一样，首先将10与根节点50进行比较，发现比根节点要小，所以继续与根节点的左子树30进行比较。
（2发现10比左子树30要小，所以继续与30的左子树10进行比较。
(2-3)删除节点
删除节点的情况相对复杂，主要分为以下三种情形：
（1删除的是叶节点(即没有孩子节点的)。比如20，
删除它不会破坏原来树的结构，最简单。如图所示。
（2删除的是单孩子节点。比如90，删除它后需要将它的孩子节点与自己的父节点相连。情形比第一种复杂一些。
（3删除的是有左右孩子的节点。比如根节点50。这里有一个问题就是删除它后，谁将作为根节点？利用二叉树的中序遍历，就是右节点的左子树的最左孩子。
平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。
平衡二叉树的构造
在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树
5.哈希表的构造（除留余数法）、解决冲突的方法（线性探测再散列法、二次探测再散列法）
哈希表的构造（除留余数法）
设定哈希函数为:H(key)= key MOD p(p≤m)其中,m为表长,p为不大于m的素数或是不含20以下的质因子
解决冲突的方法（线性探测再散列法、二次探测再散列法）
开放定址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=（H（key）+di）%m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。
（1）线性探测再散列
dii=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
（2）二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 +1）% 11 =4，仍然冲突，再找下一个哈希地址为H2=（3 +2）% 11 =5，还是冲突，继续找下一个哈希地址为H3=（3 +3）% 11 =6，此时不再冲突，将69填入5号单元，参图(a)。如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 =4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 =2，此时不再冲突，将69填入2号单元，参图(b)。
第十章排序
1.排序的分类
排序的分类：排序分为插入排序、选择排序、交换排序、归并排序四大类
七大经典排序：冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序
2.堆排序、希尔排序、归并排序、快速排序的排序过程
堆排序
堆( Heap )设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它
们从根开始，自顶向下，同一层自左向右，从 1开始连续编号。若满足K
i ≤K
2i
&&K
i
≤K
2i+1
或K
i
≥K
2i
&&K
i
≥
K
2i+1
,则称该关键字集合构成一个堆。前者成为最小堆，后者称为最大堆。过程：1.将序列构造成一棵完全二叉树；
2.把这棵普通的完全二叉树改造成堆，便可获取最大值；
3.输出最大值；
4.删除根结点，继续改造剩余树成堆，便可获取次大值；
5.输出次大值；
希尔排序（Shellsort）的名称源于它的发明者Donald Shell，它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而缩小，直到只比较相邻元素的最后一趟排序为止。由于这个原因，希尔排序有时候也叫缩小增量排序。
过程：我们把 h1,h2,...,ht叫做增量序列。只要h1=1，任何增量序列都是可行的。在使用增量hk的一趟排序后，对于每一个i有A[i]<=A[i+{h_k}]，即所有相隔hk的元素都被排序。此时称数组是hk排序的。有两点需要说明，- h1必须要等于1，假设h1=2，那么最后排序的结果是：奇数位置上的排序，偶数位置上的排序，而整体未必排序。- 一个hk排序数组保持它的hk
排序性，也就是说，后面的排序不能破坏前面的排序结果。
3-排序后，位置0,3,6,9,12;1,4,7,10;2,5,8,11上的元素分别被排序；
1-排序后，位置0,1,2,3,4,5,6,7,8,9,10,11,12上的元素被排序。
增量序列的一种流行选择是使用希尔建议的序列：ht=[N/2]和hk=hk+1/2（这不是最好的增量序列）。其中一趟hk排序的作用就是对独立的hk个子数组进行排序，与插入排序一样，为了性能。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
过程：(1)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
(2)设定两个指针，最初位置分别为两个已经排序序列的起始位置。
(3)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
(4)重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。快速排序是对冒泡排序的一种改进。
快速排序的基本思想:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
过程：快速排序分为数组划分和递归排序两个过程。
<1>数组划分
选取一个基值，将数组分为大于基值以及小于基值两部分，并返回基值所在位置以利用于递归划分。
对数组a，设需要划分的一段为a[p]~a[r]，我们期望得到一个q，其中p<=q<=r，使得a[p]~ a[q-1] <=a[q]<= a[q+1]~a[r]，这个时候原先的一段数组被分成了三部分。我们可以设基值为这段数组的第一个元素a[p]。然后令i=p+1，j=r。当a[j]>=x时，j--；当a[j]
<2>递归排序
在对整个数组进行了划分后，我们将数组分成了两部分，一部分比基值小，一部分比基值大，并且我们知道了基值所在的位置，因此只需对划分出来的两部分进行递归排序即可。
排序过程如下：
原序列： 6 8 1 4 5 3 7 2
以6为基准：3 2 1 4 5 6 7 8 //交换2与8，交换3与6 以3为基准：1 2 3 4 5 6 7 8 //交换3与1
以1为基准：1 2 3 4 5 6 7 8 //无需交换
3.堆排序的适用情况
若n较大，则应采用时间复杂度为O(nlog2(n))的排序方法：快速排序、堆排序或归并排序。
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。优先队列通常用堆排序来实现。
4.各类排序算法的稳定性及时间和空间复杂度
小学语文1－6年级阅读知识点汇总 解题步骤 1．通读文章，了解主要内容，揣摩中心思想。 2．认真通读所有题目，理解题意，明确题目的要求。 3．逐条解答，要带着问题，仔细地阅读有关内容，认真地思考、组织答案。4．检查，看回答是否切题，内容是否完整，语句是否通顺，标点是否正确。 主要题型及其解题方法 第一部分：词语 一、某句话中某个词换成另一个行吗为什么 动词：不行。因为该词准确生动具体地写出了…… 形容词：不行。因为该词生动形象地描写了…… 副词：如（如：都，大都，非常只有等）：不行。因为该词准确地说明了……的情况（表程度，表限制，表时间，表范围等），换了后就变成……，与事实不符。 （注：有些是可以换的，不要一律写不能换，要根据题目看看具体能不能哦！） 二、动词理解。 XX生动表现了人（事）物XX的特点（情状）（或描绘出一幅……的场景），反映了人物……的心情 三、一句话中某两三个词的顺序能否调换为什么 答：不能。因为： （1）与人们认识事物的（由浅入深、由表入里、由现象到本质）规律不一致；（2）该词与上文是一一对应的关系； （3）这些词是递进关系，环环相扣，不能互换。 （注：有些是可以的，不要一律写不能，要根据题目看看具体能不能哦！） 第二部分：句子 一、句子分析
这样的题目，句子中往往有一个词语或短语用了比喻、对比、借代、象征等表现方法。答题时，把它们所指的对象揭示出来，再联系上下文，围绕主题，挖掘出句子深层含义，再整理一下自己的语言就可以了。 例题：请问文中划线部分用了怎样的修辞手法，表达了作者怎样的心情 修辞的分析： （1）它本身的作用； （2）结合上下文，分析句子里词语的表达效果。 （3）答题格式：修辞+结合上下文，修辞的作用 A、比喻、拟人：生动形象； 答题格式：把XX比作（把XX拟人化）XX，生动形象地写出了（事物）……的特点，表达了（人物）…… B、排比：有气势、加强语气、一气呵成等； 答题格式：应用排比句能使句式更整齐，更有气势，强调了（事物）的……，突出了（事物）……的特点 C、设问：引起读者注意和思考； 答题格式：开头出现，其作用通常为“设置悬念，吸引读者” 文中或结尾出现，其作用通常为“引起了对……的问题的关注（或引人深思），给人以启迪，突出了文章的主旨” D、对比：强调了……突出了…… E、反复：强调了……加强语气 F、反问：强调，加强语气等； 答题格式：这个反问句的意思是……，以强烈的语气表达了（人物）……的感情 G、借代：用XX代XX，使被借代的更加具体，生动表达了什么感情或特点 H、引用：引用诗句，其作用通常为“增强文章的诗情画意，使文章语言更优美（或引用诗句是为了说明……）” 引用故事，神话传说，其作用通常为“增强文章的趣味性，吸引读者” 二、某句话在文中的作用 1、文首：开篇点题；渲染气氛（记叙文、小说）；埋下伏笔（记叙文、小说）；设置悬念（小说）；为下文作辅垫；总领下文； 2、文中：承上启下；总领下文；总结上文； 3、文末：点明中心（记叙文、小说）；深化主题（记叙文、小说）；照应开头（议论文、记叙文、小说） 三、仿写句子。 公式： ①数清例句的字数。? ②弄清例句所采用的修辞手法（没有修辞手法的除外）。? ③读懂例句与所要仿写的句子在概念和现象上的联系。 第三部分：段落篇章词语 一、标题作用 （1）全文的线索，推动情节发展 （2）总结文章内容，点名主旨（突出主题）
925 数据结构 1、绪论。（1）掌握相关的基本概念，如数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等；（2）掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度和空间复杂度的方法；（3）了解使用类 C 语言描述算法的方法。 2、线性表。（1）掌握线性表的逻辑结构和存储结构；（2）掌握线性表在顺序结构和链式结构上实现基本操作的方法；（3）理解线性表两种存储结构的不同特点及其适用场合，会针对需求选用合适的存储结构解决实际问题；（4）了解一元多项式的表示方法和基本运算的实现方法。 3、栈和队列。（1）了解栈和队列的特点；（2）掌握在两种存储结构上栈的基本操作的实现；（3）掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；（4）掌握循环队列和链队列的基本运算；（5）会应用队列结构解决实际问题。 4、串。（1）掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法；（2）了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种操作的方法；（3）理解 KMP 算法，掌握 NEXT 函数和改进 NEXT 函数的定义和计算。 5、数组和广义表。（1）掌握数组在以行为主和以列为主的存储结构中的地址计算方法；（2）掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法；（3）理解广义表的定义及其存储结构，理解广义表的头尾和子表两种分析方法。 6、树和二叉树。（1）熟练掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及构建方法；（2）掌握按先序、中序、后序和层次次序遍历二叉树的算法，
理解二叉树的线索化实质和方法；（3）利用二叉树的遍历求解实际问题；（3）掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法；（4）掌握建立最优二叉树和哈夫曼编码的方法。 7、图。（1）熟练掌握图的基本概念，会构建各种图的存储结构；（2）掌握深度优先搜索遍历图和广度优先搜索遍历图的算法；（3）灵活运用图的遍历算法求解各种路径问题，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。 8、查找。（1）熟练掌握各种静态查找和动态查找算法，会计算查找成功时和失败时的平均查找长度；（2）掌握二叉排序树的建立、插入和删除过程，掌握二叉平衡树的建立和旋 转平衡方法；（3）掌握 B-树的建立、插入和删除结点的过程；（4）熟练掌握哈希表的构造方法和处理冲突的方法。 9、排序。（1）掌握各种排序算法，包括插入类、交换类、选择类、归并类排序及基数排序；（2）能够对各种排序方法进行比较分析，如稳定性、时间和空间性能等，了解各种排序方法的特点和不同并灵活应用；（3）理解外部排序的主要思想和过程。
数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
小学语文知识体系汇总 一、拼音 1、基础知识回顾：23个声母、24个韵母、16个整体认读音节。 2、声调：分为四声。标调歌：“有a 不放过，无a 找o、e ,i、u 并列标在后” 3、音节：音节是声母、韵母和声调的组合。 (1)当韵母“u”和声母“j、q、x、y”相拼时，去掉“u”头上的两点，如“ju”。 (2)人或事物等专用名词的拼音，第一个字母大写，如“北京Beijing” 4、隔音符号：当a、o、e 开头的音节连接在其他音节后面，读音易发生混淆时， 应在第一个音节后面加上隔音符号，用“’”表示，帮助分清两个音节。 如“ping’an（平安）”、“qi’e（企鹅）”。 二、汉字 1、笔画与笔顺规则 “先横后竖（十），先撇后捺（八），从上到下（景），从左到右（树），从外到内（同），从内到外（函），先里面后封口（国），先中间后两边（水）。” 2、偏旁部首和间架结构（7种结构） 独体字（中）、左右结构（秋）、左中右结构（做）、上下结构（恩）、上中下结构（翼）、全包围和半包围结构（园、区）、品字形结构（晶） 3、无声的老师——字典（3种查字方法） （1）“音序查字法”的步骤：认准字音；定字母、翻索引；查音节、找汉字。 （2）“部首查字法”的步骤：定部首、翻索引；数余画；查汉字。 部首查字法的规则：上下都有，取上不去下； 左右都有，取左不取右； 内外都有，取外不取内。 独体字一般将字的第一画作为其部首。 （3）“数笔画查字法”的步骤：数准笔画数；翻索引、查‘难检字索引’；找汉字。 4、形近字（8种表现形式）——理解记忆法、口诀记忆法 （1）笔画相同而位置不同“由”和“甲” (2)字形相似但笔形不同“外”和“处” （3）字形相似但偏旁不同“晴”和“睛” （4）字形相似但笔画数量不同“今”和“令” （5）结构单位相同但位置不同“陪”和“部” （6）形近音相同“很”和“狠” （7）形近音相近“清”和“情” （8）形近音不同“贫”和“贪” 5、多音字：字形相同，读音不同。如“塞”、“露”、“咽”。 同音字：音同形不同。如“燥”和“躁”。 6、多义字：有两种或两种以上意思的字。 如：“张”(1)展开（2）看、望（3）陈设（4）姓 三、词语 实词：名词（木）、动词（跑）、形容词（美丽）、数词（一）、量词（位）、代词（你、我、他们） 1、词性划分 虚词：副词（特别、不）、介词（在、关于）、连词（和）、助词（着、的、啊）、象声词（叮咚） 2、近义词和反义词 （1）意思相同的词：“爸爸——父亲”、“互相——相互” （2）意思相近的词：
姓名 ： 报 考 专 业 ： 准考 证号码 ： 密 封 线 内 不 要 写 题 2019年全国硕士研究生招生考试初试自命题试题 科目名称：数据结构（C 语言版）（□√A 卷□B 卷）科目代码：856 考试时间：3小时 满分150分 可使用的常用工具：□√无 □计算器 □直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共15小题，每小题2分，共30分) 1. 计算算法的时间复杂度是属于一种（ ）的方法。 A ）事前统计 B ）事前分析估算 C ）事后统计 D ）事后分析估算 2. 数据的逻辑结构可以分为（ ）。 A ）静态结构和动态结构 B ）物理结构和存储结构 C ）线性结构和非线性结构 D ）虚拟结构和抽象结构 3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A ）必须是连续的 B ）部分地址必须是连续的 C ）一定是不连续的 D ）连续不连续都可以 4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。 A ）使空表和非空表的处理统一 B ）可以加快对表的遍历 C ）节省存储空间 D ）可以提高存取表元素的速度 5. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear 和front 的值分别为（ ）。 A ）1和5 B ）2和4 C ）4和2 D ）5和1 6. 对二叉树T 中的某个结点x ，它在先根序列、中根序列、后根序列中的序号分别为pre （x ），in （x ）、post （x ），a 和b 是T 中的任意两个结点，下列选项一定错误的是（ ）。 A ）a 是b 的后代且pre （a ）