腾讯面试抱佛脚

发表于 | 分类于 ， | 次

1. TCP建立连接为什么是三次握手？

在不可靠的信道上进行可靠的数据传输，至少要进行三次握手。如果小于三次，无法保证数据可靠传输；如果大于三次，存在资源浪费。防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误

三次握手图示

PS：TCP协议中，主动发起请求的一端称为『客户端』，被动连接的一端称为『服务端』。不管是客户端还是服务端，TCP连接建立完后都能发送和接收数据。

起初，服务器和客户端都为CLOSED状态。在通信开始前，双方都得创建各自的传输控制块（TCB）。
服务器创建完TCB后遍进入LISTEN状态，此时准备接收客户端发来的连接请求。

第一次握手
客户端向服务端发送连接请求报文段。该报文段的头部中SYN=1，ACK=0，seq=x。请求发送后，客户端便进入SYN-SENT状态。

  • PS1：SYN=1，ACK=0表示该报文段为连接请求报文。
  • PS2：x为本次TCP通信的字节流的初始序号。
    TCP规定：SYN=1的报文段不能有数据部分，但要消耗掉一个序号。

第二次握手
服务端收到连接请求报文段后，如果同意连接，则会发送一个应答：SYN=1，ACK=1，seq=y，ack=x+1。
该应答发送完成后便进入SYN-RCVD状态。

  • PS1：SYN=1，ACK=1表示该报文段为连接同意的应答报文。
  • PS2：seq=y表示服务端作为发送者时，发送字节流的初始序号。
  • PS3：ack=x+1表示服务端希望下一个数据报发送序号从x+1开始的字节。

第三次握手
当客户端收到连接同意的应答后，还要向服务端发送一个确认报文段，表示：服务端发来的连接同意应答已经成功收到。
该报文段的头部为：ACK=1，seq=x+1，ack=y+1。
客户端发完这个报文段后便进入ESTABLISHED状态，服务端收到这个应答后也进入ESTABLISHED状态，此时连接的建立完成！

为什么连接建立需要三次握手，而不是两次握手？
防止失效的连接请求报文段被服务端接收，从而产生错误。

PS：失效的连接请求：若客户端向服务端发送的连接请求丢失，客户端等待应答超时后就会再次发送连接请求，此时，上一个连接请求就是『失效的』。

若建立连接只需两次握手，客户端并没有太大的变化，仍然需要获得服务端的应答后才进入ESTABLISHED状态，而服务端在收到连接请求后就进入ESTABLISHED状态。此时如果网络拥塞，客户端发送的连接请求迟迟到不了服务端，客户端便超时重发请求。此时，如果那个失效的连接请求抵达了服务端，由于只有两次握手，服务端收到请求就会进入ESTABLISHED状态，等待发送数据或主动发送数据。但此时的客户端并没有进入ESTABLISHED状态，所以服务端将会一直等待下去，这样浪费服务端连接资源。

2. TCP释放连接-四次挥手

四次挥手图示

TCP连接的释放一共需要四步，因此称为『四次挥手』。
我们知道，TCP连接是双向的，因此在四次挥手中，前两次挥手用于断开一个方向的连接，后两次挥手用于断开另一方向的连接。

第一次挥手
若A认为数据发送完成，则它需要向B发送连接释放请求。该请求只有报文头，头中携带的主要参数为：
FIN=1，seq=u。此时，A将进入FIN-WAIT-1状态。

  • PS1：FIN=1表示该报文段是一个连接释放请求。
  • PS2：seq=u，u-1是A向B发送的最后一个字节的序号。

第二次挥手
B收到连接释放请求后，会通知相应的应用程序，告诉它A向B这个方向的连接已经释放。此时B进入CLOSE-WAIT状态，并向A发送连接释放的应答，其报文头包含：
ACK=1，seq=v，ack=u+1。

  • PS1：ACK=1：除TCP连接请求报文段以外，TCP通信过程中所有数据报的ACK都为1，表示应答。
  • PS2：seq=v，v-1是B向A发送的最后一个字节的序号。
  • PS3：ack=u+1表示希望收到从第u+1个字节开始的报文段，并且已经成功接收了前u个字节。

A收到该应答，进入FIN-WAIT-2状态，等待B发送连接释放请求。

第二次挥手完成后，A到B方向的连接已经释放，B不会再接收数据，A也不会再发送数据。但B到A方向的连接仍然存在，B可以继续向A发送数据。

第三次挥手
当B向A发完所有数据后，向A发送连接释放请求，请求头：FIN=1，ACK=1，seq=w，ack=u+1。B便进入LAST-ACK状态。

第四次挥手
A收到释放请求后，向B发送确认应答，此时A进入TIME-WAIT状态。该状态会持续2MSL时间，若该时间段内没有B的重发请求的话，就进入CLOSED状态，撤销TCB。当B收到确认应答后，也便进入CLOSED状态，撤销TCB。

为什么A要先进入TIME-WAIT状态，等待2MSL时间后才进入CLOSED状态？
为了保证B能收到A的确认应答。
若A发完确认应答后直接进入CLOSED状态，那么如果该应答丢失，B等待超时后就会重新发送连接释放请求，但此时A已经关闭了，不会作出任何响应，因此B永远无法正常关闭。

3. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ActList* ReverseList3(ActList* list)
{
    if(NULL==list)
        return list;
    ActList* head;
    head->next=list;
	ActList* p=list;
	ActList* q;
	while(p->next!=NULL){
		q=p->next;
		p->next=q->next;
		q->next=head->next;
		head->next=q;
	}
	return head->next;
}

