计算机基础类面试（计网，操作系统，数据库，数据结构等） - 好文

计算机网络

基础

Q：五层协议的体系结构分别是什么？每一层都有哪些协议？

https://blog.csdn.net/cainv89/article/details/46885197
<https://blog.csdn.net/cainv89/article/details/46885197>

*
应用层
<https://www.baidu.com/s?wd=%E5%BA%94%E7%94%A8%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
，应用层
<https://www.baidu.com/s?wd=%E5%BA%94%E7%94%A8%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
确定进程之间通信的性质以满足用户的需要。应用层
<https://www.baidu.com/s?wd=%E5%BA%94%E7%94%A8%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
不仅要提供应用进程所需要的信息交换
<https://www.baidu.com/s?wd=%E4%BF%A1%E6%81%AF%E4%BA%A4%E6%8D%A2&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
和远地操作，还要作为互相作用的应用进程的用户代理
<https://www.baidu.com/s?wd=%E7%94%A8%E6%88%B7%E4%BB%A3%E7%90%86&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
（user agent)；

*
运输层
<https://www.baidu.com/s?wd=%E8%BF%90%E8%BE%93%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
任务是负责主机中两个进程间的通信；

*
网络层
<https://www.baidu.com/s?wd=%E7%BD%91%E7%BB%9C%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
网络层
<https://www.baidu.com/s?wd=%E7%BD%91%E7%BB%9C%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
负责的是分组选择合适的路由；

*
数据链路层
<https://www.baidu.com/s?wd=%E6%95%B0%E6%8D%AE%E9%93%BE%E8%B7%AF%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
数据链路层
<https://www.baidu.com/s?wd=%E6%95%B0%E6%8D%AE%E9%93%BE%E8%B7%AF%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
的任务：将在网络层
<https://www.baidu.com/s?wd=%E7%BD%91%E7%BB%9C%E5%B1%82&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
交下来的数据报组装成帧（frame)，两个相邻结点间的链路实现帧的传输；

*
物理层物理层的任务：透明地传输比特
<https://www.baidu.com/s?wd=%E6%AF%94%E7%89%B9&tn=SE_PcZhidaonwhc_ngpagmjz&rsv_dl=gh_pc_zhidao>
流。

Q：为何有MAC地址还要IP地址？

http://blog.sciencenet.cn/blog-411071-1037673.html
<http://blog.sciencenet.cn/blog-411071-1037673.html>

基本上一个观点就是一个是物理地址，一个是逻辑地址。

假设两点在一个网络内。在这种情况下，只需要MAC地址就可以了。例如通过交换机将多台电脑组成一个网络。

然而，如果两点不在一个网络内。这时就需要IP地址了。因为IP地址含有两个部分，一个是网络地址，一个是主机地址。因此，通过对方的IP地址，是可以判断出对方是否和本机在一个网络内。如果在一个网络内，如上所述，只需要知道对方的MAC地址即可通信。

如果不在一个网络内，本机的网络层就认为数据应该发送给网关。道理是显然的，如果不在一个网络内，首先得把数据发送出网络才可以。如何发出网络，当然是发给网关，因为网关就相当于网络的门卫。要想把数据发给网关，同样需要知道网关的MAC地址，如何知道网关的MAC地址呢？这就涉及到ARP协议。

电脑缓存里有一张ARP表，该表主要有两列：一列是IP地址，另外一列是MAC地址。这张表不是天生就有的，是随着网卡收到网络中的各种通信数据，不断学习增加的。

话说回来，如果ARP表中有网关IP地址对应的MAC地址，则问题就转化为网内数据发送，上面已经讲的很清楚了。如果ARP表中没有网关IP地址对应的MAC地址，则启动ARP协议，即向网内广播，询问该IP地址的MAC地址。广播询问的结果是网关收到广播后，发现是问自己的MAC地址，所以就回复询问方自己的MAC地址。然后数据发给网关的问题，也转化为网内数据发送。

TCP

Q：TCP和UDP的区别？

https://blog.csdn.net/xiaobangkuaipao/article/details/76793702
<https://blog.csdn.net/xiaobangkuaipao/article/details/76793702>

1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接

2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付

