PAGE PAGE 1 我为进软院在大学做过啥准备 递归函数的时间复杂度 有头节点的好处 中断的处理过程 中断在操作系统中有着重要地位，它是多道程序得以实现的基础，没有中断就没有多道程序，因此进程之间的切换是通过中断来完成的。此外，为了提高处理机的利用率和实现CPU与I/O设备的并行执行，也必须要有中断的支持。 中断和陷入 中断：是指CPU对I/O设备发来的中断信号的一种响应。CPU保护暂停当前进程，转而去处理引发中断的进程。执行完后，再返回到原进程，继续执行。I/O设备可以是字符设备（键盘），块设备（磁盘）或通信设备（网络）等。由于中断是外部造成的，所以又叫外中断。 陷入：显然，陷入是由CPU进程内部事件引发的中断，因此叫陷入或内中断。其产生的原因往往是由于进程本身出现运行时异常。 两者的区别仅仅是信号的来源 中断向量表和中断优先级 1.中断向量表 用于记录相应中断处理程序入口地址的映射表。表中有为中断类型分配的中断号和相对应的中断处理程序的入口地址。当中断来临时，由中断控制器确定中断号，再到表中寻找程序。 2.中断优先级 对于并发的中断请求，必须要给出合理的中断顺序，比如键盘中断和磁盘中断谁更重要等，要给出解决中断的优先级。 多中断的处理方式 试想一种情况：当处理机正在处理键盘引起的终端，此时又收到了高优先级的磁盘中断，应该如何处理？ 1.屏蔽（禁止）中断 对于新来的中断，在当前中断未完成之前，对于其他中断不予理睬，直到当前处理完。采用先来先服务的方式。 2.嵌套中断 中断的中断。中断处理程序也是进程，当更高优先级的中断处理程序到来时，可以剥夺当前中断处理进程的处理机，及中断的中断。此种情况下，CPU总是优先响应更高优先级的中断请求。 中断处理程序的处理过程 1.测定是否有未响应的中断信号。当设备完成I/O后，设备控制器会向处理机发送中断信号，告诉I/O完成。之后要测试在中断请求队列中是否有未响应的请求。 2.保护被中断进程的CPU环境。保存现场，将进程的CPU信息全部载入进程PCB中（堆栈区），然后切换进程。 3.转入相应的设备处理程序。根据中断号找到相应程序的入口，交给设备驱动程序。 4.中断处理。检测设备控制器中相应设备的状态（正常、异常），并给予相应的解决。 5.恢复CPU现场并退出中断。如果是屏蔽中断，返回被中断进程；嵌套中断，检查优先级队列，根据是否有更高优先级中断请求，选择返回原中断还是处理更高优先级中断； 6.检测中断是否处理正确，向上层软件确定结果，报告等后续操作。 2.微机：512*4的芯片，要组成4M的存储空间要用几个芯片级联，具体用多少引脚。 3.电子线路：逻辑电路去异步时序电路的区别 后来老师告诉第二题的答案，我问了一句,能不能麻烦老师告诉我第三题的答案啊，这个想不起来了好遗憾， 4.8259是干什么，具体内部怎么实现的 答：可编程中断控制器。? ?再问，那具体内部怎么实现的，我说了它与CPU连接的原理，老师说不对要内部的。。。我就不会了。。。后来老师说就到这里可以了 然后就是一顿自我介绍，注意了自我介绍很重要，由于那天人很多你们自我介绍一定要突出重点，本人就是得了个c语言竞赛的奖，还有学习成绩什么的，还有个中级设计师证书，然后表示对软件有兴趣，学习态度也好，很期待来软院充实的学习。 说出网络任意一层 物理层 协议 CDMA（码分多路复用） 任务 1.解决如何在连接各个计算机的传输媒体上传输数据比特流，而不是指具体的传输媒体 2.确定与传输媒体接口有关的一些特性 数据链路层 协议 HDLC（高级数据链路控制）【特点：1.面向比特2.同步】 PPP 任务 1.将源自网络层的数据可靠的传输到相邻结点的目标网络层 2.加强物理层传输原始比特流的功能 3.将物理层提供的可能出错的物理连接改造成逻辑上无差错的数据链路 4.使之对网络层表现为一条无差错的链路 网络层 协议 ICMP（网际报文控制协议），IGMP，IP，ARP，RARP 任务 1.把分组从源端传递到目的端 2.为分组交换网上的主机提供通信服务 3.单位：数据报 4.提供主机与主机之间的逻辑通信 5.功能 1.路由选择与分组转发（最佳路径） 2.异构网络互连 3.拥塞控制 1.开环控制 2.闭环控制 传输层 协议 TCP，OSPF，UDP SCTP（流控制传输协议）【可靠，端点到端点】 任务 1.使用网络层的服务，为应用层提供通信服务 功能 1.提供进程和进程之间的逻辑通信 2.复用和分用 3.对收到的报文进行差错检测 4.两种协议 应用层 协议 DHCP（动态主机配置协议） BGP，RIP，HTTP，FTP，SMTP TFTP（简单文件传输协议）【基于UDP

