百度客户端二面面经（附带答案~~~）

### 主题一：C++

#### t1. 既然C里有malloc和free，为什么C++还需要new和delete呢？

1. malloc与free是C、C++语言的标准库函数，new/delete是C++的运算符。他们都用于申请动态内存和释放内存。

2. 对于非内部数据类型的对象而言（例如类对象），只用malloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，也就不能自动执行构造函数和析构函数。因此，不能将执行构造函数和析构函数的任务强加给malloc/free。所以，在c++中需要一个能完成动态内存分配和初始化工作的运算符new，以及一个能完成清理和释放内存工作的运算符delete。

#### t2. 类似的，C里具有struct，为何C++需要增加class？有何区别？

1. 在C中struct只单纯的用作数据的复合类型，也就是说，在结构体声明中只能将数据成员放在里面，而不能将函数放在里面。而在C++中class理论上也是结构体，即也是复合数据类型，但成员不仅限于数据，含可以包含函数成员等。

2. C++是在C语言的基础上，进行了很多功能扩展，其中最重要的一条，就是引入了class。引入class的最大好处就是，使C++可以进行面向对象编程。面向对象编程，简称OOP，具备三个要素：封装性、继承性、多态性。诚然，struct可以实现封装性，但是，struct不能进行继承，更不能进行多态功能的实现。class可以进行类的继承，并且，其对虚函数的支持，使C++的类具有多态的性质。因此，引入class，是C++在C语言基础上重要的拓展，这是struct难以实现的。

3. 另外，二者的默认的访问控制属性也不同，C中struct默认是均是公有类型(public)且不能修改，C++中class默认是私有类型(private)，且可以手动修改成其他类型。

### 主题二：操作系统：

#### t1. 听说过孤儿进程和僵尸进程嘛？

孤儿进程是父进程退出后它的子进程还在执行，这时候这些子进程就成为孤儿进程。孤儿进程会被init进程收养并完成状态收集。

僵尸进程是指子进程完成并退出后父进程没有使用wait()或者waitpid()对它们进行状态收集，这些子进程的进程描述符仍然会留在系统中。这些子进程就成为僵尸进程。

#### t2. 异常和中断有何区别？

**中断：**是指由于外部设备事件所引起的中断，如通常的磁盘中断、打印机中断等；

**异常：**是指由于 CPU 内部事件所引起的中断，如程序出错(非法指令、地址越界)。

异常是由于执行了现行指令所引起的。由于系统调用引起的中断属于异常。而中断则是由于系统中某事件引起的，该事件与现行指令无关。

### 主题三：计算机网络：

#### t1. TCP的三次握手中，每一次握手的各类序号写一下？

- TCP第一次握手期间：客户机向服务器发送请求报文段，**发送序号为x**

- TCP第二次握手期间：服务器向客户机发送请求+确认报文段，**发送序号为y**，**确认报文段为x+1**

- TCP第三次握手期间：客户机向服务器发送确认报文段，**发送序号为x+1**，**确认序号为y+1**

#### t2. 第一次握手的seq序号是随机产生的嘛？

首先，seq的全称为**sequence number**：表示的是发送方这边，这个packet的数据部分的第一位应该在整个data stream中所在的位置。（注意这里使用的是“**应该**”。因为对于没有数据的传输，如ACK，虽然它有一个seq，但是这次传输在整个data stream中是不占位置的。所以下一个实际有数据的传输，会依旧从上一次发送ACK的数据包的seq开始）

- seq的初始值在不同系统实现不一样，一般为随时间增长的值。当seq超过4字节存储空间后从0开始。

- 在某个方向上传输N个字节的数据，序列号就+N，因此seq用于确认在某个方向上传输的字节数。

#### t3. TCP的粘包了解过么？如何产生的以及如何避免？

因为TCP为了减少额外开销，采取的是流式传输，所以接收端在一次接收的时候有可能一次接收多个包。而TCP粘包就是发送方的若干个数据包到达接收方的时候粘成了一个包。多个包首尾相接，无法区分。

导致TCP粘包的**原因**有三方面：

- 发送端等待缓冲区满才进行发送，造成粘包

- 接收方来不及接收缓冲区内的数据，造成粘包

- 由于TCP协议在发送较小的数据包的时候，会将几个包合成一个包后发送

**避免**粘包的措施：

- 通过编程，强制使TCP发生数据传送，不必等到缓冲区满

- 优化接收方接收数据的过程，使其来得及接收数据包，包括提高接收进程优先级等

- 设置固定长度的报文或者设置报文头部指示报文的长度。

### 主题四：算法

#### t1.手写快速排序，请问其时间复杂度和空间复杂度各为多少？

```c++

#include

using namespace std;

int a[10] = {1, 9, 4, 0, 2, 3, 5, 7};

int qPartition(int left, int right) {

int i = left, j = right;

int tmpRecord = a[j];

while (i != j) {

while (a[i] <= tmpRecord && j > i)

i++;

if (i < j) {

a[j] = a[i];

j--;

}

while (a[j] >= tmpRecord && j > i)

j--;

if (i < j) {

a[i] = a[j];

i++;

}

}

a[i] =tmpRecord;

return i;

}

void quickSort(int left, int right) {

if (left >= right)

return;

int pivot = (left + right) / 2;

swap(a[pivot], a[right]);

pivot = qPartition(left, right);

quickSort(left, pivot - 1);

quickSort(pivot + 1, right);

}

int main() {

quickSort(0, 7);

for (int i = 0; i <= 7; i++)

cout << a[i] << " ";

return 0;

}

```

时间复杂度：$O(nlogn)$

空间复杂度：$O(logn)$

#### t2. 简单叙述希尔排序的过程？

首先它把较大的数据集合按某一**特定值**分割成若干个小组（逻辑上分组，例如每隔3个位置的数为一个小组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。然后缩小特定值继续进行分组，然后进行插入排序。最后特定值为1，及只有1组，进行插入排序。

#### t3. 输入n个数，找到第一个未出现的正整数。（其中，n < 10^6，输入的整数为32位无符号数）。

这道题的处理思路分为以下几个步骤：

1. 将所有负数均设置为给定数组长度值+1。

2. 遍历数组的值，如果出现了5，则将nums[4]处的值变为负数。

3. 最后从0开始遍历，寻找数组中第一个为正数的下标值。

```c++

class Solution {

public:

int firstMissingPositive(vector& nums) {

for (int i = 0; i < nums.size(); i++) {

if (nums[i] <= 0)

nums[i] = nums.size() + 1;

}

for (auto i:nums) {

int num = abs(i);

if (num <= nums.size())

nums[num - 1] = -abs(nums[num - 1]);

}

for (int i = 0; i < nums.size(); i++) {

if (nums[i] > 0)

return i + 1;

}

return nums.size() + 1;

}

};

```