数据结构易错知识点（九推）

╰半橙微兮° 2021-12-11 22:17 284阅读 0赞

**写在前面：** 这篇博文是为接下来九推的笔面试做准备的，用来记录自己模糊易错的知识点，会不断整理，删掉掌握的，增加不熟悉的，一直更到保研结束为止。

--------------------

之前整理的一些概要：

--------------------

2019.7.19

*  栈是实现过程和函数等子程序所必需的结构
 *  堆排序是一种树形选择排序，是对直接选择排序的有效改进。
 *  有的非线性结构也可以采用顺序存储结构，比如二叉树
 *  要连通具有n个顶点的有向图,至少需要n条边，无向图的话就是n-1条边
 *  无联系、无序的数据没有必要使用指针相连接，不适合用树表示
 *  数组名当被直接使用时，是一个指向数组首地址的指针。如果数组是多维数组，那么数组名是指向第一行数组的首地址，而不是第一行第一列单个元素的地址，所以`*(a+i)与a[i]`是一个意思，当直接用`a[i]`时代表的是该一维数组的首地址，所以`*(a[i]+j)是与a[i][j]`等效
 *  线性表的两种存储结构有什么优缺点？  
    顺序存储是按索引（如数组下标）来存取数据元素，优点是可以实现快速的随机存取，缺点是插入与删除将引起元素移动，降低效率。对于链式存储，元素存储采取动态分配，利用率高。缺点是须增设指针域，存储数据元素不如顺序存储方便。有点是插入和删除操作简单，只需修改指针域。
 *  利用GetHead和GetTail操作，从广义表((((apple),pear),banana),orange)中得出banana。  
    设L=((((apple),pear),banana),orange)  
    GetHead（GetTail(GetHead(L))）
 *  栈与队列的区别和共同点是什么？图的深度优先搜索和广度优先搜索分别适用上述哪种结构，并简单说明理由？  
    1）区别：栈在表尾进行插入和删除，具有“后进先出”的特点；队列在表尾插入，在表头删除，具有“先进先出”的特点  
    2）图的深度优先探索适用栈，节点需要后进先出；图的广度优先探索适用队列，节点需要先进先出。
 *  贪心算法：  
    贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
 *  动态规划算法：  
    1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解  
    2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解  
    3.边界条件：即最简单的，可以直接得出的局部最优解

2019.8.7

*  深度为n的二叉树最多有2的k次方-1的结点
 *  当执行出队操作时，一般只需要修改队头指针即可，但当只有一个元素时，head==rear需要同时修改队头和队尾指针，不然会溢出。
 *  使用贪心算法的有：  
    [单源最短路径中的Dijkstra算法][Dijkstra]：和最小生成树中的prim算法很像  
    [最短路径Floyed算法和Dijkstra算法详解练习题][Floyed_Dijkstra]  
    [对dijkstra和Floyd算法的理解][dijkstra_Floyd]  
    [最小生成树的Prim算法（点角度）][Prim]：比起kruskal更适用于边很多的情况。  
    [最小生成树的Kruskal算法（边角度）][Kruskal]
 *  单链表将p插入q结点后面时，先把p->next=q->next, q->next=p;
 *  [希尔排序][Link 2]
 *  ![在这里插入图片描述][20190617231804229.png] \- 折半查找属于随机访问特性 链表不行  
    堆排序也不能用链表 因为调整堆时没法随机访问底层孩子节点  
    快速排序可以链表  
    归并排序可用链表  
    基数排序可用链表  
    插入排序链表比数组要快一些 减少移动次数
 *  稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
 *  如何判断循环队列Q是空还是队满？  
    `Q.front==Q.rear;`//不行，因为空满无法判断  
    `Q.front==(Q.rear+1)%Maxsize;`//可以
 *  深度优先搜索算法：按照某种条件试探搜索，如果前进中遭失败，则退回头另选通路继续，直到找到条件的目标为止。适合使用递归来实现。假设树的定点数为V，则算法的空间复杂度为O（V）
 *  广度优先搜索算法：先访问该节点的所有子节点，遍历完毕选取它未访问过的子节点重复上述过程，直到找到目标为止。
 *  下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在(\[n/2\]+2)位置上：小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点位置大于\[n/2\]
 *  逻辑运算符与（&&）有做结合性，先算左再算右，且若左表达式的值未假（0），则右表达式**不参与**运算。
 *  引用类型再堆上分配，值类型在栈上分配。值类型不会被垃圾回收，值类型不需要指针来引用。
 *  B-树是一颗平衡多叉树，是排序树，m阶B-树也就是是树的度为m，即节点最大的子节点数目为m，是一棵m叉平衡排序数。
 *  B-树
    
     *  每个结点最多有M个分支（子树）；而最少分支树要看是否为根结点，如果是根结点且不是叶子结点则至少有两个分支，非根非叶结点至少有m/2（向上取整）个分支。
     *  有n （k<n<m）个分支的结点有n-1个关键字，他们按递增顺序排列。k=2（根结点）或m/2（向上取整，非根结点）
     *  结点内关键字互不相等
     *  叶子节点处于同一层（相当于空指针）
     *  B-树的阶数是人为规定的，不要和最多的关键字搞混了，不要以为最多是3个关键字就是3阶，依然可以是5阶的。
     *  Pi所指的关键字小于Keyi+1 大于Keyi
 *  B-树与B+树的区别：
    
     *  B-树是一个空位置一个分支，B+树是一个关键字一个分支。
     *  B+树中，每个结点（除根结点以外）中的关键字个数n的取值范围为![在这里插入图片描述][20190901094718869.png]而B-树中，它们的取值范围是![在这里插入图片描述][20190901094815412.png]
     *  B+树种叶子结点包含信息，并且包含全部关键字，叶子结点引出指向记录
     *  B+树中所有非叶子结点仅仅起到一个索引作用，即结点中的每个索引只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址；而在B树中，每个关键字对应一个记录的存储地址。
     *  B+树中有一个指针指向关键字最小的叶子结点，所有叶子节点连接成一个线性链表，也就是说可以顺序查找，而B-树没有。
 *  递归是栈实现的。栈是先进后出,也就是上次递归调用的时候,保存在栈顶,  
    在返回的时候出栈,所以是递归是依靠栈实现的.  
    PS: 非递归形式的深度优先搜索要用栈,而广度优先使用了队列。
 *  一棵平衡二叉树一定是二叉排序树
 *  二分查找严格按照下表（lo+hi）/2来算 不要自己瞎想
 *  [AOV网络和AOE网络][AOV_AOE]
 *  遍历二叉树的算法中的基本操作是访问结点，则不论按哪一种次序进行遍历，对n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n,则空间复杂度也为O(n)。
 *  define是在预处理阶段就替换了 直到结束
 *  树转换成二叉树  
    将 节点的孩子 放在左子树；  
    将 节点的兄弟 放在右子树。
 *  快（快速排序）些（希）来选（选择排序）一堆（堆排序）美女–不稳定

