《C++面试宝典》V1.0 冲刺大厂~持续更新（10）

分享面试总结，涉及C++、算法、数据结构、操作系统、计算机网络、Linux、数据库、设计模式等，后面持续更新~

内容多为一问一答式，多数来自收集。整理总结，视频、书籍学习所得，如有错误请指出，万分感谢！！！

学习建议：针对八股文，不太了解的可以网上扩展，自己总结，拿来主义最好能消化成自己的。

※代表高频问题（参考）

# 网络篇--- √1

参考书籍：建议谢希仁《计算机网络》
网络部分还未总结，先m为敬

1. ※OSI各层功能了解吗？

物理层（传输单元：比特）：透明传输比特流。物理层接口标准，规定接口参数，通信链路上传输的信号意义和电气特征。

数据链路层（帧）：封装成帧。差错控制、流量控制、传输管理。典型协议：SDLC,HDLC,PPP,STP,帧中继等。

网络层（数据报）：路由选择与转发。将运输层产生的报文或用户数据报封装成分组（IP数据报）或包进行传送。流量控制、拥塞控制、网际互联等。典型协议：IP、IPX、ICMP、ARP、RARP、OSPF等。

传输层（报文段）：端到端可靠传输（进程间的通信）。典型协议：TCP、UDP等。

应用层：为用户的应用进程提供服务（HTTP、FTP等）

OSI体系结构：物理层、数据链路层、网络层、运输层、会话层、表示层、应用层
TCP/IP体系结构：网络接口层、网际层IP、运输层、应用层
两个体系结构的区别？？？

2. 网络性能指标？

速率：bps=bit/s
时延：发送时延、传播时延、排队时延、处理时延
往返时间RTT：数据报文在端到端通信中的来回一次的时间。

3. ※ip地址和mac地址？

1) IP地址是在网络上分配给每台计算机或网络设备的32位数字标识。在Internet上，每台计算机或网络设备的IP地址是全世界唯一的。IP地址的格式是xxx.xxx.xxx.xxx，其中xxx是0到255之间的任意整数。例如，每步站主机的IP地址是219.134.132.131。
2) MAC地址是数据链路层的地址，如果mac地址不可直达,直接丢弃，在LAN里面，一个网卡的MAC地址是唯一的。MAC地址在arp协议里常常用到，mac地址到ip地址的相互转化。Mac地址是48位的地址。
3) IP地址是网络层的地址，如果ip地址不可达，接着转发，在WAN里面，ip地址不唯一，计算机的ip地址可以变动。

4. IP数据报格式？

一个IP数据报由首部（20字节+可选字段）和数据两部分组成

5. ※ARP协议的作用？

ARP（地址解析）协议是一种解析协议，本来主机是完全不知道这个IP对应的是哪个主机的哪个接口，当主机要发送一个IP包的时候，会首先查一下自己的ARP高速缓存表（最近数据传递更新的IP-MAC地址对应表），如果查询的IP－MAC值对不存在，那么主机就向网络广播一个ARP请求包，这个包里面就有待查询的IP地址，而直接收到这份广播的包的所有主机都会查询自己的IP地址，如果收到广播包的某一个主机发现自己符合条件，那么就回应一个ARP应答包（将自己对应的IP-MAC对应地址发回主机），源主机拿到ARP应答包后会更新自己的ARP缓存表。源主机根据新的ARP缓存表准备好数据链路层的的数据包发送工作。

6. NAT的原理，外网与内网或内网之间的通信中如何区分不同IP的数组包？

分组转发
(1)从数据报的首部提取目的主机的IP地址D,得出目的网络地址为N。
(2)若网络N与此路由器直接相连，则把数据报直接交付目的主机D；否则是间接交付，执行(3)。
(3)若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行(4)。
(4)若路由表中有到达网络N的路由，则把数据报传送给路由表指明的下一跳路由器；否则，执行(5)。
(5)若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则，执行(6)。
(6)报告转发分组出错。

