模拟面试面经

缺乏、安全感 2023-07-07 08:06 1阅读 0赞

### 模拟面试面经 ###

0、说一下什么是 STL？

*  STL 是 C++ 标准库的组成部分，里面有 6 大组件，分别是容器、算法、迭代器、仿函数、空间配置器、配接器
 *  容器分为序列式和关联式，区别是序列式存储的是元素本身，关联式以键值对的形式存储
 *  我所了解的序列式容器有 vector、list、deque、string，其中 vector 的底层结构是动态的数组，可以随着元素的增加自动扩容，扩容分两种一种是直接扩容，一种是拷贝的方式，另外 vector 在进行插入和删除时是O(N)的时间复杂度，访问元素是以O(1)的时间复杂度，这也正是和 list 的区别，list 的底层是一个双向链表，可以在任意位置插入删除，但是访问的时候是以O(N)的时间复杂度去遍历的；string 可以理解为一种数据类型，也可以理解为字符串类，类中提供了构造，拷贝，赋值，尾加，插入等一系列的方法；deque 是一种双端队列，它支持在头部和尾部进行插入删除，都是O(1)复杂度，另外它一般不使用偏移量的方式去访问元素，因为其底层结构并不连续，结构比较复杂是由中央控制器和多个缓存区组成.
 *  我所了解的关联式容器有 set ，map ,unordered\_map，和 unordered\_set ，其中 set 和 map 底层结构是红黑树，有排序的功能，默认为升序，查找的时间复杂度是log2N,map 和 set 的区别是 set 可以去重，而 map 不会； unordered\_map 和 unordered\_set 的底层结构是哈希表，所以查找起来就比较方便，都是O(1)的时间复杂度.

1、STL 容器中的迭代器的作用是啥？

*  迭代器的行为表现的很像指针，但又不是指针，它只是模拟了指针的行为，或者进行了封装，迭代器返回的是对象的引用，所以输出的时候需要解引用
 *  它存在的意义，我觉得可以不用暴露集合的内部结构，就可以达到循环遍历的效果
 *  我知道的类型有四种，分别是正向迭代器(iterator)，反向迭代器(reverse\_iterator)，const 正向迭代器(const \_iterator)，const 反向迭代器(const\_reverse\_iterator)
 *  迭代器如果使用不恰当可能会造成迭代器失效，就比如 vector 在插入的时候，如果导致原来的空间被释放，那么迭代器也就失效了，如果在删除的时候，没有返回赋值给下一个迭代器，也会造成失效，导致非法访问.

2、空间配置器是啥？

*  STL 六大组件之一，容器通过配置器取得数据存储空间,算法通过迭代器获取容器内容,仿函数可以协助算法完成不同的策略变化,配接器可以修饰或套接仿函数。
 *  空间配置器目的为各个容器高效的管理空间，我们平时使用 vector，list 、map …可能感觉不到它，但是如果申请内存失败了，或者发生内存泄漏，还有就是频繁的申请造成内存碎片，这些问题都是空间配置器解决的
 *  空间配置器可以分为一级和两级，一级处理的是大块内存(超过 128 K)，二级处理的是小块内存，其中一级处理器直接对 malloc 和 free 进行了封装， 如果申请内存成功则返回，如果失败了则会检查用户是否设置了对应措施，如果没有措施则抛出异常；二级空间配置器通过内存池来实现，提高申请空间的速度，减少了额外的空间浪费
 *  内存池是先申请一块比较大的内存，用户如果需要直接去内存池取就行了，用完再返回内存池，这样可以避免频繁的向系统申请空间所造成的内存碎片。

3、仿函数是啥？可以举个例子吗？

*  仿函数主要是为了搭配算法使用的，使一个类看上去像一个函数，它本质其实是重载了一个 `()`操作符，有了类似函数的作用，所以叫仿函数，但其实是一个类；使用仿函数，代码写起来易于扩展
 *  和函数指针很相似，但是函数指针无法满足对抽象性的要求，不能和其他组件搭配使用，另外仿函数的执行速度也比普通函数快，比如说普通函数的调用需要保存当前的寄存器值，传递参数，返回值，返回到函数调用地方继续执行等

案列1

struct MyPlus { 
    	int operator()(const int &a, const int &b) const { 
    		return a + b;
    	}
    };
    
    int main(){ 
    	MyPlus a;
    	//1、通过产生临时对象调用重载运算符
    	cout << MyPlus()(1, 2) << endl;
    	//2、通过对象显示调用重载运算符
    	cout << a.operator()(1, 2) << endl;
    	//3、通过对象类似函数调用 隐示地调用重载运算符
    	cout << a(1, 2) << endl;
    	return 0;
    }

案例2：

struct Cmp{ 
    	bool operator()(const int a,const int b){ 
    		return a>b;
    	}
    }cmp; 
    
    int main(){ 
    	vector<int>v{ 1,3,4,5,2,6};
    	sort(v.begin(),v.end(),cmp);
    	
    	return 0;
    }

