第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
北航面试题.docx
1 离散数学
1.1 旋转矩阵
1.2 无向图边数和度数
1.3 图的存储
1.4 如何判断连通图
1.5 主析取范式
1.6 基本回路和简单回路
1.7 有限无限集合
2 等价、偏序、
2.1 集合的基数
2.2 二元关系与函数
2.3 命题逻辑、谓词逻辑
2.4 二分图
2.5 全域关系、恒等关系、空关系
2.6 群论
2.7 哈密顿图 欧拉图
2.8 Prim算法
2.9 握手定理
2.10 单射满射双射
2.11 群
2.12 最短路径的两种方法的区别
2.13 完全二叉树、满二叉树
3 数学
3.1 先验概率、后验概率
3.2 中心极限定理
3.3 二项分布
3.4 雅可比行列式
3.5 导数的定义
3.6 行列式的作用，本质
3.7 矩阵的作用（本质是运动（跃迁）的描述）
3.8 极大似然估计、矩估计
3.9 数学中常见分布
3.10 线性无关的几何意义
3.11 矩阵的秩
3.12 特征值意义
3.13 极限、可导、连续
3.14 期望方差
3.15 可逆矩阵
3.16 矩阵有解
3.17 什么是线性函数
3.18 傅里叶级数和变换
3.19 全概率、贝叶斯
3.20 高等数学右手定则
3.21 曲线光滑判断
3.22 概率模型
4 专业课
4.1 冯诺依曼体系结构
4.2 程序运行的流程
4.3 Hashtable解决冲突（链式结构）数据结构PPT
4.4 编译过程
4.5 32位最大支持内存
4.6 堆栈的作用
4.7 操作系统的功能
4.8 AI在计算机网络中的应用
4.9 七层协议的功能
4.10 OSI和TCP/IP 的区别
4.11 什么是算法
4.12 Intel体系结构
4.13 哈佛体系结构
4.14 时序逻辑和组合逻辑的异同
4.15 流水线技术和并行技术的区别
4.16 Mips指令集、流水线，延迟时间片
4.17 三种相关
4.18 死锁以及解决
4.19 PV原语（操作）
4.20 OSI模型
4.21 蜂窝网络
4.22 滑动窗口
4.23 查找算法
4.24 排序算法（复杂度算法）
4.25 排序算法总结
4.26 QQ聊天过程，传输图片
4.27 进程通信
4.28 管道和内存共享是不是一个级别
4.29 内存中没有需要的数据该怎么解决
4.30 http,https区别，http如何工作
4.31 内存、外存区别
4.32 硬盘构成
4.33 计算机开机
4.34 登录网页
4.35 操作系统异常分几类
4.36 数据链路层子层
4.37 OSPF如何避免回路
4.38 DNS查询
4.39 Tcp和udp的区别
4.40 拥塞控制
4.41 慢启动
4.42 进程和线程
4.43 Linux和windows调度算法
4.44 精简指令集（CISC），复杂指令集(RISC)区别
4.45 Csma/cd协议
4.46 P NP问题
4.47 拉普拉斯算子
4.48 组成和体系结构的区别
4.49 流水线的级数多好还是少好
4.50 时序逻辑、组合逻辑
4.51 Cookie和session
4.52 操作系统线程调度
4.53 程序的内存分配
4.54 堆和栈的区别
4.55 TLB（笔记）
4.56 字典树
4.57 回归和分类
4.58 最小二乘法
4.59 物联网
4.60 虚存
4.61 递归
4.62 流水线三种冲突
4.63 流水线级数越多好还是越少好
4.64 图形和图像的区别
5 Java/c++
5.1 C++/java区别
5.2 动态库和静态库的区别
5.3 C和c#的区别
5.4 Static const区别
5.5 静态变量
5.6 C++三个特点
5.7 重载和多态的区别
5.8 面向对象三大特征：封装继承多态
5.9 Int& int*
5.10 面向对象的优点
5.11 动态规划
5.12 最小生成树
5.13 红黑树 b+ b-树
6 数据库
6.1 数据库优化
7 软件工程
7.1 软件开发过程
7.2 开发模型
7.3 白盒黑盒测试
7.4 单元测试、集成测试、功能测试
7.5 软件测试流程
1 离散数学
1.1 旋转矩阵
旋转矩阵（英语：Rotation matrix）是在乘以一个向量的时候有改变向量的方向但不改变大小的效果并保持
了手性的矩阵。
1.2 无向图边数和度数
总度数等于边数的两倍。
1.3 图的存储
1. 邻接矩阵
优点：简单直观，易于判断两点之间是否有边。方便计算顶点的度，方便找任意顶点的邻接点。
缺点：占用内存，判断边数需遍历。
2. 邻接表
优点：随机数据下空间小 缺点：极端数据下空间大
3. 链式前向星
4. Vector 邻接表
1.4 如何判断连通图
1. 连通图的概念：无向图：任意两个顶点存在路径可以连通，那么就是连通图。
2. 强连通图：有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就
是都含有至少一条通路，则称此有向图为强连通图。如图 4 所示就是一个强连通图。
3. 极大连通子图：连通图只有一个极大连通子图，就是它本身。（是唯一的）
连通分量：非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是一
个连通图）称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。
4．极小连通子图：一个连通图的生成树是该连通图顶点集确定的极小连通子图。（同一个连通图可以有
不同的生成树，所以生成树不是唯一的）（极小连通子图只存在于连通图中）之所以称为极小是因为此时如果删
除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。
5.判断连通性的方法：1.DFS 2.BFS
1.5 主析取范式
1. 命题变元：一个特定的命题就是一个常值命题，可以具有值 0 或 1。而一个任意的没有赋予具体内容
的原子命题是一个命题变量。他的变域是｛0，1｝。
2. 文字：命题变元或者其否定称为文字。
3. 简单析取（子句）/合取（短语）式：有限个文字的析取称为简单析取/合取式。
4. 范式：有限个简单析取式的合取称为合取范式，有限个简单合取式的析取称为析取范式。
5. 极小项：若在 n 个命题变元中，每个命题变元与其否定不同时出现，但一定出现其中一个，并且每个
命题变元按顺序出现，则他们的合取即简单合取式（短语）称为极小项。（2 的 n 次方个）
6. 极大项：若在 n 个命题变元中，每个命题变元与其否定不同时出现，但一定出现其中一个，并且每个
命题变元按顺序析取，即子句即简单析取析取式称为极大项。
7. 析取范式：有限个简单合取式（短语）的析取称为析取范式。
8. 合取范式：有限个简单析取式（子句）的合取称为合取范式。
9. 主析取范式：析取范式中，每个简单合取式（短语）都为极小项，且按照编码从小到大排列。
10. 主合取范式：合取范式中，每个简单析取式（子句）都为极大项，且按照编码从小到大排列。
11. 原子命题：不能分解为更为简单命题的命题。
复合命题：或者、并且、不、如果、则、当且仅当
1.6 基本回路和简单回路
1. 通路：给定图 G=（无向图或有向图）, G 中顶点与边的交替序列£=v0e1v1e2…envn.称为 v0 到 vn
的通路。
2. 回路：若通路的起点和终点相同，则称为回路。
3. 简单\复杂通路（回路）：若通路（回路）中的所有边互不相同，则称为简单通路，否则称为复杂通路。
4. 基本（初级）通路：若通路（回路）中的所有点互不相同，则称为基本（初级）通路（回路）。
5. 基本通路一定是简单通路，但简单通路不一定是基本通路。
1.7 有限无限集合
集合 A 中元素的个数成为该集合的基数，若一个集合的基数是有限的，称该集合为有限集，否则称为无限
集。
2 等价、偏序、
1.
2.
3.
4.
5.
6.
7.
关系的自反性：设 R 是集合 A 上的关系，若对于任意 x 属于 A，均有（x,x）属于 R，则称关系 R
具有自反性。
关系的反自反性：….均有（x,x）不属于 R，则称关系 R 具有反自反性。
关系的对称性：设 R 是集合 A 上的关系，若对于任意 x,y 属于 A，均有属于 R 且属于 R，
则称关系 R 具有对称性。
反对称性：设 R 是集合 A 上的 关系，若对于任意的 x,y 属于 A，若属于 R 且属于 R，则
x=y，则称 R 具有反对称性。
传递性：设 R 是集合 A 上的关系，若对于任意 x,y 属于 A，若属于 R，属于 R，则
属于 R，则称 R 具有传递性。
等价关系：若 R 是集合 A 上的非空关系，若 R 是自反的、对称的、传递的，则称 R 是 A 上的等价
关系。
二元关系：设 A，B 是两个集合，R 是 A×B 的任意一个子集，则称 R 为从集合 A 到集合 B 的一个
二元关系，简称为从 A 到 B 的一个二元关系。
8.
空关系：若 R 等于空集，则称 R 为空关系。非空集合中的空关系是反自反的、对称的、反对称的和
传递的，但不是自反的；空集合中的空关系则是自反的、反自反的、对称的、反对称的和传递的。
非空集合的空关系的矩阵各元素都是 0。
全关系：若 R=AxB 则 R 是全关系。
A 上的二元关系：若 A=B。则 R 是 A 上的二元关系。
A 上的恒等关系：若 A=B，且 R=。
9.
10.
11.
12. 偏序关系：若 R 是非空集合 A 上的，若 R 是自反的、反对称的、传递的，则称 R 是集合上的偏序
关系。
13. 因此。空关系既不是偏序关系也不是等价关系。
2.1 集合的基数
集合 A 中元素的个数成为该集合的基数，若一个集合的基数是有限的，称该集合为有限集，否则成为无限
集。
2.2 二元关系与函数
1. 二元关系：设 A、B 为两个非空集合，称 AxB 的任意子集 R 为 A 到 B 的一个二元关系，A 称为关系
R 的前域，B 称为关系 R 的后域，若 A=B 则称 R 为 A 上的一个二元关系。
2. 函数：设 f 是集合 A 到 B 上的关系，如果对于每一个 x 属于 A，都存在唯一的 y 属于 B，使得
属于 f，则称 f 是集合 A 到 B 上的函数或者映射，其中 A（doom）称为称为函数的定义域，B(ran)称
为函数的值域。
3.
2.3 命题逻辑、谓词逻辑
1.
2.
命题逻辑：命题逻辑主要有命题和连接词构成，命题是一个不具有二义性的陈述句，只有真假两个
值，连接词包括否定连接词，合取连接词和析取连接词。
谓词逻辑：在谓词逻辑中，可以独立存在的客体，称为个体词，而用于刻画客体的性质和客体之间
的关系的词则称为谓词，另外谓词逻辑还引入了量词，量词分为全称量词和存在量词。
2.4 二分图
设 G=(V,E)是一个无向图，如果顶点 V 可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所
关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A,j in B)，则称图 G 为一个二分图。简单来说，如果图
中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划
分为两个不相交子集 ，使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分，则此图为一个二分
图。
2.5 全域关系、恒等关系、空关系
1. 全关系：若 R=AxB 则 R 是全关系。
2. 恒等关系：A 上的恒等关系：若 A=B，且 R=。
3. 空关系：若 R 等于空集，则称 R 为空关系。非空集合中的空关系是反自反的、对称的、反对称的和传递的，
但不是自反的；空集合中的空关系则是自反的、反自反的、对称的、反对称的和传递的。非空集合的空
关系的矩阵各元素都是 0。
2.6 群论
1. 在数学中，群表示一个拥有满足封闭性、满足结合律、有单位元、有逆元的二元运算的代数结构
封闭性，又称闭包。数学里，给定一个非空集合 S 和一个函数 F : S X S -> S ，则称 F 为在 S 上之
二元运算(binary operation)，或称 (S,F) 具有封闭性(closure)。在数学中，若对某个集合的成员进行一
种运算，生成的仍然是这个集合的元素，则该集合被称为在这个运算下闭合。
加法,乘法,对于自然数是封闭的：
2. 结合律
3. 单位元：单位元(英文常写作 Identity Element，即 IE)是集合里的一种特别的元，与该集合里的运算（可
理解为实数里的*，但并不局限于）有关。当它和其他元素结合时，并不会改变那些元素。也叫幺元（么
元）。
4. 逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和
乘法中的倒数。
2.7 哈密顿图 欧拉图
见离散
2.8 Prim算法
见离散
2.9 握手定理
有 n 个人握手，每人握手 x 次，握手总次数为 S= nx/2。
2.10
单射满射双射
见离散
群
完全二叉树、满二叉树
最短路径的两种方法的区别
2.11
2.12
2.13
满二叉树：指深度为 k 且有 2^k-1 个结点的二叉树，如上图。
完全二叉树：当二叉树的深度为 h 时，它的 h 层节点必须都是连续靠左并不可隔开的(满二叉树也符合)，
并且 1～h-1 层的结点数都达到最大个数(即 1~h-1 层为一个满二叉树)。
3 数学
3.1 先验概率、后验概率
1. 条件概率：P(A|B)表示在 B 事件发生的情况下，A 事件发生的概率。
2. 先验概率：事件发生前的预判概率。可以是基于历史数据的统计，可以由背景常识得出，也可以是人
的主观观点给出。一般都是单独事件概率，如 P(x),P(y)。
3. 后验概率：事情已经发生了，事情发生可能有很多原因，判断事情发生时由哪个原因引起的概率。
3.2 中心极限定理
在适当的条件下，大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布。每次从这些总体
中随机抽取 n 个抽样，一共抽 m 次。 然后把这 m 组抽样分别求出平均值， 这些平均值的分布接近正态分
布。设从均值为μ、方差为（有限）的任意一个总体中抽取样本量为 n 的样本，当 n 充分大时，样本均值的抽
样分布近似服从均值为μ、方差为的正态分布。
3.3 二项分布
3.4 雅可比行列式
3.5 导数的定义
3.6 行列式的作用，本质
本质：行列式是由一些数据排列成的方阵经过规定的计算方法而得到的一个数。当然，如果行列式中含有
未知数，那么行列式就是一个多项式。它本质上代表一个数值。
作用：二阶行列式：
有向面积：给定多边形的顶点坐标（有序），让你来求这个多边形的面积，点如果是顺时针给出，有向面积
为负，逆时针给出，有向面积为正。
N 阶行列式：行列式就是行列式中的行或列向量所构成的超平行多面体的有向面积或有向体积；
有向体积：
3.7 矩阵的作用（本质是运动（跃迁）的描述）
1. 空间：存在一个集合，在这个集合上定义某某概念，然后满足某些性质”，就可以被称为空间，空间”
是容纳运动的一个对象集合，而变换则规定了对应空间的运动。
2. 线性空间：向量空间亦称线性空间。它是线性代数的中心内容和基本概念之一。设 V 是一个非空集合，
P 是一个域。若：
1.在 V 中定义了一种运算，称为加法，即对 V 中任意两个元素α与β都按某一法则对应于 V 内惟一确
定的一个元素α+β，称为α与β的和。 [2]
2.在 P 与 V 的元素间定义了一种运算，称为纯量乘法(亦称数量乘法)，即对 V 中任意元素α和 P 中任
意元素 k，都按某一法则对应 V 内惟一确定的一个元素 kα，称为 k 与α的积。
3. 线性变换：线性空间中的运动，被称为线性变换。从线性空间中的一个点运动到任意的另外一个
点，都可以通过一个线性变化来完成。当选定一组基之后，不仅可以用一个向量来描述空间中的任何一个
对象，而且可以用矩阵来描述该空间中的任何一个运动（变换）。而使某个对象发生对应运动的方法，就
动。
是用代表那个运动的矩阵，乘以代表那个对象的向量。设有一种变换 T，使得对于线性空间 V 中间任何两
个不相同的对象 x 和 y，以及任意实数 a 和 b，有：
T(ax + by) = aT(x) + bT(y)
简而言之，在线性空间中选定基之后，向量刻画对象，矩阵刻画对象的运动，用矩阵与向量的乘法施加运
3. 矩阵是线性空间中的线性变换的一个描述。在一个线性空间中，只要我们选定一组基，那么对于任何
一个线性变换，都能够用一个确定的矩阵来加以描述。同样的，对于一个线性变换，只要你选定一组
基，那么就可以找到一个矩阵来描述这个线性变换。换一组基，就得到一个不同的矩阵。所有这些矩
阵都是这同一个线性变换的描述，但又都不是线性变换本身。
4. 相似矩阵：若矩阵 A 与 B 是同一个线性变换的两个不同的描述（之所以会不同，是因为选定了不同的
基，也就是选定了不同的坐标系），则一定能找到一个非奇异矩阵 P，使得 A、B 之间满足这样的关系：
A = P-1BP
5. 行列式就是线性变换的放大率。
3.8 极大似然估计、矩估计
1.
极大似然估计：在一次抽样中，样本出现的概率是关于参数 θ 的函数，若在一些试验中，得到观
测值 x1,x2,...,xn ，则我们可以选取 θ^(x1,x2,..,xn) 作为 θ 的估计值，使得当 θ=θ^(x1,x2,..,xn)
时，样本出现的概率最大。而极大似然估计就是要求解出参数 θ 的估计值。可采用极大似然估计
法。（概率最大的事件，最可能发生）
2.距估计：就是利用样本矩来估计总体中相应的参数。首先推导涉及感兴趣的参数的总体矩（即所考虑的
随机变量的幂的期望值）的方程。然后取出一个样本并从这个样本估计总体矩。接着使用样本矩取代（未
知的）总体矩，解出感兴趣的参数。从而得到那些参数的估计。
3.9 数学中常见分布
3.10
线性无关的几何意义
1.
2.
3.线性表出
4.方程组的解
