【C++】面试常用知识点总结——基础篇_c++面试知识点总结

1、算法

1.1、排序

思想和写法，要会敲代码，最好会手撕代码

1.1.1、快排

一定要会手撕代码、思想要清楚。
实质是分治法，选择一个基准来分，这个分的过程是partition，它是快排的灵魂。基于以上特点，用递归的方式来描述。

#include <iostream>
using namespace std;

int partition(int arr[], int left, int right) {
    int key = arr[right];
    int k = left;
    for(int i = left; i < right; ++i) {
        if(arr[i] < key) {
            swap(arr[i], arr[k++]);
        }
    }
    swap(arr[right], arr[k]);
    return k;
}

void quicksort(int arr[], int left, int right) {
    if(left < right) {
        int i = partition(arr, left, right);
        quicksort(arr, left, i-1);
        quicksort(arr, i+1, right);
    }
    return;
}

int main() {
    int arr[10] = {2, 5, 4, 3, 1, 6, 9, 7, 8, 10};
    for(int i = 0; i < 10; ++i)
        cout << arr[i] << " ";
    cout << endl;
    quicksort(arr, 0, 9);
    for(int i = 0; i < 10; ++i)
        cout << arr[i] << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

1.1.2、归并

一定要会手撕代码、思想要清楚。
先递归划分子问题，然后合并结果

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& A, vector<int> L, vector<int> R) {
    int l = L.size();
    int r = R.size();
    int i = 0;
    int j = 0;
    int k = 0;
    while(i < l && j < r) {
        if(L[i] < R[j]) {
            A[k++] = L[i++];
        } else {
            A[k++] = R[j++];
        }
    }
    while(i < l) A[k++] = L[i++];
    while(j < r) A[k++] = R[j++];
}

void mergesort(vector<int>& arr) {
    int n = arr.size();
    if(n < 2) return;
    int mid = n/2;
    int i;
    vector<int> L(mid);
    vector<int> R(n - mid);
    for(i = 0; i < mid; ++i) {
        L[i] = arr[i];
    }
    for(;i < n; ++i) {
        R[i-mid] = arr[i];
    }
    mergesort(L);
    mergesort(R);
    merge(arr, L, R);
}