Tcp通过校验和，重传控制，序号标识，滑动窗口、确认应答实现可靠传输。如丢包时的重发控制，还可以对次序乱掉的分包进行顺序控制。

3、UDP具有较好的实时性，工作效率比TCP高，适用于对高速传输和实时性有较高的通信或广播通信。

4.每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信

5、TCP对系统资源要求较多，UDP对系统资源要求较少。

Q：拥塞控制和流量控制都是什么，两者的区别？

https://blog.csdn.net/ailunlee/article/details/53716367
<https://blog.csdn.net/ailunlee/article/details/53716367>

流量控制是端到端的控制，例如A通过网络给B发数据，A发送的太快导致B没法接收(B缓冲窗口过小或者处理过慢)，这时候的控制就是流量控制，原理是通过滑动窗口的大小改变来实现。

拥塞控制是A与B之间的网络发生堵塞导致传输过慢或者丢包，来不及传输。防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不至于过载。拥塞控制是一个全局性的过程，涉及到所有的主机、路由器，以及与降低网络性能有关的所有因素。

Q：谈谈TCP为什么要三次握手？为什么要四次挥手？

https://blog.csdn.net/zhaobudaofangxia/article/details/55260259
<https://blog.csdn.net/zhaobudaofangxia/article/details/55260259>

https://blog.csdn.net/qq_33982721/article/details/78493967
<https://blog.csdn.net/qq_33982721/article/details/78493967>

三次握手：

* 第一次。A跟B说，我要建立连接了。
* 第二次。B跟A说，OK，那我也建立连接。
* 第三次。A跟B说，嗯，我知道了。
四次挥手：

* 第一次。A跟B说，我要断开连接了。
* 第二次。B跟A说，好的，我知道了，我不再接收你的信息了。
* 第三次。B跟A说，我传给你的信息传完了，你可以关闭连接了。
* 第四次。A跟B说，好的，我关闭连接了。

Q：播放视频用TCP还是UDP？为什么？

TCP 和 UDP 是质量和实时性的权衡。
拿视频网站来说，你完全可以缓冲 20s 再播放，不会带来什么影响，但如果画面有马赛克之类的东西出现肯定是不好的，所以用 TCP。
而对于视频聊天，如果缓冲 5s，相信整个聊天已经没法愉快的进行了，而这时出现一些画面质量的损失也可以被接受，所以用 UDP。

HTTP

Q：HTTP报文格式？

https://blog.csdn.net/holmofy/article/details/68492045
<https://blog.csdn.net/holmofy/article/details/68492045>

Q：了解哪些响应状态码？

https://blog.csdn.net/oops_qu/article/details/75675702
<https://blog.csdn.net/oops_qu/article/details/75675702>

http状态返回代码 1xx（临时响应）：表示临时响应并需要请求者继续执行操作的状态代码。

http状态返回代码 2xx （成功）：表示成功处理了请求的状态代码。

http状态返回代码 3xx （重定向）：表示要完成请求，需要进一步操作。通常，这些状态代码用来重定向。

http状态返回代码 4xx（请求错误）：这些状态代码表示请求可能出错，妨碍了服务器的处理。

http状态返回代码 5xx（服务器错误）：这些状态代码表示服务器在尝试处理请求时发生内部错误。这些错误可能是服务器本身的错误，而不是请求出错。

Q：get和post的区别？

https://www.cnblogs.com/huaxingtianxia/p/5895236.html
<https://www.cnblogs.com/huaxingtianxia/p/5895236.html>

* GET在浏览器回退时是无害的，而POST会再次提交请求。
* GET产生的URL地址可以被Bookmark，而POST不可以。
* GET请求会被浏览器主动cache，而POST不会，除非手动设置。
* GET请求只能进行url编码，而POST支持多种编码方式。
* GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。
* GET请求在URL中传送的参数是有长度限制的，而POST么有。
* 对参数的数据类型，GET只接受ASCII字符，而POST没有限制。
* GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。
* GET参数通过URL传递，POST放在Request body中。
GET和POST还有一个重大区别

简单的说：

GET产生一个TCP数据包；POST产生两个TCP数据包。

长的说：

对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；

而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

也就是说，GET只需要汽车跑一趟就把货送到了，而POST得跑两趟，第一趟，先去和服务器打个招呼“嗨，我等下要送一批货来，你们打开门迎接我”，然后再回头把货送过去。