NAT网络地址转换协议：
1. 公有IP地址：也叫全局地址，是指合法的IP地址，它是由NIC（网络信息中心）或者ISP(网络服务提供商)分配的地址，对外代表一个或多个内部局部地址，是全球统一的可寻址的地址。
2. 私有IP地址：也叫内部地址，属于非注册地址，专门为组织机构内部使用。因特网分配编号委员会（IANA）保留了3块IP地址做为私有IP地址；
3. NAT英文全称是“Network Address Translation”，中文意思是“网络地址转换”，它是一个IETF(Internet Engineering Task Force, Internet工程任务组)标准，允许一个整体机构以一个公用IP（Internet Protocol）地址出现在Internet上。顾名思义，它是一种把内部私有网络地址（IP地址）翻译成合法网络IP地址的技术，如下图所示。因此我们可以认为，NAT在一定程度上，能够有效的解决公网地址不足的问题。
4. NAT就是在局域网内部网络中使用内部地址，而当内部节点要与外部网络进行通讯时，就在网关（可以理解为出口，打个比方就像院子的门一样）处，将内部地址替换成公用地址，从而在外部公网（internet）上正常使用，NAT可以使多台计算机共享Internet连接，这一功能很好地解决了公共IP地址紧缺的问题。通过这种方法，可以只申请一个合法IP地址，就把整个局域网中的计算机接入Internet中。这时，NAT屏蔽了内部网络，所有内部网计算机对于公共网络来说是不可见的，而内部网计算机用户通常不会意识到NAT的存在。
5. NAT路由器(普通路由转发ip数据报时，不改变源ip和目的ip地址)使用NAT转换表将本地ip转换成全球ip，{本地ip地址：端口}到{全球ip地址：端口}

7. RIP路由协议？

1. 网络中的每一个路由器都要维护从它自己到其他每一个目标网络的距离记录；
2. 距离也称为跳数，规定从一路由器到直接连接的网络跳数为1，而每经过一个路由器，则距离加1；
3. RIP认为好的路由就是它通过的路由器数量最少；
4. RIP允许一条路径上最多有15个路由器，因为规定最大跳数为16；
5. RIP默认每30秒广播一次RIP路由更新信息。

每一个路由表项目包括三个内容：目的网络、距离、下一跳路由器
1、对地址为X的路由器发过来的路由表，先修改此路由表中的所有项目：把”下一跳”字段中的地址改为X，并把所有”距离”字段都加1。

2、对修改后的路由表中的每一个项目，进行以下步骤：
a.将X的路由表(修改过的)，与S的路由表的目的网络进行对比。
若在X中出现，在S中没出现，则将X路由表中的这一条项目添加到S的路由表中。
b.对于目的网络在S和X路由表中都有的项目进行下面步骤
c.在S的路由表中，若下一跳地址是x
则直接用X路由表中这条项目替换S路由表中的项目。
d.在S的路由表中，若下一跳地址不是x
若X路由表项目中的距离d小于S路由表中的距离，则进行更新。

3、若3分钟还没有收到相邻路由器的更新表，则把此相邻路由器记为不可到达路由器，即把距离设置为16(认为无穷大，不可到达）。

8. 为什么使用IP地址通信？

1) 由于全世界存在着各式各样的网络，它们使用不同的硬件地址。要使这些异构网络能够互相通信就必须进行非常复杂的硬件地址转换工作，因此几乎是不可能的事。
2) 连接到因特网的主机都拥有统一的IP地址，它们之间的通信就像连接在同一个网络上那样简单方便，因为调用ARP来寻找某个路由器或主机的硬件地址都是由计算机软件自动进行的，对用户来说是看不见这种调用过程的。

9. 子网掩码有什么用？

子网掩码是一种用来指明一个IP地址所标示的主机处于哪个子网中。子网掩码不能单独存在，它必须结合IP地址一起使用。子网掩码只有一个作用，就是将某个IP地址划分成网络地址和主机地址两部分。

10. 子网划分的方法？