1、给你四个坐标点，判断它们能不能组成一个矩形，如判断 ([0,0],[0,1],[1,1],[1,0]) 能组成一个矩形。

勾股定理，矩形是对角线相等的四边形。只要任意三点不在一条直线上，任选一点，求这一点到另外三点的长度的平方，两个短的之和如果等于最长的，那么这就是矩形。

2、写一段代码判断单向链表中有没有形成环，如果形成环，请找出环的入口处，即 P 点

65、php 进程模型，php 怎么支持多个并发

守护进程模型（需要知道 php-fpm 的各种配置了）

66、nginx 的进程模型，怎么支持多个并发

这个三言两语说不清楚。

php-fpm 的配置并不多，常用的就更少了。

68、让你实现一个简单的架构，并保持高可用，两个接口，一个上传一条文本，一个获取上传的内容，你怎么来设计？要避免单机房故障，同时要让代码层面无感。

参考：分布式架构设计必备 CAP 原理。

69、两台 mysql 服务器，其中一台挂了，怎么让业务端无感切换，并保证正常情况下讲台服务器的数据是一致的

不是核心业务的话，先停写，把备机拉起来，查看两台机器的日志，进行数据补偿，开写。

如果是核心业务的话，现在所有的写操作都在正常的状态机器上。把好的这台机器的备机拉起来，当主机。

以上全是应急操作。实际上数据库的容灾设计要复杂的多。

面试官要是问你，备机的数据不一致怎么办，你要勇敢怼回去，你们每秒多少写入操作。按照百万级表，每秒 1000 的写入效率，正常的设计是，分布在 2 台机器上每台 500。这个级别的数据同步，出现差异的概率 可以忽略不计的。有一台出现问题，另一台也可以抗住。

（正常的操作，还是先停写，等数据一致，切换，开写。我们公司搞这些切换都是在凌晨 4.00 左右，核心业务的每秒写操作，只有十几个。前后耽搁不到 20 秒）。

70、http 协议具体的定义

这种题 有是很难回答的。太宽泛了，我们面试早就不问这种问题了。

参考：日本人写的《图解 HTTP》

71、什么是锁，怎么解决锁的问题

计算机原理学的，生产者消费者模型，银行家模型，都可以解决锁的问题。

我实习的时候遇到这个坑。

在随机数区间不大的情况下并没有很大的效率差距。但是出现重复数的几率，rand 要比 mt_rand 高很多。

73、mysql 事务隔离是怎么实现的

通过各种行锁表锁，各种乐观锁悲观锁，排他锁实现的呀。

75、对称加密和非对称加密的方式

对称加密：我们俩共用一个秘钥，你加密，我解密。

非对称加密：我给你一个公钥，你加密完了，我还能有我的私钥把密文解开。但是你没有我的私钥。

