研究生面试专业知识整理

2020-07-29

目录 展开

1 数学

1. 离散基本概念

等价关系：设一个非空集合上的二元关系，若它是自反、对称、传递的，则说它是该非空集合上的等价关系，同班的同学关系、三角形间的相似关系都是二元关系

一个关系的闭包是指加上最小数目的有序对而形成的具有自反、对称或传递性的新的有序对集，这样的集合就是关系的闭包。

单射：设 F 是 A 到 B 的函数，对于任意的 y，y 属于 F 的值域都能在 A 中找到唯一的 x 与之对应。

满射：F 的值域就是 B，则称 F 是满射的。

双射: F 既是单射的又是满射的。

欧拉图：看能否找到一条经过图中所有边仅一次且行遍所有顶点的回路。

哈密顿图：看能否找到一条经过图中所有顶点仅一次的回路。

函数：给定一个数集A，对A施加对应法则F，得到另一个数集B,也就是B=F(A)，那么这个关系式就叫函数的关系式，简称函数。

2. 图的同构

邻接矩阵相同 https://www.jianshu.com/p/c33b5d1b4cd9

3. 协方差

协方差用于衡量两个变量的总体误差。而方差是协方差的一种特殊情况，即当两个变量是相同的情况。如果两个变量的变化趋势一致，那么两个变量之间的协方差就是正值。变化趋势相反，负值。不相关，0。

4. 估计

极大似然估计，最小二乘估计（最小均方误差），矩估计（用样本 k 阶矩代替总体的 k 阶矩）。

矩估计法（也称数字特征法）：

直观意义比较明显，但要求总体 k 阶矩存在。
缺点是不唯一，此时尽量使用样本低阶矩。
观测值受异常值影响较大，不够稳健，实际中避免使用样本高阶矩。
估计值可能不落在参数空间

极大似然估计法：

具有一些理论上的优点（不变性、相合性、渐近正态性）
缺点是如果似然函数不可微，没有一般的求解法则。

5. 协方差和相关性有什么区别？

相关性是协方差的标准化格式。协方差本身很难做比较。

2 C++

https://blog.csdn.net/xiongchao99/article/details/73381280

https://blog.csdn.net/LuyaoYing001/article/details/81702020

https://www.nowcoder.com/tutorial/93/

https://www.jianshu.com/p/92b1957e6dd0

1. 虚函数可以/不可以出现在哪里？

见 6

2. 数组指针 指针数组

数组指针 数组的指针 char (*pa)[4];

指针数组 指针的数组 char *arr[4] = {"hello", "world"};

3. 函数调用

调用之前的工作：

  1. 为被调用函数分配数据存储区；
  2. 将所有的实参、返回地址等信息传给被调用函数保存；
  3. 将控制转移到被调用函数的入口。

返回前的工作：

  1. 保存计算结果；
  2. 释放存储区；
  3. 控制转移。

4. 递归函数优缺点：

优点：简洁，在树的三种遍历方式中递归的实现要比非递归的实现简单。

缺点：效率较低，递归是有时间和空间消耗的，递归中很多计算都是重复的，从而给性能带来很大的负面影响。递归的本质是把一个问题分解为两个或多个小问题，这些小问题存在相互重叠的部分，因此也就存在重复的计算。递归也可能导致调用栈溢出，每一次函数调用都会在内存栈中分配空间，而每个进程的栈容量是有限的，如果函数调用的层级太多，就会超出栈的容量，从而导致栈溢出。

5. 面向对象：

面向过程就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了；面向对象是把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在整个解决问题的步骤中的行为。

https://blog.csdn.net/bieleyang/article/details/78330362

面向对象三个特征：

  1. 封装：隐藏实现细节，使得代码模块化，实现代码重用
  2. 继承：扩展已存在的代码，实现代码重用
  3. 多态：不论传来哪个类的对象，函数都能够通过同一个接口调用到适应各自对象，实现接口重用

https://blog.csdn.net/ruyue_ruyue/article/details/8211809

  1. 封装: 隐藏对象的属性和细节, 仅对外提供公共访问方式。(控制属性的读和修改的访问级别)
  2. 继承: 一个类继承另一个类的功能, 可以直接使用其属性和方法，并可以添加；Java单继承, c++可以多继承(多个爹)
  3. 多态: 接口的多种不同的实现方式. (允许将子类类型指针赋值给父类类型指针)

6. 多态

多态性（polymorphisn）是允许你将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作

多态分为静态多态（函数重载，编译期间完成）和动态多态（通过虚函数实现，运行时完成）。下面主要描述后者

多个类继承一个类（或者说一个类派生出多个类），子类和父类可以使用相同名称，但是不同功能的函数，函数的参数甚至也可以相同。在基类的函数前要加 virtual 关键字。在派生类中重新定义基类中定义的虚函数时，会告诉编译器不要静态链接到该函数。

  1. 虚函数：虚函数是在基类中被声明为virtual，并在派生类中重新定义的成员函数，可实现成员函数的动态覆盖（Override）
  2. 抽象类：包含纯虚函数的类称为抽象类。由于抽象类包含了没有定义的纯虚函数，所以不能定义抽象类的对象。
  3. 纯虚函数：在基类中声明的虚函数，它在基类中没有定义，但要求任何派生类都要定义自己的实现方法。在基类中实现纯虚函数的方法是在函数原型后加“=0”

当把基类的某个成员函数声明为虚函数后，允许在其派生类中对该函数重新定义，赋予它新的功能，并且可以通过指向基类的指针指向同一类族中不同类的对象，从而调用其中的同名函数。由虚函数实现的动态多态性就是：同一类族中不同类的对象，对同一函数调用作出不同的响应。

https://www.cnblogs.com/-believe-me/p/11743099.html

  1. 重载多态：普通函数及类的成员函数的重载还有运算符的重载
  2. 强制多态：强制类型转换
  3. 包含多态：基类中必须包含虚函数，并且派生类中一定要对基类中的虚函数进行重写。通过基类对象的指针或者引用调用虚函数。
  4. 参数多态：用函数模板创建一个通用的函数，以支持多种不同形参，避免重载函数的函数体重复设计，通过给出不同的类型参数，使得一个结构有多种类型。以实现参数多态。

6. 动态多态的条件：

  • 基类中必须包含虚函数，并且派生类中一定要对基类中的虚函数进行重写。
  • 通过基类对象的指针或者引用调用虚函数。

6. 虚函数可以/不可以出现在哪里？

  1. 只有类的成员函数才能说明为虚函数；
  2. 静态成员函数不能是虚函数；
  3. 内联函数不能为虚函数；
  4. 构造函数不能是虚函数；
  5. 析构函数可以是虚函数，而且通常声明为虚函数。