因为POST需要两步，时间上消耗的要多一点，看起来GET比POST更有效。因此Yahoo团队有推荐用GET替换POST来优化网站性能。但这是一个坑！跳入需谨慎。为什么？

1. GET与POST都有自己的语义，不能随便混用。

2.
据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基本可以无视。而在网络环境差的情况下，两次包的TCP在验证数据包完整性上，有非常大的优点。

3. 并不是所有浏览器都会在POST中发送两次包，Firefox就只发送一次。

Q：Http1.0、Http1.1、Http2.0的区别？

https://blog.csdn.net/linsongbin1/article/details/54980801/
<https://blog.csdn.net/linsongbin1/article/details/54980801/>

Q：HTTP和TCP的区别?

实际上，传输层的TCP是基于网络层的IP协议的，而应用层的HTTP协议又是基于传输层的TCP协议的，而Socket本身不算是协议，它只是提供了一个针对TCP或者UDP编程的接口。

Q：HTTP和HTTPS的区别?

https://www.cnblogs.com/wqhwe/p/5407468.html
<https://www.cnblogs.com/wqhwe/p/5407468.html>

HTTP：是互联网上应用最为广泛的一种网络协议，是一个客户端和服务器端请求和应答的标准（TCP），用于从WWW服务器传输超文本到本地浏览器的传输协议，它可以使浏览器更加高效，使网络传输减少。

HTTPS：是以安全为目标的HTTP通道，简单讲是HTTP的安全版，即HTTP下加入SSL层，HTTPS的安全基础是SSL，因此加密的详细内容就需要SSL。

HTTPS协议的主要作用可以分为两种：一种是建立一个信息安全通道，来保证数据传输的安全；另一种就是确认网站的真实性。

Q：HTTP和Socket的区别?

https://blog.csdn.net/w369033345/article/details/72779553
<https://blog.csdn.net/w369033345/article/details/72779553>

https://blog.csdn.net/w369033345/article/details/72779553
<https://blog.csdn.net/w369033345/article/details/72779553>

http 为短连接：
客户端发送请求都需要服务器端回送响应.请求结束后，主动释放链接，因此为短连接。通常的做法是，不需要任何数据，也要保持每隔一段时间向服务器发送"保持连接"的请求。这样可以保证客户端在服务器端是"上线"状态。

Socket为长连接：通常情况下Socket 连接就是 TCP 连接，因此 Socket
连接一旦建立,通讯双方开始互发数据内容，直到双方断开连接。在实际应用中，由于网络节点过多，在传输过程中，会被节点断开连接，因此要通过轮询高速网络，该节点处于活跃状态。

Q：在地址栏打入http://www.baidu.com会发生什么？

当输入www.baidu.com时，计算机会请求DNS服务器，进行域名转换，得到服务器IP地址，同时对服务器发出请求，服务器响应请求，客户端浏览器发起一个HTTP会话到IP地址，然后通过tcp进行封装数据包，输入到网络层

Q：长链接与短连接？

https://www.cnblogs.com/gotodsp/p/6366163.html
<https://www.cnblogs.com/gotodsp/p/6366163.html>

操作系统

Q：操作系统中进程和线程的区别？

进程是程序执行的一个实体，线程是CPU调度的最小单位

Q：死锁的产生和避免?

https://www.cnblogs.com/fangrong/p/5271724.html
<https://www.cnblogs.com/fangrong/p/5271724.html>

死锁的四个必要条件：
(1)互斥条件(Mutual exclusion)：资源不能被共享，只能由一个进程使用。
(2)请求与保持条件(Hold and wait)：已经得到资源的进程可以再次申请新的资源。
(3)非剥夺条件(No pre-emption)：已经分配的资源不能从相应的进程中被强制地剥夺。
(4)循环等待条件(Circular wait)：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。

　死锁避免（deadlock
avoidence）是在系统运行过程中注意避免死锁的发生。这就要求每当申请一个资源时，系统都应根据一定的算法判断是否认可这次申请，使得在今后一段时间内系统不会出现死锁。这面方最著名的算法首推Dijkstra[1965]提出的银行家（banker）算法。

数据库

Q：数据库中的事务了解吗？事务的四大特性？