76、10 瓶水，其中一瓶有毒，小白鼠喝完有毒的水之后，会在 24 小时后死亡，问：最少用几只小白鼠可以在 24 小时后找到具体是哪一瓶水有毒。

二进制问题。薛定谔的老鼠。

一只老鼠有两个状态，死活，对应 01。假设老鼠的个数为 A，则有 2^A>=10; A=4；

0 不喝。第一只老鼠喝所有个位是 1 的：13579，第二只喝十位是 1 的，第三只和百位是 1 的，第四只喝千位是 1 的。

24 小时后，看下死了的是 1，活着的是 0。按老鼠的顺序乖乖站好…… 假如第一只和第三只死了，那就是 0101，就是 5 有问题。

77、redis 是如何进行同步的，同步的方式，同步回滚怎么办，数据异常怎么办，同时会问 MYSQL 的同步方式和相关异常情况

redis 集群主从同步的简单原理

　　Redis 的复制功能是基于内存快照的持久化策略基础上的，也就是说无论你的持久化策略选择的是什么，只要用到了 Redis 的复制功能，就一定会有内存快照发生。

　　Slave 首先会将数据文件保存到本地 之后再将 数据 加载到内存中。

　　当第一次链接 或者是 故障后 重新连接 都会先判断 Slave 的存活状态 在做全部数据的同步 ， 之后只会同步 Master 的写操作 (将命令发送给 Slave)

　　当 Master 同步数据时 若数据量较大 而 Master 本身只会启用一个后台进程 来对多个 Slave 进行同步 ， 这样 Master 就会压力过大 ， 而且 Slave 恢复的时间也会很慢！

redis 主从复制的优点：

 (1)在一个Redis集群中，master负责写请求，slave负责读请求，这么做一方面通过将读请求分散到其他机器从而大大减少了master服务器的压力，另一方面slave专注于提供

读服务从而提高了响应和读取速度。

　　(2) 在一个 Redis 集群中，如果 master 宕机，slave 可以介入并取代 master 的位置，因此对于整个 Redis 服务来说不至于提供不了服务，这样使得整个 Redis 服务足够安全。

　　(3) 水平增加 Slave 机器可以提高性能

（1）可读性方面：基本相同，XML 的可读性比较好；

（2）可扩展性方面：都具有良好的扩展性；

（3）编码难度方面：相对而言，JSON 的编码比较容易；

（4）解码难度：JSON 的解码难度基本为零，XML 需要考虑子节点和父节点；

（5）数据体积方面：JSON 相对于 XML 来讲，数据体积小，传递的速度比较快；

（6）数据交互方面：JSON 与 javascript 的交互更加方便，更容易解析处理，更好的数据交互；

（7）数据描述方面：XML 对数据描述性比较好；

（8）传输速度方面：JSON 的速度远远快于 XML。

在 trait 继承中，优先顺序依次是：来自当前类的成员覆盖了 trait 的方法，而 trait 则覆盖了被继承的方法

81、a 引用 b，报错 c 里面类重复定义，循环引用会出现什么问题

82、下面员工 3 的薪水大于其主管的薪水，一条 SQL 找到薪水比下属低的主管

82、在一个坐标系内有一个 N 个点组成的多边形，现在有一个坐标点，写代码或思路来判断这个点是否处于多边形内

83、数据库如果出现了死锁，你怎么排查，怎么判断出现了死锁？

84、写一个一个程序来查找最长子串

85、分析一个问题:php-fpm 的日志正常，但客户端却超时了，你认为可能是哪里出了问题，怎么排查？

86、nginx 的工作流程是什么样的，可以画图描述

87、进程间通信方式有哪些

管道分为有名管道和无名管道
无名管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系一般指的是父子关系。无名管道一般用于两个不同进程之间的通信。当一个进程创建了一个管道，并调用 fork 创建自己的一个子进程后，父进程关闭读管道端，子进程关闭写管道端，这样提供了两个进程之间数据流动的一种方式。
有名管道也是一种半双工的通信方式，但是它允许无亲缘关系进程间的通信。