7. 重载

C++ 允许在同一作用域（namespace）中的某个函数和运算符指定多个定义，分别称为函数重载和运算符重载。

重载要求该作用域内声明过的函数或方法，再用相同名称声明时，它们的参数列表和定义（实现）必须不相同。调用一个重载函数或重载运算符时，编译器通过把您所使用的参数类型与定义中的参数类型进行比较，决定选用最合适的定义。

8. 引用

类型 &引用变量名 = 已定义过的变量名

9. static 关键字作用

种类 内存中位置 初始化 作用域 特点
全局静态变量 静态存储区 自动初始化为0 从定义之处到文件结尾
局部静态变量 静态存储区 自动初始化为0 局部
静态函数 本 cpp 内
类的静态成员 实现多个对象之间的数据共享
类的静态函数 对静态成员的引用不需要用对象名

10. C 与 C++ 区别

设计思想上：

  • C++ 是面向对象的语言，而 C 是面向过程的结构化编程语言

语法上：

  • C++ 具有封装、继承和多态三种特性
  • C++ 相比 C，增加多许多类型安全的功能，比如强制类型转换
  • C++ 支持范式编程，比如模板类、函数模板等

11. 两次 fclose

一次正常的 fclose 会争取释放 FILE 指针的相关内容。再次 fclose 释放已经释放掉了的 FILE 指针，所以会出错

12. 宏

在预编译期间进行的，将代码中的指定字符转换，转换结束后，再进行编译，所以不占用程序运行时间

13. fclose

当顺利执行了文件关闭操作时， fclose.函数的返回值是0

14. malloc vs new

malloc 是 c 库函数（头文件，free），而 new 是 c++ 操作符（delete-指针null），都是用来申请内存的

malloc 是库函数只能作用于内部数据类型，对于非内部数据动态对象而言，就不能完成对象的初始化与销毁，即执行构造函数与析构函数。而new 与 deletev此类运算符就能够在编译器的控制权限内完成对象的初始化与销毁任务，即执行构造函数与析构函数｡

new/delete 的功能完全覆盖了 malloc/free，为什么 C++ 不把 malloc/free 淘汰出局呢？这是因为 C++ 程序经常要调用 C 函数，而 C 程序只能用 malloc/free 管理动态内存。

15. io

输入和输出并不是 C++ 语言中的正式组成成分｡ C 和 C++ 本身都没有为输入和输出提供专门的语句结构｡输入输出不是由 C++ 本身定义的,而是在编译系统提供的 I/O 库中定义的｡

16. finally

在异常处理中，如释放资源，关闭数据库、关闭文件应由 finally 语句来完成。

17. 静态数据成员、静态成员函数

https://blog.csdn.net/Qiana_/article/details/82083313

静态数据成员甚至在类没有任何对象的时候都可以访问，静态成员可以独立访问，无需依赖任何对象的建立（是类的一部分，而不是对象的一部分）。静态数据成员被类的所有对象共享，包括该类的派生类对象，基类对象和派生类对象共享基类的静态数据成员

静态成员函数是类的成员函数,该函数不属于该类申请的任何一个对象，而是所有该类成员共同共有的一个函数。

静态成员存在于内存，非静态成员需要实例化才会分配内存，所以静态成员函数不能访问非静态的成员；因为静态成员存在于内存，所以非静态成员函数可以直接访问类中静态的成员

18. c++11 的数组初始化规则

int a[4] = {1,2,3,4}; //okey
int b[4]; //okey
float c[5] = {5.0, 2.5} //初始化数组时，提供的值可以少于数组的元素数目
long d[500] = {0};  // 将数组所有元素初始化为0
short e[] = {1,5,2,3};  //c++编译器自动计算元素个数
double f[4] {1.2e4, 1.6e4, 1.1e4, 1.7e4 }  //可以省略等号 =
float g[100] {} // 大括号可以不包括任何东西， 这将把所有元素设置为0

19. 指针加一

对指针增加该指针类型所占的内存的字节数。不同类型的指针加1后，增加的大小不同。

20. 引用作为返回值

当函数返回一个引用时，则返回一个指向返回值的隐式指针。这样，函数就可以放在赋值语句的左边。

21. const 与 #define 相比，优点？

const：定义常量；修饰函数参数；修饰函数返回值；修饰类成员函数。
好处：const 修饰的有数据类型，而宏没有，所以可以做类型检查；而宏仅作字符替换，无安全检查。const常量可以调试.宏有副作用。不加括号的话有副作用。

22. 虚函数 VS 纯虚函数

多态的基础是继承，需要虚函数的支持。

纯虚函数声明如下： virtual void funtion1()=0，在基类没有定义，纯虚函数用来规范派生类的行为，即接口。包含纯虚函数的类是抽象类，抽象类不能定义实例，但可以声明指向实现该抽象类的具体类的指针或引用

虚函数声明如下：virtual ReturnType FunctionName(Parameter)；在基类有定义，如果不实现，编译器将报错

23. 空指针、野指针、悬空指针、智能指针

空：->NULL
野：不知道指哪里（随机创建、free 后未置 NULL、指针操作超过变量的作用范围）
悬空：指针指向的内存已经释放（delete 指针），但是没有对指针赋空（->nullptr）
智能：通过类的构造和析构，来对一个指针进行自动分配和回收

24. 缓冲区溢出？有什么危害？其原因是什么？

  1. 定义：当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。
  2. 危害：程序崩溃，导致拒绝额服务；跳转并且执行一段恶意代码。
  3. 原因：程序中没有仔细检查用户输入。

25. 数组和指针的区别

  1. 数组要么在静态存储区创建，要么在栈上创建。指针可以随时指向任意类型的内存块。
  2. 当数组作为函数参数进行传递时，该数组退化成指针
  3. 数组名不能自加自减，但是指针可以。

26. 引用与指针区别：

  1. 引用必须初始化，指针不用。
  2. 引用初始化后不能改变，指针可以改变所指的内容。
  3. 不存在指向空值的引用，但是存在指向空值的指针。
  4. 指针可以有多级；引用就一级。
  5. 指针要解引用，引用不用。
  6. 引用没有 const，但是指针有。
  7. sizeof 结果不同。
  8. 自增的语义不同。

27. 覆盖(override)、重载(overload)和重写(overwrite)

  1. 覆盖（override）派生类覆盖基类 virtual，函数名相同，参数相同
  2. 重载（overload）同一个类里面，函数名相同，参数不同
  3. 重写（overwrite）指派生类的函数屏蔽了与其同名的基类函数
    • 如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual关键字，基类的函数将被隐藏。
    • 如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual关键字。此时，基类的函数被隐藏（注意别与覆盖混淆)

