【面试】 深信服 C++软件开发 研发 物联 方向

微信搜索“编程笔记本”，获取更多信息
————- codingbook2020 ————-

早上在逛 leetcode 时看到一篇面经分享的帖子，苦于只有面试题，没有答案。今天我就来总结一下答案，以备后阅。

面试题目

文章目录

• • • 面试题目
    • 1. C++ 内存分区，未初始化的全局变量放在哪果进行编译，在二进制文件中有它的位置吗/li>
    • 2. 野指针是什么什么工具可以检测吗/li>
    • 3. 进程间通信方式，知道互斥锁和自旋锁吗/li>
    • 4. 能用 memcpy 判断两个结构体存放的内容是不一样的吗/li>
    • 5. 知道哈希冲突吗么解决冲突果只有 32 个槽，怎么存放几千个数据/li>
    • 6. 路由器和二层交换机的区别/li>
    • 7. 用过 shell 脚本吗/li>
    • 8. 知道二叉树有哪些遍历的方式吗续遍历的实现/li>
    • 9. 假设 4 个人在夜里过桥，每个人过桥的时间分别为 1,2,5,8 ，只有一个手电筒，一次最多过两个人，怎么过桥速度最快果是 n 个人，怎么计算过桥时间/li>
    • 10. ARP 协议的功能是什么/li>
    • 11. 快速排序的思想/li>

1. C++ 内存分区，未初始化的全局变量放在哪果进行编译，在二进制文件中有它的位置吗/h3>

在 C++ 语言中，内存被分为 5 个区：堆、栈、自由存储区、全局/静态存储区和常量存储区。

• 栈：由编译器在需要时分配，不需要时自动清除的变量存储区。存储的变量通常为局部变量、函数参数、返回值等

• 堆：一般由程序员主动分配（malloc）和释放（free），如果程序员分配后未释放，那么在程序运行结束后，操作系统会自动回收。

• 自由存储区：由程序员主动使用 new 和 delete 生成和释放的内存区域，自由存储区

• 全局/静态存储区：存放全部变量和静态变量的内存区域。在 C 语言里，全部变量分为已初始化的和未初始化的，而在 C++ 里没有这种区分，它们都存放在同一块内存区域

• 常量存储区：存放常量

因此我们知道，未初始化的全部变量存放在全局/静态存储区。

再来看一下 bss 段、data 段、text 段、heap 段、stack 段。

• bss 段：bss 段，通常是指用来存放程序中未初始化的全局变量的一块内存区域，属于静态内存分配

• data 段：数据段，通常是指用来存放程序中已初始化的全局变量的一块内存区域，属于静态内存分配

• text 段：代码段，通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。

• heap 段：堆，是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）

• stack 段：栈，是用户存放程序临时创建的局部变量，但不包括 static 声明的变量，static 意味着在数据段中存放变量。

一个程序本质上都是由 bss 段、data 段、text 段三个部分组成的。一般在初始化时 bss 段部分将会清零。bss段属于静态内存分配，即程序一开始就将其清零了。在C语言之类的程序编译完成之后，已初始化的全局变量保存在 data 段中，未初始化的全局变量保存在 bss 段中。text 和 data 段都在可执行文件中，由系统从可执行文件中加载；而 bss 段不在可执行文件中，由系统初始化。

2. 野指针是什么什么工具可以检测吗/h3>

野指针：指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）。指针变量在定义时如果未初始化，其值是随机的。指针变量的值是别的变量的地址，意味着指针指向了一个地址是不确定的变量，此时去解引用就是去访问了一个不确定的地址，所以结果是不可知的。

检测工具：valgrind 中的 memcheck 工具。（Valgrind 是一款用于内存调试、内存泄漏检测以及性能分析的软件开发工具。）

3. 进程间通信方式，知道互斥锁和自旋锁吗/h3>

进程间通信方式：管道、消息队列、信 、信 量、共享内存等。

接下来，我们考虑一个实际场景：
两个线程 A,B 访问同一块内存。理想情况下的执行顺序是 A 执行完成后，B 再执行。但是，执行是要占用 CPU 指令时间的，如果不用任何机制的话，当 A 执行到一半时，B 占用了 CPU ，B 去处理这段内存，然后 B 执行完毕，A 再得到 CPU ，内存数据不就出错（改变）了吗/p>

为了内存的数据安全，就采用了一种互斥的技术。

A 访问这段内存的时候，首先判断这段内存有没有在使用中的标志（取个名字叫做锁），没有的话对这段内存加一个标志（锁），然后 A 去处理这段内存，A 处理完了解锁。如果在 A 处理这段内存的时候 B 来访问的话，B 看到这段内存已经有使用中的标志（锁）了，B 可以有如下几种行为。

• 行为一：占用 CPU。不断循环并测试锁的状态，线程不会挂起（睡眠），处于忙等状态，采用这种行为的锁叫做自旋锁。
• 行为二：线程 B 休眠阻塞，放弃 CPU，直到 A 执行完了，锁没了，再使用内存。这种行为叫做互斥锁。

看到这里你大概也明白了，锁就是实现互斥作用的同步机制。自旋锁就是互斥锁的一种情况（等待的时候会占用 CPU 的互斥锁）罢了。

4. 能用 memcpy 判断两个结构体存放的内容是不一样的吗/h3>

这个题目的意思我不是十分明确，所以我不做解答，只列出 memcpy 相关内容。

