计算机保研专业课必备之数据结构_数据结构与算法保研

数据结构保研面试准备

1. 算法的五大特征

   • 有穷性——有限的步骤
   • 确定性——不可二义性
   • 可行性——每一步都是通过执行有限次数完成的
   • 输入——零个或多个输入
   • 输出——至少有一个或多个输出

2. O(n)的大O是什么意思？什么是时间复杂度?

   大O表示的是最坏情况下的时间复杂度，对算法运行时间的度量。

3. 循环队列元素个数、队满、队空表示？

   元素个数：(rear+MaxSize-front)%MaxSize

   队满：(rear+1)%MaxSize==front

   队空：front==rear

4. B+树与B树的区别

   • B+树中具有n个关键字的结点只含有n棵子树。每个结点关键字个数的范围是|m/2| <= n <= m
     B树中具有n个关键字的结点含有n+1棵子树。每个结点关键字个数的范围是|m/2| -1<= n <= m-1

   • B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。

   • B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

   • 由于B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，可以利用空间局部性，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快。

5. 红黑树原理是什么？建立过程？

   红黑树特点：根叶黑，不红红，黑路同。

   红黑树应用：Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

   红黑树的插入：

   • 先查找，确定插入位置（原理同二叉排序树），插入新结点；新结点是根——染为黑色；新结点非根——染为红色；若插入新结点后依然满足红黑树定义，则插入结束；
   • 若插入新结点后不满足红黑树定义，需要进行调整，使其重新满足红黑树定义；
     如何调整？看新结点叔叔的颜色：
     黑叔：旋转+染色【对新结点所在子树进行旋转，对原先的儿、父或爷进行颜色的更换，旋转规则和颜色更换规则取决于新结点作为孙子结点的子树形态属于LL型、RR型、LR型、RL型中的哪一种，如下】；
     LL型：右单旋，父换爷+染色【父、爷进行颜色的更换】；
     RR型：左单旋，父换爷+染色【父、爷进行颜色的更换】；
     LR型：左、右双旋，儿换爷+染色【儿、爷进行颜色的更换】；
     RL型：右、左双旋，儿换爷+染色【儿、爷进行颜色的更换】；
     红叔：染色+变新【对叔、父、爷都进行颜色的更换，爷结点因此而变成新结点，然后再看看是否影响了红黑树的定义，看看还要不要操作什么】

6. [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SWQeskKj-1668767278969)(C:\Users\ThinkPad\AppData\Roaming\Typora\typora-user-images\image-20220908105913923.png)]

7. 贪心算法和动态规划区别？

   • 贪心算法：做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，的到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。
   • 动态规划：把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。

8. 介绍一下字符串匹配算法：朴素的匹配算法和 KMP 算法，它们的实现过程如何？

   • BF：将主串为n中所有⻓度为 m 的⼦串依次与模式串对⽐，直到找到⼀个完全匹配的⼦串，或所有的⼦串都不匹配为⽌，最多对比n - m + 1 次。
   • KMP：利用匹配失败后的信息，尽量减少子串与主串的匹配次数以达到快速匹配的目的

9. 哪些图算法中用到了动态规划的思想?

   首先图算法有：DFS、BFS、Prim、克鲁斯卡尔、迪杰斯特拉、弗洛伊德、拓扑排序、关键路径。

10. 树和图的区别

    树是分层结构，图是网络模型结构；

    树有根节点，图没有根节点的概念；

    树的边数为节点数减一，图的边数没有限制；

    树不能有环，图可以有。

11. 散列表的查找效率取决于三个因素

    散列函数、处理冲突的方法和装填因子