实践出真知
实践出真知

中山大学考研复试内容复习

Timothy Wu 收录于 计算机基础
 约 8200 字 预计阅读 17 分钟  - 次阅读  

中山大学考研复试内容复习

原文地址

复试复习以基本概念为主，重点概念为主，偏题怪题一律不考虑。

计算机网络

网络基础

OSI七层模型

OSI七层模型

OSI七层模型，从下到上依次为物理层、数据链路层、网络层、运输层、会话层、表示层、应用层。

其中底下三层称为通信子网，是为了联网而附加上去的通信设备，完成数据传输功能。顶三层称为资源子网，相当于计算机系统，完成数据的处理等功能。

  • 物理层：传输单位比特，功能是在物理媒体上为数据端设备透明的传输原始比特流。主要定义数据终端设备DTE和数据通信设备DCE的物理和逻辑连接方法。

物理层主要研究以下内容：

  1. 通信链路与通信结点之间的连接需要的电路接口的参数（机械形状、尺寸、交换电路的数量与排列）
  2. 通信链路上传输的信号的意义和电气特征，比如高低电平的规定，信号的规定等。

PS：传输信息所利用的一些物理媒体，比如双绞线、光缆、无线信道等，并不在物理层协议之内。

  • 数据链路层：传输单位是帧，任务是将网络层传下来的IP数据组装成帧。功能为：成帧、差错控制、流量控制和传输管理。
  1. 差错控制：检测物理层发生的差错，并丢弃收到的错误信息。
  2. 流量控制：协调相邻物理结点之间的速度。

数据链路层协议：SDLC、HDLC、PPP、STP和帧中继

  • 网络层：传输单位是数据报（分组、包），主要任务是把网络层协议数据单元（分组）从源端传到目的端，为分组交换网上的不同主机提供通信服务。关键问题是路由选择，并实现流量控制、拥塞控制、差错控制和网际互联等功能。
  1. 差错控制：同上
  2. 拥塞控制：如果拥塞状态使得网络层中的两个结点无法正常通信，则采用一些措施缓解拥塞。

网络层协议：IP、IPX、ICMP、IGMP、ARP、RARP、OSPF

  • 传输层：传输单位是报文段TCP或用户数据包UDP(报文)，任务是负责主机中两个进程之间的通信，功能为端到端提供可靠的传输服务；为端到端连接提供流量控制、差错控制、服务质量、数据传输管理等服务。

传输层协议：TCP、UDP

  • 会话层：允许不同主机上各进程之间的绘画，利用传输层提供的端到端服务，管理主机之间的会话进程，包括建立、管理以及终止进程间的绘画。
  • 表示层：主要用于处理在两个通信系统中交换信息的表示方式。比如不同机器会采用不同的编码和表示方式，以及数据结构。
  • 应用层：最高层，包括FTP、SMTP、HTTP等协议。

TCP模型

  • 网络接口层：对应于OSI的物理层和数据链路层，表示与物理网络的接口
  • 网际层：（主机-主机），即OSI的网络层，将分组发往任何网络并独立选择合适的路由。
  • 传输层：与OSI的传输层类似，使发送端和目的端的主机上的对等实体可以进行会话，主要使用TCP和UDP。
  • 应用层：用户-用户，包含所有高层协议，对应于OSI的应用层呢个、表示层和会话层。

介质访问控制相关

CSMA相关模型

3.5.1 信道划分介质访问控制

使用介质的每个设备与来自同一通信信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。

多路复用技术：传输介质的带宽超过了传输单个信号所需的带宽时，在一条介质上同时携带多个传输信号的方法来提高传输系统的利用率。即将多个输入通道的信息整合到一个复用通道，然后在接收端把收到的信息分离出来传送到对应的输出通道中。

信道划分的实质是通过分时、分频、分码等方法，把原来的一条广播信道，逻辑上分为几条用于两个结点之间通信的互不干扰的子信道。

  1. 频分多路复用FDM：将多路基带信号调制到不同频率载波上再进行叠加形成一个复合信号的多路复用技术。即将物理信道的总带宽分割成若干格传输单个信号带宽相同（略宽）的子信道
  2. 时分多路复用TDM：将一条物理信道按时间分成若干个时间片，轮流地分配给多个信号使用。每一个时间片复用的一个信号占用。利用每个信号在时间上的交叉，在一条物理信道上传输多个信号。改进：STDM，统计时分多路复用，可以动态地分配时隙，提高线路的利用率。
  3. 波分多路复用WDM：光的频分多路复用，在一根光纤中传输多种不同波长的光信号，最后用波长分解复用器将各路波长分解出来。
  4. 码分多路复用CDM：靠不同的编码来区分各路原始信号，既共享信道的频率、又共享时间。码分多址CDMA是码分复用的一种方式。（要求各个站点的芯片序列是相互正交的）优点：抗干扰能力强、保密性强、语音质量好，主要用于无线通信特别是移动通信领域。