28. 友元

https://www.cnblogs.com/zhuguanhao/p/6286145.html

一个类将对其非公有成员的访问权授予指定的函数或者类，友元的声明以 friend 开始。

友元函数（均可访问 A 类的友元函数）、友元类（B 类 可访问 A 类的任意）、友元成员函数（B 类 可访问 A 类的友元函数）

29. 编译型 vs 解释型

30. 动态语言 vs 静态语言

  • 动态类型语言是指在运行期间才去做数据类型检查的语言 py、ruby
  • 静态类型语言数据类型是在编译其间检查的 c、c++、c#、java

31. 强类型定义语言和弱类型定义语言

  • 强类型定义语言：一旦一个变量被指定了某个数据类型，如果不经过强制转换，那么它就永远是这个数据类型了
  • 弱：数据类型可以被忽略

32. NULL vs nullptr

NULL 在 C++ 中就是 0，这是因为在 C++ 中 void* 类型是不允许隐式转换成其他类型的，所以之前 C++ 中用 0 来代表空指针，但是在重载整形的情况下，会出现问题。所以，C++11 加入了 nullptr，可以保证在任何情况下都代表空指针，而不会出现上述的情况，

3 DS

1. Tire 树

  • 根节点不包含字符;
  • 除根节点外每一个节点都只包含一个字符:
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同

2. 排序

常用的排序：插入（简单插入，二分插入，希尔排序），选择（简单选择，堆），交换（冒泡，快排），归并，基数。

其中稳定的排序有：直接插入排序，折半插入，冒泡排序，归并排序、基数排序

不稳定的有：希尔排序，简单选择排序，堆排序，快速排序。

时间复杂度为O(n²)的：简单选择排序，简单插入排序，冒泡排序。

时间复杂度为O(nlogn)的：快速排序，堆排序，归并排序。

比较次数和原始序列无关：折半插入、简单选择、基数

排序趟数与原始序列有关：起泡、快排

每趟保证确定一个位置：起泡、快排、简单选择、堆

记录本身比较大：简单选择排序，用链表存储

初始基本有序：直接插入（n）、冒泡排序（n）

3. 快排

其中最快的一般为快速排序，但是如果是有序数列，则快速排序的时间复杂度为O(n^2);

快速排序虽然快，但是不稳定。

既稳定又快的就是归并排序。

4. 希尔

（分组+直接插入）最后一趟已经基本有序

5. 各种排序的时间复杂度证明

https://blog.csdn.net/qfikh/article/details/52870875
空间复杂度：快排 O(logn)，归并 O(n)，堆O(1)

6. 与开放定址法相比，拉链法其中优点有：

· 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
· 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况。

7. 线索二叉树

tag = 0 孩子 tag = 1 线索

8. 后序线索二叉树

是不完善的,要对它进行遍历,还需要使用栈

9. 二叉树可以为空，但树不可以为空，树是图的特例，图是不能为空的。

10. 归并趟数 s = log(k,m) k 路归并，m 个归并段

11. 声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，参数是int*，正确的是：

int (*(*p)[10])(int *)

12. 局部变量是分配在栈上的，new 出来的对象是分配在堆上的，动态申请的对象分配在堆上。

13. bfs vs dfs

邻接表 BFS DFS 复杂度都是 n+e，邻接表 BFS DFS 复杂度都是 n^2

  1. BFS 是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为 BFS 搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用 DFS，因为 DFS 搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索 ID-DFS 去弥补）

  2. 空间优劣上，DFS 是有优势的，DFS 不需要保存搜索过程中的状态，而 BFS 在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。

  3. DFS 适合搜索全部的解，因为要搜索全部的解，那么 BFS 搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS 搜索也会搜索全部，但是相比 DFS 不用记录过多信息，所以搜素全部解的问题，DFS 显然更加合适。

14. 建堆 O(n) ，空间复杂度 O(1)

15. 野指针

指向不可用内存区域的指针。指针变量未初始化（会乱指，可能存储关键信息，一下子就被修改了），指针释放后未置空，指针操作超越变量作用域造成。对野指针进行操作很容易造成程序错误，甚至可能直接引起崩溃。野指针与空指针不同，野指针无法通过简单地判断是否为NULL避免. 如何避免？指针变量初始化置null，指针释放后置null.

16. 给你一组N个数字(比如 vector<int> num), 然后给你一个常数(比如 int target) ，我们的 goal 是在这一堆数里面找到 K 个数字，使得这 K 个数字的和等于 target。

2sum: 先对数组中的数进行排序，再设置两个指针，一个指向头，一个指向尾。判断两数和是否等于想要的数，如果是则在结果集添加这个数组；如果小了说明左边指针指向的数小了，因此左指针右移；反之如果大了则右指针左移。

2sum 时间复杂度是 O(nlogn)(排序)，因为头尾指针线性扫描，只需要 O(n) 就可以了

3sum: 同样先对数组排序，设置三个指针p,q,r，p指针指向第一个数x，则q,r要指向数组中剩余数中的两个，并且指向的两数和为-x，从而转化为两数和问题。对p指向第一个数的情况分析完毕后，不可能再有满足题意且包含x的情况，于是p右移。这样一直分析到p指向数组中倒数第三个数的情况。

3sum 时间复杂度 O(n^2)，排序(nlogn)

最外层遍历一遍，等于选出一个数， 之后的数组中转化为找和为 target-nums[i] 的 2sum 问题。

17. 时间复杂度

  1. Θ（西塔）：紧确界。相当于"="
  2. O（大欧）：上界。相当于"<=" 欧，牛，达到最大了
  3. o（小欧）：非紧的上界。相当于"<"
  4. Ω（大欧米伽）：下界。相当于">="
  5. ω（小欧米伽）：非紧的下界。 相当于">"

18. Hash 取模为什么要模质数

首先来说假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。

19. B树和B+树的区别，以一个m阶树为例。

  1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。
  2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
  3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
  4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

20. 贪心算法、动态规划、分治

  1. 贪心算法：局部最优，划分的每个子问题都最优，得到全局最优，但是不能保证是全局最优解，所以对于贪心算法来说，解是从上到下的，一步一步最优，直到最后。
  2. 动态规划：将问题分解成重复的子问题，每次都寻找左右子问题解中最优的解，一步步得到全局的最优解.重复的子问题可以通过记录的方式，避免多次计算。所以对于动态规划来说，解是从小到上，从底层所有可能性中找到最优解，再一步步向上。
  3. 分治法：和动态规划类似，将大问题分解成小问题，但是这些小问题是独立的，没有重复的问题。独立问题取得解，再合并成大问题的解。

