17、 应许结点共享的表称为再入表。广义表的深度：展开后所含括号 的层数。
18、 稀疏矩阵的三元组表是顺序存储结构
19、 广义表表头和表尾深度相同，则广义表深度+1，不同则为深度最 深。
20、 假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q 中，则数组Q的大小至少为5n-6(n>5)。
后一个记录交换，这正好与选择排序相反。堆排序就是一个不断建堆的 过程。
最好情况 最坏情 时间复杂度 空间复杂 排序算法
况
度
直接选择 排序
O(n2)
O(1)
不稳定
堆排序
O(log2n)
O(1)
不稳定
6、归并排序的基本思想：首先将待排序文件看成n个长度为1的有序子 文件，把这些子文件两两归并，得到n/2个长度为2的有序子文件，然后 再把这n/2个有序的子文件两两归并， 如此反复，知道最后得到一个长度为n的有序文件位置，这种排序方法 称为二路归并排序。
3.1直接插入排序是一个就地排序（若排序算法所需要的额外空间相 对于输入数据量来说是一个常数，则成该类排序算法为就地排序）。
最好情 最坏情
况
况
时间复杂度
空间复杂 排序算法 度
直接插 正序
入
O(n)
逆序 O(n2)
O(n2)
O(1)
稳定
希尔排 序
O(nlog2n)或 O(n1.25)
O(1)
不稳定
4、 交换排序的基本思想：两两比较待排序记录的关键字，如果发现两 个记录的次序相反时即进行交换，知道所有记录都没有反序时为止。包
按层次遍历，按
O(n2)
层带有大小顺序 邻接表：
依次访问
O(n+e)
最小生成树：普利姆算法和克鲁斯卡尔算法 46、 最短路径：迪杰斯特拉算法：按路径长度递增的顺序产生诸顶点
的最短路径算法，图中某顶点到其他顶点的最短路径。O（n+e） 47、 带权图的最短路径问题，路径长度指：路径上各边的权值之和。 48、 我们把这种顶点表示活动，边表示活动间先后关系的有向无环图
括：冒泡排序和快速排序
4.1冒泡排序是相邻元素之间的比较和交换，快速排序记录关键字的比 较和记录的交换是从两端向中间进行的，即该元素将比它大的和小的区
分在两边，例如：23 16 35 67 36 70
最好情况 最坏情 时间复杂度 空间复杂 排序算法
况
度
冒泡排序
O(n2)
O(1)
稳定
快速排序（划分交换 排序）
38、 已知一颗含有50个节点的二叉树中只有一个叶子结点，则该二叉 树中度为1的结点个数为49。
39、 一颗完全二叉树中含有1000个结点，则其中度为2的结点个数 为499.
40、 用二叉链表保存有n个结点的二叉树，则结点中有n+1个空指针 域。
41、 在含100个结点的完全二叉树中，叶子结点的个数为50。 42、 已知完全二叉树的第4层有4个结点，则其叶子结点数是6。 43、 已知完全二叉树的第7层有8个结点，则叶子结点数是32。 2、 最优二叉树（哈夫曼树）
动（n-1)/2 6、 最节省时间的存储结构式：仅有尾指针的单循环链表，带头结点
的双循环链表。 7、 将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储
单元里，用这种方法存储的线性表称为顺序表。 8、 在第i个元素之前插入一个新元素需要进n-i+1次移动，在第i个元素
之后插入一个新元素需要后移n-i个元素。 9、 单链表中每个结点的存储地址是存放在其直接前驱结点的指针域
O(nlog2n) O(log2n) 不稳定
5、选择排序的基本思想：每一趟在待排序的记录中选出关键字最小的 记录，一次存放在已排序号的记录序列的最后，知道全部记录排序完为 止。包括：直接选择排序和堆排序
5.1堆排序：完全二叉树的顺序存储结构，利用完全二叉树中双亲结 点和孩子结点之间的内在联系，在当前无序区中选择关键字最大（或最 小）记录。堆排序正是利用大根堆（小根堆）来选取当前无序区中关键 字最大（最小）的记录实现排序的。每一趟排序的操作是：将当前无序 区调整成一个大根堆，选取关键字最大的堆顶记录，将它和无序区中最
第7章 ：排序
1、 排序过程中需要进行两种基本操作：比较两个关键字的大小、改变 指向记录的指针或移动记录本身。而待排序记录的存储方式一般有三
种：顺序结构、链式结构和辅助表结构。评价排序算法的标准主要有两 条：执行算法需要的时间，以及算法所需要的附加空间。 2、 内排序：插入、选择、交换、归并和分配排序。 3、 插入排序的基本思想：每次将一个待排序的记录按其关键字的大小 插入到前面已排好序的文件中的适当位置，知道全部记录插入完为止。 包括：直接插入排序和希尔排序。
,则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。
中 10、 在双链表中要删除已知结点*p，其时间复杂度为O（1）
第3章 栈和队列
11、 循环队列出队列：（front+1）%m 入队列：（rear+1）%m 循环队 列元素个数：（rear-front+m)%m
12、 栈的链式存储结构：不需要判断栈满单需要判断栈空。顺序存储 结构：既需要判断栈空也需要判断栈满且需要置空栈。
利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中 从根到每个结点都有一条路径，对路径上的各分支约定指向左子树的分 支表示“0”码，指向右子树的分子表示“1”码，取每条路径上 的“0”或“1”的序列作为每个叶子结点对应的字符编码，这就是哈夫曼编 码。
第6章 图
44、 无向图边或弧e的取值范围0~n(n-1)/2 有向图边或弧的取值范围 0~n(n-1)
45、 深度优先算法（DFS）遍历类似于树的前序遍历。广度优先遍历 （BFS）类似于树的按层遍历
时间复遍历类似于树的 前序遍历，从顶 点v出发，依次访
问邻接点
邻接矩阵： O(n2)
邻接表： O(n+e)
广度优先算法 遍历类似于树的 邻接矩阵：
O(n)
（BFS）
查询成功时平均长度：ASL=((n+1)/n) * log2(n+1) - 1 ，二分查找的 最坏性能和平均性能相当接近。
二分查找速度快快，效率高，适用于表不易改动且又经常查找的情 况。时间复杂度：O(log2n) 3、 索引顺序查找（分块查找）：是一种介于顺序查找和二分查找之间 的查找方法。
在表中插入或删除一个记录时，只要找到该记录所属的块，就可以 在该块内进行插入或删除运算。插入或删除记录时无需移动大量记录。 缺点：需要一个辅助数组的存储空间，不适宜用链式存储结构。时间复 杂度：O(n的开根号) 4、 散列表查找：1 散列存储中使用的函数H(key)称为散列函数或哈希 函数。它实现关键字到存储地址的映射。H(key)的值称为散列地址或哈 希地址，使用的数组空间是线性表进行散列存储的地址空间，被称为散 列表或哈希表2处理冲突的方法：a、开放定址法 b、拉链法
在两个节点构成的路径上的分支（边）数目称为路劲长度，而树根 到树中每个结点的路径长度之和称为路径长度。完全二叉树就是这种路 径长度最短的二叉树。
从树根结点到某结点之间的路径长度与该节点上权的乘积称为该结 点的带权路径长度，树中所有叶子结点的带权路径长度之和称为该树的 带全路径长度，通常记为：WPL = w1l1 + w2l2 + …+ wili
第8章 ：查找
1、顺序查找：
顺序查找成功时的平均查找长度约为表长的一半：ASL=(n+1)/ 2，查 找最多需要n+1次。
如果查找成功和不成功机会相等，那么顺序查找的平均查找长 度：3/4*(n+1)
优点：简单，且对表的结构无任何要求，无论是顺序存储还是链式 存储，无论是否有序，都适用。缺点：效率低。时间复杂度：O(n) 2、二分查找：又称折半查找，效率较高。二分查找要求查找对象的线 性表必须是顺序存储结构的有序表。
第5章 ：树和二叉树
1、 二叉树的性质 21、 一个结点拥有的子树称为该树的度，一棵树中结点的最大度称为
该树的度。 22、 度为零的结点称为叶子结点或终端结点，树中的最大层次称为该
树的深度或高度 23、 在二叉树的第i层上至多有2i-1个节点，深度为K的二叉树至多有
2k-1个结点。 24、 对任何一棵二叉树T，若其终端结点数为n0,度数为2的节点数为n2
最好情况 最坏情 时间复杂度 空间复杂 排序算法
况
度
归并排序
O(nlog2n)
7、 分配排序：箱（桶）排序和基数排序