3.5.2 随机访问介质访问控制

随机访问协议中，如果有两个或多个用户同时发送信息，就会造成冲突，产生帧的碰撞，导致所有冲突用户的发送均以失败告终。

算法思想：胜利者通过争用获得信道，从而获得信息的发送权。又称为争用型协议，实质上是将广播信道转化为点对点通信的行为。

  1. 纯ALOHA协议：任何一个站点需要发送数据时，可以不进行任何检测就发送数据。如果一段时间内没有收到确认，该站点就认为传输过程中发生了冲突。发送站点需要等待一段时间后再发送数据，直至发送成功。（等待的时间随机）缺点是吞吐量很低。

  2. 时隙ALOHA协议：在时间上把所有站点同步起来，并将时间划分为一段段等长的时隙，规定只能够在每个时隙开始的时候才能发送一个帧，以避免用户发送数据的随意性。这样，每个帧正好在一个时隙内发送完毕，碰撞重传的机制是一样的。吞吐量S与网络负载G的关系是S=Ge^(-G)，当G=1时S=0.368，达到最大值。

  3. 1-坚持CSMA协议：当一个结点要发送数据时，首先侦听信道，如果信道空闲立即发送数据；如果信道忙则等待，同时继续侦听直至信道空闲。如果发生冲突，则随机等待一段时间，再重新侦听信道。（1的意思是侦听到信道空闲后，发送帧的概率为1）。受传播延迟的影响较大

  4. 非坚持CSMA：当一个结点要发送数据时，首先侦听信道；如果信道空闲就立即发送数据；如果信道忙就放弃侦听，等待一个随机的时间后再重复上述过程。降低了冲突的概率，但是使得数据在网络中的平均延迟增加了。

  5. p-坚持CSMA：用于时分信道，基本思想是当一个结点要发送数据时，首先侦听信道，如果信道忙，则等待下一个时隙再侦听；如果信道空闲，便以概率p发送数据，依次类推。这个过程一直持续到数据发送成功或者其他结点发送数据而检测到信道忙为止。若是后者，则等待一个随机时间后再重新开始侦听。 CSMA

  6. CSMA/CD协议，载波侦听多路访问/碰撞检测，是CSMA的改进方案（特点是边听边发，CSMA的侦听和发送不是同时的），适用于总线型网络或半双工网络环境。即每一个站在发送数据之前先检测一下总线上是否有其他站点在发送数据。如果有，则暂时不要发送数据，要等待信道变为空闲再发送。碰撞检测就是边发送边侦听。概括为先听后发，边听边发，冲突停发，随机重发。 显然，CSMA/CD不可能进行全双工通信，只能进行半双工通信。 争用期：把以太网端到端往返时间称为争用期，又称为冲突窗口或碰撞窗口。每一个站在自己发送数据之后的一小段时间内，存在着遭遇冲突的可能性，只有经过争用期这段时间还没有检测到冲突，才能确定这次发送不会发生冲突。 为了确保发送站在发送数据的同时能检测到可能存在的冲突，需要在发送完帧之前就能收到自己发送出去的数据，也就是说帧的传输时延至少要两倍于信号在总线中的传播时延。CSMA/CD总线网的所有数据帧必须要大于一个最小帧长，最小帧长=总线传播时延*数据传输速率*2 比如对于以太网，规定51.2微秒的争用期，则对于10Mb/s的以太网，争用期内可发送512bit，如果前64B未发送冲突，则后面也不会发生冲突。因此规定最短帧长为64B。

CSMA/CD的重点在于二进制指数退避算法，以此来从冲突中恢复。

  1. 确定基本退避时间，一般取两倍的总线端到端传播时延。（即争用期）

  2. 定义参数k=重传次数，且不超过10

  3. 从离散整数集合{0,1,2,…,2^k-1}中选择一个数，重传所需要的退避时间就是r倍的基本退避时间。（全取）

  4. 重传达16次仍不能成功，说明网络太拥挤，抛弃此帧并向高层报告出错。

  5. CSMA/CA协议。CSMA/CD成功用于有线连接的局域网，而CSMA/CA则是在无线局域网环境运行的。CA即为碰撞避免。碰撞避免的实现：

    • 二进制指数退避算法
    • 预约信道。发送方在发送数据的同时通知其他站点自己传输数据所需要的长度。
    • ACK帧，站点在正确收到发给自己的数据帧后，都需要发回一个ACK帧
    • RTS/CTS帧，可选的碰撞避免机制，主要用于解决无线网中的隐蔽站问题。