21. 给定一个单链表，只给出头指针h：

  1. 如何判断是否存在环？
  2. 如何知道环的长度？
  3. 如何找出环的连接点在哪里？
  4. 带环链表的长度是多少？

解法：

  1. 使用追赶的方法，设定两个指针 slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast 遇到 NULL 退出。
  2. 记录下问题 1 的碰撞点 p，slow、fast 从该点开始，再次碰撞所走过的操作数就是环的长度 s。
  3. 有定理：碰撞点 p 到连接点的距离 = 头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。4. 问题 3 中已经求出连接点距离头指针的长度，加上问题 2 中求出的环的长度，二者之和就是带环单链表的长度

22. 快排存在的问题，如何优化

问题：

  1. 有序时 O(n^2)
  2. 划分不平衡

优化：

  1. 剪枝：当整个序列有序时退出算法；
  2. 小规模换：当序列长度很小时（根据经验是大概小于 8），应该使用常数更小的算法，比如插入排序等（当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差）；
  3. 随机选取分割位置；
  4. 当分割位置不理想时，考虑是否重新选取分割位置；
  5. 尾递归：分割成两个序列时，只对其中一个递归进去，另一个序列仍可以在这一函数内继续划分，可以显著减小栈的大小（尾递归）（如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。）
  6. 将单向扫描改成双向扫描，可以减少划分过程中的交换次数
  7. 在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割

23. 二叉排序树删除节点z

  1. 查找待删除节点，保存其父结点（使得二叉排序树不断）
  2. 如果是叶节点（左右子节点都不存在），那么直接删除。
  3. 如果其存在一颗左子树或右子树，直接将z的子树替换z即可。
  4. 如果左右子树都存在，需要从左子树或右子树中选择后补节点。
    a) 如果左子树中选，选左子树中最右边的叶子节点。
    b) 如果右子树中选，选右子树中最左边的叶子节点。

24. 外部归并：

m 个初始归并段，k 路归并，趟数 [logkm]+1

  • 置换选择：生成初始归并段，减少初始归并段个数。每个数据均两次 io
  • 最佳归并树：添加虚段的多路哈弗曼树
  • 败者树：完全二叉树、增大归并路数

25. 归并排序求逆序对

26. 前 k 小的元素的排列

冒泡（kn）、简单选择（kn）、小跟堆（4n + klogn）、大根堆（nlogk）

堆排序的作用是快速选出最大的几个数，使用小顶堆、快速选出最小的数，使用大顶堆。

建立一个最小堆（优先队列），最小堆的大小控制在m之内
for 每个数：
    if 这个数比最小堆的堆顶元素大：
    弹出最小堆的最小元素
    把这个数插入到最小堆
最小堆中的m个元素就是所要求的元素
其中最小堆的作用就是保持里面始终有m个最大元素，且m个元素中最小的元素在堆顶。

27. 最长不重复子串、最长不重复子序列、最大子串和

https://blog.csdn.net/H0_0P/article/details/78013790
https://blog.csdn.net/weixin_43320847/article/details/83045856

28. 树状数组

C[i] = A[i – x+1] + A[i – x+2] + … + A[i]; // i 为 lowbit(k)

29. lowbit

求某一个数的二进制表示中最低的一位1 return x & -x;

30. 二分查找 vs 二叉查找树

二分查找即折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难

二叉查找树，它或者是一棵空树，或者若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

两者明显的区别是二分查找速度快删除和插入困难，二对于建立的二叉树索引来说，他的插入和删除是相对较快的。

什么时候采用二分什么时候采用二叉索引

  1. 如果我们的数据是不进行频繁变化且是有序，而且查询相对较多的情况下采用二分查找
  2. 我们的数据是频繁变化的考虑到后面的数据扩容的情况下，我们考虑采用二叉索引的方式，但是这种会有一点空间资源的牺牲。

31. 链式 vs 顺序

  1. 从空间性能，顺序存储会对空间资源做到百分之百的利用，而链式存储对对空间的利用不是百分之百，因为存储了指针，不是真正的数据
  2. 从时间性能上来讲读取速度的话顺序存储更优，插入和删除操作链式存储更优，链式存储只需要移动指针，不需要移动元素。

32. 循环单链表尾指针比头指针效率高

33. 四种数据存储结构

链表、顺序、hash、索引

34. BST 删除：

  • 叶子节点；(直接删除即可)
  • 仅有左或右子树的节点；（上移子树即可）
  • 左右子树都有的节点。( 用删除节点的直接前驱或者直接后继来替换当前节点，调整直接前驱或者直接后继的位置)

35. 如果不是连通图，则图中的极大连通子图称为连通分量。

4 计网

1. TCP/UDP区别

TCP 和 UDP都是运输层中的协议。TCP 面向连接提供可靠的数据传输服务，UDP 面向非连接不提供可靠传输服务；TCP 面向字节流数据传输慢，UDP 面向报文数据传输快

2. 搜索栏输入一个网址点击鼠标所发生的事情： URL – IP – TCP – HTTP

  1. 浏览器分析链接指向页面的 URL。
  2. 浏览器向 DNS 请求解析域名的 IP 地址。
  3. 域名系统 DNS 解析出域名的 IP 地址。
  4. 浏览器与该服务器建立 TCP 连接（默认端口号80）
  5. 浏览器发出 HTTP 请求。
  6. 服务器通过 HTTP 响应把文件发送给浏览器。
  7. TCP 连接释放。
  8. 浏览器将所得到的文件进行解释，并将 web 页显示给用户。

2. 在浏览器中输入www.baidu.com后执行的全部过程

  1. 客户端浏览器通过DNS解析到www.baidu.com的IP地址220.181.27.48，通过这个IP地址找到客户端到服务器的路径。客户端浏览器发起一个HTTP会话到220.161.27.48，然后通过TCP进行封装数据包，输入到网络层。
  2. 在客户端的传输层，把HTTP会话请求分成报文段，添加源和目的端口，如服务器使用80端口监听客户端的请求，客户端由系统随机选择一个端口如5000，与服务器进行交换，服务器把相应的请求返回给客户端的5000端口。然后使用IP层的IP地址查找目的端。
  3. 客户端的网络层不用关心应用层或者传输层的东西，主要做的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是由路由器来完成的工作，我不作过多的描述，无非就是通过查找路由表决定通过那个路径到达服务器。
  4. 客户端的链路层，包通过链路层发送到路由器，通过邻居协议查找给定IP地址的MAC地址，然后发送ARP请求查找目的地址，如果得到回应后就可以使用ARP的请求应答交换的IP数据包现在就可以传输了，然后发送IP数据包到达服务器的地址。