1.传统子网划分：ip地址结构=网络号+主机号，子网划分IP地址 = {<网络号>, <子网号>, <主机号>}
2.子网掩码：传统两级IP地址的缺点：IP地址空间的利用率有时很低；给每一个物理网络分配一个网络号会使路由表变得太大而使网络性能变坏；两级的IP地址不够灵活。
3.CIDR：无分类编址，减少了传统分法的ip浪费。在变长子网掩码的基础上提出的一种消除传统A、B、C类网络划分，并且可以在软件的支持下实现超网构造的一种IP地址划分方法。

※※※重点：TCP协议，重在理解

参考资料传送门：https://blog.csdn.net/zhang6223284/article/details/81414149
https://blog.csdn.net/zhangxinrun/article/details/6721495

1. TCP协议有几大计时器？

1) 重传计时器
在一个TCP连接中，TCP每发送一个报文段，就对此报文段设置一个超时重传计时器。若在收到了对此特定报文段的确认之前计时器截止期到，则重传此报文段，并将计时器复位。

2) 持续计时器
为了对付零窗口大小通知，TCP需要另一个计时器。假定接收TCP宣布了窗口大小为零。发送TCP就停止传送报文段，直到接收TCP发送确认并宣布一个非零的窗口大小。但这个确认可能会丢失。我们知道在TCP中，对确认是不需要发送确认的。若确认丢失了，接收TCP并不知道，而是会认为它已经完成任务了，并等待着发送TCP接着会发送更多的报文段。但发送TCP由于没有收到确认，就等待对方发送确认来通知窗口的大小。双方的TCP都在永远地等待着对方。要打开这种死锁，TCP为每一个连接使用一个坚持计时器。当发送TCP收到一个窗口大小为零的确认时，就启动坚持计时器。当坚持计时器期限到时，发送TCP就发送一个特殊的报文段，叫做探测报文段。这个报文段只有一个字节的数据。它有一个序号，但它的序号永远不需要确认；甚至在计算对其他部分的数据的确认时该序号也被忽略。探测报文段提醒对端：确认已丢失，必须重传。

3) 保活计时器
保活计时器使用在某些实现中，用来防止在两个TCP之间的连接出现长时期的空闲。假定客户打开了到服务器的连接，传送了一些数据，然后就保持静默了。也许这个客户出故障了。在这种情况下，这个连接将永远地处理打开状态。

4) 时间等待计时器
时间等待计时器是在连接终止期间使用的。当TCP关闭一个连接时，它并不认为这个连接马上就真正地关闭了。在时间等待期间中，连接还处于一种中间过渡状态。这就可以使重复的FIN报文段（如果有的话）可以到达目的站因而可将其丢弃。这个计时器的值通常设置为一个报文段的寿命期待值的两倍。

2. 详细说一下TCP协议，三次握手传输的内容，13种状态？

1) 第一次握手：建立连接。客户端发送连接请求报文段，将SYN位置为1，Sequence Number为x；然后，客户端进入SYN_SEND状态，等待服务器的确认；
2) 第二次握手：服务器收到SYN报文段。服务器收到客户端的SYN报文段，需要对这个SYN报文段进行确认，设置Acknowledgment Number为x+1(Sequence Number+1)；同时，自己自己还要发送SYN请求信息，将SYN位置为1，Sequence Number为y；服务器端将上述所有信息放到一个报文段（即SYN+ACK报文段）中，一并发送给客户端，此时服务器进入SYN_RECV状态；
3) 第三次握手：客户端收到服务器的SYN+ACK报文段。然后将Acknowledgment Number设置为y+1，向服务器发送ACK报文段，这个报文段发送完毕以后，客户端和服务器端都进入ESTABLISHED状态，完成TCP三次握手。