与CSMA/CD的区别： 区别

吞吐量计算

  • 网络负载（T0时间内所有站点发送的成功和未成功而重传的帧数）G
  • 网络吞吐量（T0时间内成功发送的平均帧数）S
算法名称 计算公式
ALOHA S=Ge^(-2G)
时隙ALOHA S=Ge^(-G)

3.5.3 轮询访问介质访问控制：令牌传递协议

用户不能随机地发送信息，而是通过一个集中控制的监控站，以循环的方式轮询每一个结点，再决定信道的分配。当某结点使用信道时，其他结点都不能使用信道。

令牌传递协议：一个令牌再各结点之间以某个固定次序交换，令牌是一组特殊的比特组合而成的帧。环上的一个站希望传送帧时，必须等待令牌，一旦收到令牌，站点便可启动发送帧。帧在环上发送的时候，所有站点一律进行转发，直到到达始发站，并由始发站撤销该帧。

物理拓扑不必成环，但是为了把对访问介质的许可从一个设备传递到另一个设备，令牌在设备间的传递通路在逻辑上必须是一个环。

非常适合负载很高的广播信道

通信基础

如何保证可靠传输。拥塞控制与流量控制。 在通信子网中，由于过量的分组而引起的网络性能下降称为拥塞。

判断网络是否进入拥塞状态的方法：观察网络的吞吐量与网络负载的关系。

如果随着网络负载的增加，网络的吞吐量明显小于正常的吞吐量，那么网络就可能进入“轻度拥塞”状态；如果网络的吞吐量随着网络负载的增大反而下降，网络就可能进入拥塞状态；如果网络的负载继续增大，而网络的吞吐量下降到零，网络就可能进入到死锁状态。

拥塞控制主要解决的问题：如何获取网络中发生拥塞的信息，从而利用这些信息进行控制，以避免由于拥塞出现分组的丢失以及严重拥塞而产生网络死锁的现象。目标是确保子网能够承受所达到的流量。

  • 流量控制：发送端到接收端点对点通信量的控制，局部问题。
  • 拥塞控制：确保通信子网能够传送待传送的数据，全局问题。

方法：

  1. 开环控制：静态预防方法，在设计网路的时候将有关发生拥塞的因素考虑周到，力求网络在工作时不产生拥塞。控制手段：确定何时接收新流量、何时可丢弃分组以及哪些分组，确定何种调度决策等。共性：在做决定时不考虑当前网络的状态。
  2. 闭环控制：事先不考虑有关发生拥塞的各种因素，采用监控网络系统去监视，及时检测到哪里发生拥塞，然后将拥塞信息传到合适的地方，以便调整网络系统的运行，并解决出现的问题。动态的方法。

TCP相关

TCP连接的三个阶段：连接建立、数据传送和连接释放

  1. TCP连接的建立：三次握手。
  • 第一步，客户端向服务端发送SYN=1,seq=x且不含应用层数据的特殊报文段。
  • 第二步，服务器为TCP连接分配TCP缓存和变量，在确认报文段中，SYN和ACK位置1，确认字号ack=x+1,seq=y
  • 第三步，客户端也给该连接分配缓存和变量。ACK=1,seq=x+1,ack=y+1
  1. TCP连接的释放，四次挥手。
  • 第一步：客户机打算关闭连接，FIN=1,seq=u。发送FIN的一端不能再发送数据
  • 第二步：服务器收到，ack=u+1,seq=v,ACK=1，TCP连接半关闭。
  • 第三步：若服务器没有要向客户机发送的数据，就通知TCP释放连接，FIN=1，ACK=1,seq=w,ack=u+1
  • 第四步：客户机确认释放报文段，ACK=1,ack=w+1,seq=u+1

总结序号变化：回复的ack=seq+1，seq=ack

5.3.4 TCP可靠传输

TCP校验和与UDP校验和一样

  1. 序号：TCP首部的序号字段(seq)用来保证数据能够有序提高给应用层。
  2. 确认：TCP首部的确认号是期望收到对方的下一个报文段的数据的第一个字节的序号。TCP使用累计确认，只确认数据流中至第一个丢失字节为止的字节。
  3. 重传：在超时或有冗余ACK的时候会重传。

冗余确认：TCP规定每当比期望序号大的失序报文到达时，发送一个冗余ACK，致命下一个期待字节的序号。