3. SSL 协议

https://blog.csdn.net/hnust_xiehonghao/article/details/37754871

5. telent

在 Internet 的服务功能中，Telnet 服务将联网计算机作为远程主机的终端，可以利用远程主机的各种硬件和软件资源。

7. Internet 始于 1968 年美国***部的高级计划局 (darpa) 建立的全世界第一个分组交换网 ARPANET

8. PING 命令

使用 ICMP 的 Echo 回响

9. BGP

路由器对使用 179 端口的半永久 TCP 连接来交换选路信息，是运行于 TCP 上的一种自治系统的路由协议。

10. 树形拓扑的特征

有中央交换单元

11. iptables 既可以根据IP制定策略，也可以根据端口制定策略

12. 0-1023 是周知端口号

13. 通过 netstat 命令，可以查看进程监听端口的情况

14. ATM 异步传输模式：ATM网络的“打包”特点是采用短的定长的快速分组交换方式

15. HTTP 应答

101 切换协议

200 成功

301 永久重定向

302 暂时重定向

400 语法错误

403 没有足够的权限

404 找不到对应的资源

500 服务器内部错误

503 服务不可用

16. 常见协议工作层：

  • 应用层：telnet , ftp , smtp , dns
  • 传输层：icmp , ip , arp , rarp
  • 物理和数据链路层：arpanet , satnet , Packet Radio , lan

17. 乱七八糟的协议

  • ping 用来检查网络是否连通。
  • tracert 用于确定 IP 数据包访问目标所采取的路径
  • netstat 用于显示当前网络的信息
  • arp 根据 IP 地址获取物理地址的一个TCP/IP协议

19. 完成路径选择功能是在 OSI 模型的网络层

20. 在一个 IP 数据包到达目的地之前，可能成为碎片，但是不会重组

21. 交换机收到一个帧，但该帧的目标地址在其 MAC 地址表中找不到对应，交换机将洪泛

22. 因特网的基本服务

  1. 远程登录服务 Telnet
  2. 文件传送服务 FTP
  3. 电子邮件服务 E-mail
  4. 电子公告板系统 BBS
  5. 万维网 WWW

23. 时延

  • 发送时延：结点在发送数据时使数据块从结点进入到传输媒体所需的时间，也就是从数据块的第一个比特开始发送算起，到最后一个比特发送完毕所需的时间。发送时延又称为传输时延。发送时延=数据帧长度/发送速率
  • 传播时延：从链路起点到终点传播所需要的时间。传播时延=d/s（其中d为起点和终点距离，s为传播速率）
  • 处理时延：进行转发处理所花费的时间，如首部处理、差错检验等
  • 排队时延：分组在输入队列中排队等待处理，在输出队列中等待转发，就形成了排队时延。
  • 总时延 = 发送时延+传播时延+处理时延+排队时延
  • 往返时延：从发送端发送数据开始，到发送端接收到来自接收端的确认，总共经历的时延。

24. TCP/IP：

应用层，传输层，网络层，网络接口层。其中，应用层与 OSI 应用层相对应，传输层与 OSI 传输层相对应，网络层与 OSI 网络层相对应，网络接口层与 OSI 数据链路层及物理层相对应。在 TCP/IP 参考模型中，对 OSI 表示层、会话层没有对应的协议。

25. 帧中继是一种使用了包交换方式的广域网技术

26. 就局域网而言

  • 通信子网：由网卡、线缆、集线器、中继器、网桥、路由器、交换机等设备和相关软件组成。
  • 资源子网：由连网的服务器、工作站、共享的打印机和其它设备及相关软件所组成。

27. 交换机端口：独占

28. OSI 全称

Open System Interconnection Reference Model.

29. 面向连接 vs 无连接

  • 面向连接 每一条tcp连接只能由两个端点 提供可靠交付 全双工 面向字节流
  • 无连接 尽最大努力交付 面向报文, 首部开销小，不提供流量控制, 没有拥塞控制 (两个都是连接的事) 不保证顺序接受支持一对一，一对多，多对一，多对多的交互通信,

30. TCP的三次握手过程？为什么会采用三次握手，若采用二次握手可以吗？

建立连接的过程是利用客户服务器模式，假设主机A为客户端，主机B为服务器端。

  1. TCP的三次握手过程：主机A向B发送连接请求；主机B对收到的主机A的报文段进行确认；主机A再次对主机B的确认进行确认。
  2. 采用三次握手是为了防止失效的连接请求报文段突然又传送到主机B，因而产生错误。失效的连接请求报文段是指：主机A发出的连接请求没有收到主机B的确认，于是经过一段时间后，主机A又重新向主机B发送连接请求，且建立成功，顺序完成数据传输。考虑这样一种特殊情况，主机A第一次发送的连接请求并没有丢失，而是因为网络节点导致延迟达到主机B，主机B以为是主机A又发起的新连接，于是主机B同意连接，并向主机A发回确认，但是此时主机A根本不会理会，主机B就一直在等待主机A发送数据，导致主机B的资源浪费。
  3. 采用两次握手不行，原因就是上面说的失效的连接请求的特殊情况。

31. 网关（Gateway）

网关是连接两个网络的设备，在传统TCP/IP术语中，网络设备只分成两种，一种为网关（gateway），另一种为主机（host）。网关能在网络间转递数据包，但主机不能转送数据包。在主机中，数据包需经过TCP/IP四层协议处理，但是在网关只需要到达网际层，决定路径之后就可以转送。

在现代网络术语中，网关（gateway）与路由器（router）的定义不同。网关（gateway）能在不同协议间移动数据，而路由器（router）是在不同网络间移动数据.

32. RARP

逆地址解析协议，作用是完成硬件地址到IP地址的映射，主要用于无盘工作站，因为给无盘工作站配置的IP地址不能保存。工作流程：在网络中配置一台RARP服务器，里面保存着IP地址和MAC地址的映射关系，当无盘工作站启动后，就封装一个RARP数据包，里面有其MAC地址，然后广播到网络上去，当服务器收到请求包后，就查找对应的MAC地址的IP地址装入响应报文中发回给请求者。因为需要广播请求报文，因此RARP只能用于具有广播能力的网络。（已淘汰，集成在 DHCP）

33. TCP的滑动窗口，流量控制和拥塞控制，快重传和快恢复，超时重传

快重传和快恢复则是为了减少因为拥塞导致的数据包丢失带来的重传时间，从而避免传递无用的数据到网络。

