主题一：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第一次握手期间：客户机向服务器发送请求报文段，发送序号为

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

• TCP第三次握手期间：客户机向服务器发送确认报文段，发送序号为 ，确认序号为

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.手写快速排序，请问其时间复杂度和空间复杂度各为多少？

#include <bits/stdc++.h>
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;
}

• 时间复杂度：

• 空间复杂度：

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

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

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

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

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

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

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

class Solution {
public:
    int firstMissingPositive(vector<int>& 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;
    }
};