vlambda博客
学习文章列表

本来计划是有c语言的，但是后面找了一下又感觉没啥好问的，索性就删掉c语言的内容只包含了计网和数据结构。

数据结构

Q1:顺序表和链路表的优缺点：

顺序表仨优点：

(1) 方法简单，各种高级语言中都有数组，容易实现。

(2) 不用为表示结点间的逻辑关系而增加额外的存储开销。

(3) 顺序表具有按元素序号随机访问的特点。

顺序存储俩缺点：

　 ⑴ 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。

   ⑵ 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

   链表的优缺点恰好与顺序表相反。

Q2:栈和队列的应用：

栈：数制转换、括号匹配、迷宫求解、递归

队列：阻塞缓冲

二叉树三种遍历：先序中序后序遍历

最短路径算法：深度优先和广度优先

最小生成树：普利姆算法（从图中某一个顶点出发，寻找它相连的所有结点，比较这些结点的权值大小，然后连接权值最小的那个结点。然后将寻找这两个结点相连的所有结点，找到权值最小的连接。重复上一步，知道所有结点都连接上）

克鲁斯卡尔算法（普里姆算法是从某一顶点为起点，逐步找各个顶点最小权值的边来构成最小生成树。那我们也可以直接从边出发，寻找权值最小的边来构建最小生成树。不过在构建的过程中要考虑是否会形成环的情况）

深度优先DFS：

广度优先BFS：广度优先搜索遍历图的过程中以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2,…的顶点。

排序算法：

（1）直接插入排序：是一种简单的插入排序方法，基本思想为：在R[1]至R[i-1]长度为i-1的子表已经有序的情况下，将R[i]插入，得到R[1]至R[i]长度为i的子表有序，这样通过n-1趟（i=2..n）之后，R[1]至R[n]有序。

（2）折半插入排序：在寻找R[i]的插入位置时，就可以采用折半查找的方法，用折半查找方法查找R[i]的插入位置，再将R[i]插入进去，使得R[1]到R[i]有序，这种方法就是折半插入排序。和直接插入排序时间复杂度一样，减小了查找次数

（3）冒泡排序

（4）快速排序：选第一个数字作为支点和low的开始点，high从后往前找，找到比支点小的就放到low的位置，停下来；low从前往后找到比支点大的放到high的位置，停下来。最后相等的时候结束这一次的循环，放入刚开始的支点数字。左右分成两个快排再次进行。时间复杂度nlogn

（4）选择排序：把最小的放到第一个，一共进行n-1次

计算机网络

Q1:OSI和TCP/IP体系结构

Q2：说一下TCP建立连接的三次握手，以及其必要性

• 客户端–发送带有 SYN 标志的数据包–一次握手–服务端

• 服务端–发送带有 SYN/ACK 标志的数据包–二次握手–客户端

• 客户端–发送带有带有 ACK 标志的数据包–三次握手–服务端

第一次握手：Client 什么都不能确认；Server 确认了对方发送正常

第二次握手：Client 确认了：自己发送、接收正常，对方发送、接收正常；Server 确认了：自己接收正常，对方发送正常

第三次握手：Client 确认了：自己发送、接收正常，对方发送、接收正常；Server 确认了：自己发送、接收正常，对方发送接收正常

所以三次握手就能确认双发收发功能都正常，缺一不可。

Q3：断开TCP连接的四次握手

• 客户端-发送一个 FIN，用来关闭客户端到服务器的数据传送

• 服务器-收到这个 FIN，它发回一 个 ACK，确认序号为收到的序号加1 。和 SYN 一样，一个 FIN 将占用一个序号

• 服务器-关闭与客户端的连接，发送一个FIN给客户端

• 客户端-发回 ACK 报文确认，并将确认序号设置为收到序号加1

Q4:TCP、UDP的区别

UDP 在传送数据之前不需要先建立连接，远地主机在收到 UDP 报文后，不需要给出任何确认。虽然 UDP 不提供可靠交付，但在某些情况下 UDP 确是一种最有效的工作方式（一般用于即时通信），比如：QQ 语音、 QQ 视频 、直播等等

TCP 提供面向连接的服务。在传送数据之前必须先建立连接，数据传送结束后要释放连接。TCP 不提供广播或多播服务。由于 TCP 要提供可靠的，面向连接的运输服务（TCP的可靠体现在TCP在传递数据之前，会有三次握手来建立连接，而且在数据传递时，有确认、窗口、重传、拥塞控制机制，在数据传完后，还会断开连接用来节约系统资源），这一难以避免增加了许多开销，如确认，流量控制，计时器以及连接管理等。这不仅使协议数据单元的首部增大很多，还要占用许多处理机资源。TCP 一般用于文件传输、发送和接收邮件、远程登录等场景。

Q5:TCP如何保证可靠传输

应用数据被分割成 TCP 认为最适合发送的数据块。

TCP 给发送的每一个包进行编号，接收方对数据包进行排序，把有序数据传送给应用层。

校验和： TCP 将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP 将丢弃这个报文段和不确认收到此报文段。

TCP 的接收端会丢弃重复的数据。

流量控制： TCP 连接的每一方都有固定大小的缓冲空间，TCP的接收端只允许发送端发送接收端缓冲区能接纳的数据。当接收方来不及处理发送方的数据，能提示发送方降低发送的速率，防止包丢失。TCP 使用的流量控制协议是可变大小的滑动窗口协议。（TCP 利用滑动窗口实现流量控制）

拥塞控制： 当网络拥塞时，减少数据的发送。

停止等待协议 也是为了实现可靠传输的，它的基本原理就是每发完一个分组就停止发送，等待对方确认。在收到确认后再发下一个分组。 超时重传： 当 TCP 发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。

Q6：打开一个网页所需要的的协议(感觉有点超选修范围，但是据说常考？)

香农第一定理是可变长无失真信源编码定理，给出了无损条件下，编码压缩的极限，即信息熵是无失真信源编码的极限值

香农第二定理是有噪信道编码定理，公式为C=B*log2(1+S/N)

香农第三定理是保失真度准则下的有失真信源编码定理

一些牢骚

属于是重头上了一遍大学...把PPT都翻了一遍= =返校之后还有俩月就夏令营了..保研真痛苦，还是在家里，完全没有考研的氛围，自己一个人搁家一屋里学学学，大学所有的科目都复习一遍...也不知道老师面试会随机问你啥= =

（找不着对应封面了，所以用表情包代替，以及感觉我的表情包封面很像完美日记的动物眼影盘..

整理不易，希望读者看完Q&A之后发出“原来是这样..”的感叹就值得了T T