快重传的机制是：

  1. 接收方如果发现一个包丢失，则对后续的包继续发送针对该包的重传请求；
  2. 一旦发送方接收到三个一样的确认，就知道该包之后出现了错误，立刻重传该包；
  3. 此时发送方开始执行“快恢复”算法：
    1. 慢开始门限减半；
    2. cwnd设为慢开始门限减半后的数值；
    3. 执行拥塞避免算法（高起点，线性增长）；

超时重传是TCP协议保证数据可靠性的另一个重要机制，其原理是在发送某一个数据以后就开启一个计时器，在一定时间内如果没有得到发送的数据报的ACK报文，那么就重新发送数据，直到发送成功为止。

34. ICMP协议

因特网控制报文协议。它是TCP/IP协议族的一个子协议，用于在IP主机、路由器之间传递控制消息；分为差错报文、询问报文。是网络层的协议，ICMP 报文 + 头 = IP 报文；应用：ping

35. DHCP协议

动态主机配置协议，使用UDP协议工作。广播请求，单播响应。应用层协议。发现，提供，请求，确认。

36. ARP

网络层。主机的 ARP Cache，没有-广播请求单播响应，dst：同一网络-主机，不同网络-本网络的一个router地址。

一个主机向另一个主机发送 IP 数据报，可能使用多次 ARP。

37. TCP vs UDP

  1. TCP 提供面向连接的、可靠的数据流传输，而UDP提供的是非面向连接的、不可靠的数据流传输。
  2. TCP 传输单位称为TCP报文段，UDP传输单位称为用户数据报。
  3. TCP 注重数据安全性，UDP数据传输快，因为不需要连接等待，少了许多操作，但是其安全性却一般。

38. TCP对应的协议和UDP对应的协议

TCP对应的协议：

  1. FTP：定义了文件传输协议，使用21端口。
  2. Telnet：一种用于远程登陆的端口，使用23端口，用户可以以自己的身份远程连接到计算机上，可提供基于DOS模式下的通信服务。
  3. SMTP：邮件传送协议，用于发送邮件。服务器开放的是25号端口。
  4. POP3：它是和SMTP对应，POP3用于接收邮件。POP3协议所用的是110端口。
  5. HTTP：是从Web服务器传输超文本到本地浏览器的传送协议。默认端口：80

UDP对应的协议：

  1. DNS：用于域名解析服务，将域名地址转换为IP地址。DNS用的是53号端口。
  2. SNMP：简单网络管理协议，使用161号端口，是用来管理网络设备的。由于网络设备很多，无连接的服务就体现出其优势。
  3. TFTP：简单文件传输协议，该协议在熟知端口69上使用UDP服务。

39. 广播 Vs 洪泛

泛洪操作广播的是普通数据帧而不是广播帧。洪泛只在 2 层，广播 23层。

广播是向同一子网内所有的端口（包括自己的那个端口）发送消息; 泛洪只是在所有的端口中不包括发送消息的（自己的）那个端口发送消息.

40. 二层 Vs 三层广播

用 router or 地址挡

41. 1、p、非 坚持 CSMA（不检测冲突）

42. 冲突检测载波侦听：

争用期：2 * 往返时延，征用期无冲突，保证本次发送无冲突

最小帧长：区分噪声 or 因发生碰撞而异常终止的短帧，与距离 & 传输速率有关

最大帧长：公平

截断二进制指数类型避退

43. http vs https

  1. http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
  2. http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
  3. http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。

44. 为何三次握手，而非两次

握手（序号+确认）：可靠

三次：两边的起始 seq 都要确认，

45. RIP vs OSPF

  1. 距离向量-链路状态
  2. 贪心-dj整体最优
  3. 相邻-所有
  4. udp-ip
  5. 慢收敛-快
  6. 无区域-划分区域
  7. 跳<15-无限制

BGP-TCP

46. 各层功能

  • 应用层：文件传输、访问管理、电子邮件
  • 传输层：端到端服务、流量、差错、拥塞控制
  • 网络层：路由选择、流量控制、拥塞控制、差错控制、网际互联
  • 数据链路：成帧、差错、流量控制
  • 物理层：比特传输

47. 编码调制

用数字信号承载数字或模拟数据——编码；用模拟信号承载数字或模拟数据——调制

48. 电路交换、报文交换、分组（数据报+虚电路）交换

时延（132）链接（100）信道利用率（123）节点存储（021）差错控制（011）

报文交换和分组交换不需要预先分配传输带宽，在传送突发数据时可提高整个网络的信道利用率。若要连续传送大量的数据，且其传送时间远大于连接建立时间，则电路交换的传输速率较快，但是电路交换应对突发数据能力差

49. PPP vs HDLC：数据链路层

  1. 字节（0x7E）-比特（5连1添0）
  2. 无差错-可靠

50. ftp

控制 21，数据 20

5 计组

1. 影响流水线性能的因素：

结构相关：由于多条指令在同一时刻争用同一资源而形成的冲突称为结构相关。

  1. lw 访存，后面指令取址：bubble or 指令数据分开放
  2. lw 写回，后面指令译码：先写后读，各半周期

数据相关：在一个程序中必须等待前一条指令执行完才能执行后一条指令的情况。

  1. 一般：数据旁路
  2. lw 后面的：只能 bubble

控制相关：当流水线遇到转移指令和其他改变PC值的指令而造成断流时，会引起控制相关。

  1. I 型无条件：取址时确定转移，无影响
  2. R 型无条件：译码时确定转移，1 bubble
  3. 条件：执行时确定，2 bubbles or 增加额外电路，1 bubble
  4. 延迟转移

2. cache 的原理和思想

Cache 是一种小容量的高速缓冲存储器，由快速的 SRAM 组成，直接制作在 CPU 芯片中。其根据程序访问的局部性，将主存中活跃的程序块和数据块复制到 cache 中，CPU 直接从 cache 中读取数据，而不必访问低速的内存

Cache 的评价标准：命中率，访存时间

改进方案：选用较好的替换算法，扩大 cache 的容量，采用多级 cache 和数据和指令 cache 分类策略。

用到 cache 的思想的有：基地址寄存器，将经常使用的基地址放在一个高速寄存器中，存储器的分层结构。

3. 翻译

翻译：高级->机器

汇编：汇编->机器

编译：高级->汇编

解释：不形成目标程序，一句一句（比编译程序慢）

4. 字长

机器字长：计算机直接处理的二进制数据位数

指令字长：指令字的长度

存储字长：存储单元的长度

5. 硬链接 Vs 软连接

硬:基于索引节点，不同 FCB 指向同一个索引节点，多用户共享时拥有者不能删除，count = 0 才可以删除

软:基于符号键，FCB -> 索引节点 -> Link 类型文件

6. 内存映射编址 与 IO 独立编址的区别