数据库事务是数据库运行中的逻辑工作单位，单个逻辑工作单元所执行的一系列操作，要么都执行，要么都不执行。例如银行取款事务分为2个步骤(1)存折减款(2)提取现金，2个步骤必须同时完成或者都不完成。

数据库事务的四大特性（ACID)：

(1) 原子性(Atomicity)：
事务的原子性指的是，事务中包含的程序作为数据库的逻辑工作单位，它所做的对数据修改操作要么全部执行，要么完全不执行。这种特性称为原子性。
(2)一致性(Consistency) ：

事务的一致性指的是在一个事务执行之前和执行之后数据库都必须处于一致性状态。这种特性称为事务的一致性。假如数据库的状态满足所有的完整性约束，就说该数据库是一致的。
(3)分离性(Isolation)：

分离性指并发的事务是相互隔离的。即一个事务内部的操作及正在操作的数据必须封锁起来，不被其它企图进行修改的事务看到。假如并发交叉执行的事务没有任何控制，操纵相同的共享对象的多个并发事务的执行可能引起异常情况。
(4)持久性(Durability)：

持久性意味着当系统或介质发生故障时，确保已提交事务的更新不能丢失。即一旦一个事务提交，DBMS保证它对数据库中数据的改变应该是永久性的，即对已提交事务的更新能恢复。持久性通过数据库备份和恢复来保证。

Q：如何理解数据库的范式？

https://blog.csdn.net/zymx14/article/details/69789326
<https://blog.csdn.net/zymx14/article/details/69789326>

第一范式（1NF）：确保每一列的原子性

如果每一列都是不可再分的最小数据单元，则满足第一范式。

第二范式:非键字段必须依赖于键字段

如果一个关系满足1NF，并且除了主键以外的其它列，都依赖与该主键，则满足二范式(2NF)，第二范式要求每个表只描述一件事。

第三范式：在1NF基础上，除了主键以外的其它列都不传递依赖于主键列，或者说：任何非主属性不依赖于其它非主属性

（在2NF基础上消除传递依赖）

数据结构与算法

Q：怎么理解数据结构？

带有机构的数据元素的集合

Q：什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割
<https://baike.baidu.com/item/%E9%BB%84%E9%87%91%E5%88%86%E5%89%B2/115896>数列、因
数学家 <https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%AE%B6/1210991>
列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列
<https://baike.baidu.com/item/%E5%85%94%E5%AD%90%E6%95%B0%E5%88%97/6849441>
”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1,
F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

Q：迭代和递归的特点，并比较优缺点

https://blog.csdn.net/laoyang360/article/details/7855860
<https://blog.csdn.net/laoyang360/article/details/7855860>

定义

优点

缺点

递归

程序调用自身的编程技巧称为递归

1）大问题化为小问题,可以极大的减少代码量；

2）用有限的语句来定义对象的无限集合.；

3）代码更简洁清晰，可读性更好

1）递归调用函数,浪费空间；

2）递归太深容易造成堆栈的溢出；

迭代

利用变量的原值推算出变量的一个新值，迭代就是A不停的调用B.

1）迭代效率高，运行时间只因循环次数增加而增加；

2）没什么额外开销，空间上也没有什么增加，

1）不容易理解；

2）代码不如递归简洁；

3）编写复杂问题时困难。

二者关系

1）递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。

2）能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出./*相对*/

Q：了解哪些查找算法，时间复杂度都是多少？

https://blog.csdn.net/qq_23217629/article/details/52517741
<https://blog.csdn.net/qq_23217629/article/details/52517741>

查找

平均时间复杂度

查找条件

算法描述

顺序查找

O(n)

无序或有序队列

按顺序比较每个元素，直到找到关键字为止

二分查找（折半查找）

O(logn)

有序数组

查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。　如果在某一步骤数组为空，则代表找不到。

二叉排序树查找

O(logn)

二叉排序树

在二叉查找树b中查找x的过程为：

1. 若b是空树，则搜索失败

2. 若x等于b的根节点的数据域之值，则查找成功；

3. 若x小于b的根节点的数据域之值，则搜索左子树

4. 查找右子树。

哈希表法（散列表）

O(1)

先创建哈希表（散列表）

根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。

