牛人整理分享面试知识：操作系统、计算机网络、设计模式、Linux编程，数据结构总结

╰半橙微兮° 2021-12-10 16:09 94阅读 0赞

感谢面试群 S-北京-陈磊 的整理分享。  
[https://blog.51cto.com/qiaopeng688/1856781][https_blog.51cto.com_qiaopeng688_1856781]

[https://juejin.im/entry/592257b62f301e006b183b95][https_juejin.im_entry_592257b62f301e006b183b95]

基础篇：操作系统、计算机网络、设计模式

一：操作系统

1.  进程的有哪几种状态，状态转换图，及导致转换的事件。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjQyOTg3_size_16_color_FFFFFF_t_70]

> 运行状态：进程正在处理机上运行。在单处理机环境下，每一时刻最多只有一个进程处于运行状态。
> 
> 就绪状态：进程已处于准备运行的状态，即进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。
> 
> 阻塞状态，又称等待状态：进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。
> 
> 注意区别就绪状态和等待状态：就绪状态是指进程仅缺少处理机，只要获得处理机资源就立即执行；而等待状态是指进程需要其他资源（除了处理机）或等待某一事件。
> 
> 就绪状态 -> 运行状态：处于就绪状态的进程被调度后，获得处理机资源（分派处理机时间片），于是进程由就绪状态转换为运行状态。
> 
> 运行状态 ->  
> 就绪状态：处于运行状态的进程在时间片用完后，不得不让出处理机，从而进程由运行状态转换为就绪状态。此外，在可剥夺的操作系统中，当有更高优先级的进程就  
> 、 绪时，调度程度将正执行的进程转换为就绪状态，让更高优先级的进程执行。
> 
> 运行状态 ->  
> 阻塞状态：当进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如I/O操作的完成）时，它就从运行状态转换为阻塞状态。进程以系统调用的形式请求操作系统提供服务，这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式。
> 
> 阻塞状态 -> 就绪状态：当进程等待的事件到来时，如I/O操作结束或中断结束时，中断处理程序必须把相应进程的状态由阻塞状态转换为就绪状态。

1.  **进程与线程的区别。**
2.  **进程通信的几种方式**。

进程通信是指进程之间的信息交换。PV操作是低级通信方式，髙级通信方式是指以较高的效率传输大量数据的通信方式。高级通信方法主要有以下三个类。

> **共享存储**
> 
> 在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换。在对共享空间进行写/读操作时，需要使用同步互斥工具（如  
> P操作、V操作），对共享空间的写/读进行控制。共享存储又分为两种：低级方式的共享是基于数据结构的共享；高级方式则是基于存储区的共享。操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。
> 
> 需要注意的是，用户进程空间一般都是独立的，要想让两个用户进程共享空间必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。
> 
> **消息传递**
> 
> 在消息传递系统中，进程间的数据交换是以格式化的消息(Message)为单位的。若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。
> 
> 1.  直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。
> 2.  
> 
> 间接通信方式：发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。该通信方式广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。
> 
> **管道通信**
> 
> 管道通信是消息传递的一种特殊方式。\*\*所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入（写）管道；而接收管道输出的接收进程（即读进程），则从管道中接收（读）数据。\*\*为了协调双方的通信，**管道机制**必须提供以下三方面的协调能力：**互斥、同步和确定对方的存在**。

1.  线程同步几种方式。**(一定要会写生产者、消费者问题，完全消化理解)**

> 多进程虽然提高了系统资源利用率和吞吐量，但是由于进程的异步性可能造成系统的混乱。进程同步的任务就是对多个相关进程在执行顺序上进行协调，使并发执行的多个进程之间可以有效的共享资源和相互合作，保证程序执行的可再现性
> 
> **同步机制需要遵循的原则：**
> 
> \*\*空闲让进：\*\*当没有进程处于临界区的时候，应该许可其他进程进入临界区的申请  
> \*\*忙则等待：\*\*当前如果有进程处于临界区，如果有其他进程申请进入，则必须等待，**保证对临界区的互斥访问**  
> \*\*有限等待：\*\*对要求访问临界资源的进程，需要在有限时间内进入临界区，防止出现死等  
> \*\*让权等待：\*\*当进程无法进入临界区的时候，需要释放处理机，边陷入忙等  
> **经典的进程同步问题：生产者-消费者问题；哲学家进餐问题；读者-写者问题**
> 
> **同步的解决方案：管程，信号量。**

1.  线程的实现方式. (也就是用户线程与内核线程的区别)
2.  用户态和核心态的区别。
3.  用户栈和内核栈的区别。
4.  内存池、进程池、线程池。(c++程序员必须掌握)
5.  死锁的概念，导致死锁的原因.
6.  导致死锁的四个必要条件。

> 死锁产生的必要条件：  
> 互斥条件:进程对所分配的资源进行排他性的使用  
> 请求和保持条件：进程被阻塞的时候并不释放锁申请到的资源  
> 不可剥夺条件：进程对于已经申请到的资源在使用完成之前不可以被剥夺  
> 环路等待条件：发生死锁的时候存在的一个 进程-资源 环形等待链

1.  **处理死锁的四个方式**。

> 预防死锁：破坏产生死锁的4个必要条件中的一个或者多个；实现起来比较简单，但是如果限制过于严格会降低系统资源利用率以及吞吐量
> 
> 避免死锁：在资源的动态分配中，防止系统进入不安全状态(可能产生死锁的状态)-如银行家算法
> 
> 检测死锁：允许系统运行过程中产生死锁，在死锁发生之后，采用一定的算法进行检测，并确定与死锁相关的资源和进程，采取相关方法清除检测到的死锁。实现难度大
> 
> 解除死锁：与死锁检测配合，将系统从死锁中解脱出来（撤销进程或者剥夺资源）。对检测到的和死锁相关的进程以及资源，通过撤销或者挂起的方式，释放一些资源并将其分配给处于阻塞状态的进程，使其转变为就绪态。实现难度大

1.  **预防死锁的方法、避免死锁的方**法。
2.  **进程调度算法。(周转时间 = 程序结束时间 – 开始服务时间、带权周转时间= 周转时间 / 要求服务时间)**

> 先来先服务调度算法FCFS：既可以作为作业调度算法也可以作为进程调度算法；按作业或者进程到达的先后顺序依次调度；因此对于长作业比较有利；
> 
> 短作业优先调度算法SJF：作业调度算法，算法从就绪队列中选择估计时间最短的作业进行处理，直到得出结果或者无法继续执行；缺点：不利于长作业；未考虑作业的重要性；运行时间是预估的，并不靠谱  
> ；
> 
> 高响应比算法HRN：响应比=(等待时间+要求服务时间)/要求服务时间；
> 
> 时间片轮转调度RR：按到达的先后对进程放入队列中，然后给队首进程分配CPU时间片，时间片用完之后计时器发出中断，暂停当前进程并将其放到队列尾部，循环  
> ;
> 
> 多级反馈队列调度算法：目前公认较好的调度算法；设置多个就绪队列并为每个队列设置不同的优先级，第一个队列优先级最高，其余依次递减。优先级越高的队列分配的时间片越短，进程到达之后按FCFS放入第一个队列，如果调度执行后没有完成，那么放到第二个队列尾部等待调度，如果第二次调度仍然没有完成，放入第三队列尾部…。只有当前一个队列为空的时候才会去调度下一个队列的进程。

1.  **Windows内存管理的方式(块式、页式、段式、段页式)**.
2.  内存连续分配方式采用的几种算法及各自优劣。
3.  动态链接及静态链接.
4.  基本分页、请求分页储存管理方式。
5.  基本分段、请求分段储存管理方式。
6.  分段分页方式的比较各自优缺点。
7.  几种页面置换算法，会算所需换页数。(LRU用程序如何实现？)
8.  虚拟内存的定义及实现方式。
9.  操作系统的四个特性。
10. DMA。
11. Spooling。
12. 外存分配的几种方式，及各种优劣。

二：计算机网络

1.  电路交换与分组交换的区别？优劣对比。
2.  OSI有哪几层，会画出来，知道主要几层的各自作用。
3.  TCP/IP有哪几层，会画出来，知道所有层数的作用，会列举各层主要的协议名称。
4.  硬件(MAC)地址的概念及作用。
5.  ARP协议的用途 及算法、在哪一层上会使用arp ？
6.  CRC冗余校验算法，反码和检验算法。
7.  如何实现透明传输。
8.  知道各个层使用的是哪个数据交换设备。（交换机、路由器、网关）
9.  路由表的内容。
10. 分组转发算法。
11. IP报文的格式，格式的各个字段的含义要理解。

12.MTU的概念，啥叫路径MTU？ MTU发现机制，TraceRoute(了解)。

13.RIP协议的概念及算法。

14.ICMP协议的主要功能。

15.组播和广播的概念，IGMP的用途。(环回地址、广播地址)

16.Ping协议的实现原理，ping 命令格式。

1.  子网划分的概念，子网掩码。
2.  IP地址的分类，如何划分的，及会计算各类地址支持的主机数。

19.DNS的概念，用途，DNS查询的实现算法。

1.  TCP与UDP的概念，相互的区别及优劣。

21.UDP报文的格式，字段的意义。

1.  TCP 报文的格式，字段的意义。

23.TCP通过哪些措施，保证传输可靠？

1.  三次握手，四次断开过程。
2.  TIME\_WAIT状态的概念及意义。

26.滑动窗口协议 与停止等待协议的区别。

1.  TCP的流量控制和拥塞控制实现原理(会画拥塞控制的典型图)。

28.TCP的快速重传与快速恢复算法。

29.TFTP 与 FTP的区别。

30.阻塞方式和非阻塞方式，阻塞connect与非阻塞connect。(比较难，有兴趣可以了解)

1.  HTTP基本格式。（Java程序员必须掌握）

三：设计模式

1.  各种常用模式的用途，使用方法(类图)。
2.  单例模式的双重检查实现。
3.  MVC模式

提高篇：WIN32、MFC与Linux

一： WIN32

1.  Win32应用程序的基本类型.
2.  创建win32窗口程序的几个步骤，及使用到的函数。
3.  nmake 与 makefile。
4.  有哪些字符集？ Win32对于各种字符集如何进行兼容及转换？ (wchar\_t、TCHAR、TEXT() )。
5.  怎么创建一个子窗口？在哪进行设置？
6.  窗口类的分类，如何创建一个应用程序全局窗口类。
7.  Win32窗口程序运行机制与控制台程序的运行机制有何区别?
8.  Getmessage函数的作用，与Peekmessage函数的区别。
9.  发送WM\_QUIT消息使程序终止的内部过程。
10. TranslateMessage及 DispatchMessage的作用。
11. SendMessage与PostMessage的区别。
12. Win32消息机制获取消息的过程(先查看什么消息？再查看什么消息?)
13. 知道有哪几类主要的消息。(WM\_CREATE, WM\_DESTROY, WM\_SIZE, WM\_SYSCOMMAND, WM\_COMMAND, WM\_PAINT, 鼠标消息, 键盘消息)。
14. 定时器如何使用。
15. 用户自定义消息如何定义。
16. 创建菜单、设置菜单的函数，在哪处理菜单命令的消息。
17. 加速键如何使用？
18. GDI绘图对象，使用的步骤，及函数。
19. 使用位图的步骤及用到的主要函数。
20. 可用于文字绘制的API函数。
21. 有模式对话框与无模式对话框的区别，创建步骤。收到的创建消息是什么？
22. 子控件和父窗口通过什么进行通信？ 父窗口在哪里处理子窗口发送的消息？
23. 有哪些常见的子控件？(静态框、编辑框、按钮、listbox、comboBox、滚动条)25. 什么样的控件支持自绘制？
24. 动态库与静态库的区别。
25. Win32里面怎样用静态库？ C++程序在引用c的静态库时，需要注意什么？
26. Win32里面动态库有哪几种导出方式，有哪几种导入方式？（注意c++的导出方式）
27. Win32里面文件打开和关闭的API。
28. Windows地址空间的划分。
29. Windows 内存使用的几种方式及相应的函数(虚拟内存、堆内存、栈内存)。
30. Malloc内部调用A函数，A函数调用B函数。A和B分别是什么？
31. 内存映射文件的作用。主要函数。
32. 创建进程和打开进程用什么函数？ 有什么区别？
33. 创建线程用什么函数？
34. Waitforsingleobject与Waitformultiobjects的区别。Waitforsingleobject的第二个参数为0表示什么意思?37. 关闭线程和关闭进程的函数分别是什么？
35. 线程局部存储(TLS)的意义,如何指定一个变量的TLS属性。
36. Win32线程同步提供的方式，及主要函数为什么？
37. 提供的同步措施中哪些是内核对象？ 试比较互斥量和临界区。

二：MFC

1.  MFC包含哪几类程序？ 其中MFC应用程序又包含哪几类？
2.  MFC的中的大多数类都继承自哪个类？
3.  MFC主要要用到哪几个类？及其各个类的作用。
4.  MFC中有哪6类核心机制？Cobject中封装了哪些机制？
5.  在哪个类的什么函数中进行MFC程序初始化？ 相当于main功能的函数。
6.  MFC应用程序的启动机制的实现。（几个步骤及相关函数）
7.  窗口的创建及窗口处理函数机制的实现。（几个步骤及相关用到函数）
8.  消息映射机制的原理及实现。宏。(查找消息处理函数的几个步骤及其函数)
9.  MFC的消息分类。自注册消息用什么函数进行注册？消息映射宏是什么？
10. MFC菜单、工具栏、状态栏所用的类是什么？
11. 怎么定义一个视图窗口？
12. 划分窗口使用什么类？ 划分窗口有哪两类，有什么区别？
13. 运行时类信息 机制的宏，及原理。CRuntimeClass的内容，isKindOf实现方法。
14. 动态创建 机制的宏，及实现。与运行时类信息在内容添加上的区别？
15. 消息的派发会经过哪几个类？一般在哪个类里进行处理？SetActiveView的作用。
16. 单文档、多文档模板类是什么？ 保存模板类用什么函数？新建模板用什么函数？
17. 单文档视图的创建过程及所用到的相关函数。
18. MFC绘图有哪几类DC？各自的类名，及区别。
19. MFC有哪几类绘图对象？各自的类名。
20. MFC有哪几类数据集合类？CMAP的底层实现？
21. MFC的文件类是什么？文件查找类是什么？
22. 序列化机制 的宏，怎么使用？ 执行>>和<<时进行的内部操作及其相应函数。
23. MFC的对话框的种类，各自怎么使用？及相关函数。
24. 定义对话框数据交换的步骤，及使用方法，实现原理。
25. 通用对话框有哪些，试举例。
26. MFC常用的通用控件有哪些？举出类名。
27. MFC的动态库有哪几种类型？扩展库一般用来做什么？
28. MFC的线程有哪几类？ 相互有什么区别？各自的创建方法是什么？
29. VC环境下可以使用哪几类socket？ 其中MFC的socket类 有哪几种，各自区别？类名是什么？用什么函数初始化MFC的socket库。

三：Linux基本命令

1.  绝对路径用什么符号表示？当前目录、上层目录用什么表示？主目录用什么表示? 切换目录用什么命令？
2.  怎么查看当前进程？怎么执行退出？怎么查看当前路径？
3.  怎么清屏？怎么退出当前命令？怎么执行睡眠？怎么查看当前用户id？查看指定帮助用什么命令？
4.  Ls 命令执行什么功能？ 可以带哪些参数，有什么区别？
5.  建立软链接(快捷方式)，以及硬链接的命令。
6.  目录创建用什么命令？创建文件用什么命令？复制文件用什么命令？
7.  文件权限修改用什么命令？格式是怎么样的？
8.  查看文件内容有哪些命令可以使用？
9.  随意写文件命令？怎么向屏幕输出带空格的字符串，比如”hello world”?
10. 终端是哪个文件夹下的哪个文件？黑洞文件是哪个文件夹下的哪个命令？
11. 移动文件用哪个命令？改名用哪个命令？
12. 复制文件用哪个命令？如果需要连同文件夹一块复制呢？如何需要有提示功能呢？
13. 删除文件用哪个命令？如果需要连目录及目录下文件一块删除呢？删除空文件夹用什么命令？
14. Linux下命令有哪几种可使用的通配符？分别代表什么含义?
15. 用什么命令对一个文件的内容进行统计？(行号、单词数、字节数)
16. Grep命令有什么用？ 如何忽略大小写？ 如何查找不含该串的行?
17. Linux中进程有哪几种状态？在ps显示出来的信息中，分别用什么符号表示的？
18. 怎么使一个命令在后台运行?
19. 利用ps怎么显示所有的进程? 怎么利用ps查看指定进程的信息？
20. 哪个命令专门用来查看后台任务?
21. 把后台任务调到前台执行使用什么命令?把停下的后台任务在后台执行起来用什么命令?
22. 终止进程用什么命令? 带什么参数?
23. 怎么查看系统支持的所有信号？
24. 搜索文件用什么命令? 格式是怎么样的?
25. 查看当前谁在使用该主机用什么命令? 查找自己所在的终端信息用什么命令?
26. 使用什么命令查看用过的命令列表?
27. 使用什么命令查看磁盘使用空间？ 空闲空间呢?
28. 使用什么命令查看网络是否连通?
29. 使用什么命令查看ip地址及接口信息？
30. 查看各类环境变量用什么命令?
31. 通过什么命令指定命令提示符?
32. 查找命令的可执行文件是去哪查找的? 怎么对其进行设置及添加?
33. 通过什么命令查找执行命令?34. 怎么对命令进行取别名？

四：Linux编程

1.  列举Linux内存管理相关的几个函数，各自有什么功能？
2.  GCC只编译的选项是什么？只进行预处理的选项是什么？在命令行定义宏的选项是什么？
3.  Linux静态库的使用，怎么创建一个静态库？ 怎么使用一个静态库？静态库文件的后缀名是什么？静态库的命名规范。
4.  nm 工具的作用，ldd工具的作用。
5.  Linux动态库的使用，怎么创建一个动态库？ 动态库文件的后缀名是什么？怎么使用一个动态库？动态库的命名规范？ 系统默认的动态库的查找路径？动态库显示连接所使用的系统库是什么？
6.  Linux下make 与makefile。用什么参数指定makefile文件？ 什么是默认的makefile文件。
7.  在哪个文件夹下存有进程运行时的所有信息？
8.  每个程序默认打开哪三个文件设备？
9.  操作文件描述符的读写函数是什么？打开文件描述符以及关闭文件描述符的函数？
10. Fcntl函数主要的几个作用。
11. 创建进程的几个函数，及各自区别。
12. 父进程先结束，子进程会变为？ 子进程先结束，子进程会变为？
13. 怎么使父进程回收子进程？ 相关的几个函数。
14. 子进程在创建时与父进程的内存资源的复制问题。
15. 中断信号、终止信号、定时器信号的宏是什么？
16. 在程序中注册信号和发送信号用什么函数?
17. 信号的可靠与不可靠的含义。哪些信号是可靠的？哪些信号是不可靠的？
18. 信号屏蔽用什么函数？ SigSuspend的作用？ Sigpending的作用？
19. 信号处理函数处理信号时是否会被信号中断？
20. 最新版本的信号发送与处理函数？与老版本的发送与数据函数有什么区别？
21. Linux下进程有哪些通信方式(IPC)？
22. TCP服务器编程模型。
23. UDP服务器编程模型。
24. TCP编程特征，由于每次不定长数据到达，则一般使用什么选项？
25. Selected模型是什么？ 相比而言多进程实现方式有什么区别？Selected、epoll模型、poll模型的区别。
26. 常用的socket选项有哪些？利用哪个函数来设置socket选项？
27. 怎么发送和设置带外(OOB)数据？
28. Linux 下多线程的库是什么？ 利用哪个函数创建线程？利用哪个函数强制结束线程？主线程等待子线程结束时使用的函数?
29. 线程怎样在被迫退出时能做一些善后处理？以及怎么用linux特有的方式处理？

算法篇：算法与数据结构

一：算法

1.  算法的几个特征是什么。
2.  算法复杂性的定义。大O、θ、、小o分别表示的含义。
3.  递归算法的定义、递归算法的两要素。
4.  分治算法的思想，经典的分治算法(全排列、二分搜索、归并排序、快速排序、线性时间选择、最接近点对问题)。
5.  动态规划算法解题框架，动态规划算法的两个要素是什么？备忘录方法是什么？
6.  经典的动态规划问题(矩阵连乘问题、最长公共子序列问题、0-1背包问题)。
7.  贪心算法的思想，贪心算法的两个要素。
8.  经典的贪心问题(活动安排问题、背包问题、装载问题、哈夫曼编码、单源最短路径、最小生成树问题)。9. 回溯法的思想，回溯法中有哪两种典型的模型。
9.  经典的回溯算法(n后问题、0-1背包问题、旅行售货商问题)。
10. 分支限界法思想，有哪两种分支限界法。
11. 经典的分支限界算法(0-1背包问题、旅行售货商问题)。

二：数据结构

1.  数据结构的定义。
2.  栈的两个应用：括号匹配和表达式的计算。是怎么应用的？表达式计算用的是哪种表达方式？有什么好处?
3.  字符串匹配算法：朴素的匹配算法、KMP算法。
4.  二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。
5.  堆，建堆算法，堆的插入和删除算法，堆排序。
6.  哈希。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？
7.  二叉搜索树的搜索、插入、删除。时间复杂度。
8.  二叉平衡树的插入结点的原理，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。
9.  红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。
10. 图有哪些储存表示。
11. 链表插入排序、链表归并排序。
12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。
13. 常用分配排序有哪几种？ 基数排序的定义，分类及原理。
14. 外部排序的过程。
15. B树、B+树、Trie的概念及用途，添加删除结点的原理。

记录一下这些问题。都解决喽！！！

转载：[http://www.itmian4.com/forum.php?mod=viewthread&tid=3614][http_www.itmian4.com_forum.php_mod_viewthread_tid_3614]

[https_blog.51cto.com_qiaopeng688_1856781]: https://blog.51cto.com/qiaopeng688/1856781
[https_juejin.im_entry_592257b62f301e006b183b95]: https://juejin.im/entry/592257b62f301e006b183b95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjQyOTg3_size_16_color_FFFFFF_t_70]: /images/20211210/d1c1f5f8f68442da9e25c4f75512675b.png
[http_www.itmian4.com_forum.php_mod_viewthread_tid_3614]: http://www.itmian4.com/forum.php?mod=viewthread&tid=3614