【408】数据结构知识点（查漏补缺）

知识点大部分来自于王道课后习题中易出错知识及薄弱内容，有问题的地方欢迎朋友们指出，一起讨论学习。

第一、二、三章

1.同一个算法，实现语言的级别越高，执行效率越低；
2.顺序表是一种存储结构，与之对应的是链表；有序表是顺序表的基础上，各个元素数值大小有序；
3.顺序队列：用数组存队列（长度为n的数组最多有n - 1个元素），存在假溢出，故而有了循环队列；
4.静态链表的next是下一个元素的数组下标，动态链表的next是指针；（它的特点：要分配较大空间+插入和删除和动态链表一样只修改next；静态链表用于不支持指针的高级语言）
5.n个元素的一位数组，建立成有序单链表的最低时间复杂度：先排好序O(n log n)，再链表O(n)，总的为O(n log n)；
6.通常情况下，递归算法比非递归算法包含一些重复的计算，效率更低；

第五章 树

1.树的路径长度等于树根到每个节点的路径长度总和，根到每个节点的路径长度最大值等于树的高度 - 1；
2.二叉树是每个节点的分叉最多有2个，度为2的树是至少有一个节点有2个分叉；
3.有n个节点的二叉树用二叉链存储节点，空指针数为n+1；
4.一棵有124个叶子节点的完全二叉树，最多有248个节点（不是247，因为第8层有120 + 1个叶子节点，即第7层最右边4个叶子节点的最左边可以有一个左孩子）；
5.二叉树中m是n的祖先，则后序遍历可找到从m到n的路径；
6.二叉树是一种逻辑结构，线索二叉树（链表结构）是一种存储结构，即物理结构；
7.n个节点的线索二叉树上含有的线索数为n+1（空指针数）；
8.先序序列为abcd，则有1/(n+1)•C（n，2n）；
9.满二叉树转化为森林，森林中树的个数等于二叉树的高度；
10.

11.平衡二叉树的节点数递推公式：n[h]=1+n[h-1]+n[h-2]，（最少节点数），n1=1，n2=2；

第六章 图

1.图中的“路径”是指由顶点和相邻顶点构成的边所形成的序列，如1到2的路径为{<1，3>，< 3，2>}；（即路径是边的序列集合，而非顶点集合）
2.简单路径：任意顶点不重复出现的路径；简单回路：除了顶点=终点，其余顶点不重复出现；
3.n个顶点n条边的无向图一定有环，但不一定是连通的；（如5个顶点5个边）
4.图G={V，{E}}，顶点子集V’，边子集E’，则{V’，{E’}}是G的子图。这句话是错的，因为V’={1，2}，E’={ <2，3> }就不是子图，因为边集E’中包含的顶点在V’中没有找到；
5.无向图的连通分量=极大连通子图（该子图包含了与子图中的点有关的所有边）；
6.有7个顶点的无向图，要保证任何情况下都是连通的，边数最少为16（其中6个顶点构成完全图，再加一个边即可），边数最多为21；
7.一个连通无向图中有7个顶点，边至少为6；一个强连通有向图中有7个顶点，边至少为7（回路）；
8.有n个顶点和e条边的有向图用邻接表存储，则删除某顶点的所有边，时间复杂度为Ｏ(n+e)；（因为该顶点最多有n个出度，有e个入度）
9.邻接多重表是无向图的存储结构，十字链表是有向图的存储结构；
10.各边权值相等时，广度优先算法可以解决单源最短路径（从一点到其它各点的最短路径）问题；
11.n个顶点和e条边的图使用邻接表存储，则dfs（递归层数）和bfs（队列）的时复都是Ｏ(n+e)，空复都是Ｏ(n)；（此时拓扑排序的时复也是n+e）
12.n个顶点和e条边的图使用邻接矩阵存储，则dfs（递归层数）和bfs（队列）的时复都是Ｏ(n^2)，空复都是Ｏ(n)；
13.DFS算法递归遍历一个无环有向图，在退出递归时输出相应顶点，得到的是逆拓扑排序；
14.深度DFS、拓扑排序、关键路径这3个方法可以判断出一个有向图是否有环；
15.若有向图的拓扑排序序列唯一，则每个节点的入度和出度最多为1。这句话是错的，但反过来是对的，最多为1可以推序列必是唯一的；
16.若有向图不能排成一个拓扑序列，则该有向图必是含有顶点数大于1的强连通分量；
17.有向无环图的拓扑序列唯一，也不能唯一确定该图；

第七章 查找

1.折半查找和二叉排序树的时间性能比较，要对比两树的高度；
2.对于6505个元素建立索引顺序表（OS中的概念，多条记录构成一个组，每个组对应一个索引表项），则最好情况下共需要16次比较，即每组255个元素，共255组，组内和组间都用折半查找，则需要log(255+1) + log(255+1) = 16次比较；
3.有n个关键字的m阶Ｂ树，应有n+1个叶节点（失败节点）；
4.散列查找是关键字由散列函数计算出该元素存储位置，从而直接定位查找，时复为Ｏ(1)；
5.在使用开放定址法处理冲突之后，删除某元素时，不是直接删除，而是做删除标记，否则会导致搜索路径被中断；

第八章 排序

1.对任意n个关键字排序的比较次数至少为log(n!)（向上取整）；
2.折半插入和直接插入的不同点在于减少了比较的次数，但移动的次数不变，因此时复都是Ｏ(n^2)；
3.稳定的算法：直接插入、冒泡、归并、基数；
4.不稳定的算法：简单选择、希尔、快排、堆排序；
5.每趟都会有一个元素确定位置的有：简单选择排序、冒泡排序、快排、堆排序；
6.与原始序列是否有序无关的算法：简单选择、堆排序、归并排序、基数排序；
7.与原始序列是否有序有关的算法：插入排序、快排、冒泡；
8.在最后一趟开始之前，所有元素都不在最终位置上：直接插入；
9.平均空复为Ｏ(n)的算法：归并；最环情况下空复为Ｏ(n)的算法：归并、快排（平均空复为Ｏ(log n)）；
10.堆排序的时复：建堆Ｏ(n)，调整堆Ｏ(log n)，共调用调整堆n-1次，故时复为Ｏ(n) + Ｏ(n log n) = Ｏ(n log n)；
11.在有n个节点的堆中插入（需要向上调整）和删除元素，时复都为Ｏ(log n)；
12.各有n个元素的有序表合并成一个有序表，最少的比较次数为n，最多的比较次数为2n-1（依次间隔比较，注意与时间复杂度区分开来）；
13.排序的趟数与序列原始状态有关的算法：冒泡、快排；

• 计划任务