int main() {
    int arr[10] = {2, 5, 4, 3, 1, 6, 9, 7, 8, 10};
    vector<int> Arr(arr, arr + 10);
    for(int i = 0; i < 10; ++i)
        cout << Arr[i] << " ";
    cout << endl;
    mergesort(Arr);
    for(int i = 0; i < 10; ++i)
        cout << Arr[i] << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

1.1.3、稳定性、效率

从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序

稳定性算法：基数排序，插入排序，冒泡排序，归并排序
不稳定性算法：希尔排序，快速排序，选择排序，堆排序，桶排序

时间复杂度：评估执行程序所需的时间，可以估算出程序对处理器的使用程度
空间复杂度：评估执行程序所需的存储空间，可以估算出程序对计算机内存的使用程度

1.2、BFPRT算法

由5位外国人（Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan）提出，并以他们的名首字母命名，称为 中位数的中位数算法，又称 线性查找算法。

• 将n个元素每5个一组，分成n/5(上界)组。
• 取出每一组的中位数，任意排序方法，比如插入排序。
• 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
• 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
• 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
• 终止条件：n=1时，返回的即是i小元素。

结合不同考题侧面的去考（经典：选出第k大（第k小）的元素，）

1.3、二叉树

1.3.1、广度优先算法BFS和深度优先算法DFS

BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。类似层次遍历
DFS：一直往深处走，直到找到解或者走不下去为止（使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测），类似先序遍历。

总结：最短路径用广度优先搜索BFS，全部解用深度优先搜索DFS。

结合不同考题侧面的去考

1.3.2、遍历方式

• 前序遍历：先访问根节点，再遍历左子树，然后再遍历右子树。总的来说是根—左—右
• 中序遍历：先中序访问左子树，然后访问根，最后访问右子树。总的来说是左—根—右
• 后序遍历：先后序访问左子树，然后访问右子树，最后访问根。总的来说是左—右—根
• 层次遍历（宽度优先遍历）：利用队列，依次将根，左子树，右子树存入队列，按照队列的先进先出规则来实现层次遍历。
• 深度优先遍历：利用栈，先将根入栈，再将根出栈，并将根的右子树，左子树存入栈，按照栈的先进后出规则来实现深度优先遍历。

2、数据库

2.1、画E-R图

2.2、备份

2.2.1、备份类型

• 完全备份：指的是备份整个数据集（即整个数据库）
• 部分备份：指的是备份部分数据集（例如: 只备份一个表）
• 增量备份：指的是备份自上一次备份以来（增量或完全）以来变化的数据。特点: 节约空间、还原麻烦
• 差异备份：指的是备份自上一次完全备份以来变化的数据。特点: 浪费空间、还原比增量备份简单

2.2.2、备份方式

• 热备份：指的是当数据库进行备份时, 数据库的读写操作均不是受影响
• 温备份：指的是当数据库进行备份时, 数据库的读操作可以执行, 但是不能执行写操作
• 冷备份：指的是当数据库进行备份时, 数据库不能进行读写操作, 即数据库要下线

2.2.3、Mysql如何备份

• 直接拷贝数据库
• mysqldump命令
• mysqlhotcopy命令
• 使用文件系统快照（LVM等）进行
• Xtrabackup开源的热备份软件

2.3、加快数据库查询有几种方式

• 选取最适用的字段属性：申请过大字段属性增加了不必要的空间
• 使用连接（JOIN）来代替子查询（Sub-Queries）：不需要在内存中创建临时表
• 使用联合（UNION）来代替手动创建的临时表
• 使用事务
• 锁定表：可以维护数据的完整性
• 使用外键：锁定表不能保证数据的关联性。这个时候我们就可以使用外键
• 使用索引：根据业务建立在JOIN,WHERE判断和ORDERBY排序的字段上
• 优化的查询语句，例如LIKE关键字（这种通配符是以牺牲系统性能为代价的）

2.4、建立索引

2.4.1、建立索引如何加快查询

因为索引是一种优化查询的数据结构，比如MySQL中的索引是B+树实现的，而B+树就是一种数据结构，可以优化查询速度，可以利用索引快速查找数据，所以能优化查询！

2.4.2、表结构中字段是否添加索引判断依据是什么？

字段是否是查询条件或者是排序条件。适合于查询多而添删改少的表。

2.4.3、是否将所有的字段都添加索引，来加快查询？

不可以的

• 索引是有大量数据的时候才建立的，没有大量数据反而会浪费时间，因为索引是使用二叉树建立.
• 当一个系统查询比较频繁，而新建，修改等操作比较少时，可以创建索引，这样查询的速度会比以前快很多，同时也带来弊端，就是新建或修改等操作时，比没有索引或没有建立覆盖索引时的要慢。
• 索引并不是越多越好，太多索引会占用很多的索引表空间，甚至比存储一条记录更多。
  对于需要频繁新增记录的表，最好不要创建索引，没有索引的表，执行insert、append都很快，有了索引以后，会多一个维护索引的操作，一些大表可能导致insert 速度非常慢。

2.5、内、外链接，左、右链接

数据库分为：内连接、外连接、交叉连接

2.5.1、内连接

有两种，显式的和隐式的，返回连接表中符合连接条件和查询条件的数据行

• 显式
  
• 隐式
  

2.5.2、外连接(OUTER JOIN)

• 左外连接(LEFT OUTER JOIN或LEFT JOIN)
• 右外连接(RIGHT OUTER JOIN或RIGHT JOIN)
• 全外连接(FULL OUTER JOIN或FULL JOIN)

2.5.3、交叉连接(CROSS JOIN)

没有WHERE 子句，它返回连接表中所有数据行的笛卡尔积

2.6、事务（transaction）

2.6.1、特点、特性

①原子性：事务作为一个整体被执行，要么全部执行，要么全部不执行。
②一致性：保证数据库的状态从一个一致状态转变为另一个一致状态。
③隔离性：多个事务并发执行时，一个事务的执行并不影响其他事务的执行。
④持久性：一个事务一旦提交，对数据库的修改应该永久保存。

2.6.2、并发访问问题（由隔离性引起）

①脏读：B事务读取到了A事务尚未提交的数据。
②不可重复读：一个事务中，两次读取的数据的内容不一致。
③幻读/虚读：一个事务中，两次读取的数据的数量不一致。

2.6.3、隔离级别

读未提交、读已提交、可重复读和序列化
①读取尚未提交的数据：哪个问题都不能解决。
②读取已经提交的数据：可以解决脏读。（oracle默认）
③重读读取：可以解决脏读，不可重复读。（mysql默认）
④串行化：都可以解决。—相当于锁表，一般没人用，效率太低。

3、网络

3.1、http、https的区别

• https协议需要到ca申请证书，一般免费证书较少，因而需要一定费用。
• http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
• http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
• http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。

3.1.1、Https的优点

• 使用Https协议可认证用户和服务器，确保数据发送到正确的客户机和服务器。
• Https协议是由SSL+Http协议构建的可进行加密传输、身份认证的网络协议，要比http协议安全，可防止数据在传输过程中不被窃取、修改，确保数据的完整性。
• Https是现行架构下最安全的解决方案，虽然不是绝对安全，但它大幅增加了中间人攻击的成本。

3.1.2、Https的缺点（对比优点）

• Https协议握手阶段比较费时，会使页面的加载时间延长近
• Https连接缓存不如Http高效，会增加数据开销，甚至已有的安全措施也会因此而受到影响
• SSL证书通常需要绑定IP，不能在同一IP上绑定多个域名，IPv4资源不可能支撑这个消耗
• Https协议的加密范围也比较有限。最关键的，SSL证书的信用链体系并不安全，特别是在某些国家可以控制CA根证书的情况下，中间人攻击一样可行

3.2、tcp/ip的三次握手

3.2.1、讲述过程

• 第一次握手：Client将标志位SYN置为1（表示要发起一个连接），随机产生一个值seq=J，并将该数据包发送给Server，Client进入SYN_SENT状态，等待Server确认。
• 第二次握手：Server收到数据包后由标志位SYN=1知道Client请求建立连接，Server将标志位SYN和ACK都置为1，ack=J+1，随机产生一个值seq=K，并将该数据包发送给Client以确认连接请求，Server进入SYN_RCVD状态。
• 第三次握手：Client收到确认后，检查ack是否为J+1，ACK是否为1，如果正确则将标志位ACK置为1，ack=K+1，并将该数据包发送给Server，Server检查ack是否为K+1，ACK是否为1，如果正确则连接建立成功，Client和Server进入ESTABLISHED状态，完成三次握手，随后Client与Server之间可以开始传输数据了。

3.2.2、为什么是三次握手不是两次不是四次

三次握手的最主要目的是确认双方都有收发数据的能力。三次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。

• 第一次： A发给B。证明A有发消息的能力。
• 第二次： B收到并发消息给A。证明B有收消息，并且有发消息的能力。
• 第三次： A收到B消息。证明A有收消息的能力。

二次握手达不到目的，四次多余。

3.3、tcp/ip的四次挥手

• 第一次挥手：首先，客户端发送一个FIN，用来关闭客户端到服务器的数据传送，然后等待服务器的确认。其中终止标志位FIN=1，序列号seq=u。
• 第二次挥手：服务器收到这个FIN，它发送一个ACK，确认ack为收到的序号加一。
• 第三次挥手：关闭服务器到客户端的连接，发送一个FIN给客户端。
• 第四次挥手：客户端收到FIN后，并发回一个ACK报文确认，并将确认序号seq设置为收到序号加一。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。

3.3.1、为什么是四次挥手

双方关闭连接要经过双方都同意。所以，首先是客服端给服务器发送FIN，要求关闭连接，服务器收到后会发送一个ACK进行确认。服务器然后再发送一个FIN，客户端发送ACK确认，并进入TIME_WAIT状态。等待2MSL后自动关闭。

3.3.2、为什么需要2MSL时间？

首先，MSL即Maximum Segment Lifetime，就是最大报文生存时间，是任何报文在网络上的存在的最长时间，超过这个时间报文将被丢弃。《TCP/IP详解》中是这样描述的：MSL是任何报文段被丢弃前在网络内的最长时间。RFC 793中规定MSL为2分钟，实际应用中常用的是30秒、1分钟、2分钟等。

TCP的TIME_WAIT需要等待2MSL，当TCP的一端发起主动关闭，三次挥手完成后发送第四次挥手的ACK包后就进入这个状态，等待2MSL时间主要目的是：防止最后一个ACK包对方没有收到，那么对方在超时后将重发第三次握手的FIN包，主动关闭端接到重发的FIN包后可以再发一个ACK应答包。在TIME_WAIT状态时两端的端口不能使用，要等到2MSL时间结束才可以继续使用。当连接处于2MSL等待阶段时任何迟到的报文段都将被丢弃。

3.4、OSI七层

从低到高分别是：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

OSI七层模型是一种框架性的设计方法，设计的主要目的是为了解决异种网络互联时遇到的兼容问题，主要功能就是帮助不同类型的主机实现数据传输。最大优点是将服务，协议，接口三者明确的区分开来，通过七个层次化的结构模型使得不同的主机不同的网络之间实现可靠的通讯。服务说明下一层为上一层提供什么功能，接口说明上一层如何实现下一层提供的服务，协议涉及本层如何实现自己的服务。

• 优点：
  1.发生故障易排除。
  2.各层各自定义标准接口，使得相同等级的对应层之间的不同网络设备实现互操作。
  3.技术更新可在小范围内进行，不必对整个网络更新。

3.4.1、物理层

电缆连线连接器，网卡等。不包括具体的物理媒体。

物理层的任务就是为它的上一层提供一个物理连接，以及它们的机械、电气、功能和过程特性。如规定使用电缆和接头的类型、传送信号的电压等。在这一层，数据还没有被组织，仅作为原始的位流或电气电压处理，单位是比特。

3.4.2、数据链路层

交换机。

控制物理层和网络层之间的通讯，把网络层的数据分割成物理层可以传输的帧。

3.4.3、网络层

路由器。

将网络地址翻译成对应的物理地址，并决定如何将数据从发送方路由到接收方。通过综合考虑发送优先权、网络拥塞程度、服务质量以及可选路由的花费来决定从一个网络中节点Ａ 到另一个网络中节点Ｂ 的最佳路径。

3.4.4、传输层

最重要的一层。OSI下3层的主要任务是数据通信，上3层的任务是数据处理。而传输层（Transport Layer）是OSI模型的第4层。因此该层是通信子网和资源子网的接口和桥梁，起到承上启下的作用。协议 和 端口号 是在传输层定义的。

该层的主要任务是：定义了一些传输数据的协议和端口号（如HTTP的端口80等），TCP（传输控制协议，传输效率低，可靠性强，可以用于传输可靠性要求高，数据量大的数据），UDP（用户数据报协议，与TCP特性恰恰相反，用于传输可靠性要求不高，数据量小的数据，如QQ聊天数据就是通过这种方式传输的）。 主要是从下层接收的数据进行分段和传输，到达目的地址后再进行重组。常常把这一层数据叫做报文段

eg:电脑如何识别某一个应用程序？
通过端口号：每一个应用程序都有很多的服务，每一个服务对应着一个端口号

3.4.5、会话层

负责网络中两个节点之间建立和保持通信。

会话层的功能包括：建立通信链接，保持会话过程通信链接的畅通，同步两个节点之间的对话，决定通信是否被中断以及通信中断时决定从何处重新发送。

数据的传输是在会话层完成的，而不是传输层，传输层只是定义了数据传输的协议。

3.4.6、表示层

应用程序和网络之间的翻译官，在表示层，数据将按照网络能理解的方案进行格式化；这种格式化也因所使用网络的类型不同而不同。表示层管理数据的解密与加密，如系统口令的处理。在网络中传输需要加密数据的时候，表示层进行加密解密。对图片的编码解码也是表示层的工作。

其主要功能是“处理用户信息的表示问题，如编码、数据格式转换和加密解密”等

3.4.7、应用层

负责对软件提供接口以使程序能使用网络服务。术语“应用层”并不是指运行在网络上的某个特别应用程序 ，应用层提供的服务包括文件传输、文件管理以及电子邮件的信息处理。

它是计算机用户，以及各种应用程序和网络之间的接口，其功能是直接向用户提供服务，完成用户希望在网络上完成的各种工作。是最靠近用户的OSI层。这一层为用户的应用程序（例如电子邮件、文件传输和终端仿真）提供网络服务。

4、操作系统

4.1、select、poll和epoll的区别

• 消息传递方式
  select：内核需要将消息传递到用户空间，需要内核的拷贝动作；
  poll：同上；
  epoll：通过内核和用户空间共享一块内存来实现，性能较高；

• 文件句柄剧增后带来的IO效率问题
  select：因为每次调用都会对连接进行线性遍历，所以随着FD剧增后会造成遍历速度的“线性下降”的性能问题；
  poll：同上；
  epoll：由于epoll是根据每个FD上的callable函数来实现的，只有活跃的socket才会主动调用callback，所以在活跃socket较少的情况下，使用epoll不会对性能产生线性下降的问题，如果所有socket都很活跃的情况下，可能会有性能问题；

• 支持一个进程所能打开的最大连接数
  select：单个进程所能打开的最大连接数，是由FD_SETSIZE宏定义的，其大小是32个整数大小（在32位的机器上，大小是3232,64位机器上FD_SETSIZE=3264），我们可以对其进行修改，然后重新编译内核，但是性能无法保证，需要做进一步测试；
  poll：本质上与select没什么区别，但是他没有最大连接数限制，他是基于链表来存储的；
  epoll：虽然连接数有上线，但是很大，1G内存的机器上可以打开10W左右的连接；

综上，在选择select，poll，epoll时要根据具体的使用场合以及这三种方式的自身特点：
1、表面上看epoll的性能最好，但是在连接数少并且连接都十分活跃的情况下，select和poll的性能可能比epoll好，毕竟epoll的通知机制需要很多函数回调。
2、select低效是因为每次它都需要轮询。但低效也是相对的，视情况而定，也可通过良好的设计改善。

4.2、负载均衡

软件负载均衡、硬件负载均衡、DNS负载均衡。
DNS负载均衡是地理级别的，硬件负载均衡对应的是集群级别的，软件负载均衡对应的是机器级别的。

4.2.1、软件负载均衡

常见的软件有 LVS、 Nginx 、HAProxy 。

软件负载负载均衡又分四层和七层负载均衡，四层负载均衡就是在网络层利用IP地址端口进行请求的转发，基本上就是起个转发分配作用。而七层负载均衡就是可以根据访问用户的HTTP请求头、URL信息将请求转发到特定的主机。 LVS为四层负载均衡。Nginx、HAProxy可四可七。Nginx是万级别的，通常只用它来做七层负载，LVS来做四层负载。LVS是十万级别的，所以如果顶不住常见的也有这样的搭配：将LVS和NGINX组合起来。

• 优点：在于便宜而且简单灵活，就买个主机，装下软件，配置一下就能用了，配置也很简单对于一般小型企业，或者并发量不高的企业来说就够用了。而且在高峰期时容易扩容。
• 缺点：在于(和硬件负载均衡比)性能一般，流量很大的企业就用软件负载均衡顶不住，没防火墙或者防DDos攻击等安全性功能。

4.2.2、硬件负载均衡

就是用一个硬件一个基础网络设备，类似我们的交换机啊这样的硬件，来实现负载均衡。 常见的硬件有F5、A10。

优点：

• 功能强大，支持全局负载均衡提供全面的复杂均衡算法。
• 性能强悍，支持百万以上的并发。
• 提供安全功能，例如防火墙，防DDos攻击等。

缺点:

• 贵！这算是它最大的缺点了。为了安全通常还得一主一备。
• 扩展能力差，当访问量突增的时候超过限度不能动态扩容。

4.2.3、DNS负载均衡

这个负载均衡时通过DNS来的，因为DNS解析同一个域名可以返回不同的ip。所以例如哈尔滨的人访问百度就返回距离他近的那个机房的IP，海南的人访问百度就返回距离他近的那个机房的IP。所以主要是用来实现地理级别的负载均衡。

优点:

• 交给DNS服务器处理咱们都不用干活
• 因为是就近访问可以减少响应的时间，提升访问速度

缺点：

• DNS有缓存而且缓存时间较长，所以当机房迁移等需要修改DNS配置的时候，用户可能还会访问之前的IP，导致访问失败。
• 扩展能力差，因为运营商管理控制的，由不得我们定制或者扩展。
• 比较笨，不能区分服务器之间的差异，也不能反映服务器的当前运行状态

4.3、内存管理

4.3.1、页式、段式管理

• 分页式存储管理
  分页存储管理是将一个进程的地址（逻辑地址空间）空间划分成若干个大小相等的区域，称为页，相应地，将内存空间划分成与页相同大小（为了保证页内偏移一致）的若干个物理块，称为块或页框（页架）。在为进程分配内存时，将进程中的若干页分别装入多个不相邻接的块中。

• 分段式存储管理
  在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，如有主程序段、子程序段、数据段及堆栈段等，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。

两者的区别：

• 页是信息的物理单位，分页是为了实现非连续的分配，以便解决内存的碎片问题，或者说分页是为了由于系统管理的需要。
• 页的大小固定是由系统确定的，将逻辑地址划分为页号和页内地址是由机器硬件实现的。而段的长度是不固定的，决定与用户的程序长度，通常由编译程序进行编译时根据信息的性质来划分。
• 分页式存储管理的作业地址空间是一维的，分段式的存储管理的作业管理地址空间是二维的。

4.3.2、页面置换算法

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

• 页面置换算法有哪些？
  （1）最佳置换算法（Optimal）：即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。（它是一种理想化的算法，性能最好，但在实际上难于实现）。
  （2）先进先出置换算法FIFO：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
  （3）最近最久未使用置换算法LRU（Least Recently Used）：该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。
  （4）Clock置换算法：也叫最近未用算法NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置“1”。在选择一页淘汰时，就检查其访问位，如果是“0”，就选择该页换出；若为“1”，则重新置为“0”，暂不换出该页，在循环队列中检查下一个页面，直到访问位为“0”的页面为止。由于该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，所以把该算法称为最近未用算法。
  （5）最少使用置换算法LFU：该算法选择最近时期使用最少的页面作为淘汰页。

4.4、进程、线程

进程：具有独立功能的程序关于某个数据集合上的一次运行活动。
线程：进程的一个实体。
比喻：一列火车是一个进程，火车的每一节车厢是线程。

4.4.1、进程、线程的联系与区别

（1）粒度性分析：线程的粒度小于进程。
（2）调度性分析：进程是资源拥有的基本单位，线程是独立调度与独立运行的基本单位，出了寄存器，程序计数器等必要的资源外基本不拥有其他资源。
（3）系统开销分析：由于线程基本不拥有系统资源，所以在进行切换时，线程切换的开销远远小于进程。

• 联系
  ①一个线程只能属于一个进程，一个进程可以有多个线程；
  ②系统资源分配给进程，同一进程的所有线程共享该进程的所有资源；
  ③真正在处理机上运行的是线程；
  ④不同进程的线程间利用消息通信的方式实现同步。
• 区别
  ①调度：线程是系统调度和分配的基本单位，进程是作为拥有系统资源的基本单位；
  ②并发性：进程之间可以并发执行，同一进程的多个线程时间亦可以并发执行；
  ③拥有资源：进程是拥有资源的独立单位，线程不拥有资源，但可以访问隶属于进程的资源；
  ④系统开销：创建和撤销进程的开销更大；进程拥有独立的地址空间，一个进程的崩溃不会影响其他进程；线程拥有自己的堆栈和局部变量，没有独立的地址空间，因此进程里的一个线程崩溃会导致其他线程均崩溃。

4.4.2、进程、线程的通信方式

• 进程间
  ①管道( pipe )：
  管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
  ②有名管道 (namedpipe) ：
  有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
  ③信号量(semophore ) ：
  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
  ④消息队列( messagequeue ) ：
  消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
  ⑤信号 (sinal ) ：
  信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
  ⑥共享内存(shared memory ) ：
  共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
  ⑦套接字(socket ) ：
  套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。
• 线程间
  ①锁机制：包括互斥锁、条件变量、读写锁
  互斥锁提供了以排他方式防止数据结构被并发修改的方法。
  读写锁允许多个线程同时读共享数据，而对写操作是互斥的。
  条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
  ②信号量机制(Semaphore)：包括无名线程信号量和命名线程信号量
  ③信号机制(Signal)：类似进程间的信号处理，线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

4.4.3、死锁

• 死锁产生的原因
  （1）竞争资源；
  （2）进程推进顺序不当。
• 死锁产生的必要条件
  （1）互斥条件：一个资源一次只能被一个进程所使用，即是排它性使用。
  （2）不剥夺条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。
  （3）请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。
  （4）环路等待条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。
• 预防死锁
  破坏四个必要条件之一。
• 死锁的避免
  银行家算法，该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。
• 死锁定理
  S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的，该充分条件称为死锁定理。
• 死锁的解除
  （1）方法1：强制性地从系统中撤消一个或多个死锁的进程以断开循环等待链，并收回分配给终止进程的全部资源供剩下的进程使用。
  （2）方法2：使用一个有效的挂起和解除机构来挂起一些死锁的进程，其实质是从被挂起的进程那里抢占资源以解除死锁。

4.4.4、进程的五种基本状态

• 创建状态
  进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态
• 就绪状态
  进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行
• 执行状态
  进程处于就绪状态被调度后，进程进入执行状态
• 阻塞状态
  正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用
• 终止状态
  进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行

4.4.5、进程同步与互斥的区别

• 互斥
  是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
• 同步
  是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

简单地说：同步体现的是一种协作性，互斥体现的是一种排他性。

5、C++基础知识

5.1、C++的三大特性

5.1.1、面向对象特征：封装、继承、多态

面向对象的理解：是一种“万物皆对象”的编程思想。面向对象的编程是以对象为中心，以消息为驱动，所以程序=对象+消息。
多态：函数多态，一个接口，多种方法。（C++以虚函数）
纯虚函数：是虚函数再加上=0（如：virtual void eat()=0；）
虚函数总是在派生类中被改写，这种改写被称为“override”（覆盖）

5.1.2、析构函数可以为 virtual 型，构造函数则不能，为什么？

虚函数采用一种虚调用的办法。虚调用是一种可以在只有部分信息的情况下工作的机制，特别允许我们调用一个只知道接口而不知道其准确对象类型的函数。但是如果要创建一个对象，你势必要知道对象的准确类型，因此构造函数不能为 virtual。

5.1.3、如果虚函数是非常有效的，我们是否可以把每个函数都声明为虚函数？

不行，这是因为虚函数是有代价的。由于每个虚函数的对象都必须维护一个虚函数表，因此在使用虚函数的时候会产生一个系统开销。如果仅是一个很小的类，且不派生其他类，那么根本没必要使用虚函数。

5.2、重载、重写

重载：编写一个与自己已有函数同名但是参数表不同的函数
重写（覆盖）：重写的函数必须有一致的参数表和返回值

5.3、程序编译过程

• 编辑：编辑程序
• 预处理：删除宏定义、头文件、注释等，添加行号和文件标识，保留所有的#pragma编译器指令，因为编译器须要使用它们
• 编译：生成汇编代码
• 汇编：汇编器是将汇编代码转变成机器可以执行的命令
• 链接：生成可执行文件
• 运行：执行可执行程序

5.4、加载程序会经过几个区（堆和栈的区别）

• 栈区：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
• 堆区：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
• 全局区（静态区）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后有系统释放
• 文字常量区：常量字符串就是放在这里的。程序结束后由系统释放
• 程序代码区：存放函数体的二进制代码。

有些说法，把全局区，常量区合在一起。
也有些说法，把全局区分成：自由存储区（malloc/free）和全局（静态）存储区。

5.5、链表和数组有什么不同

• 数组元素在栈区，链表元素在堆区
• 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
• 数组从栈中分配空间, 对于程序员方便快速,但自由度小。链表从堆中分配空间，自由度大，但管理比较麻烦。
  数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
  数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

5.6、深拷贝、浅拷贝的区别

最根本的区别在于是否真正获取了一个对象的复制实体，而不是引用。

• 浅拷贝：只是拷贝了基本类型的数据，而引用类型数据，复制后也是会发生引用，我们把这种拷贝叫做“（浅复制）浅拷贝”，换句话说，浅复制仅仅是指向被复制的内存地址，如果原地址中对象被改变了，那么浅复制出来的对象也会相应改变。
• 深拷贝：在计算机中开辟了一块新的内存地址用于存放复制的对象。

5.7、pragma预处理指令

#pragma once(比较常用）只要在头文件的最开始加入这条指令就能够保证头文件被编译一次，约等于#ifndef，#define，#endif

5.8、结构体和共同体的区别

• 结构体 struct：把不同类型的数据组合成一个整体，自定义类型
• 共同体 union：使几个不同类型的变量共同占用一段内存