快速重传：同时TCP规定发送方收到对同一个报文段的3个冗余ACK时，就可以认为跟在这个被确认报文段之后的报文段已经丢失。

5.3.5 TCP流量控制

TCP流量控制是一个速度匹配服务，为了消除发送方发送速度过快使接收方缓存区溢出的可能性。TCP的流量控制是基于窗口实现的。

  • 接收窗口rwnd:接收方根据自己接收缓存的大小，动态地调整发送方的发送窗口大小。
  • 拥塞窗口cwnd：发送方那个根据当前对网络拥塞程序的估计而确定的值。

TCP通过报文的窗口字段将rwnd通知给发送方，表示接收方允许连续接收的最大能力，单位是字节。发送方根据收到的最新的rwnd来限制自己发送窗口的大小，将未确认的数据量控制在rwnd之内。实际上发送窗口的大小是取rwnd和cwnd的最小值。

5.3.6 TCP拥塞控制

拥塞控制的目的时为了防止过多的数据注入网中，使网络中的路由器或者链路不过载。

  • 接收窗口rwnd:接收方根据自己接收缓存的大小所许诺的最新的窗口值，反应了接收方的容量，由接收方根据其放在TCP报文的首部的窗口字段通知发送方。
  • 拥塞窗口cwnd：发送方那个根据自己估算的网络拥塞程度而设置的窗口值，反应了网络的当前容量。

发送窗口上限取rwnd和cwnd较小的一个。

维护拥塞窗口
  1. 慢开始算法：在TCP刚连接好时，发送方设置拥塞窗口cwnd=1，即一个最大报文长度MSS，然后在每收到一个对新的报文段的确认后，将cwnd加1。这样，每个RTT后，cwnd加倍。直到超过阈值ssthresh。
  2. 拥塞避免算法：cwnd每经过一个MSS就加一而不是加倍。当出现一次超时，ssthresh等于当前cwnd的一半。
  3. 网络拥塞的处理：遇到网络拥塞，将ssthresh=cwnd/2，并将cwnd=1，执行慢开始算法。
快重传和快恢复
  1. 快速重传：当发送方连续收到三个重复的ACK报文时，直接重传对方尚未收到的报文段。
  2. 快恢复：当发送端收到连续三个ACK时，ssthresh=cwnd/2，但是cwnd=cwnd/2（即此时的阈值）
重传时间间隔

相关资料：B站视频 对应的标准为RFC6298 TCP需要设置一个重传的时间间隔，太短会导致过多的重传，太长会影响算法性能。因此使用了Jacobson算法来进行参数的设置。 需要维护以下几个变量：

  1. RTT，往返时间估计量，测量TCP本次的往返时间M，RTT = aRTT + (1-a)M，a为平滑因子，典型值为7/8
  2. D，平滑的平均偏差。D = aD + (1-a)|RTT-M|，此处的a为3/4 重传的定时值=RTT+4D

Jacobson 算法只用于处理正常的情况，但是当发生重传后，如果收到一个确认，这时候就不用这个算法来调整 RTO 值了。因为你无法判断这个确认是针对第一次传输，还是后来的重传。在这种情况下，采用 Karn 算法来调整 RTO 的值 。

Karn 算法很简单： 1）、 对于发生重传的数据段，在收到确认后，不更新 RTT 2）、在重传的时候，RTO 是倍增的，直到达到最大值的限制。如果重传超过一定的次数，TCP 连接会断开 3）、在重传并收到确认后，如果下一次的数据段没有发生重传（即一次性收到确认），则又恢复

QoS

QoS提供以下三种服务模型： 　　l Best-Effort service（尽力而为服务模型）是一个单一的服务模型，也是最简单的服务模型。对Best-Effort服务模型，网络尽最大的可能性来发送报文。但对时延、可靠性等性能不提供任何保证。是网络的缺省服务模型，通过FIFO队列来实现。它适用于绝大多数网络应用，如FTP、E-Mail、IP传输等。 　　l Integrated service（综合服务模型，简称Int-Serv）Int-Serv服务模型Int-Serv是一个综合服务模型，它可以满足多种QoS需求。该模型使用资源预留协议（RSVP），RSVP运行在从源端到目的端的每个设备上，可以监视每个流，以防止其消耗资源过多。这种体系能够明确区分并保证每一个业务流的服务质量，为网络提供最细粒度化的服务质量区分。Inter-Serv模型对设备的要求很高，当网络中的数据流数量很大时，设备的存储和处理能力会遇到很大的压力。Inter-Serv模型可扩展性很差，难以在Internet核心网络实施。 　　l Differentiated service（区分服务模型，简称Diff-Serv）Diff-Serv服务模型Diff-Serv是一个多服务模型，它可以满足不同的QoS需求。与Int-Serv不同，它不需要通知网络为每个业务预留资源。区分服务实现简单，扩展性较好。