编址 指令 地址空间 优点 缺点
内存 访存指令 大 所有访存指令可访问 IO 占内存
独立 IO IO 指令 小 不占内存、易区分访存 / IO 指令 指令少

7. 诺依曼：

  1. 必须有一个存储器；
  2. 必须有一个控制器；
  3. 必须有一个运算器，用于完成算术运算和逻辑运算；
  4. 必须有输入设备和输出设备，用于进行人机通信；
  5. 程序和数据统一存储并在程序控制下自动工作。

6 OS

1. 线程同步方式

互斥量、信号量

2. 进程通信方式

管道、系统IPC（包括消息队列、信号量、共享存储），socket

3. 调度

进程调度策略：先来先服务、优先级、时间片轮转调度、高响应比调度、多级反馈队列调度

作业调度算法：先来先服务、短作业优先，高响应比优先、优先级调度算法

页面置换分配：最佳置换算法、先进先出页面置换算法、最近最久未使用页面置换算法、时钟置换算法

4. 管程

管程是由一组数据以及定义在这组数据上对这组数据的操作所组成的软件模块，特点：局部于管城内的数据变量只能被管程的过程访问，任何时候只能有一个进程在管程中执行，调用管程的其他任何进程都被阻塞。

5. 死锁的处理策略

预防死锁（破坏死锁产生的四个必要条件（互斥、不可抢占、循环等待、请求与保持））、避免死锁（安全状态、银行家算法）、检测死锁（死锁定理化简资源分配图）、解除死锁（资源剥夺、进程回退）

6. OS 功能

进程与处理机管理、作业管理、存储管理、设备管理、文件管理

7. 多道程序设计

单个终端，单个CPU可以利用分时功能实现多道程序设计；没有分时技术，可以利用多个CPU实现多道程序设计；但是不论使用哪种方法实现多道程序设计，底层都要结合中断功能

8. 指令是内核态的多还是用户态的多？

内核态，CPU可以访问内存所有数据，用户态下是受限访问，只能访问自己空间中的内存。

9. 中断：

解决处理器速度和硬件速度不匹配，是多道程序设计的必要条件。每个中断都有自己的数字标识，当中断发生时，指令计数器PC和处理机状态字PSW中的内容自动压入处理器堆栈，同时新的PC和PSW的中断向量也装入各自的寄存器中。这时，PC中包含的是该中断的中断处理程序的入口地址，它控制程序转向相应的处理，当中断处理程序执行完毕，该程序的最后一条iret（中断返回），它控制着恢复调用程序的环境。

中断和系统调用的区别:

  • 中断是由外设产生, 无意的, 被动的
  • 系统调用是由应用程序请求操作系统提供服务产生, 有意的, 主动的。

联系：要从用户态通过中断进入内核态。

中断过程：中断请求 中断响应 断点保护 执行中断服务程序 断点恢复 中断返回

系统调用过程：应用程序在用户态执行时请求系统调用，中断，从用户态进入内核态，在内核态执行相应的内核代码。

中断之后保存什么？保存pc, psw, 通用寄存器。

10. 分页和分段有什么区别？

  • 段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
  • 段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定
  • 段向用户提供二维地址空间；页向用户提供的是一维地址空间
  • 段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

11. 进程和线程以及它们的区别。

  • 进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。
  • 线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

一个进程可以有多个线程，多个线程也可以并发执行

12. 进程通信

管道pipe：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

消息队列MessageQueue：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

共享存储SharedMemory：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。

信号量Semaphore：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

套接字Socket：套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

13. 进程不能切换

处理中断过程、操作系统内核程序临界区中、原子操作过程中

14. 进程切换

正常终止、请求阻塞、时间片用完、被抢占

15. 进程和线程的区别？

（1）进程是资源的分配和调度的一个独立单元，而线程是CPU调度的基本单元

（2）同一个进程中可以包括多个线程，并且线程共享整个进程的资源（寄存器、堆栈、上下文），一个进程至少包括一个线程。

（3）进程的创建调用fork或者vfork，而线程的创建调用pthread_create，进程结束后它拥有的所有线程都将销毁，而线程的结束不会影响同个进程中的其他线程的结束

（4）线程是轻量级的进程，它的创建和销毁所需要的时间比进程小很多，所有操作系统中的执行功能都是创建线程去完成的

（5）线程中执行时一般都要进行同步和互斥，因为他们共享同一进程的所有资源

（6）线程有自己的私有属性TCB，线程id，寄存器、硬件上下文，而进程也有自己的私有属性进程控制块PCB，这些私有属性是不被共享的，用来标示一个进程或一个线程的标志

16. 存储管理的功能

分配、共享、保护、扩充、地址映射

17. 源程序 -> 运行程序

编译（高级语言 -> 汇编语言）、链接（不同模块之间的符号解析）、装入（创建进程）

18. 高级调度（作业）、中级调度（挂起）、低级调度（切换）

19. 优先级更大：系统，前台，IO

20. 磁盘

寻道时间、延迟时间、传输时间

先来先服务、最短优先、scan（到两边）、look（没有就回）、c-scan（单向）

21. 覆盖、交换、置换

覆盖：程序分多段，固定区 & 置换区（一个进程内的段之间）
交换：进程换入换出（不同进程之间）
置换：虚拟内存页面置换（最佳、先进先出、最近最久未使用、时钟、改进时钟）

7 ML

1. 数据挖掘任务：

  1. 回归任务：回归任务是一种对连续型随机变量进行预测和建模的监督学习算法，使用案例包括房价预测、股票走势等。
  2. 分类任务：分类是一种对离散型变量建模或预测的监督学习算法，使用案例包括邮件过滤、金融欺诈等。
  3. 聚类任务：聚类是一种无监督学习，它是基于数据的内部结构寻找观察样本的自然族群（集群），使用案例包括新闻聚类、文章推荐等。
  4. 相关性分组 或 关联规则：两件事之间有没有关系
  5. 可视化

2. 监督

监督学习：数据集中每个样本都有相应的标签。
无监督学习：数据集中的样本没有相应的标签。

3. 数据挖掘流程

  1. 问题定义：分类/回归/聚类
  2. 数据准备与数据预处理：数据清洗（清除错误异常样本），处理缺失值（样本缺失较少时，使用均值/众数填充）， 数据转换。
  3. 特征工程：通过特征工程分析数据之间的联系、数据分布等。
  4. 特征选择：特征选择可以基于模型的特征排序方法，模型学习的过程和特征选择的过程是同时进行的，利用xgboost模型训练完后可以输出特征的重要性，据此可以选择topN个特征从而达到特征选择的目的。特征选择目的：减少特征的数量、降低维度，是模型泛化能力（在训练集上训练得到的模型能够在多大程度上对新的实例预测出正确输出）更强，减少过拟合。
  5. 模型训练及评估
  6. 模型融合