信号量是一个计数器，可以用来控制多个线程对共享资源的访问., 它不是用于交换大批数据，而用于多线程之间的同步。它常作为一种锁机制，防止某进程在访问资源时其它进程也访问该资源。因此，主要作为进程间以及同一个进程内不同线程之间的同步手段.

信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生.

消息队列是消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点。消息队列是 UNIX 下不同进程之间可实现共享资源的一种机制，UNIX 允许不同进程将格式化的数据流以消息队列形式发送给任意进程。对消息队列具有操作权限的进程都可以使用 msget 完成对消息队列的操作控制。通过使用消息类型，进程可以按任何顺序读信息，或为消息安排优先级顺序.

共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC (进程间通信) 方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步与通信.

6) 套接字：可用于不同及其间的进程通信

88、主从复制，从服务器会读取到主服务器正在回滚的数据吗？主数据库写成功，从服务器因为一些原因写失败，最后会出现什么情况？主从复制如果键冲突怎么办？

不会；主从数据不一致；正常是不会出现这种情景，具体看情况，是否可以修复，恢复到之前的时间点，然后追回同步。

89、事务有几种隔离级别？事务的隔离级别是怎么实现的？

91、mysql 中的字符集，客户端与数据库不一致，怎么办？MYSQL 中字符串到显示到界面，字符转换的过程是怎样的？数据库中的字符集是 latin1, 你现在将 utf8 的字符串存到 latin1 字符集的数据库表，你能将 utf8 的字符串存进去吗？假如你说能存，追问：能否恢复？假如能，那怎么恢复？

94、设计一个缓存系统，可以定期或空间占满之后自动删除长期不用的数据，不能使用用遍历。

我当时的答案是用链表来存，缓存命中就将该缓存移到链表头，然后链表尾就都是冷数据了。
我记得之前是在哪里看过这个设计，但我忘记在连接了，请知道朋友的把连接贴上来。

• == 等于，不需要对比数据类型
• === 全等，需要对比类型

96、一个排序好的数组，将它从中间任意一个位置切分成两个数组，然后交换它们的位置并合并，合并后新数组元素如：20,21,22,25,30,1,2,3,5,6,7,8,15,18,19, 写一个查询函数来查找某个值是否存在。

97、设计一个树形结构，再写一个函数对它进行层序遍历

双引号串中的内容可以被解释而且替换，而单引号串中的内容总被认为是普通字符。

在单引号串中甚至反斜杠也失去了他的扩展含义（除了插入反斜杠 \ 和插入单引号 \'）。所以，当你想在字串中进行变量代换和包 含 \n（换行符）等转义序列时，你应该使用双引号。单引号串可以用在其他任何地方，脚本中使用单引号串处理速度会更快些。

static：如果在子类中重写了父类中的 static 方法、属性，父类就会去访问了子类的 static 方法

self: 是类内指针，不管子类有没有重写过父类中的方法、属性都指向本类的静态方法、属性

100、PHP 的协程以及用途

103、哪些属性唯一确定一条 TCP 连接

区别主要在数据和索引的存储结构和存储方式上，以及对于事务的支持。

105、断开 TCP 连接时，timewait 状态会出现在发起分手的一端还是被分手的一端

为什么建立 TCP 连接需要三次握手？
原因：为了应对网络中存在的延迟的重复数组的问题
假设 client 发起连接的连接请求报文段在网络中没有丢失，而是在某个网络节点长时间滞留了，导致延迟到达 server。本来这是一个已经失效的连接报文，但是 server 接收到这个连接报文之后，误认为 client 发起了新的连接，于是向 client 发送确认报文段。此时因为没有了连接的 3 次握手，client 不会对 server 的确认报文作出回应，也不会向 server 发送数据，server 就以为连接已经建立，一直在空等 client 的数据，这样 server 的这一部分网络资源就被浪费了。

