第一章 概论
1、若结点的存储地址与其关键字之间存在某种映射关系则称为：散列存储结构。
2、数据类型通常称为原子型和结构型。索引存储：附加索引表。关键字是能唯一标识一个元素的一个数据项或多个数据项的组合。
3、抽象数据类型是指数据逻辑结构及与之相关的操作
第二章 线性表
4、顺序表便于按号查结点
5、顺序表中插入一个元素平均需要移动n/2 删除一个元素平均需要移动（n-1)/2
6、最节省时间的存储结构式：仅有尾指针的单循环链表，带头结点的双循环链表。
7、将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。
8、在第i个元素之前插入一个新元素需要进n-i+1次移动，在第i个元素之后插入一个新元素需要后移n-i个元素。
9、单链表中每个结点的存储地址是存放在其直接前驱结点的指针域中
10、在双链表中要删除已知结点*p，其时间复杂度为O（1）
第三章 栈和队列
11、循环队列出队列：（front+1）%m 入队列：（rear+1）%m 循环队列元素个数：（rear-front+m)%m
12、栈的链式存储结构：不需要判断栈满单需要判断栈空。顺序存储结构：既需要判断栈空也需要判断栈满且需要置空栈。
13、递归实现和函数调用时，处理参数及返回地址，应采用的数据结构是堆栈。
14、初始top为n+1，则X入栈操作：top=top-1; V[top]=X;
第四章 多维数组和广义表
15、二维数组Am*n按行优先顺序存储公式：LOC(aij) = LOC(a00) + (i*n+j)*d
16、三位数组Am*n*p按行优先顺序存储公式：LOC(aijk) = LOC(a000)+(i*n*p+j*p+k)*d
17、应许结点共享的表称为再入表。广义表的深度：展开后所含括号的层数。
18、稀疏矩阵的三元组表是顺序存储结构
19、广义表表头和表尾深度相同，则广义表深度+1，不同则为深度最深。
20、 假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为5n-6(n>5)。
第五章 ：树和二叉树
1、二叉树的性质
21、一个结点拥有的子树称为该树的度，一棵树中结点的最大度称为该树的度。
22、度为零的结点称为叶子结点或终端结点，树中的最大层次称为该树的深度或高度
23、在二叉树的第i层上至多有2i-1个节点，深度为K的二叉树至多有2k-1个结点。
24、对任何一棵二叉树T，若其终端结点数为n0,度数为2的节点数为n2 ,则n0=n2+1
25、满二叉树：一颗深度为k且有2k-1个结点的二叉树成为满二叉树.
26、完全二叉树：若一棵深度为K的二叉树，其前k-1层是一个满二叉树，而下一层（即第k层）上的结点都集中在该层最左边的若干位置上，则称为完全二叉树
27、具有n个结点的完全二叉树的深度为logn+1或者log(n+1)。
28、已知一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中叶子结点为11
29、含有3个结点a,b,c的二叉树，前序序列a,b,c且后序序列为cba的二叉树共有4棵。
30、哈夫曼树：带权路径长度最短的树。哈夫曼树一个有2n-1个结点。
31、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则二叉树的高度一
定为n.
32、一棵左子树为空的二叉树的前序线索化后，其空指针为2。
33、在左右子树均不空的先序线索二叉树中，空链域的数目是1。
34、一棵树的后序遍历等价于该二叉树的中序遍历。
35、森林：m棵互不相交树的集合。若将一棵树的根结点删除，就得到该树构成的森林。
36、N个顶点的生成树有n-1条边。一个带权的无向连通图的最小生成树有一颗或多棵。
37、已知二叉树的中序序列和后序序列均为ABCDEF，则先序序列为FEDCBA。
38、已知一颗含有50个节点的二叉树中只有一个叶子结点，则该二叉树中度为1的结点个数为49。
39、一颗完全二叉树中含有1000个结点，则其中度为2的结点个数为499.
40、用二叉链表保存有n个结点的二叉树，则结点中有n+1个空指针域。
41、在含100个结点的完全二叉树中，叶子结点的个数为50。
42、已知完全二叉树的第4层有4个结点，则其叶子结点数是6。
43、已知完全二叉树的第7层有8个结点，则叶子结点数是32。
2、最优二叉树（哈夫曼树）
在两个节点构成的路径上的分支（边）数目称为路劲长度，而树根到树中每个结点的路径长度之和称为路径长度。完全二叉树就是这种路径长度最短的二叉树。
从树根结点到某结点之间的路径长度与该节点上权的乘积称为该结点的带权路径长度，树中所有叶子结点的带权路径长度之和称为该树的带全路径长度，通常记为：WPL = w1l1 + w2l2 + …+ wili
利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个结点都有一条路径，对路径上的各分支约定指向左子树的分支表示“0”码，指向右子树的分子表示“1”码，取每条路径上的“0”或“1”的序列作为每个叶子结点对应的字符编码，这就是哈夫曼编码。
第六章 图
44、无向图边或弧e的取值范围0~n(n-1)/2 有向图边或弧的取值范围0~n(n-1)
45、深度优先算法（DFS）遍历类似于树的前序遍历。广度优先遍历（BFS）类似于树的按层遍历
时间复杂度 | 空间复杂度 | ||
深度优先算法（DFS） | 遍历类似于树的前序遍历，从顶点v出发，依次访问邻接点 | 邻接矩阵：O(n2) 邻接表：O(n+e) | |
广度优先算法（BFS） | 遍历类似于树的按层次遍历，按层带有大小顺序依次访问 | 邻接矩阵：O(n2) 邻接表：O(n+e) | O(n) |
| 二叉树公式 |
最小生成树：普利姆算法和克鲁斯卡尔算法
46、最短路径：迪杰斯特拉算法：按路径长度递增的顺序产生诸顶点的最短路径算法，图中某顶点到其他顶点的最短路径。O（n+e）
47、带权图的最短路径问题，路径长度指：路径上各边的权值之和。
48、我们把这种顶点表示活动，边表示活动间先后关系的有向无环图（DAG）称为顶点活动网，简称AOV网。在AOV网中，若不存在回路（即环），所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，此序列就是拓扑序列。由AOV网构造拓扑序列的过程称为拓扑排序。
49、对于一个具有n个顶点和e跳变的无向图，若采用邻接表表示，则表头向量的大小为n，所有邻接表中的节点数2e.
50、若无向图有n个顶点和e条边，则它的邻接表共用n个头结点和2e个表头结点。
51、在无向图中，如果对任意两个顶点Vi和Vj都连通，即从Vi到Vj和Vj到Vi都存在路径，则称图G是连通图
52、无向图的极大连通子图称为连通分量，显然，任何连通图的连通分量只有一个，就是其本身。而非连通图的无向图有多个连通分量。
53、在有向图中，如果对任意两个顶点Vi和Vj都连通，即从Vi到Vj和Vj到Vi都存在路径，则称图G是强连通图
54、有向图的极大连通子图称作有向图的强连通分量
55、在每条边上标上某种值，带权图的连通图称为网络。若图G中任意两个不同的顶点间都有路径，则称该图为连通图。
56、一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图。
57、若用邻接矩阵表示有向图，则顶点i的入度等于邻接矩阵中第i列非零元素个数。
58、N个顶点且含有回路的无向连同图中，至少含有n条边。
59、若要建立网络的邻接表，则需要在边表的每个结点中增加一个存储边上权值的数据域。
第七章 ：排序
1、排序过程中需要进行两种基本操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身。而待排序记录的存储方式一般有三种：顺序结构、链式结构和辅助表结构。评价排序算法的标准主要有两条：执行算法需要的时间，以及算法所需要的附加空间。
2、内排序：插入、选择、交换、归并和分配排序。
3、插入排序的基本思想：每次将一个待排序的记录按其关键字的大小插入到前面已排好序的文件中的适当位置，知道全部记录插入完为止。包括：直接插入排序和希尔排序。
3.1直接插入排序是一个就地排序（若排序算法所需要的额外空间相对于输入数据量来说是一个常数，则成该类排序算法为就地排序）。
最好情况 | 最坏情况 | 时间复杂度 | 空间复杂度 | 排序算法 | |
直接插入 | 正序O(n) | 逆序O(n2) | O(n2) | O(1) | 稳定 |
希尔排序 | O(nlog2n)或O(n1.25) | O(1) | 不稳定 | ||
4、交换排序的基本思想：两两比较待排序记录的关键字，如果发现两个记录的次序相反时即进行交换，知道所有记录都没有反序时为止。包括：冒泡排序和快速排序
4.1冒泡排序是相邻元素之间的比较和交换，快速排序记录关键字的比较和记录的交换是从两端向中间进行的，即该元素将比它大的和小的区分在两边，例如：23 16 35 67 36 70
最好情况 | 最坏情况 | 时间复杂度 | 空间复杂度 | 排序算法 | |
冒泡排序 | O(n2) | O(1) | 稳定 | ||
快速排序（划分交换排序） | O(nlog2n) | O(log2n) | 不稳定 | ||
5、选择排序的基本思想：每一趟在待排序的记录中选出关键字最小的记录，一次存放在已排序号的记录序列的最后，知道全部记录排序完为止。包括：直接选择排序和堆排序
5.1堆排序：完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在联系，在当前无序区中选择关键字最大（或最小）记录。堆排序正是利用大根堆（小根堆）来选取当前无序区中关键字最大（最小）的记录实现排序的。每一趟排序的操作是：将当前
无序区调整成一个大根堆，选取关键字最大的堆顶记录，将它和无序区中最后一个记录交换，这正好与选择排序相反。堆排序就是一个不断建堆的过程。
最好情况 | 最坏情况 | 时间复杂度 | 空间复杂度 | 排序算法 | |
直接选择排序 | O(n2) | O(1) | 不稳定 | ||
堆排序 | O(log2n) | O(1) | 不稳定 | ||
6、归并排序的基本思想：首先将待排序文件看成n个长度为1的有序子文件，把这些子文件两两归并，得到n/2个长度为2的有序子文件，然后再把这n/2个有序的子文件两两归并，
如此反复，知道最后得到一个长度为n的有序文件位置，这种排序方法称为二路归并排序。
最好情况 | 最坏情况 | 时间复杂度 | 空间复杂度 | 排序算法 | |
归并排序 | O(nlog2n) | O(n) | 稳定 | ||
7、分配排序：箱（桶）排序和基数排序
最好情况 | 最坏情况 | 时间复杂度 | 空间复杂度 | 排序算法 | |
基数排序 | O(d*(rd+n)) | O(n+rd) | 稳定 | ||
其中rd为基数，d是关键字的位数，n是元素个数
9、排序方法的选取：
1、若待排序的一组记录数目n较小（n<=50）时，可采用插入排序和选择排序
2、若n比较大时，则应采用快速排序、堆排序或归并排序
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论