操作系统

进程与线程

线程的生命周期 同步，信号量等

死锁

死锁的四要素 死锁的解决方案

内存

内存页面分配

文件

文件实现

IO

四种IO的特点

计算机组成

架构

CPU、缓存、内存三层体系架构

内存与缓存

指令寻址方式

流水线

中断与异常

数据结构与算法

大O表示法的意思

时间复杂度指的是程序语句的执行次数，空间复杂度指的是一个算法在运行过程中临时占用存储空间的大小。 大O表示法即时间复杂度的上界，是描述函数渐进行为的数学符号，因此称为渐进上界。

算法的特征

  1. 有穷性：必须能够在有限个步骤后终止。
  2. 有输入：允许0个输入，表示算法给定了初始条件。
  3. 有输出：没有输出的算法是没有意义的。
  4. 确定性：算法的每一个步骤必须有确切的定义。
  5. 可行性：算法的每一个步骤都可以被分解成基本的可执行步，每一个可执行步可以在有限的时间内完成。

基础结构

数组与链表的区别，逻辑结构和数据结构

排序算法

二分排序、快速排序等

树和图

B树和B+树

B树的特点：

  1. 所有叶子节点均在同一层。
  2. 一般索引结点存在磁盘中，数据存在内存中，用以实现索引。
  3. M阶B树，每个子结点最多有M-1个关键字，最少有ceil(M/2)-1个关键字

B+树与B树的区别，在于数据全部在叶子节点内，所以可以顺序索引。

  • B+树能够容纳更多的索引结点，显得更加矮胖
  • B+树必须查找到叶子节点，所以B+树的查找更稳定。
  • 对于范围查找来说，B+树只需要遍历叶子链表，而B树需要反复进行中序遍历。

高级算法

扩展，KMP、红黑树

数据库

概念模型

  1. 实体(entity)：客观存在并相互区别的事物称为实体
  2. 属性(attribute)：实体的某一特定属性称为属性
  3. 码(key)：唯一标识实体的属性集 ER模型：实体-联系方法 常用的数据模型：层次模型、网状模型、关系模型、面向对象数据模型、对象关系数据模型、半结构化数据模型。

关系运算：选择、投影、连接、除运算

存取方法

存取方法是快速存取数据库中数据的技术。常用的有索引方法和聚簇方法 B+树索引和哈希索引是最经典的两种方式。

  1. B+树索引

索引 B树和B+树，插入、删除、维护、查询 哈希的原理，区间查询

数学

高等数学 中值定理 拉格朗日乘数法 线性代数： 什么时候方程有解、有一解、有多解 矩阵相关知识：矩阵的迹 线性代数的相关性 离散数学： 等价 集合：有穷集和无穷集 函数与关系 概率论： 贝叶斯和全概率公式

软件工程

软件测试和需求分析和系统分析与设计

软件测试方法： 等价类划分…

软件工程管理： 核心路径管理

系统分析与设计： UML图： 用例视图：

  • 用例图：显示系统的外观可视行为 静态视图：
  • 类图：显示类的定义和关系
  • 对象图：某种状态或时间段内，系统中活跃的对象及其关系
  • 包图：显示设计的层次结构 行为视图：
  • 顺序图：显示对象随着时间的交互
  • 状态图：显示响应时间的状态改变
  • 活动图：显示系统行为的描述 实现视图：
  • 组件图：显示系统的体系结构
  • 部署图：显示系统的物理体系结构

分析过程 设计模式：工厂模式，等等

软件生命周期

CMM，提出者，级别

软件工程需求分析所用的模型。

计算机视觉

基础知识为主，要知道一些算法是干什么的，怎么用。 重点集中在我所做的实验上。

边缘检测

canny边缘检测 代码：https://blog.csdn.net/xiajun07061225/article/details/6926108 首先进行高斯滤波，然后进行梯度计算，对梯度进行非最大值抑制来瘦边，然后利用双阈值法来确定阈值，小于下阈值设为0，大于上阈值设为1。

机器学习和人工智能

围绕那两本课本完成。 可以参考算法工程师的面试题，比如正则化的意义之类的。

神经网络

同上，以基础知识为主

云计算

本行，要准备一下自己的项目经历，毕业设计相关，等等。

时间序列预测

同上，好好组织语言。

更新于 2020-04-04 
CC BY-NC-SA 4.0
知识/考研
返回 | 主页
0%