为什么断开 TCP 连接需要进行四次握手 ？
因为 TCP 连接是全双工的网络协议，允许同时通信的双方同时进行数据的收发，同样也允许收发两个方向的连接被独立关闭，以避免 client 数据发送完毕，向 server 发送 FIN 关闭连接，而 server 还有发送到 client 的数据没有发送完毕的情况。所以关闭 TCP 连接需要进行四次握手，每次关闭一个方向上的连接需要 FIN 和 ACK 两次握手。

被动关闭连接的一方 (图中的 server) 在一段时间内没有收到对方的 ACK 确认数据包，会重新发送 FIN 数据包，因而主动关闭连接的一方需要停留在等待状态以处理对方重新发送的 FIN 数据包。否则他会回应一个 RST 数据包给被动关闭连接的一方，使得对方莫名其妙。

在 TIME_WAIT 状态下，不允许应用程序在当前 ip 和端口上和之前通信的 client (这个 client 的 ip 和端口号不变) 建立一个新的连接。这样就能避免新的连接收到之前的 ip 和端口一致的连接残存在网络中的数据包。这也是 TIME_WAIT 状态的等待时间被设置为 2MSL 的原因，以确保网络上当前连接两个方向上尚未接收的 TCP 报文已经全部消失。

106、AWK 各种数据分析考得非常多，要多练习，题目不再一一写了

108、描述一下：一个请求到达 nginx 的全部处理过程（nginx 自身会调用哪些逻辑）、然后怎么与 php 通信，中间的流程是什么样的等等？

109、nginx 和 php-fpm 的相关配置，随便问里面各种参数啥意思

110、假如有一张地图，如下图，"-" 代表海洋、"+" 代表陆地，用你最擅长的方式，取出陆地的坐标。

比如上图在数组中表示成，1 表示成陆地，0 表示海洋:

写个算法取出所有陆地的坐标，并按块放到一起，如地图上左上角第一个陆地的坐标是:

111、Jsonp 的实现原理，你还知道哪些跨域方式？

112、如果某个博客通过判断 referer 方式来进行图片防盗链，如何破解？

curl 设置来源地址来欺骗对方服务器验证

113、简述 mysql 查询优化的本质，并举 2 个例子

114、设计一个秒杀系统，如何保证商品不超卖？

115、单例模式的优点是什么？抽象类是什么？ 还了解哪些设计模式？

单例模式又称为职责模式，它用来在程序中创建一个单一功能的访问点，通俗地说就是实例化出来的对象是唯一的。
所有的单例模式至少拥有以下三种公共元素：

1. 它们必须拥有一个构造函数，并且必须被标记为 private
2. 它们拥有一个保存类的实例的静态成员变量
3. 它们拥有一个访问这个实例的公共的静态方法
   单例类不能再其它类中直接实例化，只能被其自身实例化。它不会创建实例副本，而是会向单例类内部存储的实例返回一个引用。

抽象的类不能被实例化。任何一个类，如果它里面至少有一个方法是被声明为抽象的，那么这个类就必须被声明为抽象的。被定义为抽象的方法只是声明了其调用方式（参数），不能定义其具体的功能实现。

116、斗地主中，地主比农民得到王炸的概率多多少？

很多人在刚接触这个行业的时候或者是在遇到瓶颈期的时候，总会遇到一些问题，比如学了一段时间感觉没有方向感，不知道该从那里入手去学习，对此我整理了一些资料，需要的可以免费分享给大家

如果喜欢我的文章，想与一群资深开发者一起交流学习的话，获取更多相关大厂面试咨询和指导，欢迎加入我的学习交流群

1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是

2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是A．1 B.2 C.3 D.4

3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL

4.下列二叉排序树中，满足平衡二叉树定义的是

5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是

6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系

7.下列关于无向连通图特性的叙述中，正确的是

I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1

8.下列叙述中，不符合m阶B树定义要求的是

A．根节点最多有m棵子树 B.所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接

9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是

10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是

A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序