好家伙，四次挥手？
1) 第一次分手：主机1（可以使客户端，也可以是服务器端），设置Sequence Number和Acknowledgment Number，向主机2发送一个FIN报文段；此时，主机1进入FIN_WAIT_1状态；这表示主机1没有数据要发送给主机2了；
2) 第二次分手：主机2收到了主机1发送的FIN报文段，向主机1回一个ACK报文段，Acknowledgment Number为Sequence Number加1；主机1进入FIN_WAIT_2状态；主机2告诉主机1，我“同意”你的关闭请求；
3) 第三次分手：主机2向主机1发送FIN报文段，请求关闭连接，同时主机2进入LAST_ACK状态；
4) 第四次分手：主机1收到主机2发送的FIN报文段，向主机2发送ACK报文段，然后主机1进入TIME_WAIT状态；主机2收到主机1的ACK报文段以后，就关闭连接；此时，主机1等待2MSL后依然没有收到回复，则证明Server端已正常关闭，那好，主机1也可以关闭连接了。

六大标志位：
SYN，同步标志位；ACK确认标志位；PSH传送标志位；FIN结束标志位；RST重置标志位；URG紧急标志位；seq序号；ack确认号

3. TCP为啥挥手要比握手多一次？

因为当处于LISTEN状态的服务器端收到来自客户端的SYN报文(客户端希望新建一个TCP连接)时，它可以把ACK(确认应答)和SYN(同步序号)放在同一个报文里来发送给客户端。但在关闭TCP连接时，当收到对方的FIN报文时，对方仅仅表示对方已经没有数据发送给你了，但是你自己可能还有数据需要发送给对方，则等你发送完剩余的数据给对方之后，再发送FIN报文给对方来表示你数据已经发送完毕，并请求关闭连接，所以通常情况下，这里的ACK报文和FIN报文都是分开发送的。

4. 为什么一定进行三次握手？

当客户端向服务器端发送一个连接请求时，由于某种原因长时间驻留在网络节点中，无法达到服务器端，由于TCP的超时重传机制，当客户端在特定的时间内没有收到服务器端的确认应答信息，则会重新向服务器端发送连接请求，且该连接请求得到服务器端的响应并正常建立连接，进而传输数据，当数据传输完毕，并释放了此次TCP连接。若此时第一次发送的连接请求报文段延迟了一段时间后，到达了服务器端，本来这是一个早已失效的报文段，但是服务器端收到该连接请求后误以为客户端又发出了一次新的连接请求，于是服务器端向客户端发出确认应答报文段，并同意建立连接。
如果没有采用三次握手建立连接，由于服务器端发送了确认应答信息，则表示新的连接已成功建立，但是客户端此时并没有向服务器端发出任何连接请求，因此客户端忽略服务器端的确认应答报文，更不会向服务器端传输数据。而服务器端却认为新的连接已经建立了，并在一直等待客户端发送数据，这样服务器端一直处于等待接收数据，直到超出计数器的设定值，则认为服务器端出现异常，并且关闭这个连接。在这个等待的过程中，浪费服务器的资源。如果采用三次握手，客户端就不会向服务器发出确认应答消息，服务器端由于没有收到客户端的确认应答信息，从而判定客户端并没有请求建立连接，从而不建立该连接。

5. TCP与UDP的区别？应用场景都有哪些？

1) TCP面向字节流，UTP面向数据报；
2) TCP面向连接（如打电话要先拨号建立连接），连接前需要三次握手，释放需要四次挥手，对资源要求较多（首部20-60字节）;UDP是无连接的，即发送数据之前不需要建立连接（发：8字节首部+数据）UDP校验，需要在其首部加12字节的伪首部，用于计算校验和。开销小，传输数据报文高效；
3) TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付Tcp通过校验和，重传控制，序号标识，滑动窗口、确认应答实现可靠传输。
4) UDP具有较好的实时性，工作效率比TCP高，适用于对高速传输和实时性有较高的通信或广播通信。
5) 每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信（单播、多播、广播）
6) TCP对系统资源要求较多，UDP对系统资源要求较少。
7) 若通信数据完整性需让位与通信实时性，则应该选用TCP协议（如文件传输、重要状态的更新等）；反之，则使用UDP协议（如视频传输、实时通信等）。TCP为了实现网络通信的可靠性，使用了复杂的拥塞控制算法，建立了繁琐的握手过程，由于TCP内置的系统协议栈中，极难对其进行改进。采用TCP，一旦发生丢包，TCP会将后续的包缓存起来，等前面的包重传并接收到后再继续发送，延时会越来越大。还有粘包问题。基于UDP对实时性要求较为严格的情况下，采用自定义重传机制，能够把丢包产生的延迟降到最低，尽量减少网络问题对游戏性造成影响。

