计算机保研专业课必备之数据结构
数据结构保研面试准备
-
TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
红黑树的插入：
- 先查找，确定插入位置（原理同二叉排序树），插入新结点；新结点是根——染为黑色；新结点非根——染为红色；若插入新结点后依然满足红黑树定义，则插入结束；
- 若插入新结点后不满足红黑树定义，需要进行调整，使其重新满足红黑树定义；
如何调整？看新结点叔叔的颜色：
黑叔：旋转+染色【对新结点所在子树进行旋转，对原先的儿、父或爷进行颜色的更换，旋转规则和颜色更换规则取决于新结点作为孙子结点的子树形态属于LL型、RR型、LR型、RL型中的哪一种，如下】；
LL型：右单旋，父换爷+染色【父、爷进行颜色的更换】；
RR型：左单旋，父换爷+染色【父、爷进行颜色的更换】；
LR型：左、右双旋，儿换爷+染色【儿、爷进行颜色的更换】；
RL型：右、左双旋，儿换爷+染色【儿、爷进行颜色的更换】；
红叔：染色+变新【对叔、父、爷都进行颜色的更换，爷结点因此而变成新结点，然后再看看是否影响了红黑树的定义，看看还要不要操作什么】
-
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SWQeskKj-1668767278969)(C:\Users\ThinkPad\AppData\Roaming\Typora\typora-user-images\image-20220908105913923.png)]
-
贪心算法和动态规划区别？
- 贪心算法：做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，的到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。
- 动态规划：把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。
-
介绍一下字符串匹配算法：朴素的匹配算法和 KMP 算法，它们的实现过程如何？
- BF：将主串为n中所有⻓度为 m 的⼦串依次与模式串对⽐，直到找到⼀个完全匹配的⼦串，或所有的⼦串都不匹配为⽌，最多对比n - m + 1 次。
- KMP：利用匹配失败后的信息，尽量减少子串与主串的匹配次数以达到快速匹配的目的
-
哪些图算法中用到了动态规划的思想?
首先图算法有：DFS、BFS、Prim、克鲁斯卡尔、迪杰斯特拉、弗洛伊德、拓扑排序、关键路径。
-
树和图的区别
树是分层结构，图是网络模型结构；
树有根节点，图没有根节点的概念；
树的边数为节点数减一，图的边数没有限制；
树不能有环，图可以有。
-
散列表的查找效率取决于三个因素
散列函数、处理冲突的方法和装填因子
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！