第一篇

1、在函数内定义一个字符数组，用gets函数输入字符串的时候，如果输入越界，为什么程序会崩溃？

答：因为gets无法截断数组越界部分，会将所有输入都写入内存，这样越界部分就可能覆盖其他内容，造成程序崩溃。

2、C++中引用与指针的区别

答：联系：引用是变量的别名，可以将引用看做操作受限的指针；

区别：

1） 指针是一个实体，而引用仅是个别名；

2）引用只能在定义时必须初始化，指针可以不初始化为空；

3）引用初始化之后其地址就不可改变（即始终作该变量的别名直至销毁，即从一而终。注意：并不表示引用的值不可变，因为只要所指向的变量值改变。引用的值也就改变了），但指针所指地址是可变的；如下：

int m=23,n=12;

int& a=m;

a=12; //合法，相当于修改m=12

a=n； //不合法，引用指向的内存地址不可变

3、C/C++程序的内存分区

答：其实C和C++的内存分区还是有一定区别的，但此处不作区分：

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

栈区与堆区的区别：

1）堆和栈中的存储内容：栈存局部变量、函数参数等。堆存储使用new、malloc申请的变量等；

2）申请方式：栈内存由系统分配，堆内存由自己申请；

3）申请后系统的响应：栈——只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆——首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表 中删除，并将该结点的空间分配给程序；

4）申请大小的限制：Windows下栈的大小一般是2M，堆的容量较大；

5）申请效率的比较：栈由系统自动分配，速度较快。堆使用new、malloc等分配，较慢；

总结：栈区优势在处理效率，堆区优势在于灵活；

内存模型：自由区、静态区、动态区；

根据c/c++对象生命周期不同，c/c++的内存模型有三种不同的内存区域，即：自由存储区，动态区、静态区。

自由存储区：局部非静态变量的存储区域，即平常所说的栈；

动态区： 用new ，malloc分配的内存，即平常所说的堆；

静态区：全局变量，静态变量，字符串常量存在的位置；

注：代码虽然占内存，但不属于c/c++内存模型的一部分；

4、快速排序的思想、时间复杂度、实现以及优化方法

答：快速排序的三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）；
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

基准的选择：

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。

即：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时间复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；

快排代码实现：

我们一般选择序列的第一个作为基数，那么快排代码如下：

void quicksort(vector<int> &v,int left, int right)
{  
    if(left < right)//false则递归结束
    {    
        int key=v[left];//基数赋值
        int low = left;                
        int high = right;   
        while(low < high)    //当low=high时，表示一轮分割结束
        {                        
            while(low < high && v[high] >= key)//v[low]为基数，从后向前与基数比较
            {                                
                high--;                        
            }
            swap(v[low],v[high]);

            while(low < high && v[low] <= key)//v[high]为基数，从前向后与基数比较
            {                                
                low++;                        
            }      
            swap(v[low],v[high]);
        }                 
        //分割后，对每一分段重复上述操作
        quicksort(v,left,low-1);               
        quicksort(v,low+1,right);
    }
}
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

注：上述数组或序列v必须是引用类型的形参，因为后续快排结果需要直接反映在原序列中；

优化：

上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最差的o(n^2)。所以，优化方向就是合理的选择基数。

常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等），如下：

①当序列区间长度小于 7 时，采用插入排序；
②当序列区间长度小于 40 时，将区间分成2段，得到左端点、右端点和中点，我们对这三个点取中数作为基数；
③当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分别再得到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取中数，然后将该值作为基数。
具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：

       int key=v[left];//基数赋值
        if(right-left+1<=7){
            insertion_sort(v,left,right);//插入排序
            return;
        }else if(right-left+1<=8){
            key=SelectPivotOfThree(v,left,right);//三个取中
        }else{
            //三组三个取中，再三个取中（使用4次SelectPivotOfThree，此处不具体展示）
        }
1
2
3
4
5
6
7
8

需要调用的函数：

void insertion_sort(vector<int> &unsorted,int left, int right)  //插入排序算法      
{        
    for (int i = left+1; i <= right; i++)        
    {        
        if (unsorted[i - 1] > unsorted[i])        
        {       
            int temp = unsorted[i];       
            int j = i;       
            while (j > left && unsorted[j - 1] > temp)

            {         
                unsorted[j] = unsorted[j - 1];        
                j--;        
            }   
            unsorted[j] = temp;    
        }    
    }   
}

int SelectPivotOfThree(vector<int> &arr,int low,int high)  //三数取中，同时将中值移到序列第一位
{  
    int mid = low + (high - low)/2;//计算数组中间的元素的下标  

    //使用三数取中法选择枢轴
    if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]  
    {  
        swap(arr[mid],arr[high]);
    }  
    if (arr[low] > arr[high])//目标: arr[low] <= arr[high]  
    {  
        swap(arr[low],arr[high]);
    }  
    if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]  
    {  
        swap(arr[mid],arr[low]);
    }  
    //此时，arr[mid] <= arr[low] <= arr[high]  
    return arr[low];  
    //low的位置上保存这三个位置中间的值  
    //分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了  
}  
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

这里需要注意的有两点：

①插入排序算法实现代码；

②三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然可用。

5、 IO模型——IO多路复用机制

答：预备知识介绍：

IO模型有4中：同步阻塞IO、同步非阻塞IO、异步阻塞IO、异步非阻塞IO；IO多路复用属于IO模型中的异步阻塞IO模型，在服务器高性能IO构建中常常用到。

上述几个模型原理如下图：

同步阻塞IO：                                                           同步非阻塞IO：                                            IO多路复用（异步阻塞IO）：

如上：同步异步是表示服务端的，阻塞非阻塞是表示用户端，所以可解释为什么IO多路复用（异步阻塞）常用于服务器端的原因；

文件描述符（FD，又叫文件句柄）：描述符就是一个数字，它指向内核中的一个结构体(文件路径，数据区等属性)。具体来源：Linux内核将所有外部设备都看作一个文件来操作，对文件的操作都会调用内核提供的系统命令，返回一个fd(文件描述符)。

下面开始介绍IO多路复用：

（1）I/O多路复用技术通过把多个I/O的阻塞复用到同一个select、poll或epoll的阻塞上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。与传统的多线程/多进程模型比，I/O多路复用的最大优势是系统开销小，系统不需要创建新的额外进程或者线程。

（2）select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。

（3）I/O多路复用的主要应用场景如下：

服务器需要同时处理多个处于监听状态或者多个连接状态的套接字；
服务器需要同时处理多种网络协议的套接字；

（4）目前支持I/O多路复用的系统调用有 select，poll，epoll，epoll与select的原理比较类似，但epoll作了很多重大改进，现总结如下：

①支持一个进程打开的文件句柄FD个数不受限制（为什么select的句柄数量受限制：select使用位域的方式来传递关心的文件描述符，因为位域就有最大长度，在linux下是1024，所以有数量限制）；

②I/O效率不会随着FD数目的增加而线性下降；

③epoll的API更加简单；

（5）三种接口调用介绍：

①select函数调用格式：

#include <sys/select.h>




1
2
3
4
5