请自行理解和网上扩展！

6. TCP如何保证可靠性传输？

1. 序号
TCP首部的序号字段用来保证数据能有序提交给应用层，TCP把数据看成无结构的有序的字节流。数据流中的每一个字节都编上一个序号字段的值是指本报文段所发送的数据的第一个字节序号。
2. 确认
TCP首部的确认号是期望收到对方的下一个报文段的数据的第一个字节的序号；
3. 重传
超时重传
冗余ACK重传
4. 流量控制
TCP采用大小可变的滑动窗口进行流量控制，窗口大小的单位是字节。
发送窗口在连接建立时由双方商定。但在通信的过程中，接收端可根据自己的资源情况，随时动态地调整对方的发送窗口上限值(可增大或减小)。
窗口：
接受窗口rwnd，接收端缓冲区大小。接收端将此窗口值放在TCP报文的首部中的窗口字段，传送给发送端。
拥塞窗口cwnd，发送缓冲区大小。
发送窗口swnd,发送窗口的上限值=Min [rwnd,cwnd]
5. 拥塞控制
6. 流量控制与拥塞控制的区别
所谓拥塞控制就是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。拥塞控制所要做的都有一个前提，就是网络能承受现有的网络负荷。流量控制往往指的是点对点通信量的控制，是个端到端的问题。流量控制所要做的就是控制发送端发送数据的速率，以便使接收端来得及接受。

7. TCP粘包问题？

1) TCP粘包是指发送方发送的若干包数据到接收方接收时粘成一包，从接收缓冲区看，后一包数据的头紧接着前一包数据的尾；
2) 发送方原因
我们知道，TCP默认会使用Nagle算法。而Nagle算法主要做两件事：1）只有上一个分组得到确认，才会发送下一个分组；2）收集多个小分组，在一个确认到来时一起发送。所以，正是Nagle算法造成了发送方有可能造成粘包现象。
3) 接收方原因
TCP接收到分组时，并不会立刻送至应用层处理，或者说，应用层并不一定会立即处理；实际上，TCP将收到的分组保存至接收缓存里，然后应用程序主动从缓存里读收到的分组。这样一来，如果TCP接收分组的速度大于应用程序读分组的速度，多个包就会被存至缓存，应用程序读时，就会读到多个首尾相接粘到一起的包。

4) 解决方法
① 发送方
对于发送方造成的粘包现象，我们可以通过关闭Nagle算法来解决，使用TCP_NODELAY选项来关闭Nagle算法。
② 接收方
遗憾的是TCP并没有处理接收方粘包现象的机制，我们只能在应用层进行处理。
③ 应用层处理
应用层的处理简单易行！并且不仅可以解决接收方造成的粘包问题，还能解决发送方造成的粘包问题。

