操作系统

1. 进程和线程区别和联系

进程和线程的关系：
（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。
（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。
（3）处理机分给线程，即真正在处理机上运行的是线程。
（4）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。线程是指进程内的一个执行单元,也是进程内的可调度实体.

进程与线程的区别：
（1）调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位
（2）并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行
（3）拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源.
（4）系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。

2. 常见的调度算法

1、先来先服务调度算法FCFS
（1）按照作业提交，或进程变为就绪状态的先后次序分派CPU；
（2）新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
（3）被唤醒的作业或进程不立即恢复执行，通常等到当前作业或进程出让CPU。（所以，默认即是非抢占方式）
（4）有利于CPU繁忙型的作业，而不利于I/O繁忙的作业（进程）。

2、短作业（进程）优先调度算法SJF（非抢占）/SPF（抢占）
（1）平均周转时间、平均带权周转时间都有明显改善。SJF/SPF调度算法能有效的降低作业的平均等待时间，提高系统吞吐量。
（2）未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理、对长作业的不利、作业（进程）的长短含主观因素，不一定能真正做到短作业优先。

3、高优先权优先调度算法HPF
（1）两种方式：非抢占式优先权算法、抢占式优先权算法（关键点：新作业产生时）
（2）类型:静态优先权：创建进程时确定，整个运行期间保持不变。动态优先权：创建进程时赋予的优先权可随进程的推进或随其等待时间的增加而改变。

4、基于时间片的轮转调度算法RR
（1）时间片轮转算法
过程：1、排成一个队列。2、每次调度时将CPU分派给队首进程。3、时间片结束时，发生时钟中断。4、暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。
说明：1、进程阻塞情况发生时，未用完时间片也要出让CPU。2、能够及时响应，但没有考虑作业长短等问题。3、系统的处理能力和系统的负载状态影响时间片长度。

3. 死锁的产生和解决

（1）互斥条件（mutual exclusion）：资源不能被共享，只能由一个进程使用；

（2）请求与保持条件（hold and wait）：进程已获得了一部分资源，但因请求其它资源被阻塞时，对已获得的资源保持不放；

（3）不可抢占条件（no pre-emption）：有些系统资源是不可抢占的，当某个进程已获得这种资源后，系统不能强行收回，只能进程使用完时自己释放；

（4）循环等待条件（circular wait）：若干个进程形成环形链，每个都占用对方申请的下一个资源。

自己总结：有个人很霸道，拿了东西就不肯还（请求保持），别人还不能抢（不可抢），又不肯和别人共享（互斥），造成了死循环（循环等待）。

4. 虚拟内存，页面置换算法

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

最佳(Optimal)置换算法：
最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。

先进先出(FIFO)页面置换算法：
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。

最近最久未使用(LRU)置换算法：
LRU(Least Recently Used)置换算法的描述：
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

5. 磁盘调度

先来先服务(FCFS，First Come First Served)：
这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。
此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

最短寻道时间优先(SSTF，Shortest Seek Time First)：
该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。

扫描(SCAN)算法：

1. 进程“饥饿”现象
   SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。
   因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必然优先满足。
   对SSTF算法略加修改后所形成的SCAN算法，即可防止老进程出现“饥饿”现象。
2. SCAN算法
   该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。
   
   循环扫描(CSCAN)算法：
   SCAN算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大、中、小型机器和网络中的磁盘调度。
   但SCAN也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。
   为了减少这种延迟，CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。
   

数据结构

1. 常见的排序算法过程和时间复杂度，空间复杂度

一、冒泡排序：

1.基本思想：

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

2.排序过程：

设想被排序的数组R［1…N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

					【示例】：49 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97