4、适配器是啥，为什么不使用 vector 作为底层结构，而要使用 deque ？

*  把一种接口转换为另一种接口，比如说把 deque 封装后可以实现 stack 功能的数据结构，把 stack 称之为适配器，常用的适配器有三种， stack 、queue、priority\_queue，其中 stack 底层结构都是 deque，而 priority\_queue 底层结构可以理解为一个大堆，有排序的功能，默认是大堆升序排序；
 *  由于 stack 和 queue 是不需要遍历的，所以 vector 的优势施展不出来，另外 deque 可以支持在首端和尾端操作，比 vector 效率高，内存的使用率也很高

5、STL 常用的算法有哪些？

*  查找算法，经常使用的是 find 函数，利用指定元素范围的元素和输入元素比较，当匹配时，返回指向该元素的迭代器
 *  排序算法，经常使用 sort 函数，默认是升序排序，也可以自己制定排序规则
 *  删除函数，常用 remove，可以删除容器内指定的元素
 *  替换函数，常用 replace 将指定范围内所有等于 old 的元素都用 new 代替
 *  其它算法，reverse 是将指定范围内元素翻转，max 返回两个元素中的最大值，min 返回最小值

6、sort 排序的底层结构是怎么样的？

*  当数据量大时，采用快速排序，分段递归进行排序
 *  如果分段后的数据量很小时，比如小于16，为了避免快排的递归带来过大的额外的开销，sort() 算法就自动改为插入排序
 *  如果递归的层次过深，比如大于 2 \* logN 则会进行堆排序
 *  所以 sort 底层会根据不同的数量级自动选择合适的排序算法

7、线程安全是啥意思，可以举个例子吗？

*  线程安全是多个线程去访问同一块临界区的资源时，不会出现二义性问题，也不会造成和预期不一样的结果，那就是线程安全的
 *  比如两个线程对一个初始值为 0 的全局变量进行 100 次的 +1 操作，而每次都只有一个线程去访问临界资源，最后的结果就是 200，那么线程是安全的

8、对于 UDP 和 TCP 之间的区别？

*  UDP 无连接，TCP 通信之前必须连接，所以这就导致了 TCP 的效率比较低，因为在建立连接和断开连接的时候需要耗费时间，UDP 虽然无连接，但是效率高，经常用于广播通信，早期的 QQ 聊天也是基于 UDP 实现的
 *  TCP 可以提供可靠的传输服务，主要的机制有确认应答，超时重传，滑动窗口，流量控制，拥塞控制，延迟应答，捎带应答，…等;而 UDP 是不可靠的
 *  TCP 是面向字节流，数据是以字节流的形式传递给接收者的，所以这也就导致了粘包问题，而 UDP 是不存在粘包问题的