指的是 C 和 C++ 使用的内存拷贝函数，函数原型为:

函数的功能是从源内存地址的起始位置开始拷贝若干个字节到目标内存地址中，即从源 source 中拷贝 n 个字节到目标 destin 中。

这里有一点需要注意，只是单纯地把指定开始位置的指定长度拷贝到指定目标位置。当我们拷贝结构体的时候，如果结构体里有指针，那么这个指针就变成共享的了。即指针所指向的内存是不会被拷贝的。

5. 知道哈希冲突吗么解决冲突果只有 32 个槽，怎么存放几千个数据/h3>

哈希冲突：通过哈希函数产生的哈希值是有限的，而数据量可能多余哈希值的数量，导致经过哈希函数处理后有不同的数据对应相同的哈希值。这时候就产生了哈希冲突。

解决方案：

1. 开放地址法

• 线性探测：按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突
• 再平方探测：按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上先加 1 的平方个单位，若仍然存在则减 1 的平方个单位。随之是 2 的平方，3 的平方等等。直至不发生哈希冲突
• 伪随机探测：按顺序决定哈希值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来哈希值的基础上加上随机数，直至不发生哈希冲突

2. 链式地址法

对于相同的哈希值，使用链表进行连接。使用数组存储每一个链表。HashMap 的哈希冲突就是使用这种方法去解决的。

• 优点：拉链法处理冲突简单，平均查找长度较短；由于各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可
• 缺点：指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率

3. 建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。

4. 再哈希法

对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

极少的槽数如何存储海量的数据/strong>

如果只有 32 个槽，却要存放几千个数据，在这种情况下产生的哈希冲突是巨大的，并且数据的具体数量我们也无法事先确定，因此使用链式地址法去处理这种情况下的哈希冲突会比较合适。

6. 路由器和二层交换机的区别/h3>

路由器：

传统地，路由器工作于 OSI 七层模型中的第三层，即 络层，其主要任务是接收来自一个 络接口的数据包，根据其中所含的目的地址，决定转发到下一个目的地址。因此，路由器首先得在转发路由表中查找它的目的地址，若找到了目的地址，就在数据包的帧格前添加下一个 MAC 地址，同时 IP 数据包头的 TTL 域也开始递减，并重新计算校验和。当数据包被送到输出端口时，它需要按顺序等待，以便被传送到输出链路上。

二层交换机：

二层交换技术是发展比较成熟，二层交换机属数据链路层设备，可以识别数据包中的 MAC 地址信息，根据 MAC 地址进行转发，并将这些 MAC 地址与对应的端口记录在自己内部的一个地址表中。

路由器和二层交换机的区别：

传统交换机从 桥发展而来，属于 OSI 第二层即数据链路层设备。它根据 MAC 地址寻址，通过站表选择路由，站表的建立和维护由交换机自动进行。其最大的好处是速度快。路由器属于 OSI 第三层即 络层设备，它根据 IP 地址寻址，通过路由表路由协议产生，依靠软件寻址，速度慢。

7. 用过 shell 脚本吗/h3>

shell ：在计算机科学中，shell俗称壳（用来区别于核），是指“为使用者提供操作界面”的软件（命令解析器）。它接收用户命令，然后调用相应的应用程序。

shell 有很多不同的版本，例如常听到的 Bourne SHell（sh）、在 Sun 里头默认的 C SHell、 商业上常用的 K SHell ， 还有 TCSH 等等。每一种 Shell 都各有其特点。至于 Linux 使用的版本就称为 “Bourne Again SHell（简称 bash）”，这个 Shell 是 Bourne Shell 的增强版本，也是基准于 GNU 的架构下发展出来的。

**shell 脚本：**简单地说，shell 就是将许多指令汇整写一起，让使用者很容易地就能够一个操作执行多个命令，而 shell script 是一种编程语言，提供了数组，循环，条件以及逻辑判断等重要功能，让使用者可以直接以 shell 来写程序。

一个简单的使用：

运行脚本：

8. 知道二叉树有哪些遍历的方式吗续遍历的实现/h3>

常用的二叉树遍历方式有：前序遍历、中序遍历、后序遍历、层次遍历。每种遍历方式都有递归和非递归两种实现方法。

前序遍历：先访问根节点，再访问左子树，最后访问右子树。

中序遍历：先访问左子树，再访问根节点，最后访问右子树。

后序遍历：先访问左子树，再访问右子树，最后访问根节点。

层次遍历：从根节点开始，每一层都按从左到右的顺序访问。常用队列的非递归实现形式。

9. 假设 4 个人在夜里过桥，每个人过桥的时间分别为 1,2,5,8 ，只有一个手电筒，一次最多过两个人，怎么过桥速度最快果是 n 个人，怎么计算过桥时间/h3>

既然每次过桥都需要手电筒照明，那么手电筒过桥了以后就必须要有人送回来，选什么人送回来呢/p>

当然是跑得最快的人啦！

所以每次让跑得最快的那个人陪同一个人过桥，然后再由其将手电带回，陪同下一个过桥。

10. ARP 协议的功能是什么/h3>

地址解析协议，即 ARP (Address Resolution Protocol) ，是根据 IP 地址获取物理地址的一个 TCP/IP 协议。

11. 快速排序的思想/h3>

快速排序采用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
具体的快速排序等十种排序方法见往期笔记。

点击下方图片关注我，或微信搜索**“编程笔记本”**，获取更多信息。