1. 一个算法不是程序，而是问题求解步骤的描述
2. 一算法的时间复杂度是O(n²)，表明该算法的执行时间与n²成正比，而问题规模还是n
3. 算法原地工作的含义是指算法需要的额外的辅助空间是常数
4. 在相同规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O(n²)的算法
5. 所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界
6. 同一个算法，实现语言的级别越高，执行效率越低
7. 对于一个线性表，既要求能够快速的进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用链式存储结构
8. 线性表最常用的操作是在最后一个结点之后插入一个结点或删除一个结点，则采用仅有尾结点指针的存储结构最节省时间
9. 两个长度为n的单链表，循环单链表和非循环单链表占用的存储空间是一样的（非循环单链表也有尾指针，只不过是NULL而已） 
10. 若长度为n的非空线性表采用顺序存储结构，在表的低i个位置插入一个数据元素，则i的合法值应该是1<=i<=n+1（顺序表从1开始）顺序表的插入算法中，当n个空间已满是，可再申请增加分配m个空间，若申请失败，则说明系统没有n+m个连续的可分配的存储空间
11.  链式存储结构比顺序存储结构能更方便表示各种逻辑结构
12. 静态链表需要分配较大的连续空间，插入和删除不需要移动元素
13. 若用单链表表示队列，则应该选用带尾指针的循环链表
14. 单链表中，增加一个头结点的目的是方便运算的实现
15. 为了方便插入和删除数据，可以使用双链表存放数据

1. C语言标识符的第一个字符必须是大小写字母或者下划线，不能是数字
2. 采用非递归方式重写递归程序时也不一定必须要使用栈，例如斐波那契数列不用递归只要写一个循环就行
3. 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是4,1,3,2。能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是4,2,1,3。既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的是4,2,3,1
4. 栈的典型应用包括：递归，进制转换，迷宫求解
5. 执行函数时，其局部变量一般采用栈结构进行存储
6. 对于数组的操作，最常见的是查找和修改
7. 
   

1. KMP算法中主串的i不用回溯，意味着对于规模较大的外存中字符串的匹配操作可以分段进行，先读入内存一部分进行匹配，完成之后即可写回外存，确保在发生不匹配时不需要将之前写回外存的部分再次读入，减少了I/O操作，提高了效率
2. 简单模式匹配算法的时间复杂度为O(mn），而KMP算法的时间复杂度为O(n+m)

1. 树的路径长度是从树根到每个结点的路径长度的总和
2. 在二叉树中，若某个结点只有一个孩子，则这个孩子的左右次序是确定的；而在度为2的有序树中，若某个结点只有一个孩子，则这个孩子就无需区分其左右次序；
3. 在二叉排序树中插入结点时，一定插入在叶节点的位置，故若先删除分支节点再插入，则会导致二叉排序树的重构，结果不再相同
4. 完全二叉树度为1的结点只能是1个或者0个
5. 二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，即它是二叉树在计算机内部的存储结构，故是一种物理结构
6. n个结点共有链域指针2n个，其中除根结点外，每个结点都被一个指针指向，剩余的链域建立线索，供n+1个线索
7. 在线索二叉树中，不是每个结点通过线索都可以直接找到它的前驱和后继。在先序线索二叉树中查找一个结点的先序后继很简单，而查找先序前驱必须知道该结点的双亲结点。同样，在后续线索二叉树中查找一个结点的前驱也很简单，而查找后序后继也必须知道该结点的双亲结点
8. 先序序列和中序序列的关系是：以先序序列入栈，则出栈序列必为中序序列
9. 用逐点插入法构造二叉排序树，若先后插入的关键字有序，二叉排序树的深度最大
10. 
    

1. 图中有关路径的定义是：由相邻顶点序偶对所形成的序列。
2. 若图中没有边，单个顶点就是一个连通分量。
3. 图的遍历是从给定的源点出发，每一个顶点仅被访问一次。
4. 图的深（广）度遍历也适用于有向图
5. 用深度优先遍历或拓扑排序的方法可以确定图中是否有环。
6. 对于含有n个顶点的带权连通图，他的最小生成树是指由n个顶点构成的边的权值之和最小的连通子图。
7. 回路不一定是简单路径，只有回路中除了开始顶点和结束顶点相同以外其余顶点都不相同的路径才是简单路径。
8. 若有向图中存在拓扑序列，则该图不存在回路
9. 设图G的邻接矩阵为A，则Aⁿ的元素Aⁿ[i][j]等于由顶点i到顶点j的长度为n的路径的数目
10. 若一个有向图的邻接矩阵的对角线以下的元素为0，则该图的拓扑序列必定存在
11. 邻接多重表是无向图的存储结构：邻接多重表就是解决了邻接表存无向图时候一条边存两次的问题，所以实际上它的链结点里会把无向边的两个端点在数组里的索引都存进去，已经没法用来表达有向图了。
12. 十字链表是有向图的存储结构
13. 一个无向图是一棵树的条件是有n-1条边的连通图；判断顶点和边的关系直接用图的信息判断，判断连通与否可以用遍历能否访问到所有顶点来判断
14. 图的DFS和BFS适用于所有的图，没有限制有向图或无向图
15. 深度优先遍历和拓扑排序方法可以判断出一个有向图是否有环
16. 当各边上的全职均相等时，BFS算法可用来解决单源最短路径问题
17. 最短路径一定是简单路径
18. Djikstra算法适合求解有回路的带权图的最短路径，也可以求任意两个顶点的最短路径，而不适合求带负权值最短路径问题
19. 若有向图的拓扑排序唯一，图中每个顶点的入度和出度不一定最多是1，例如下图其拓扑排序唯一，但是出度和入度可能大于一
20. 求关键路径是以拓扑排序为基础的
21. 关键活动一定位于关键路径上
22. 若改变所有关键路径上的公共活动，不一定会产生不同的关键路径（延长必然不会导致产生新的关键路径，缩短有可能产生新的关键路径
23. 
    

第八章 排序

第九章 查找

1. B树和B+树都能有效的支持随即查找；B树和B+树都是平衡的多叉树；B树和B+树都可以用于文件检索结构
2. 但是由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找
3. 冲突是不可避免的，与装填因子无关
4. 散列查找成功的平均查找长度与装填因子有关，与表长无关
5. 在开放定址的情形下，不能随便删除散列表中的某个元素，否则可能会导致搜索路径被中断
6. 开放定址法中散列到同一个地址而产生的“堆积”问题，是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起的现象
7. 采用再散列法处理冲突时不易发生聚集
8.