> 具体详细参考[https://blog.csdn.net/qq\_43763344/article/details/103783150][https_blog.csdn.net_qq_43763344_article_details_103783150]

9、内联函数和宏函数的区别？内联函数的展开是啥意思？

*  内联函数是在普通函数前面加一个 inline 关键字，在编译期间可能会进行展开，也就相当于给编译器一个建议，将指定的函数体(内联函数)插入并且取代每一处调用该函数的地方，从而可以减少每次调用函数带来的额外时间开销，因为函数调用会压栈，内联函数则不需要
 *  但是编译器是否会这样做，主要取决于函数的结构和调用次数，如果一个函数比较复杂，里面具有循环和递归，则不会展开，因为内联函数本质是一个空间替换时间的策略，如果展开函数，占用的空间太大反而得不偿失，另外内联函数的编译时间也会很长，使用起来也有一些注意事项，比如定义和声明不能分开，因为函数被定义为内联函数就没有地址，所以在链接的时候会找不到.
 *  内联函数相比宏而言，需要做参数类型的检查，所以更加安全，也可以进行调试，而宏是文本的替换，虽然增强了代码复用性，但是可读性差，不易维护，容易出错. 最后 C++ 中 const 定义常量和内联函数定义函数可以替代宏.

### 关于代码 ###

1、手写归并排序，归并排序的思想？

思路：首先把数列拆开排序，先使每个子序列有序，再使一个子序段之前有序，最终合并为一个有序的数列，空间复杂度为O(N),时间复杂度为O(N\*log2N)

void MergeData(int* arr, int left, int mid, int right, int* temp) { 
    	int begin1 = left;
    	int begin2 = mid;
    	int end1 = mid;
    	int end2 = right;
    	int index = left;
    	while (begin1 < end1 && begin2 < end2) { 
    		if (arr[begin1] < arr[begin2]) { 
    			temp[index++] = arr[begin1++];
    		}
    		else{ 
    			temp[index++] = arr[begin2++];
    		}
    	}
    	while (begin1 < end1) { 
    		temp[index++] = arr[begin1++];
    	}
    	while (begin2 < end2) { 
    		temp[index++] = arr[begin2++];
    	}
    }
    
    void MergeSort(int *arr, int left, int right, int* temp) { 
    	if (right - left <= 1) { 
    		return;
    	}
    	int mid = left + (right - left) / 2;
    	MergeSort(arr, left, mid, temp);
    	MergeSort(arr, mid,right, temp);
    	MergeData(arr, left, mid, right, temp);
    	memcpy(arr + left, temp + left, sizeof(arr[0])*(right - left));
    }
    int main() { 
    	int arr[10] = {  0,2,4,6,8,1,3,5,7,9 };
    	int size = sizeof(arr) / sizeof(arr[0]);
    	int* temp = new int[sizeof(arr)];
    	MergeSort(arr, 0, size, temp);
    	for (auto&e : arr) { 
    		cout << e << ' ';
    	}
    	cout << endl;
    	delete[] temp;
    
    	system("pause");
    	return 0;
    }

2、将一个平衡二叉树转换为一个有序的双向链表？

思路：因为平衡二叉树的中序遍历是有序的，所以可以按照中序遍历的思想，先遍历左子树，然后改变节点的指针指向，最后遍历右子树；改变指向时需要记录前一个节点，使当前节点的左指针指向前一个节点，前一个节点的右指针指向当前节点；所有的工作完成后，最后返回头结点.

ListNode* Convert(ListNode* root) { 
    	ListNode* last = nullptr;
    	ConvertNode(root, &last);
    	// 返回头结点
    	ListNode* head = last;
    	while (head != nullptr && head->left != nullptr) { 
    		head = head->left;
    	}
    	return head;
    }
    
    void ConvertNode(ListNode* root, ListNode** last) { 
    	if (root == nullptr) { 
    		return;
    	}
    	// 设置当前节点，遍历左子树
    	ListNode* cur = root;
    	if (cur->left){ 
    		ConvertNode(cur->left, last);
    	}
    	cur->left = *last;
    	if (*last != nullptr) { 
    		(*last)->right = cur;
    	}
    	// 更新 last 节点，遍历右子树
    	*last = cur;
    	if (cur->right) { 
    		ConvertNode(cur->right, last);
    	}
    }

### 关于项目 ###

1、说一下 HTTP 协议？

*  是一种应用层协议，这种协议是客户端和服务器之间约定的一种规则，比如网络版计算器；HTTP 协议的职责就是生成请求报文和响应报文
 *  请求报文的结构分为报文首部和报文主体，报文首部包含，请求方法，请求的地址 url, 协议版本和首部字段；
 *  响应报文结构也分为报文首部和报文主体两部分，我们平时看到的网页就是存储在响应报文的主体，而报文首部包含响应状态码，和状态码解释，还包含首部字段，是对响应报文中的属性，有键值对组成

回答这个问题，主要从报文的结构出发，可以引出很多问题，其中核心问题是 **请求方法 get ,post 的区别**，**响应报文中的状态码有哪些**？另外还需了解协议版本，常用的首部字段

> 具体详细参考  
> [https://blog.csdn.net/qq\_43763344/article/details/98677491][https_blog.csdn.net_qq_43763344_article_details_98677491]

2、如果让你实现一个服务器，你会怎么实现？具体的流程？

首先我从客户端说起，首先要创建一个套接字，之后就可以连接服务器了，当然对于 UDP 服务器不用连接， 如果是TCP的话，就调用 socket apl connect 函数建立连接，在发送数据之前，进行组装协议格式，可以按照 HTPP 协议的格式进行组装，然后调用 socket apl send 函数将数据发送给服务器，如果服务器有响应，可以使用 socket apl recv 函数去接收数据，拿到数据后则使用对应协议规则来解析

对于服务器第一步同样需要创建套接字，然后将端口号和 IP 地址绑定在一个套接字上，就比如我们通常使用的 HTTP 协议固定端口号时 80 ，那么我们在绑定的是需要避开这些常用的端口，（443 HTTPS，22 SSH远程连接），当绑定之后服务器进入监听状态，这个过程是调用 socket apl listen 函数，可以指定在同一时间最大的连接数，之后服务器进入处理事件的逻辑，在这个逻辑里面，首先调用 accept 函数阻塞等待客户端的连接，当收到一个请求时，通过调用 socket apl recv 函数去接收客户端发来的数据并进行解析，服务器经过处理后，就可以通过调用 send 函数将服务器处理的结果返回给客户端

[https_blog.csdn.net_qq_43763344_article_details_103783150]: https://blog.csdn.net/qq_43763344/article/details/103783150
[https_blog.csdn.net_qq_43763344_article_details_98677491]: https://blog.csdn.net/qq_43763344/article/details/98677491