二、快速排序（Quick Sort）
1.基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
2.排序过程：
【示例】：
初始关键字 [49 38 65 97 76 13 27 49］
第一次交换后 ［27 38 65 97 76 13 49 49］
第二次交换后 ［27 38 49 97 76 13 65 49］
J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］
I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］
J向左扫描 ［27 38 13 49 76 97 65 49］
（一次划分过程）
初始关键字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］
二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］
三趟排序之后 13 27 38 49 49 ［65］76 97
最后的排序结果 13 27 38 49 49 65 76 97

三、简单选择排序
1.基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2.排序过程：

			【示例】：初始关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13 ［38 65 97 76 49 27 49]第二趟排序后 13 27 ［65 97 76 49 38 49]第三趟排序后 13 27 38 [97 76 49 65 49]第四趟排序后 13 27 38 49 [49 97 65 76]第五趟排序后 13 27 38 49 49 [97 97 76]第六趟排序后 13 27 38 49 49 76 [76 97]第七趟排序后 13 27 38 49 49 76 76 [ 97]最后排序结果 13 27 38 49 49 76 76 97

2. 深度搜索和广度搜索

深度搜索(DFS)

一、搜索方法：
 沿出发顶点的第一条路径尽量深入，遍历路径上所有顶点；然后退回到该顶点，搜索其它路径，直到以该顶点为始点的所有路径的顶点都被访问，深度搜索算法是递归算法，因为对于没一个节点来说，执行的是同样的操作。
 简单来说，深度搜素算法就是一条道走到黑，走不动了再回溯回去，选择其他路径，举个例子，对于下面的图，假设从1开始遍历：
 
 


二、用途
 深度搜索常用于解决图的遍历问题（尤其是矩阵图如迷宫问题等），比如求解从某一个点到另一个点的最短距离，则只需遍历所有路径，在遍历同时记录路径长度，最后一定能找到最短的距离，但这种方法复杂度较高，因为要遍历完所有结点才能找到。
 深度搜索是回溯法的主要方法，沿着一条路一直走，走不通再回溯到上一节点，选择其他路径。

广度搜索（BFS）

一、搜索方法
 广度搜索，顾名思义，就是更大范围内搜索，与深度搜索不同的是，深度搜索是一次搜索一条路径，一直搜索到走不通为止；而广度搜索是同时搜索所有路径，相当于一层一层地搜索，就好比波浪的扩展一样。此搜索方法跟树的层次遍历类似，因此宽度搜索一般都用队列存储结构。搜索原则：
（1）访问遍历出发顶点，该顶点入队
（2）队列不空，则队头顶点出队；
（3）访问出队顶点所有的未访问邻接点并将其入队；
（4）重复（2）（3），直到队空或者找到目标点
举个例子，还是对下面这个图进行广度遍历：

3. 二叉树的应用，遍历方式

4. 常见的查找算法

（1）顺序查找

**类型：**无序查找。
基本思想：
从数据列中的一段开始（通常是起始位置），顺序扫描，依次比较所扫描数和目标值，如果相等则查找成功。若扫描结束仍没有找到那么就查找失败。
复杂度分析：

平均查找长度	时间复杂度
(n+1)/2	O(n)

（2）二分查找（折半查找）

**类型：**有序查找。
基本思想：
用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析：

