数据结构知识点
1. 非线性结构就是数据元素之间存在**一种多对多关系**
2. ~~数据结构中与所使用得计算机无关得就是数据得逻辑结构~~
> 在数据结构中，与所使用的计算机无关的是 **数据的逻辑结构**
3. ~~算法分析得目得就是分析算法得效率以求改进~~
> 算法分析的目的是 **分析算法的效率以求改进**
4. 算法分析主要是分析**空间复杂性**与**时间复杂性**两个主要方面。
5. 计算机算法指得就是解决问题得有限运算序列
> 计算机算法指的就是**解决问题的有限运算序列**
6. 计算机算法必须具备**输入**、**输出**与**可行性**、**确定性**与**有穷性**等5个特性。
7. 若长度为n得线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度O(n)
> 线性表的删除和插入操作的时间复杂度都为O（n）.
8. 若一个线性表中最常用的操作就是取第i个元素与找第i个元素的前趋元素，则采用**顺序表存储方式**最节省时间。
9. 具有线性结构的数据结构就是**栈**
> 是限定仅在表尾进行插入或删除操作的线性表。栈是一种后进先出(Last In First Out)/先进后出的线性表，简称为LIFO
10. 在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动 **n–i+1** 个元素。
11. 一个栈得输入序列为:a,b,c,d,e,则栈得不可能输出得序列就是** d,c,e,a,b**
12. 设计一个判别表达式中括号就**是否配对的算法**，采用**栈数据结构**最佳。
13. 带头结点的单链表head为空的判定条件就是 **head->next==NULL**
14. 一个栈的输入序列为:1，2，3，4，则栈的不可能输出得序列就**4312**
15. 若用一个大小为6的数组来实现循环队列，且当rear与front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear与front得值分别为**2与4**
16. 队列的插入操作就是在队尾
> 是只允许在表的一端进行插入，而在另一端进行删除的运算受限的线性表。其所有的插入均限定在表的一端进行，该端称为队尾（Rear）；所有的删除则限定在表的另一端进行，该端则称为队头（Front）。
17. 设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作**模式匹配**
> 模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。
18. 已知串S='aaab'，则next数组值为0123。
> next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。本质是求字符所在位是迄今第几次出现。
19. 串与普通的线性表相比较，它的特殊性体现在**数据元素就是一个字符**
20. 设串长为n，模式串长为m，则KMP算法所需得附加空间为**O(m)**
21. 空串与空格串不相同
22. 与线性表相比，串的插入与删除操作的特点就是**通常以串整体作为操作对象**
23. ~~二叉树的深度为k,则二叉树最多有2k-1个结点~~。（）
> 一颗深度为k的二叉树,最多有(2^k)-1个节点,第k层最大节点数为2^（k-1）
24. 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1….N]中，若结点R[i]有右孩子，则其右孩子就是**R[2i+1]**
25. 设a,b为一棵二叉树上得两个结点，在**中序遍历时**，a在b前面的条件就是**a在b的左方**
> 中序遍历（LDR） 先左子树，后根结点，最后右子树
26. 设一棵二叉树的中序遍历序列：badce,后序遍历序列：bdeca，则二叉树先序遍历序列为abcde
> 先序：考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)
> 中序：考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)
> 后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)
27. 在一棵具有5层的满二叉树中结点总数为**31**
>一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
28. 对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小是n（n+1）/ 2
> 逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