a) 在socket网络程序中，TCP和UDP分别是面向连接和非面向连接的。因此TCP的socket编程，收发两端（客户端和服务器端）都要有成对的socket，因此，发送端为了将多个发往接收端的包，更有效的发到对方，使用了优化方法（Nagle算法），将多次间隔较小、数据量小的数据，合并成一个大的数据块，然后进行封包。这样，接收端，就难于分辨出来了，必须提供科学的拆包机制。
b) 对于UDP，不会使用块的合并优化算法，这样，实际上目前认为，是由于UDP支持的是一对多的模式，所以接收端的skbuff(套接字缓冲区）采用了链式结构来记录每一个到达的UDP包，在每个UDP包中就有了消息头（消息来源地址，端口等信息），这样，对于接收端来说，就容易进行区分处理了。所以UDP不会出现粘包问题。

8. Time_wait为什么是2MSL的时间长度？

Time_wait的状态是为了等待连接上所有的分组的消失。单纯的想法，发送端只需要等待一个MSL就足够了。这是不够的，假设现在一个MSL的时候，接收端需要发送一个应答，这时候，我们也必须等待这个应答的消失，这个应答的消失也是需要一个MSL，所以我们需要等待2MSL。

9. TCP流量控制？

1) 如果发送方把数据发送得过快，接收方可能会来不及接收，这就会造成数据的丢失。TCP的流量控制是利用滑动窗口机制实现的，接收方在返回的ACK中会包含自己的接收窗口的大小，以控制发送方的数据发送。
2) 当某个ACK报文丢失了，就会出现A等待B确认，并且B等待A发送数据的死锁状态。为了解决这种问题，TCP引入了持续计时器（Persistence timer），当A收到rwnd=0时，就启用该计时器，时间到了则发送一个1字节的探测报文，询问B是很忙还是上个ACK丢失了，然后B回应自身的接收窗口大小，返回仍为0（A重设持续计时器继续等待）或者会重发rwnd=x。

10. 拥塞控制？

1) 慢开始
发送方维持一个叫做拥塞窗口cwnd（congestion window）的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口，另外考虑到接受方的接收能力，发送窗口可能小于拥塞窗口。慢开始算法的思路就是，不要一开始就发送大量的数据，先探测一下网络的拥塞程度，也就是说由小到大逐渐增加拥塞窗口的大小。
当然收到单个确认但此确认多个数据报的时候就加相应的数值。所以一次传输轮次之后拥塞窗口就加倍。这就是乘法增长，和后面的拥塞避免算法的加法增长比较。
为了防止cwnd增长过大引起网络拥塞，还需设置一个慢开始门限ssthresh状态变量。ssthresh的用法如下：
当cwnd<ssthresh时，使用慢开始算法。
当cwnd>ssthresh时，改用拥塞避免算法。
当cwnd=ssthresh时，慢开始与拥塞避免算法任意。
拥塞避免算法让拥塞窗口缓慢增长，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口按线性规律缓慢增长。
无论是在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认，虽然没有收到确认可能是其他原因的分组丢失，但是因为无法判定，所以都当做拥塞来处理），就把慢开始门限设置为出现拥塞时的发送窗口大小的一半。然后把拥塞窗口设置为1，执行慢开始算法。

2) 快重传和快恢复
快重传要求接收方在收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己发送数据时捎带确认。快重传算法规定，发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置的重传计时器时间到期。
快重传配合使用的还有快恢复算法，有以下两个要点:
①当发送方连续收到三个重复确认时，就执行“乘法减小”算法，把ssthresh门限减半。但是接下去并不执行慢开始算法。
②考虑到如果网络出现拥塞的话就不会收到好几个重复的确认，所以发送方现在认为网络可能没有出现拥塞。所以此时不执行慢开始算法，而是将cwnd设置为ssthresh的大小，然后执行拥塞避免算法。如下图：

3）流量控制与拥塞控制的区别？

1) 流量控制（接收窗口和拥塞窗口决定）为了消除发送方发送速率和接收方读取速率的问题，即让发送发送速率不要过快，让接收方来得及接收。利用滑动窗口机制就可以实施流量控制。原理这就是运用TCP报文段中的窗口大小字段来控制，发送方的发送窗口不可以大于接收方发回的窗口大小。
2) 拥塞控制（慢开始、拥塞避免、快重传、快恢复）就是防止过多的数据注入网络中，这样可以使网络中的路由器或链路不致过载。拥塞控制是一个全局性的过程，设计所有主机、路由器以及与降低网络传输新能相关的因数。而流量控制指点对点通信量的控制。
3) 发送窗口的实际大小由流量控制和拥塞控制共同决定。

网络重在理解，如有理解不透彻的问题，建议网上查阅，以点扩面，吸收成自己的东西。

未完待续~

需资料分享，可私聊哈

#面经##春招##实习##C/C++##学习路径##校招##网络安全##笔试题目#