.webp)
cs保研经验贴|数据结构
保研资料：数据结构
数据结构按某种逻辑关系将一批数据元素组织起来，按一定的存储方式将它们存储起来，并在这些数据元素上定义一个操作集合,就得到了一个特定的数据结构。
数据的逻辑结构逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。线性结构：线性表。只有一个始末，每个内节点只有一个前驱和后继。线性表：数组，链表，栈，队列非线性结构：层次结构（树，叶节点可能有多个）、网状结构（图）、集合。节点可能有0、多个前驱和后继。
数据的存储结构数据结构在计算机中的表示，也称物理结构。分为：顺序存储、链接存储、散列存储、索引存储。邻接表：顺序存储的顶点表+链接存储的边链表。邻接表利于找邻接顶点。
数据结构的使用跳表：logn层有序链表，最底层包含所有元素。插入后以1/2递减的概率向上插入，适合动态查找场景。实现方式：四联表。拉链法很长时，使用红黑树。哈希表用途：bool过滤器。树是分层结构，图是网络模型结构；树有根节点，图没有根节点的概念；树的边数为节点数减一，图的边数没有限制；树不能有环，图可以有。红黑树中的每一个结点的颜色不是黑色就是红色。根结点和所有外部结点（NULL节点、叶 ...
.webp)
cs保研经验贴|离散数学
保研资料：离散数学
关系笛卡尔积：设A,B是两个集合，所有有序对（x，y）做成的集合称为笛卡尔积。其中x来自A，y来自B。关系：集合ABC的一个子集F称为A,B,C上的一个n元关系。存储：关系矩阵、关系图。传递性：等价于R²包含于R。空关系：反自反、对称性、反对称性、传递性；空集合上的额外多出自反性。可用谓词、蕴含式证明。商集：以R的所有不同等价类为元素构成的集合。商集是集合的一个划分。最大元是最小上界；在集合中的上界必是最大元。（最大元、极大元在集合中；上界未必在集合中）。极大元对有限部分序集必存在，但未必唯一。完备的偏序集：有最小元、每一个链有上确界（或仅含有穷链）。一个偏序集是一个全序集，如果它本身是一条链。A包含于B，当且仅当A的幂集包含于B的幂集。
范式G与其stolen范式S的可满足性、恒假性等价。主合取范式（存在且唯一）、主析取范式（存在且唯一）；前束范式、skolem范式（首标中无存在量词、母式为合取范式）。有限个短语的析取式：析取范式。主析取范式由极小项组成：一个短语包含所有原子，且排列顺序与原始顺序一致。利用主合取范式、主析取范式可求解判定问题：判断命题公式是否等 ...
.webp)
cs保研经验贴|英文面试
保研资料：英文面试
自我介绍Good morning, dear professors. I’m very honored to be here for this interview. My name is *** and I major in Cyberspace Security Engineering in XX University.I will introduce myself from the following three aspects:
First of all, I think studying is the most important thing in University.I’m hardworking and self-disciplined,so I am the thrid-ranked student in my major.Also, I was honor to have a The First Prize Scholarship and School Outstanding Student from XX University.
Second ...
.webp)
cs保研经验贴|线性代数
保研资料：线性代数
基本知识线性代数的基本问题：方程组求解、最小二乘、特征值、奇异值。线性代数是关于线性空间和线性映射的代数学。线性映射（ linear mapping）是从一个向量空间V到另一个向量空间W的映射，且保持加法运算和数量乘法运算，而线性变换（linear transformation）是线性空间V到其自身的线性映射。线性空间：V是一个非空集合，F是一个数域，定义加法和数乘，且满足八条公理化定义，则称V为F上的线性空间，V中元素称为向量。V中的极大线性无关组称为一个基，个数称为V的维数。正定矩阵的所有顺序主子式的值大于0，特征值大于0。可逆变换保正定性。二次型存在标准型及规范型。二阶是指最高阶只有二阶即y”常系数是指y”, y’,y前面的系数p,q是常数线性是指微分方程中只包含y及其各阶导数的一次幂项（y’，y’‘）,或含这些一次幂项与x的各种运算组合构成的混合项。但是，不含y及其各阶导数的高次幂项,也不含y及其各阶导数之间的混合项。例如：只含ay、by’、cxy”一类的项,不含ayy、byyy、cyy’、fxyy”一类的项.（abcf为常数）。齐次是指微分方程中不含常数 ...
.webp)
cs保研经验贴|操作系统
保研资料：操作系统
OS实现什么？有效地管理系统中软件硬件资源（处理器、存储、设备、文件）；提供计算机用户与计算机硬件之间的接口，使计算机系统更易于使用。操作系统特性：并发性、共享性、异步性、虚拟性（虚拟存储管理技术扩充内存空间；虚拟设备管理把独占型设备改造成共享的设备。）。PSW：CPU运算器的一部分，存放两类信息：一类是体现当前指令执行结果的各类状态信息，如有无进位、有无溢出、结果正负、结果是否为0等；一类是存放控制信息，如允许中断、屏蔽字、中断码等。并发进程：间断性、非封闭性、不可再现性。并发执行的条件：Bernstein条件。软件互斥算法一般适用于单处理机系统，多机环境下可并行执行的指令的效果可能是重排序执行的结果，会不满足互斥性。硬件互斥：存储障碍、原子变量、测试并设置、交换、关中断（仅在单CPU有效）。多CPU下, 指令周期间交叉, test_and_set, swap指令不是原子的。同步机制：信号量与PV操作、管程、会合（被调用者代调用者执行调用代码，适合分布式环境）、事件。
进程特征：并发性、动态性、独立性（可以调度）、交互性、异步性（进程各自独立的速度向前推进）、结 ...
.webp)
cs保研经验贴|概率论与数理统计
保研资料：概率论与数理统计
名词解释无偏性：估计量的无偏性指的是，估计量的数学期望等于被估计参数的实际值。一致性：在样本容量逐渐增大的情况下，估计值会越来越接近参数的真实值。有效性：估计量的有效性指的是最小方差的无偏估计，估计量的方差越小，则该估计量越有效。概率：对于每一个事件A，有唯一的实数与其对应，且满足非负性，规范性（必然事件=1），可列可加性（两两不相容）。古典概型：基本事件有限等可能。伯努利概型：重复n次独立试验，每次实验只有两个可能结果。泊松定理：伯努利实验中稀有事件出现的次数近似满足泊松分布。离散分布（对应分布律）：均匀、0-1、二项（随机变量为事件发生的次数）、几何、泊松。连续型分布（对应概率密度）：均匀分布、正态分布、指数分布。当f(x,y)、fY(y)连续时，可求得X的条件概率密度函数。数学期望：对于随机变量而言，指的是在其概率意义下的加权平均值。方差：反映随机变量取值的波动程度，是随机变量与其数学期望差值平方的数学期望三阶中心矩，偏度，衡量偏离中心的点的位置情况，均值和中位数之间的距离。四阶中心矩，峰度，衡量偏离中心的点的密集程度。变量和随机变量：变量 ...
HEXO美化：弹窗、昼夜切换调用
sweetalert弹窗
step1：butterfly引入
在 inject的 bottom处加入：
1<script src="https://unpkg.com/sweetalert/dist/sweetalert.min.js"></script>
step1：nexT引入
修改 _layout.njk:
1234567891011121314151617181920212223242526<!DOCTYPE html><html lang="{{ page.lang }}"><head> {{ partial('_partials/head/head.njk', {}, {cache: theme.cache.enable}) }} {%- include '_partials/head/head-unique.n ...
MP有限状态自动机和AC自动机
模式匹配自动机
什么是有限状态自动机？定义n个不同状态，记为{1,2…n}，在状态i时输入s，达到状态j，记为goto(i,s)=j对于字符串s而言，在一个状态i下输入一个字符ch，也会达到一个指定状态 ：假定新的状态为串s[1,i]+ch的最长相等前后缀 ，便能够用这个状态机模拟KMP算法匹配字符串的过程。当字符集仅为a、b时，有：其中goto(4,a)=3，也就是说abab+a的最长相等前后缀 对应的状态是状态3 ，也即表示字符串“aba”的状态。似乎这样就足够了。我们获得了goto函数，定义为：
goto(Si,a)：串s[1,i]a的最长相等前后缀。
为了得到这个goto函数的值，我们需要定义fail函数：
fail(Si):串s[1,i]的最长相等前后缀。
因为得到goto(i,a)的前提是，知道s[1,i]的最长相等前后缀s\[1,j] ：若s[j+1]与a相同，则goto(i,a)=j+1，否则求s[1,j]的最长相等前后缀，直到长度为0。为了表示“s[j+1]与a相同”这一条件，定义函数：
follow(Si, a):状态Si输入 ...
.webp)
BM算法(手算版)
BM算法
BM算法是一种字符串匹配的算法。与KMP相比，BM算法不扫描全部输入字符，平均匹配时间c·n, 常量 c <1 (随机或真实文本), 但最坏情况是O(n·m).可以将BM算法的最坏情况改进到O(n)：通过记录文本后缀中最长的模式后缀。要使用BM算法，需要知道两个信息：1.用于坏字符规则的bc数组2.用于好后缀规则的gs数组
坏字符规则
坏字符规则分为两种情况：1.失配位置指向的文本串中对应的字符 ，不存在于模式串中。如上图所示，在这种情况下，直接将整个模式串移动到失配位置 之后。
2.失配位置指向的文本串中对应的字符 ，存在于模式串中，且在失配位置 的左边。如上图所示，在这种情况下，将模式串中的文本串中对应的字符 放在失配位置 上。需要注意两个问题：1.这个“模式串中的文本串中对应的字符 ”，是整个模式串从右往左数的第一个符合的字符。否则会造成过度左移。2.模式串中最后一个字符，不能和任何的失配位置 匹配。这是因为“失配”的前提是有匹配，而右边第一个字符必然被匹配；否则在右边第一个字符失配，那说明所需要的字符不是这个右边的第一个字符。故最后一个字符对应的位置是从右边数 ...