分块查找

O(logn)

无序或有序队列

将n个数据元素"按块有序"划分为m块（m ≤ n）。

每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。然后使用二分查找及顺序查找。

Q：了解哪些排序算法，并比较一下，以及适用场景

https://blog.csdn.net/mountain_hua/article/details/81107024
<https://blog.csdn.net/mountain_hua/article/details/81107024>

排序法

最差时间分析

平均时间复杂度

稳定度

空间复杂度

冒泡排序

O(n2)

O(n2)

稳定

O(1)

插入排序

O(n2)

O(n2)

稳定

O(1)

选择排序

O(n2)

O(n2)

稳定

O(1)

二叉树排序

O(n2)

O(n*log2n)

不一顶

O(n)

快速排序

O(n2)

O(n*log2n)

不稳定

O(log2n)~O(n)

堆排序

O(n*log2n)

O(n*log2n)

不稳定

O(1)

希尔排序

O

O

不稳定

O(1)

Q：快排的基本思路是什么？最差的时间复杂度是多少？如何优化？

（升序）以某个记录的关键字为划分元，将整个数据分为两组，左边的数据小于等于划分元，右边的数据大于等于划分元。对左右两组数据，再各自选择一个划分元，将两组数据划分为更小的序列，这样一直进行下去，直到整个序列有序。
public static void quickSort(int[] array, int left, int right) { if (left <
right) { int pivot = array[left]; int low = left; int high = right; while (low
< high) { while (low < high && array[high] >= pivot) { high--; } array[low] =
array[high]; while (low < high && array[low] <= pivot) { low++; } array[high] =
array[low]; } array[low] = pivot; quickSort(array, left, low - 1);
quickSort(array, low + 1, right); } }
最差时间复杂度即是但数据有序的时候，这时候退化为冒泡排序，时间复杂度为O（n2）

优化：https://blog.csdn.net/sinat_28676875/article/details/69053449
<https://blog.csdn.net/sinat_28676875/article/details/69053449>

Q：冒泡排序如何优化？
public static void bubbleSort(int[] array) { int len = array.length; boolean
flag = true; while (flag) { flag = false; for (int i = 0; i < len - 1; i++) {
if (array[i] > array[i + 1]) { int temp = array[i + 1]; array[i + 1] =
array[j]; array[i] = temp; flag = true; } } len--; } }

存在这样一一种情况，冒泡过程中，后面的若干记录没有发生交换，这时候再继续进行冒泡就显得多此一举了，那么我们只需要记录没有发生交换的位置，对这个位置之后的数据不进行冒泡处理，只对这个位置之前的数据进行冒泡处理，提升算法的效率。

优化后的冒泡排序：
void Bubble_Modified_Sort(int R[],int n){ int i=n; int j; int
LastExchangeIndex; while(i>1){ LastExchangeIndex=1; for(j=0,j<i,j++){
if(R[j]>R[j+1]){ int temp=R[j+1]; R[j+1]=R[j]; R[j]=temp; LastExchangeIndex=j;
} //end if } //end for i=LastExchangeIndex; } //end while }

Q：AVL树插入或删除一个节点的过程是怎样的？

https://blog.csdn.net/Ivan_zgj/article/details/51495926
<https://blog.csdn.net/Ivan_zgj/article/details/51495926>

https://blog.csdn.net/friendbkf/article/details/50160141
<https://blog.csdn.net/friendbkf/article/details/50160141>

Q：什么是红黑树？

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机
<https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA>科学中用到的一种数据结构
<https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450>
，典型的用途是实现关联数组
<https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84/3317025>。

它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo
J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

https://blog.csdn.net/eric491179912/article/details/6179908
<https://blog.csdn.net/eric491179912/article/details/6179908>

Q：100盏灯问题
Q：老鼠和毒药问题，加个条件，必须要求第二天出结果
Q：海量数据问题
Q：（手写算法）二分查找
Q：（手写算法）反转链表
Q：（手写算法）用两个栈实现队列
Q：（手写算法）多线程轮流打印问题
Q：（手写算法）如何判断一个链有环/两条链交叉
Q：（手写算法）快速从一组无序数中找到第k大的数/前k个大的数
Q：（手写算法）最长（不）重复子串

热门工具换一换