2019.8.9

*  [关于哈希表的一些知识点（线性探测、二次探测等）][Link 3]
 *  散列表的装填因子等于关键字总数/表长

2019.8.10

资料：  
[一篇文章搞定面试中的二叉树题目(java实现)][java]  
[几道和「二叉树」有关的算法面试题][Link 4]  
[二叉树的递归与非递归遍历][Link 5]

2019.8.28

*  二叉树的定义  
    把满足以下两个条件的树形结构叫做二叉树  
    （1）每个节点的度都不大于2；  
    （2）每个节点的孩子节点次序不能任意颠倒。
 *  二叉树的应用  
    二叉排序树、平衡二叉树（具体需查）
 *  [动态规划以分治法的区别][Link 6]
 *  动态查找和静态查找有什么区别
    
     *  静态查找（顺序查找，二分查找，斐波那契），只是查找这个元素是否存在，不会对结构产生影响。
     *  动态查找（二叉排序树，平衡二叉树），先查找是否存在，如果不存在，则可以进行插入操作，若存在，则可以进行删除操作，对表的结构可能产生影响。
 *  栈和堆的区别
    
     *  栈是一种先进后出的线性表，只要符合先进后出的原则的线性表都是栈。至于采用的存储方式（实现方式）是顺序存储（顺序栈）还是链式存储（链式栈）是没有关系的。
     *  堆则是二叉树的一种，有最大堆最小堆，排序算法中有常用的堆排序。

[_ 1-5]: https://blog.csdn.net/qq_43145926/article/details/98737505
[Link 1]: https://blog.csdn.net/qq_43145926/article/details/96728736
[_ _]: https://blog.csdn.net/qq_43145926/article/details/97126620
[_ _ 1]: https://blog.csdn.net/qq_43145926/article/details/97136858
[_ _ 2]: https://blog.csdn.net/qq_43145926/article/details/96995918
[Dijkstra]: https://blog.csdn.net/cjc211322/article/details/24933909
[Floyed_Dijkstra]: https://blog.csdn.net/C20180602_csq/article/details/52850104
[dijkstra_Floyd]: https://blog.csdn.net/qq_42391248/article/details/82228155
[Prim]: https://blog.csdn.net/fzl1941572592/article/details/75213380
[Kruskal]: https://blog.csdn.net/mgsky1/article/details/77840286
[Link 2]: https://blog.csdn.net/changhangshi/article/details/82744427
[20190617231804229.png]: /images/20211211/90a1bb668d8446398998cf79ef3e4770.png
[20190901094718869.png]: https://img-blog.csdnimg.cn/20190901094718869.png
[20190901094815412.png]: /images/20211211/7433f58b7ee94bedbb9cf00829dce92a.png
[AOV_AOE]: https://blog.csdn.net/leelitian3/article/details/84728838
[Link 3]: https://blog.csdn.net/qq_27093465/article/details/52269862
[java]: https://www.jianshu.com/p/0190985635eb
[Link 4]: https://mp.weixin.qq.com/s/AHmQN920hLar85T6PHZhoA
[Link 5]: https://blog.csdn.net/zhangxiao93/article/details/52734630
[Link 6]: https://blog.csdn.net/qq_40674821/article/details/86364504