算法与数据结构
2.8 B树是什么?主要作用是什么? (哈工大)
B树是一种平衡的多叉树,它最初启发于二叉查找树,因为二叉查找树呢有个缺点,就是数据一多,他的深度就比较高,而你每查找一次节点就相当于访问一次磁盘,这样的话就会降低速度,B树的根本思想就是在一个节点上存更多的索引信息,也就是改二叉为多叉,减少查找时的io操作.
概率论
X是随机变量,X在[0,1]之间,E[X]=u,1>c,请证明P(X < cu)<=(1-u)/(1-cu)
缺少
两个正太分布相加是不是正太分布
简单随机事件
是指在某次随机试验中可能会出现也可能不会出现,但是在大量重复事件中具有某种规律性.
概率图模型中的三种分布 参考
联合分布
表示多维随机变量的概率分布,多个随机变量所代表的事件同时发生情况下的概率分布就是联合分布.比如P(X<1,Y<2)就是说x<1和y<2这两个事件同时发生的情况下整体概率
边缘分布
在联合分布中,单独的某一维随机变量的分布就是他的边缘分布
一旦定义了随机变量,我们就能用分布来描述X所描述的事件,这个分布就是随机变量X的边缘分布.
条件分布
对于多维随机变量,当某些变量取特定值时,其余变量的分布就是条件分布,他相当于在边缘分布的基础上增加了”其他随机变量取特定值”的限定条件
分布函数和密度函数 参考
密度函数是针对连续型随机变量而言,而分布函数是连续型和离散型随机变量都有的.
对于离散型随机变量而言,知道了分布列可以求分布函数,知道了分布函数同样可以求分布列.
对于连续型随机变量,对密度函数求积分可以得到分布函数,同样对分布函数求导可以得到密度函数
密度函数作为分布函数的导数,他的意义是随机变量X的取值落在deitax区间内的概率等于区间密度区间长度,也就是deita x密度函数(x)
随机变量独立与相关(见)
相关是指两个随机变量之间是线性相关,而独立是指两个随机变量之间没有一点关系,这个关系包括线性关系和非线性关系.
也就是说,如果两个随机变量是独立的那么他们一定不相关,但是如果他们不相关,却不一定独立,因为可能存在一种非线性的关系.
相关系数、协方差 参考
相关系数和协方差都是用来衡量两个随机变量之间的相关性.
其中,协方差呢是对两个随机变量与各自期望的差的成绩求平均得到的,也就是E( (X-EX)*(Y-EY) ),但是这样的话X和Y可能有不同的量纲,比如说同样是正比例的关系时,cov(X,Y) 和cov(2X,2Y)相差了四倍,这就容易引起误解,所以在这个基础上才引入了相关系数.
相关系数是用协方差除以X和Y的标准差从而实现标准化.可以说相关系数就是经过标准化的协方差.
高数
零点定理
1闭区间连续
2 f(a)与f(b)异号,则存在kesei属于(a,b) 使得f (kesei)=0
罗尔中值定理
1闭区间连续
2开区间可导
3 f(a) = f(b) 那么存在kesei属于(a,b) 使得f ’ (kesei)=0
拉格朗日中值定理
拉格朗日中值定理是罗尔定理的推广,同样是在闭区间连续,开区间可导的情况下,ab之间必然存在一点使得f(a)-f(b) / a-b = f’(ξ),
这实际上相当于泰勒公式的一阶展开
他的几何意义是函数在ab区间中必然存在一点,该点处切线的斜率等于a和b连线的斜率,
什么是柯西中值定理
柯西中值定理是拉格朗日中值定理的推广,他同样是在闭区间连续,开区间可导的条件下,ab之间存在一点,使得 f(a)-f(b) / g(a)- g(b) = f’(ξ) / g’(ξ) ,
实际上如果你把f (x)和 g(x)当作曲线的参数方程的话,它所表达的几何意义和拉格朗日一样,就是两端点之间的平面弧上存在一点的切线等与端点连线的斜率.
如果你令g(x) = x的话,那么柯西就成了拉氏定理.
凹凸函数
凹函数是指函数任意两点之间的连线始终在曲线的上方,他的充要条件是:函数二阶可导且f”(x)在这个区间上>=0
凸函数则相反,
函数极限,函数导数,函数极值,函数连续,函数微分,函数积分
函数极限:函数在点x0处有极限,首先需要fx在x0附近有定义,那么如果存在常数A,对于任意给定的m,总是存在一个数n , 当x位于x0-n到x0+n的区间内时,他的函数值总能满足f(x)在区间A-m到A+m之间,那么A就是函数在x0点的极限
函数导数: 函数在这一点的变化率 (可导一定连续,连续不一定可导,比如f(x)=|x| 连续但是不可导)
函数极值: 给定范围内的最大值最小值
函数微分:函数的导数乘以自变量的增量也就是dy = f’(x)*Δx,是因变量的增量的线性主部,就是delta y = dy + o(x)
函数积分: 定积分是某种特殊合式的极限,不定积分是某个函数f(x)的原函数的集合
泰勒展开
泰勒展开是用多项式去近似在x0邻域内的函数,展开越多近似的程度就越高,这样的话就相当于我们用更简单的形式去表达一个复杂的函数.泰勒公式的n阶展开呢需要函数在闭区间内有n阶导数,比如说一阶展开就是f(x)=f(x0)+f’(x0)(x-x0)+一个一阶无穷小量
开放性问题
9.1 证明一个有m个元素的数列a(全是整数),让你证明存在i<=j使得(ai+….+aj) mod m = 0.
反证法,假设不存在,那么任意一个数mod m都不等于零,ai mod m 只能有m-1种可能(也就是ai只能有m-1种可能),ai
+ai-1 mod m也不会等于零,则ai-1 只能由m-2种(因为ai有m-1种而ai-1 mod m也不能等于0相当于又减少了一种) 依次类推,a1只能有零种,矛盾
9.2 两个人每次能拿1到4枚硬币,从30个硬币中拿,最后拿完的人赢,第一个人能赢吗
利用动态规划记录状态,如果当前状态的后四个状态是必胜态,那么这个状态就是必负态(没看懂)
第一个人赢不了,因为无论第一个人拿多少,第二个人都能凑出来整数5,30能被整数五整除,所以第二个人稳赢. 如果是31个则第一个人第一次拿一个,第一个人会稳赢,如果是最后拿完的人输,则31的情况下第二个人会赢,因为一定能凑出5,最后剩下的一个一定被第一个人拿
9.3 三个盒子有一个有金币,你选了一个,主持人打开一个盒子是空的,你换不换
如果主持人明确知道那个箱子有金币的话,就得换,因为这相当于你选一个箱子而主持人选剩下两个箱子,不管开不开箱,你不换的概率都已经定为1/3了,那么剩下两个箱子有金币的概率是2/3 ,主持人去掉其中一个空箱子之后,剩下那个箱子的获奖概率就变成了2/3
如果主持人不知道那个箱子有金币,那么换不换无所谓,因为他只是恰好选了一个空箱子,相当于随机排除了一个选项,那么剩下两个选项都是一样1/2
线性代数
什么是对称矩阵和反称矩阵?
矩阵的转置=矩阵本身,则为对称矩阵(关于主对角线对称的元素相等)
AT=-A则为反衬矩阵(主对角线为0 关于主对角线对称的元素互为相反数)
什么是可交换矩阵
AB=BA则A与B为可交换的矩阵
什么是矩阵的初等变换和矩阵的等价,矩阵的等价标准型
矩阵的初等变换包括矩阵的行变换和列变换,比如对调某两行的位置,某一行进行倍乘,对某一行进行倍加,如果矩阵A经过有限次的初等变换能变成B,那么A与B等价
矩阵通过初等变换变成一种特殊形式的类单位阵
什么是范德蒙德行列式(行列式求法)
什么是可逆矩阵以及可逆的充要条件
AB=BA=E,则B是A的逆
可逆的充要条件是|A|!=0
什么是奇异阵
|A|=0
怎么求线性方程组?
matlab中的求逆运算是怎么实现的
恒等变换、初等变换、特征值和特征向量（定义及用途）、正交矩阵、矩阵等价（相似与合同）、线性相关和无关（定义及用途）、施密特正交化
数模
说说spss的流程和特征分解
项目
Q：你编程怎么样？
A：代码经验应该有5万行以上吧。主要是C和MATLAB。
Q：具体一点，你做过什么东西？
A：学校的项目、课设，比赛，还有毕业设计。
英语单词
编译原理
递归下降语法分析和lr分析的区别
递归下降语法分析是从文法的开始符号出发,反复使用各种产生式,寻找匹配的推导
自底向上语法分析是从输入串开始,一步一步进行”归约”,也就是按照产生式规则,将他的右部替换为左部,一直到文法的开始符号,相当于从树的末端开始构造语法树,
操作系统
进程切换会发生什么
进程切换首先要保存当前进程的上下文信息,然后把当前进程挂起,这就需要进行中断处理,然后再为就绪队列中的进程分配cpu