4. 虚函数的实现

4.1. 虚函数表

https://jocent.me/2017/08/07/virtual-table.html

一旦发现一个类型中有虚函数，就会为该类型生成一个虚函数表，并在该类型的每一个实例中添加一个指向该虚函数表的指针。

4.2. 单继承下的虚函数表

派生类未覆盖基类虚函数

虚函数表中依照声明顺序先放基类的虚函数地址，再放派生类的虚函数地址。

派生类覆盖基类虚函数

虚表中派生类覆盖基类虚函数的地址被放在基类相应函数原来的位置，派生类中不覆盖的虚函数延用基类的

4.3. 多继承下的虚函数表

无虚函数覆盖

  1. 有几个基类就有几个虚函数表
  2. 派生类的虚函数地址依照声明顺序放在第一个基类的虚表最后

有虚函数覆盖

  1. 有几个基类就有几个虚函数表
  2. 派生类的虚函数地址依照声明顺序放在第一个基类的虚表最后
  3. 若有覆盖，则放在被覆盖的基类虚函数对应位置

5. 虚析构

  • 虚析构函数是为了解决这样的一个问题：基类的指针指向派生类对象，并用基类的指针删除派生类对象。
  • 将一个函数定义为纯虚函数，实际上是将这个类定义为抽象类。简单方法：在想要成为抽象类的类里声明一个纯虚析构函数。

6. TCP滑动窗口协议

  • 数据传输可靠性：保证数据到达目的地，否则超时重传。
  • 数据流控制：管理发送速率，避免过载。
  • TCP将独立的字节数据当作流来处理。将数据流划分为片段，片段内所有字节都是一起发送和确认的。确认机制使用片段内最后一个字节的序列号。

6.1. TCP数据流划分

  • 1、已发送已确认
  • 2、已发送未确认
  • 3、未发送但接收方准备好
  • 4、未发送且接收方未准备好

6.2. 发送窗口与确认窗口

  • 整个过程关键的操作在于接收方允许发送方一次能容纳的未确认的字节数（2+3）：发送窗口

  • 可用窗口的定义是：考虑到正在传输的数据量，发送方仍被允许发送的数据量（3）。

6.3. 确认处理以及窗口缩放

  • 目标设备会发送自上一次成功接收后的最长字节数来确认接收到的数据流。（TCP的确认机制是累计的）
  • 收到确认信息，发送窗口右移，产生新的可用窗口。

6.4. 处理丢失确认信息

  • 假设已发送未确认字节（32至45）分为4段传输：32-34，35-36，37-41，42-45。第1，2，4已经到达，而3段没有收到。接收方只会发回32-36的确认信息，接收方会保留42-45但不会确认。
  • 在接收到第3段（37-41）之前，接收设备不会发送确认信息，也不会发送这一段之后字节的确认信息。发送设备可以将新的字节添加到第3类之后，即46-50。发送设备之后会停止发送，窗口停留在37-50。
  • TCP包括一个传输及重传的计时机制。TCP会重传丢失的片段。但有一个缺陷是：因为它不会对每一个片段分别进行确认，这可能会导致其他实际上已经接收到的片段被重传（比如42至45）。

7. TCP拥塞控制

  • 拥塞窗口

7.1. 慢开始与拥塞避免

发送的最初执行慢开始，令 cwnd = 1，每次收到确认后，将 cwnd 加倍，设置一个慢开始门限 ssthresh，当 cwnd >= ssthresh 时，进入拥塞避免，每个轮次只将 cwnd 加 1。如果出现了超时，则令 ssthresh = cwnd / 2，然后重新执行慢开始。

7.2. 快重传与快恢复

在发送方，如果收到三个重复确认，那么可以知道下一个报文段丢失，此时执行快重传，立即重传下一个报文段。例如收到三个 M2，则 M3 丢失，立即重传 M3。

在这种情况下，只是丢失个别报文段，而不是网络拥塞。因此执行快恢复，令 ssthresh = cwnd / 2 ，cwnd = ssthresh，注意到此时直接进入拥塞避免。

8. CPP基础知识

8.1. new 与 malloc

  • malloc的全称是memory allocation，中文叫动态内存分配。 malloc()之后必须有一个free()与之对应。

  • C++中，用new和delete动态创建和释放数组或单个对象。

malloc和new的区别

  1. new 返回指定类型的指针，并且可以自动计算所需要大小。而malloc则必须要由我们计算字节数，并且在返回后强行转换为实际类型的指针。

  2. malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。new创建的对象可以用初始化变量的方式初始化。

示例

1
2
3
4
5
6
7
8
9
10
11
int* p = new int(10); 
//返回类型为int*类型，分配大小为 sizeof(int); 

double *pd=(double*) malloc (sizeof(double)*12);
//分配12个double型存储单元，并将首地址存储到指针变量pd中

delete pi ;// 释放单个对象
delete []pi;//释放数组

free(pd);//释放malloc开辟的空间
pd=NULL;

8.2. 栈与堆

  • 栈由编译器自动分配释放，存放函数的参数值、局部变量的值等。

  • 堆一般由程序员分配释放，若不释放，程序结束时可能由操作系统回收。注意这里说是可能，并非一定。所以堆一定要释放！

9. 并查集

  • MakeSet

  • Union：秩，保证小的树成为大树的子树。秩相同则合并后的树秩加一。

  • Find：路径压缩，Find递归地经过树，改变每一个节点的引用到根节点。

    1
    2
    3
    4
    function Find(x)
        if x.parent != x
           x.parent := Find(x.parent)
        return x.parent

  • 应用：判断图是否连通