4. K-Means

聚类算法，事先确定常数K，K代表着聚类类别数，首先随机选取K个初始点为质心，并通过计算每一个样本与质心之间的相似度（可以采用欧式距离），将样本点归到最相似的类中，接着重新计算每个类的质心（该类中所有点的平均值），重复这样的过程直到质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。

优点：原理简单、容易实现，

缺点：收敛太慢、算法复杂度高、需先确定K的个数、结果不一定是全局最优，只能保证局部最优。

5. 逻辑回归：

逻辑回归是一个使用逻辑函数将线性回归的结果归一化的分类模型，这里的归一化指将值约束在0和1之间。缺点：容易欠拟合，分类精度可能不高。

6. K-NN算法：

K最邻近分类算法，每个样本都可以用它最接近的K个邻居中大多数样本所属的类别来代表，其中近邻距离的度量方法有余弦值，在实际中K值一般取一个比较小的数值，通常采用交叉验证法（就是利用一部分样本做训练集，一部分样本做测试集），通过观察K值不同时模型的分类效果来选取最优的K值。

7. 归一化：[0,1] 标准化：均值0，方差1。都是对某个特征进行缩放。

有正则项时，必须标准化（否则每个特征参数大小级别不同，则小参数就被忽略了）。标准化后，得到的参数值大小可以反应出不同特征对样本label的贡献度，方便我们进行特征筛选。

归一化后加快的梯度下降对最优解的速度（等高线更圆，梯度下降更快收敛）

标准化注意事项：先拆分出test集，不要在整个数据集上做标准化，因为那样会将test集的信息引入到训练集中

8. 怎么选择模型

决定因素：数据属性（卷积 or 时序，稀疏低秩 – 降维）、数据规模（时间复杂度）、算力（BERT）、先验知识（范数）

9. 朴素贝叶斯

  • 朴素：各特征之间相互独立
  • p(分类|特征) = p(特征|分类) * p(分类) / p(特征)
  • 优点：分类器比判别模型更快收敛;它可以忽略特征之间的相互作用；对于小规模的数据表现很好，能处理多分类问题，可以再数据超出内存时，去增量训练；对缺失数据不太敏感，算法比较简单，常用于文本分类。
  • 缺点：不适用连续性特征;它对数据分布做出了非常强的假设;在数据稀缺的情况下不能很好地工作

10. BERT

one-hot -> word class -> 词（type）embedding -> 每个 token 都有 embedding（contextualized word embedding）

ELMO：RNN 输入上文，输出下一词，+ 反向（两个单向）（ a1 * 上文的 em + a2 + 下文的 em（a1，a2 也是学出来的））

BERT：与 transformer 的 encoder 一样。

11. Transformer https://www.bilibili.com/video/BV1JE411g7XF?p=23

RNN 考虑的范围比 CNN 更多，CNN 多层便能让范围更多，CNN 可以并行计算，RNN 不可以。
Self-Attention：输入输出和 RNN 一样也是 seq-seq，且能同时计算 -> 取代 RNN
输入 a -> q（query）,k（key）,v（）-> q 对每个 k 做 atteneion 得 \alpha -> softmax 得 \hat{\alpha} -> 得到输出 b
seq2seq：用 self-attention 取代 RNN，encode-decode

12. 核函数

正定核函数，内积。RBF、sigmoid、多项式、线性。-> 核密度估计的项目

13. tf optimizer

梯度下降、momentum 动量梯度下降、sgd 随机梯度下降、adam 自适应（如果一个可学习的参数已经梯度下降了很多，则减缓其下降的速度）

14. tf 交叉熵

sigmoid、softmax、sparse_softmax(不用输入 one hot)、weight(带权重 sig)

15. 过拟合

perfrom：train 很好，test 很差 or loss↓ but test x↓

solution：regularization l1 l2、cross validation、stop at a convergence condition、big data、droupout

16. 时间序列数据集上使用什么交叉验证技术？是用k倍或LOOCV？

都不是。对于时间序列问题，k倍可能会很麻烦，因为第4年或第5年的一些模式有可能跟第3年的不同，而对数据集的重复采样会将分离这些趋势，而我们最终可能只是需要对过去几年的进行验证，这就不能用这种方法了。相反，我们可以采用如下所示的5倍正向链接策略：

fold 1 : training [1], test [2]
fold 2 : training [1 2], test [3]
fold 3 : training [1 2 3], test [4]
fold 4 : training [1 2 3 4], test [5]
fold 5 : training [1 2 3 4 5], test [6]
# 1，2，3，4，5，6代表的是年份。

17. 偏差 vs 方差

偏差：决定准确率
方差：决定鲁棒性

18. 模型受到低偏差和高方差问题的困扰。那么，应该使用哪种算法来解决问题呢？为什么？

可以使用bagging算法（如随机森林）。因为，低偏差意味着模型的预测值接近实际值，换句话说，该模型有足够的灵活性，以模仿训练数据的分布。这样貌似很好，但是别忘了，一个灵活的模型没有泛化能力，意味着当这个模型用在对一个未曾见过的数据集进行测试的时候，它会令人很失望。在这种情况下，我们可以使用bagging算法（如随机森林），以解决高方差问题。bagging算法把数据集分成重复随机取样形成的子集。然后，这些样本利用单个学习算法生成一组模型。接着，利用投票（分类）或平均（回归）把模型预测结合在一起。

另外，为了应对大方差，我们可以：

  1. 使用正则化技术，惩罚更高的模型系数，从而降低了模型的复杂性。
  2. 使用可变重要性图表中的前n个特征。可以用于当一个算法在数据集中的所有变量里很难寻找到有意义信号的时候。

19. LR vs SVM

https://www.cnblogs.com/zhizhan/p/5038747.html

相同

  1. 都是分类算法
  2. 如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的。
  3. LR和SVM都是监督学习算法

不同

  1. LR和SVM的损失函数不同（最大似然估计 vs 最大 margin）
  2. SVM只考虑局部的边界线附近的点 ，LR考虑全局，远离的点对边界线的确定也起作用。
  3. 在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法。
  4. 线性SVM依赖数据表达的距离测度，所以需要对数据先做normalization，LR不受其影响。
  5. SVM的损失函数就自带正则（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化（在训练误差和模型复杂度之间寻求平衡，防止过拟合，从而达到真实误差的最小化）算法的原因。而LR必须另外在损失函数上添加正则项。

8 其它

1. 123范式

https://blog.csdn.net/xidianliuy/article/details/51566576

发表评论