平均查找长度	时间复杂度
(log2(n+1)	O(log2n)

（3）插值查找

**类型：**有序查找。
基本思想：
是二分查找的一种优化，将查找点改进为自适应选择以提高查找效率。（将mid = (low + high) /2取中值的取法换成了mid = low + (target - arr[low]) / (arr[high] - arr[low] * (high - low))）

复杂度分析：

平均查找长度	时间复杂度
(n+1)/2	O(n)

斐波那契查找

**类型：**有序查找。
**斐波那契数列：**相信很多同学都早已有所耳闻，即1,1,2,3,5,8,13…，从第三个数开始，后面的数都等于前两个数之和，而斐波那契查找就是利用的斐波那契数列来实现查找的。
基本思想：
同样的是，它是二分查找的一个优化，它是根据斐波那契序列的特点对有序表进行分割。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;然后需要装填一个长度为n的新数组，且mid = low + fib(k - 1) - 1，k为fib(k) - 1刚好大于原数组长度的那个值。

复杂度分析：

平均查找长度	时间复杂度
*	O(log2n)

机器学习

1. 机器学习常见算法和概念

机器学习的基本思路：

无论使用什么算法，使用什么样的数据，最根本的思路都逃不出上面的3步:

1. 把现实生活中的问题抽象成数学模型，并且很清楚模型中不同参数的作用
2. 利用数学方法对这个数学模型进行求解，从而解决现实生活中的问题
3. 评估这个数学模型，是否真正的解决了现实生活中的问题，解决的如何？
   
   (当然,不是所有问题都可以转换成数学问题的。那些没有办法转换的现实问题 AI 就没有办法解决。同时最难的部分也就是把现实问题转换为数学问题这一步。)
   

机器学习在实际操作层面一共分为7步：

1. 收集数据
2. 数据准备
3. 选择一个模型
4. 训练
5. 评估
6. 参数调整
7. 预测（开始使用）

(1) 线性回归

1. 线性回归

• 什么是回归？

• 什么是线性？
  “越…，越…”符合这种说法的就可能是线性个关系：
  「房子」越大，「租金」就越高
  「汉堡」买的越多，花的「钱」就越多
  杯子里的「水」越多，「重量」就越大
  线性关系不仅仅只能存在 2 个变量（二维平面）。3 个变量时（三维空间），线性关系就是一个平面，4 个变量时（四维空间），线性关系就是一个体。以此类推…

优点：

1. 建模速度快，不需要很复杂的计算，在数据量大的情况下依然运行速度很快。
2. 可以根据系数给出每个变量的理解和解释

缺点：
不能很好地拟合非线性数据。所以需要先判断变量之间是否是线性关系。

为什么在深度学习大杀四方的今天还使用线性回归呢？
一方面，线性回归所能够模拟的关系其实远不止线性关系。线性回归中的“线性”指的是系数的线性，而通过对特征的非线性变换，以及广义线性模型的推广，输出和特征之间的函数关系可以是高度非线性的。另一方面，也是更为重要的一点，线性模型的易解释性使得它在物理学、经济学、商学等领域中占据了难以取代的地位。

(2) 逻辑回归

线性回归和逻辑回归是 2 种经典的算法。经常被拿来做比较，下面整理了一些两者的区别：

1. 线性回归只能用于回归问题，逻辑回归虽然名字叫回归，但是更多用于分类问题
2. 线性回归要求因变量是连续性数值变量，而逻辑回归要求因变量是离散的变量
3. 线性回归要求自变量和因变量呈线性关系，而逻辑回归不要求自变量和因变量呈线性关系
4. 线性回归可以直观的表达自变量和因变量之间的关系，逻辑回归则无法表达变量之间的关系

注：
自变量：主动操作的变量，可以看做「因变量」的原因
因变量：因为「自变量」的变化而变化，可以看做「自变量」的结果。也是我们想要预测的结果。

线性回归的位置如下图所示，它属于机器学习 – 监督学习 – 分类 – 逻辑回归。

**逻辑回归（Logistic Regression）**主要解决二分类问题，用来表示某件事情发生的可能性。

比如：

1. 一封邮件是垃圾邮件的可能性（是、不是）
2. 你购买一件商品的可能性（买、不买）
3. 广告被点击的可能性（点、不点）

逻辑回归的优缺点
优点：

• 实现简单，广泛的应用于工业问题上；
• 分类时计算量非常小，速度很快，存储资源低；
• 便利的观测样本概率分数；
• 对逻辑回归而言，多重共线性并不是问题，它可以结合L2正则化来解决该问题；
• 计算代价不高，易于理解和实现；

缺点：

• 当特征空间很大时，逻辑回归的性能不是很好；
• 容易欠拟合，一般准确度不太高
• 不能很好地处理大量多类特征或变量；
• 只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；
• 对于非线性特征，需要进行转换；

(3) 决策树

• 什么是决策树？

决策树是一种解决分类问题的算法；
决策树算法采用树形结构，使用层层推理来实现最终的分类。决策树由下面几种元素构成：

• 根节点：包含样本的全集
• 内部节点：对应特征属性测试
• 叶节点：代表决策的结果
  

预测时，在树的内部节点处用某一属性值进行判断，根据判断结果决定进入哪个分支节点，直到到达叶节点处，得到分类结果。

这是一种基于 if-then-else 规则的有监督学习算法，决策树的这些规则通过训练得到，而不是人工制定的。

决策树是最简单的机器学习算法，它易于实现，可解释性强，完全符合人类的直观思维，有着广泛的应用。

• 决策树学习的 3 个步骤
  
• 特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。

在特征选择中通常使用的准则是：信息增益。

- 决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。

- 决策树剪枝

剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。

决策树的优缺点：
优点

• 决策树易于理解和解释，可以可视化分析，容易提取出规则；
• 可以同时处理标称型和数值型数据；
• 比较适合处理有缺失属性的样本；
• 能够处理不相关的特征；
• 测试数据集时，运行速度比较快；
• 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

缺点

• 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
• 容易忽略数据集中属性的相互关联；
• 对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向；信息增益准则对可取数目较多的属性有所偏好（典型代表ID3算法），而增益率准则（CART）则对可取数目较少的属性有所偏好，但CART进行属性划分时候不再简单地直接利用增益率尽心划分，而是采用一种启发式规则）（只要是使用了信息增益，都有这个缺点，如RF）。
• ID3算法计算信息增益时结果偏向数值比较多的特征。

(4) SVM

(5) 神经网络

(6) KNN

(7) K-Means

优点

• 算法简单，容易实现 ；
• 算法速度很快；
• 对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O(nkt)，其中n是所有对象的数目，k是簇的数目,t是迭代的次数。通常k<<n。这个算法通常局部收敛。
• 算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。

缺点

• 对数据类型要求较高，适合数值型数据；
• 可能收敛到局部最小值，在大规模数据上收敛较慢
• 分组的数目k是一个输入参数，不合适的k可能返回较差的结果。
• 对初值的簇心值敏感，对于不同的初始值，可能会导致不同的聚类结果；
• 不适合于发现非凸面形状的簇，或者大小差别很大的簇。
• 对于”噪声”和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。

(8) 过拟合和欠拟合

(9) 聚类、回归、分类

(10) 监督学习和非监督学习

机器学习根据训练方法大致可以分为3大类：

1. 监督学习
2. 非监督学习
3. 强化学习

监督学习
监督学习是指我们给算法一个数据集，并且给定正确答案(标签)。机器通过数据来学习正确答案的计算方法。
这种通过大量人工打标签来帮助机器学习的方式就是监督学习。这种学习方式效果非常好，但是成本也非常高。

非监督学习
非监督学习中，给定的数据集没有“正确答案”，所有的数据都是一样的。无监督学习的任务是从给定的数据集中，挖掘出潜在的结构。
非监督学习中，虽然照片分为了猫和狗，但是机器并不知道哪个是猫，哪个是狗。对于机器来说，相当于分成了 A、B 两类。

强化学习
强化学习更接近生物学习的本质，因此有望获得更高的智能。它关注的是智能体如何在环境中采取一系列行为，从而获得最大的累积回报。通过强化学习，一个智能体应该知道在什么状态下应该采取什么行为。

• (2019年1月25日，AlphaStar（Google 研发的人工智能程序，采用了强化学习的训练方式）
  完虐星际争霸的职业选手职业选手“TLO”和“MANA”。新闻链接)

2. 深度学习和一些前沿领域

项目

1. 项目背景和创新点

2. 项目用到了哪些技术

3. 毕业设计(重点)

4. 项目中的难点以及如何解决

5. 项目中还有哪些可以继续改进

6. 你的获奖(ACM获奖，编程大赛等)

常见其他问题

1. cache的作用是什么

2. 进程与线程的关系

3. 解释TCP为什么需要三次握手

4. TCP如何解决拥塞阻塞

5. 数据库三大范式

6. 说说快排的过程，时间复杂度

7. 傅里叶变换，矩阵的秩是什么

8. 你对AI怎么看

9. 你最常用的语言是什么，为什么

10. 你将来准备读博吗？研究生计划是什么.