中科大复试准备

数据结构->操作系统->计算机网络->通信原理->微机原理->

软件工程，编译原理，数据库

计算机考研复试整理

PDF文件自取

数据结构

1. 时间复杂度

时间复杂度是指执行算法所需要的计算工作量，因为整个算法的执行时间与基本操作重复执行的次数成正比，所以将算法中基本操作的次数作为算法时间复杂度的度量，一般情况下，按照基本操作次数最多的输入来计算时间复杂度，并且多数情况下我们去最深层循环内的语句所描述的操作作为基本操作。

2. 循环队列的顺序表中，为什么要空一个位置？

这是为了用来区分队空与队满的情况。如果不空一个位置，则判断队空和队满的条件是一样的。

3. 什么是二叉排序树？以及它的原理，算法。（二叉排序树的查找过程）

二叉排序树又称二叉查找树，它或者是一颗空树，或者满足一下性质的二叉树：

① 若左子树不空，则左子树上所有结点的值均小于根节点的值；

② 若右子树不空，则右子树上所有结点的值均大于根节点的值；

③ 左右子树也分别是二叉排序树。

原理步骤：

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

4. 哈夫曼树

定义：

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

构造方法：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

特点：

① 权值越大的结点，距离根节点越近；

② 树中没有度为一的结点。

应用：

哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码。

5. 什么是哈希冲突？以及如何解决。

散列（哈希）表：

根据关键码值(Key value)而直接进行访问的数据结构。根据给定的关键字来计算出关键字在表中的地址，以加快查找的速度。

冲突：指的是多个关键字映射同一个地址的情况。

解决办法：

（1） 开放定址法

① 线性探查法（产生堆积问题）；

② 平方探查法（不能探查到哈希表上所有的地址，但至少能探查到一半的地址）

（2） 链地址法

把所有的同义词用单链表连接起来。

补充（常见的哈希函数构造方法）

直接定址法，数字分析法，平方取中法，除留余数法。

6. 深度优先搜索遍历和广度优先搜索遍历的过程

深度优先搜索遍历

基本思想：首先访问出发点V，并将其标记为已访问；然后选取与V邻接的未被访问的邻接顶点W，访问W；再选取与W邻接的未被访问的顶点访问，以此类推。当一个顶点所有的邻接顶点都被访问过时，则依次退回最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些顶点中去一个顶点进行上述的过程，直至图中所有顶点都被访问过为止。

广度优先搜索遍历

基本思想：首先访问起始顶点V，然后选取与V邻接的全部顶点w1，w2，….，wn进行访问，再一次访问与w1，w2，…

，wn邻接的全部顶点（不包括已访问过的顶点），以此类推，直至所有顶点都被访问过为止。

7. 迪杰斯特拉算法的过程

该算法可以求得某一顶点到其余各顶点的最短路径。

算法思想：设有两个顶点集合S和T，其中集合S中存放的是图中已找到最短路径的顶点，集合T中存放的是图中的剩余顶点。

初始状态时，集合S中只包含源点V0，然后不断从集合T中选取到顶点V0路径最短的顶点Vu并加入集合S中。集合S每加入一个新的顶点Vu，都要修改V0到集合T中各个顶点的最短路径的长度值。不断重复这个过程，直至集合T中的顶点全部并入到S中为止。

8. 链表查找某个元素，平均的时间复杂度是多少？

O(n) 链表是顺序存储，故（1+n）/2。

9. 图的存储方式

① 邻接矩阵：是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元素之间的关系（边/弧）的信息。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称的。

② 邻接表：是图的链式存储结构，由单链表的表头形成的顶点表和单链表其余结点所形成的边表两部分组成。

③ 十字链表：有向图的另一种链式存储结构。

④ 邻接多重表：无向图的链式存储结构。

10. 图的深度遍历是否唯一

不一定是不唯一。我们可以取图中任一顶点进行深度遍历。

11. 图的相关概念

图：由结点的有穷集合V和边的集合E组成。

类别：有向图和无向图。

顶点的度：出度和入度。

有向完全图和无向完全图： 若有向图有n个顶点，则最多有n(n-1)条边，则称为有向完全图；

​ 若无向图有n个顶点，则最多有n(n-1)/2条边，则称为无向完全图。

路径：相邻顶点序偶所构成的序列。

简单路径：序列中的顶点和路径不重复出现的路径。

回路：路径中第一个顶点和最后一个顶点相同的路径。

连通： 无向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中任意两个顶点之间都连通，则称改图为连通图。

有向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中每一对顶点Vi和Vj，从Vi到Vj和Vj到Vi都有路径，则称改图为强连通图。

12. 最小生成树的概念

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。如果在最小生成树中添加一条边，必定成一个环。

相关算法：

① 普里姆算法

② 克鲁斯卡尔算法

N个结点的最小生成树有几个结点，几条边：n个结点，n-1 条边。

13. 平衡二叉树

平衡二叉树又称AVL树，是一种特殊的二叉排序树，其左右子树都是平衡二叉树，且左右子树的高度差的绝对值不超过1.

平衡因子： 左子树高度减去右子树高度的差。

平衡调整： 先找到失去平衡的最小子树，即以距离插入结点最近，且平衡因子绝对值大于1的结点最为根节点的子树，分为LL,LR,RL,RR四中调节方式。

14. 二叉树的存储

① 顺序存储结构：用一个数组来存储一颗二叉树，二叉树中的结点值按照编号依次存入一个一维数组中。适用于完全二叉树，若用于一般的二叉树则会浪费大量存储空间。

Lchild	Data	Rchild

② 链式存储结构：二叉树中的每一个结点用一个链结点来存放。

15. M阶B-树和M阶B+树的主要区别

① B+树所有有效数据全在叶子节点，而B-树所有节点分散在树中，B-树中的关键字不重复。

② B+树种有几个关键字就有几个子树，B-树中具有n 个关键字的节点含有(n+1)棵子树。

③ B+树有两个指针，根指针和只想最小节点的指针，叶子节点连接成一个不定长的线性链表

④ B+树中，每个节点（除根节点外）中的关键字个数n 的取值范围是⌈m/2⌉<=n<=m，根节点n 的取值

⑤ 范围是2<=n<=m。B-树中，每个节点（除根节点外的所有最底层非叶子节点）中的关键字取值范围是

⑥ ⌈m/2⌉-1<=n<=m-1，根节点n 的取值范围是1<=n<[m-1]。

⑦ B+树中的所有非叶子节点仅仅起到索引的作用，节点中的每个索引项只包含对应子树的最大关键字和

指向该子树的指针，不含有该关键字对应记录的存储地址。而在B-树中，每个关键字对应记录的存储

地址。

16. 折半查找，以及其适用范围和时间复杂度

又称二分查找，基本思路：

在当前的查找区间[low…high]中，首先确定mid=(low+high)/2，然后拿关键字与mid比较，若相等则查找成功，返回该位置，否则确定新的查找区间， mid>K，[low…mid-1]

​ mid<K，[mid+1…high]

直至查找自区间长度小于1时查找结束。

适用范围：顺序结构存储并按照关键字大小有序排列。

时间复杂度：O(log2N)

17. 完全二叉树

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

完全二叉树特点：

叶子结点只可能在最大的两层上出现， 对任意结点， 若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；

18. 什么是堆？有什么作用？

堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足：

任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。若父亲大孩子小，则为大顶堆，若父亲肖孩子大，则为小顶堆。

作用：应用于堆排序。

19. 如何实现循环队列？有何好处？

如何实现：把数组弄成一个环，让rear和front指针沿着环走，这样就可以产生循环队列。

好处：循环队列是顺序队列的改进，在顺序队列中，在元素进队的时候，rear要向后移动，元素出队的时候，front也要向后移动，这样经过一系列的出队和入队操作之后，两个指针最后会达到数组的末端，此时虽然队中已经没有元素了，但是还是不能让元素入队，即出现了“假溢出”的现象。循环队列就能避免出现这个现象。

20. 深度优先搜索形成的是什么？森林唯一么？

（森林，不能说树）（不唯一，因为邻接表可能不唯一）

21. 满二叉树的结点个数（n层）

2的n次方减一（2n-1）

22. 二叉查找树查找的时间复杂度以及中序遍历后得到什么样的序列

递增有序序列

23. 什么图可以进行拓扑排序？

有向无环图

24. 顺序队列的特征

队列是一种操作受限的线性表，只允许队尾入队，在队头进行出队。最大的特点是先进先出。

25. 非连通图如何访问每一个结点？

节点循环，DFS或者BFS。

26. 排序总结

	排序方法	时间复杂度	空间复杂度			稳定性
			平均情况	最坏情况	最好情况
插入排序	直接插入	O(n2)	(n2)	O(n)	O(1)	稳定
折半插入		O(n2)	O(n2)	O(n2)	O(1)	稳定
希尔排序		O(nlog2n)		O(nlog2n)	O(1)	不稳定
交换排序	冒泡排序	O(n2)	O(n2)	O(n)	O(1)	稳定
快速排序		O(nlog2n)	O(n2)	O(nlog2n)	O(log2n)	不稳定
选择排序	简单选择	O(n2)	O(n2)	O(n2)	O(1)	不稳定
堆积排序		O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
其他排序	二路归并	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
基数排序		O(d(n+r))	O(d(n+r)	O(d(n+r))	O	稳定

各类排序的算法详见书本。（需要说出每个算法的基本思想）

27. 查找：相关章节过一遍。

操作系统

1. 进程和程序的区别

① 进程是动态的，程序是静止的。进程是程序的执行，程序是有序代码的集合。

② 进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。

③ 进程和程序的组成不同：进程包括程序，数据和进程控制块。

④ 进程和程序是密切相关的。通过多次执行，一个程序可以对应多个进程；通过调度关系，一个进程可以包括多个程序。

⑤ 进程可以创建其他进程，但是程序不能形成新的程序。

2. 进程和线程的区别

① 调度：线程是独立调度的基本单位，进程是资源拥有的基本单位。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行线程切换，将会引起进程切换。

② 拥有资源：进程是拥有资源的基本单位，而线程不拥有系统资源（除了少量资源，比如栈，程序计数器，寄存器），不过线程可以访问其隶属进程的系统资源。

③ 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且同一个进程内的多个线程之间也可以并发执行，能提高系统的吞吐量，系统的并发性也更好。

④ 系统开销：在创建进程和撤销进程时，系统都要为之分配或回收资源，所以操作系统为进程付出的系统开销远大于创建线程或撤销线程的开销。

⑤ 同步和通信：多线程之间的同步和通信容易实现。

3. 什么是微内核？

微内核操作系统能有效地支持多处理机运行，非常适用于分布式系统环境。

什么是微内核操作系统到现在没有一致公认的定义，但是可以从四个方面对微内核操作系统进行描述：

① 足够小的内核：在微内核操作系统中，内核是指精心设计的，能实现现代OS最基本核心功能的部分，并非是一个完整的OS，而只是OS中最基本的部分。

② 基于C/S模式：将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放于微内核外面的一组服务器中实现。

③ 应用“极致与策略分离”原理：在传统OS中，讲极致放在OS的内核的较低层，把策略放在内核的较高层中。而在微内核OS中，通常把机制放在OS的微内核中，这样才有可能将内核做得很小。

④ 采用面向对象技术。

基本功能：

① 进程（线程）管理

② 低级存储器管理

③ 中断和陷入处理

优点：

① 提高了系统的可扩展性

② 增强系统的可靠性

③ 可移植性

④ 提供了对分布式系统的支持

⑤ 融入了面向对象技术

4. 什么是DMA？什么是中断？两者的区别。

① 中断方式是在数据缓冲寄存器满之后发出中断，要求CPU进行，而DMA方式则是在所要求传送的数据块全部传送结束时要求CPU 进行中断处理。这就大大减少了CPU进行中断处理的次数。

② 中断方式的数据传送是在中断处理时由CPU控制完成的，而DMA方式则是在DMA控制器的控制下，不经过CPU控制完成的。这就排除了CPU因并行设备过多而来不及处理以及因速度不匹配而造成数据丢失等现象。

5. 硬中断和软中断是什么？区别是什么？

软中断：

1、编程异常通常叫做软中断

2、软中断是通讯进程之间用来模拟硬中断的一种信号通讯方式。

3、中断源发中断请求或软中断信号后,CPU 或接收进程在适当的时机自动进行中断处理或完成软中断信号

对应的功能

4、软中断是软件实现的中断,也就是程序运行时其他程序对它的中断;而硬中断是硬件实现的中断,是程序运

行时设备对它的中断。

硬中断：

1、硬中断是由外部事件引起的因此具有随机性和突发性；软中断是执行中断指令产生的，无外部施加中断

请求信号，因此中断的发生不是随机的而是由程序安排好的。

2、硬中断的中断响应周期，CPU 需要发中断回合信号（NMI 不需要），软中断的中断响应周期，CPU 不

需发中断回合信号。

3、硬中断的中断号是由中断控制器提供的（NMI 硬中断中断号系统指定为02H）；软中断的中断号由指

令直接给出，无需使用中断控制器。

4、硬中断是可屏蔽的（NMI 硬中断不可屏蔽），软中断不可屏蔽。

区别：

1、软中断发生的时间是由程序控制的,而硬中断发生的时间是随机的

2、软中断是由程序调用发生的,而硬中断是由外设引发的

3、硬件中断处理程序要确保它能快速地完成它的任务,这样程序执行时才不会等待较长时间。

6. 页面置换算法有哪些？什么是LRU？

① 最佳置换算法（OPT）：在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用的货以后最迟再被使用的页面。该算法不能实现，只能作为一个标准来衡量其他置换算法的优劣。

② 先进先出算法（FIFO）：每次总是淘汰最先进入内存的页面，也就是将在内存中驻留时间最长的页面淘汰。（可能会产生Belady异常，缺页次数随着分配的物理块的增加而增加）。

③ 最近最少使用算法（LRU）：选择最近最少未被使用的页面淘汰，其思想是用以前的页面引用情况来预测将来会出现的页面引用情况。利用了局部性原理。

④ 时钟置换算法（CLOCK）：是LRU和FIFO的折中，具体方法略。

⑤ 工作集算法

⑥ 工作集时钟算法

⑦ 第二次机会算法

⑧ 最近未使用（NRU）

7. 操作系统中的磁盘调度算法

磁盘调度算法目的：使磁盘的平均寻道时间最少。

调度算法	算法思想	优点	缺点
先来先服务算法FCFS	按照进程请求访问磁盘的先后顺序进行调度。	简单，公平。	未对寻道进行优化，平均寻道时间较长，仅适用于磁盘请求较少的场合。
最短寻道时间优先算法SSTF	选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。	较FCFS有较好的寻道性能以及较少的寻道时间。	会导致饥饿现象
扫描（电梯调度）算法SCAN	在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求最为下一次服务的对象。	具有较好的寻道性能，而且防止了饥饿现象。	存在一个请求刚好被错过而需要等待很久的情形。
循环扫描算法CSCAN	规定磁头单向移动，如自里向外移动，当磁头移动到最外的磁道时立即返回到最里磁道，如此循环进行扫描。	兼顾较好的寻道性能，防止饥饿现象，同时解决了一个请求等待时间过长的问题。	可能出现磁臂长时间停留在某处不懂的情况（磁臂黏着）。
N-Step-SCAN 算法，对SCAN 算法的优化。	将磁盘请求队列分成若干个 长度为N 的子队列，磁盘调度 将按照FCFS 依次处理这些子 队列，而每处理一个队列时又 是按照SCAN 算法，对一个队列处理后再处理其他队列，将 新请求队列放入新队列。	无磁臂黏着。
FSCAN 算法，对SCAN 算法 的优化。	将请求队列分成两个子队列， 将新出现请求磁盘IO 的进程 放入另一个子队列。	无磁臂黏着。

8. 操作系统中的信号量

信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

信号量分类：

① 整型信号量：所谓整型信号量就是一个用于表示资源个数的整型量

② 记录型信号量（资源信号量）：就是用一个结构体实现，里面包含了表示资源个数的整型量和一个等待队列。

信号量的应用：

① 实现进程同步

② 实现进程互斥

9. PV操作

信号量的值除了初值外，仅能由这PV原语加以改变。P、V 操作以原语形式实现，保证了对信号量进行操作过程中不会被打断或阻塞。P 操作相当于申请资源，V 操作相当于释放资源。P操作和V操作必定成对出现，但未必在同一个进程中。

Struct semaphore{
   Int count;

   queueType queue;

   };

Wait (semaphore s) // P

{

   s.count --;

   if(s.count<0)

       {   阻塞该进程；

           将该进程插入等待序列s.queue;

       }

}

signal (semaphore s) // V

{

   s.count ++;

   if(s.count<=0)

       {   从等待队列s.queue取出第一个进程p；

           将p插入就绪队列;

       }

}

10. 什么是操作系统？

操作系统（Operating System，简称OS）是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。操作系统是用户和计算机的接口，同时也是计算机硬件和其他软件的接口。操作系统的功能包括管理计算机系统的硬件、软件及数据资源，控制程序运行，改善人机界面，为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，提供了各种形式的用户界面，使用户有一个好的工作环境，为其它软件的开发提供必要的服务和相应的接口。

11. 操作系统的组成

操作系统理论研究者有时把操作系统分成四大部分：

1. 驱动程序是最底层的、直接控制和监视各类硬件的部分，它们的职责是隐藏硬件的具体细节，并向其他部分提供一个抽象的、通用的接口。

2. 内核是操作系统之最内核部分，通常运行在最高特权级，负责提供基础性、结构性的功能。

3. 支承库是一系列特殊的程序库，它们职责在于把系统所提供的基本服务包装成应用程序所能够使用的编程接口（API），是最靠近应用程序的部分。例如，GNU C运行期库就属于此类，它把各种操作系统的内部编程接口包装成ANSI C和POSIX编程接口的形式。

4. 外围是指操作系统中除以上三类以外的所有其他部分，通常是用于提供特定高级服务的部件。例如，在微内核结构中，大部分系统服务，以及UNIX/Linux中各种守护进程都通常被划归此列。

12. 操作系统中用到了哪些数据结构中的数据结构？请举例说明

栈：运算器出栈压栈

队列：进程管理

树：目录管理

表格：优先级的设置

13. 简述操作系统中系统调用过程

系统调用提供了用户程序和操作系统之间的接口，应用程序通过系统调用实现其余OS的通信，并取得它的服务。系统调用不仅可供所有的应用程序使用，而且也可供OS本身的其它部分，如命令处理程序。

系统调用的处理步骤（三步）：

首先，将处理机状态由用户态转为系统态；然后由硬件和内核程序进行系统调用的一般性处理，即首先保护被中断进程的CPU环境，将处理机状态字PSW、程序计数器PC、系统调用号、用户栈指针以及通用寄存器内容等压入堆栈；再然后将用户定义的参数传送到指定的地址保存起来。

其次，分析系统调用类型，转入相应的系统调用处理子程序。（通过查找系统调用入口表，找到相应处理子程序的入口地址转而去执行它。）

最后，在系统调用处理子程序执行完后，应恢复被中断的货设置新进程的CPU现场，然后返回被中断进程或新进程，继续往下执行。

14. 虚拟存储器，以及相关算法。

基于局部性原理，应用程序在运行之前，仅将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂时留在盘上。程序运行时，如果它要访问的页已调入内存，便可继续执行下去；但如果程序要访问的页或段尚未调入内存（即缺页），此时程序应利用请求调入功能将它们调入内存，以使程序能继续执行下去。如果此时内存已满，无法装入新的页或段，则需要利用页面置换功能，将内存中暂不使用的页面或段调至盘上，腾出空间用于页面调入内存，是程序继续执行下去。这样，就实现了大的用户程序能在较小的内存空间里运行，也可以在内存中同时装入更多的进程使它们并发运行。从用户角度出发，该系统的内存容量比实际内存容量大很多，故成这样的存储器为虚拟存储器。

相关算法：

页面置换算法

① 最佳置换算法（OPT）：在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用的货以后最迟再被使用的页面。该算法不能实现，只能作为一个标准来衡量其他置换算法的优劣。

② 先进先出算法（FIFO）：每次总是淘汰最先进入内存的页面，也就是将在内存中驻留时间最长的页面淘汰。（可能会产生Belady异常，缺页次数随着分配的物理块的增加而增加）。

③ 最近最少使用算法（LRU）：选择最近最少未被使用的页面淘汰，其思想是用以前的页面引用情况来预测将来会出现的页面引用情况。利用了局部性原理。

④ 时钟置换算法（CLOCK）：是LRU和FIFO的折中，具体方法略。

⑤ 工作集算法

⑥ 工作集时钟算法

⑦ 第二次机会算法

⑧ 最近未使用（NRU）

15. 存储器管理应具有的功能

存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故应具有以下功能：

① 内存的分配和回收：实施内存的分配，回收系统或用户释放的内存空间。

② 地址变换：提供地址变换功能，将逻辑地址转换成物理地址。

③ 扩充内存：借助于虚拟存储技术活其他自动覆盖技术，为用户提供比内存空间大的地址空间，从逻辑上扩充内存。

④ 存储保护：保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。

16. 什么是TLB？

TLB 的作用是在处理器访问内存数据的时候做地址转换。TLB 的全称是Translation Lookaside Buffer，可以翻译做旁路缓冲，是一个具有并行查询能力的特殊高速缓冲寄存器。TLB中存放了一些页表文件，文件中记录了虚拟地址和物理地址的映射关系。当应用程序访问一个虚拟地址的时候，会从TLB 中查询出对应的物理地址，然后访问物理地址。TLB 通常是一个分层结构，使用与Cache 类似的原理。处理器使用一定的算法把最常用的页表放在最先访问的层次。

17. 程序的装入方式有哪些？

补充：应用程序从用户编写的源文件到内内存中执行的进程大致分为三个阶段，经过编译程序将源代码便以为若干个目标模块，在通过链接程序将编译好的目标模块以及所需的库函数链接到一起，形成完整的装入模块，最后通过装入程序将这些装入模块装入内存并执行。（编译，链接，装入）

装入方式：

① 绝对装入：在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。

② 可重定位装入：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。

③ 动态运行装入：允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。

18. 程序的链接方式有哪些？

① 静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开。

② 装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。

③ 运行时动态链接：知道程序运行过程中需要一些模块时，才对这些模块进行链接。

19. 交换技术，覆盖技术，以及两者的区别。

覆盖技术：把一个大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时并不要求同时装入内存的覆盖组成一组，成为覆盖段，这个覆盖段分配到同一个存储区域，这个存储区域成为覆盖区，它与覆盖段一一对应。覆盖段的大小由覆盖段中最大的覆盖来确定。（为了解决内存容量太小的问题，打破了必须将一个程序全部信息装入内存后才能运行的限制）

交换技术：把暂时不用的某个程序及数据部分从内存移到外存中去，以便腾出必要的内存空间；或者把指定的程序或数据从外存读到相应的内存中，并将控制权交给他，让其在系统上运行的一种内存扩充技术。处理器的中级调度就是采用交换技术。

区别：

① 与覆盖技术相比，交换技术不要求程序员给出的程序段之间的覆盖结构；

② 交换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行；

③ 覆盖技术只能覆盖于覆盖程序段无关的程序段，交换进程由换出和换入两个过程组成。

20. 内存连续分配管理方式有哪些？

① 单一连续分配（静态分配）

② 固定分区分配（分区大小可以不等，但事先必须确定，运行时不能改变）

③ 动态分区分配

P131详细

21. 动态分区分配的算法有哪些？

① 首次适应算法First Fit

② 循环首次适应算法Next Fit

③ 最佳适应算法Best Fit

④ 最差适应算法Worst Fit

22. 什么叫拼接技术？

在分区管理方式下，系统运行一段时间后，内存中会出现相当一部分的碎片，拼接技术是解决碎片问题的方法。

即将存储器中所有已分配分区移动到主存的一端，使本来分散的多个小空闲区连成一个大的空闲区，这种通过移动把多个分散的小分区拼接成一个大分区的方法即为拼接技术。

23. 什么叫原子操作？

所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。

24. 内部碎片和外部碎片

内部碎片：分配给作业的存储空间中未被利用的部分。

外部碎片：系统中无法利用的小存储块，比如通过动态内存分配技术从空闲内存区上分配内存后剩下的那

部分内存块。

25. 常用的存储保护方法

（1）界限寄存器

上下界寄存器方法

基址、限长寄存器方法

（2）存储保护键：给每个存储块分配一个单独的存储键，它相当于一把锁。

26. 连续分区分配和非连续分区分配的比较

27. 什么是页表？有什么作用。

为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页面映射表。

页表由页表项组成，页表项有页号和块号组成，根据页表项就可以找到每个页号对于物理内存中物理块的块号。

28. 什么是段寄存器？

段寄存器是因为对内存的分段管理而设置的。计算机需要对内存分段，以分配给不同的程序使用（类似于硬盘[分页。在描述内存分段时，需要有如下段的信息：1.段的大小；2.段的起始地址；3.段的管理属性（禁止写入/禁止/执行/系统专用等）。需要用8个字节（64位）存储这些信息，但段寄存器只有16位，因此段寄存器中只能存储段号（segment selector，也译作“段选择符”），再由段号映射到存在内存中的GDT（global (segment) descriptor table，全局段号记录表），读取段的信息。

29. 进程线程树图

进程树是一个形象化的比喻，比如一个进程启动了一个程序，而启动的这个进程就是原来那个进程的子进程，依此形成的一种树形的结构，我们可以在进程管理器选择结束进程树，就可以结束其子进程和派生的子进程。

30. 作业和进程的区别

一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成的某

项任务，是要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完

成4 个阶段。而进程是对已提交完毕的程序所执行过程的描述，是资源分配的基本单位。

其主要区别如下。

(1)作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等

待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，

只要它被创建，总有相应的部分存在于内存中。

(2) 一个作业可由多个进程组成，且必须至少由一个进程组成，反过来则不成立。

(3) 作业的概念主要用在批处理系统中，像UNIX 这样的分时系统中就没有作业的概念。而进程的概念则

用在几乎所有的多道程序系统中进程是操作系统进行资源分配的单位。在Windows 下,进程又被细化为线

程,也就是一个进程下有多个能独立运行的更小的单位。

31. 进程的三个状态以及转换过程

32. 进程调度算法有哪些？（再详细了解其中的算法思想）

① 先来先服务调度FCFS

② 短作业优先调度SJF

③ 优先级调度Priority

④ 时间片轮转调度RR

⑤ 高响应比优先调度

⑥ 多级队列调度

⑦ 多级反馈队列调度

33. 死锁

死锁： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

死锁原因：

① 系统资源不足

② 进程推进顺序不当

产生死锁的必要条件：

① 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。

② 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

③ 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

④ 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0 正在等待一个P1 占用的资源；P1 正在等待P2 占用的资源，……，Pn 正在等待已被P0占用的资源。

处理死锁的基本方法：

① 预防死锁：这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。

② 避免死锁：该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

③ 检测死锁：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。

④ 解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。

34. 什么是饥饿？与死锁有什么差别？

等待时间给进程推进和响应带来明显影响时成为进程饥饿。

饥饿并不代表系统一点死锁，但至少有一个程序的执行被无限期地推迟。

差别：

① 进入饥饿的进程可以只有一个，但是死锁必须大于等于两个；

② 出于饥饿状态的进程可以是一个就绪进程，但是死锁状态的进程必定是阻塞进程。

35. 分段和分页的区别

1、段是信息的逻辑单位，分段的目的是为了更好地实现共享,根据用户的需要划分，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要，其对用户是透明的。

2、段的大小不固定，由它所完成的功能决定；页的大小固定（一般为4K），由系统决定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。

3、段向用户提供二维地址（段号+段内地址）；页向用户提供的是一维地址（页号）

4、段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

36. 银行家算法

主要思想是避免系统进入不安全状态，在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先试行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样就保证系统始终处于安全状态，从而避免死锁现象的发生。

37. RAID磁盘阵列

独立磁盘冗余阵列（RAID，redundant array of independent disks，redundant array of inexpensive disks）是把相同的数据存储在多个硬盘的不同的地方（因此，冗余地）的方法。通过把数据放在多个硬盘上，输入输出操作能以平衡的方式交叠，改良性能。因为多个硬盘增加了平均故障间隔时间（MTBF），储存冗余数据也增加了容错。

38. 控制管理模块是写在哪个文件里的？那个文件叫做什么文件？

文件控制块

计算机网络

1. 连接2个局域网需要用什么 在那一层

集线器（多端口） 中继器（两个端口） 物理层

2. TCP与UDP的连接区别及适用情况

1. 基于连接vs无连接

TCP是面向连接的协议，而UDP是无连接的协议。这意味着当一个客户端和一个服务器端通过TCP发送数据前，必须先建立连接，建立连接的过程也被称为TCP三次握手。

2. 可靠性

TCP提供交付保证，这意味着一个使用TCP协议发送的消息是保证交付给客户端的，如果消息在传输过程中丢失，那么它将重发。UDP是不可靠的，它不提供任何交付的保证，一个数据报包在运输过程中可能会丢失。

3. 有序性

消息到达网络的另一端时可能是无序的，TCP协议将会为你排好序。UDP不提供任何有序性的保证。

4. 速度

TCP速度比较慢，而UDP速度比较快，因为TCP必须创建连接，以保证消息的可靠交付和有序性，他需要做比UDP多的事。这就是为什么UDP更适用于对速度比较敏感的应用。TCP适合传输大量数据，UDP适合传输少量数据。

5. 重量级vs轻量级

TCP是重量级的协议，UDP协议则是轻量级的协议。一个TCP数据报的报头大小最少是20个字节，UDP数据报的报头固定是8个字节。TCP报头中包含序列号，ACK号，数据偏移量，保留，控制位，窗口，紧急指针，可选项，填充项，校验位，源端口和目的端口。而UDP报头只包含长度，源端口号，目的端口号，校验和。

6. 流量控制和拥塞控制

TCP有流量控制和拥塞控制。UDP没有流量控制和拥塞控制。

7. TCP是面向字节流，UDP是面向报文的

TCP是字节流的协议，无边界记录。

UDP发送的每个数据报是记录型的数据报，所谓的记录型数据报就是接收进程可以识别接收到的数据报的记录边界。

8. TCP只能单播，不能广播和组播；UDP可以广播和组播

TCP应用场景：效率要求相对低，但对准确性要求相对高的场景。因为传输中需要对数据确认，重发，排序等操作，相比之下效率没有UDP高。举几个例子：文件传输、邮件传输、远程登录。

**UDP应用场景：**效率要求相对高，对准确性要求相对低的场景。举几个例子：QQ聊天、QQ视频，网络语音电话（即时通讯，要求速度高，但是出现偶尔断续不是太大问题，并且此处完全不可以使用重传机制）、广播通信（广播、多播）

3. 路由和交换的区别

一、 第二层交换机和路由器的区别

传统交换机从网桥发展而来，属于OSI第二层即数据链路层设备。它根据MAC地址寻址，通过站表选择路由，站表的建立和维护由交换机自动进行。路由器属于OSI第三层即网络层设备，它根据IP地址进行寻址，通过路由表路由协议产生。交换机最大的好处是快速，由于交换机只须识别帧中MAC地址，直接根据MAC地址产生选择转发端口算法简单，便于ASIC实现，因此转发速度极高。但交换机的工作机制也带来一些问题。

1.回路：根据交换机地址学习和站表建立算法，交换机之间不允许存在回路。一旦存在回路，必须启动生成树算法，阻塞掉产生回路的端口。而路由器的路由协议没有这个问题，路由器之间可以有多条通路来平衡负载，提高可靠性。

2.负载集中：交换机之间只能有一条通路，使得信息集中在一条通信链路上，不能进行动态分配，以平衡负载。而路由器的路由协议算法可以避免这一点，OSPF路由协议算法不但能产生多条路由，而且能为不同的网络应用选择各自不同的最佳路由。

3.广播控制：交换机只能缩小冲突域，而不能缩小广播域。整个交换式网络就是一个大的广播域，广播报文散到整个交换式网络。而路由器可以隔离广播域，广播报文不能通过路由器继续进行广播。

4.子网划分：交换机只能识别MAC地址。MAC地址是物理地址，而且采用平坦的地址结构，因此不能根据MAC地址来划分子网。而路由器识别IP地址，IP地址由网络管理员分配，是逻辑地址且IP地址具有层次结构，被划分成网络号和主机号，可以非常方便地用于划分子网，路由器的主要功能就是用于连接不同的网络。

5.保密问题：虽说交换机也可以根据帧的源MAC地址、目的MAC地址和其他帧中内容对帧实施过滤，但路由器根据报文的源IP地址、目的IP地址、TCP端口地址等内容对报文实施过滤，更加直观方便。

6.介质相关：交换机作为桥接设备也能完成不同链路层和物理层之间的转换，但这种转换过程比较复杂，不适合ASIC实现，势必降低交换机的转发速度。因此目前交换机主要完成相同或相似物理介质和链路协议的网络互连，而不会用来在物理介质和链路层协议相差甚元的网络之间进行互连。而路由器则不同，它主要用于不同网络之间互连，因此能连接不同物理介质、链路层协议和网络层协议的网络。路由器在功能上虽然占据了优势，但价格昂贵，报文转发速度低。

近几年，交换机为提高性能做了许多改进，其中最突出的改进是虚拟网络和三层交换。

划分子网可以缩小广播域，减少广播风暴对网络的影响。路由器每一接口连接一个子网，广播报文不能经过路由器广播出去，连接在路由器不同接口的子网属于不同子网，子网范围由路由器物理划分。对交换机而言，每一个端口对应一个网段，由于子网由若干网段构成，通过对交换机端口的组合，可以逻辑划分子网。广播报文只能在子网内广播，不能扩散到别的子网内，通过合理划分逻辑子网，达到控制广播的目的。由于逻辑子网由交换机端口任意组合，没有物理上的相关性，因此称为虚拟子网，或叫虚拟网。虚拟网技术不用路由器就解决了广播报文的隔离问题，且虚拟网内网段与其物理位置无关，即相邻网段可以属于不同虚拟网，而相隔甚远的两个网段可能属于不同虚拟网，而相隔甚远的两个网段可能属于同一个虚拟网。不同虚拟网内的终端之间不能相互通信，增强了对网络内数据的访问控制。

交换机和路由器是性能和功能的矛盾体，交换机交换速度快，但控制功能弱，路由器控制性能强，但报文转发速度慢。解决这个矛盾的技术是三层交换，既有交换机线速转发报文能力，又有路由器良好的控制功能。

二、第三层交换机和路由器的区别

在第三层交换技术出现之前，几乎没有必要将路由功能器件和路由器区别开来，他们完全是相同的：提供路由功能正在路由器的工作，然而，现在第三层交换机完全能够执行传统路由器的大多数功能。作为网络互连的设备，第三层交换机具有以下特征：

1.转发基于第三层地址的业务流；

2.完全交换功能；

3.可以完成特殊服务，如报文过滤或认证；

4.执行或不执行路由处理。

第三层交换机与传统路由器相比有如下优点：

1.子网间传输带宽可任意分配：传统路由器每个接口连接一个子网，子网通过路由器进行传输的速率被接口的带宽所限制。而三层交换机则不同，它可以把多个端口定义成一个虚拟网，把多个端口组成的虚拟网作为虚拟网接口，该虚拟网内信息可通过组成虚拟网的端口送给三层交换机，由于端口数可任意指定，子网间传输带宽没有限制。

2.合理配置信息资源：由于访问子网内资源速率和访问全局网中资源速率没有区别，子网设置单独服务器的意义不大，通过在全局网中设置服务器群不仅节省费用，更可以合理配置信息资源。

3.降低成本：通常的网络设计用交换机构成子网，用路由器进行子网间互连。目前采用三层交换机进行网络设计，既可以进行任意虚拟子网划分，又可以通过交换机三层路由功能完成子网间通信，为此节省了价格昂贵的路由器。

4.交换机之间连接灵活：作为交换机，它们之间不允许存在回路，作为路由器，又可有多条通路来提高可靠性、平衡负载。三层交换机用生成树算法阻塞造成回路的端口，但进行路由选择时，依然把阻塞掉的通路作为可选路径参与路由选择。

4. 七层网络结构

物理层

数据链路层（PPP、HDLC、CSMA/CD）

网络层(IP、ARP（IP→MAC）/RARP(MAC→IP)、ICMP)

传输层（TCP、UDP）

会话层

表示层

应用层（telnet 23、FTP 20<数据>+21<控制>、SMTP 161、DNS、SNMP、DHCP、HTTP 80）

TCP/IP是四层（网络接口层、网际层、运输层、应用层）

5. 时分复用的时隙

均等

6. IPV4****和IPV6的位数

IPV4是32位；IPV6是128位

7. 单工、半双工、全双工

单工：又称为单向通信，即只能有一个方向的通信而没有反方向的交互。例：无线电广播，电视广播

半双工：又称为双向交替通信，即通信的双方都可以发送信息，但不能双方同时发送（当然也就不能同时接受）。

全双工：又称为双向同时通信，即通信的双方可以同时发送和接受信息。

备注：单工只要一条信道，而半双工和全双工需都需要两条信道（每个方向各一条）。

9. 网络通信过程

假如当我们访问一个网站时，在知道网站IP的情况下，猫访问的是实际网卡地址，所以需要通过APD广播，通过工作站将此信息转达给互联网所有的猫(路由器)

当互联网的猫收到这个广播时会检查广播包里的IP是否与自己的IP一致，如果一致则返回给指定猫自己的网卡地址

那么此时双方会在自己内部形成一个链表将其记录下来，让IP与网卡地址形成映射，保存起来，便于下次通讯！

那么下次在通讯时,当我们要访问一个IP时，猫会在自己的链表里检查这个IP是否已经拥有对应的MAC地址，如果有则在包头里将IP更改为MAC地址，这样在对方路由器无需获取IP地址，可以直接根据猫网卡中的MAC地址进行校验，当下次对方IP地址变更时，猫也会重复上面的步骤，通过APD广播重新获取IP地址对应的MAC地址！

比如对方原本是193.2，后来更换成了193.1，这样发送时，猫在自己链表里找不到对应的MAC地址了，所以直接在发送一个APD广播，此时对方返回自己的MAC地址，猫发现原本链表里的193.2对应着这个MAC地址，所以就会直接将链表里193.2换成193.1！

为什么猫使用MAC地址？

答：这是以太网的一种协议，猫必须遵守，因为IP地址是随机变化的，有可能在你们通讯的过程中IP地址就发生了变化，所以为了确定正确性必须使用MAC地址！

假如使用IP地址，你的IP地址是193.2，通讯过程中突然换成了193.1，而193.2分配给另外一个人了，那么另外一个人就会收到这个信息，但是MAC地址是唯一的，所以当地址变更时猫能在链表里查出来，并重新通过APD广播获取新的IP地址！

上面说过猫会接受所有的包，但不是自己的不处理，其实我们可以在猫的设置页面将其猫的网卡设置成混杂模式即可接受所有包，但是接受了也不会被处理，因为包里的大多使用的是TCP/IP/UDP协议，这些协议需要socket套接字，不能保证机器下socket套接字是一致的，所以即便收到了，也不知道给哪个进程，所以直接就废弃了，但是我们可以编写一些抓包工具来抓到所有包，并分析！

注意当我们如果想要访问国外网站时，是没有办法将包转发到国外线路上的，原因很简单：

运营商会修改边界转发工作站的工作模式，在解析你发送的包，如果包里包含敏感IP则使工作站不转发此包！

因为访问国外服务器是有特定的路线的，这也是为什么部分国外网站可以访问，但是部分不让访问的原因！

如果想访问国外的网站需要特定的服务器转接，注意，大陆是可以访问香港服务器，而香港服务器可以访问国外网站，所以我们可以在香港设立服务器，并且在访问香港的服务器进行转接！

10. 简述一下停等协议

由于IP层是不可靠的，因此TCP需要采取措施使得传输层之间的通信变得可靠。停止等待协议就是保证可靠传输，以流量控制为目的的一个协议。其工作原理简单的说就是每发送一个分组就停止发送，等待对方的确认，在收到确认后再发送下一个分组，如果接受方不返回应答，则发送方必须一直等待。

细节描述：①如果发送方如果一段时间仍没有收到确认，就认为刚才发送的分组丢失了，因而重传前面发送过的分组。

②如果接收方的确认分组丢失或者因其他原因，收到了重传分组，则：丢弃这个重传分组，并且向发送方发送确认。

11. 应用层有什么协议，举出两个协议的作用

DNS(域名系统)，将网址解析成IP地址。

DHCP（动态主机设置协议），是一个局域网的网络协议，使用UDP协议工作，主要有两个用途：给内部网络或网络服务供应商自动分配IP地址，给用户或者内部网络管理员作为对所有计算机作中央管理的手段。

FTP(文件传输协议)，FTP客户机可以给服务器发出命令来下载文件，上载文件，创建或改变服务器上的目录。

TELNET(远程终端协议)，能将用户的击键传到远程主机，同时也能将远程主机的输出通过TCP连接返回到用户屏幕。

12.数据链路层的作用

数据链路层在物理层提供的服务的基础上向网络层提供服务，将原始的、有差错的物理线路改进成逻辑上无差错的数据链路，从而向网络层提供高质量的服务。功能主要有：①链路管理；②封装成帧；③透明传输；④差错检测

13.路由协议有哪些

域内：

①RIP （路由信息协议）。距离矢量协议；16跳；收敛速度慢；适用小规模网络；仅和邻居交换信息，且交换的是整个路由表，按固定时间周期性交换；实现简单，开销小；传输层使用UDP；RIP报文限制大小为512字节。

②OSPF（开放最短路由协议）。链路状态协议；基于IP；向自治域中所有路由器发送信息（防洪法），且发送的是链路状态表（LSA），触发更新；更新过程收敛快；根据代价选择最佳路由；支持多路径负载均衡。

域间：

BGP（外部网关协议）是不同AS之间的路由器之间交换路由信息的协议。

14. 频分复用如何避免各路信号间的干扰

载频之间保留了一定的保护间隔，使得相邻的频带不会相互重叠，这样传输过程中不同频率的各路信号便不会相互干扰，而且在接收端可以很容易的利用带通滤波器把各路信号再分割开来，恢复到多路复用前的分路情况。

15. 简述计算机网络中各层作用 这问题回答之后 老师一直追着网络层问了好多 问得我发懵了。。

层	传输单位	任务	功能	设备	协议
物理层	比特	透明地传输比特流	为数据端设备提供传送数据通路	集线器 中继器
数据链路层	帧	将网络层传下来的IP数据报组成帧	① 链路的建立，拆除，分离； ② 帧定界和帧同步 ③ 差错检测	交换机 网桥	PPP、HDLC、ARQ
网络层	数据包	①将传输层传下来的报文段封装成分组 ②选择适当的路由，是传输层传下来的分组能够交付到目标主机	为传输层提供服务； 组包和拆包； 路由选择； 拥塞控制。	路由器	ICMP ARP RARP IP IGMP
传输层	报文段 TCP,UDP	负责主机两个进程之间的通信	为端到端提供可靠的传输服务； 为端到端连接提供流量控制、差错控制、服务质量等管理服务。		TCP UDP
会话层 表示层 应用层	应用层	提供系统与用户的接口	文件传输； 访问和管理； 电子邮件服务。		FTP、SMTP POP3、HTTP DHCP、RIP、BGP

16. 列举数据链路层的协议。。2个即可

局域网：

①CSMA/CD(带冲突检测的载波侦听多路访问协议)，每一个站在发送数据之前要先检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不发送数据，以免发生冲突；如果没有，则发送。并且计算机在发送数据的同时边检测信道上是否有冲突发生。如果有，则采用截断二进制指数类型退避算法来等待一段随机时间后再次重发。总的来说，可概括为“先听后发，边听边发，冲突停发，随机重发”。

广域网：

①PPP（点对点协议），面向字节；不需要的功能：纠错（PPP协议只负责检错）、流量控制（由TCP负责）、序号（PPP协议是不可靠传输协议，故不需要对帧进行编号）、多点线路（PPP协议是点对点的通信方式）、半双工或单工（PPP只支持全双工链路）。

②HDLC(高级数据链路控制协议)，面向比特；标记字段（01111110），地址字段（全1是广播，全0为无效）；控制字段（根据前两位取值可以将HDLC帧划分为三类（无奸细）：信息帧，监督帧，无编号帧），信息字段，帧检验序列FCS（CRC循环冗余码）

17. 网络各层的设备分别是什么

物理层：集线器，中继器（均不能隔离冲突域和广播域）

数据链路层：交换机（转发/学习机制、存储转发、隔离冲突域不能隔离广播域），网桥

网络层：路由器（隔离冲突域和广播域）

18. 什么是滑动窗口协议

滑动窗口协议，是TCP使用的一种流量控制方法。该协议允许发送方在停止并等待确认前可以连续发送多个分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输。

19. PPP协议

点到点协议（Point to Point Protocol，PPP）是为在同等单元之间传输数据包这样的简单链路设计的链路层协议。 [1] 这种链路提供全双工操作，并按照顺序传递数据包。设计目的主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机、网桥和路由器之间简单连接的一种共通的解决方案。PPP具有以下功能：

（1）PPP具有动态分配IP地址的能力，允许在连接时刻协商IP地址；

（2）PPP支持多种网络协议，比如TCP/IP、NetBEUI、NWLINK等；

（3）PPP具有错误检测能力，但不具备纠错能力，所以ppp是不可靠传输协议；

（4）无重传的机制，网络开销小，速度快。

（5）PPP具有身份验证功能。

（6） PPP可以用于多种类型的物理介质上，包括串口线、电话线、移动电话和光纤（例如SDH），PPP也用于Internet接入。

在 TCP-IP 协议集中它是一种用来同步调制连接的数据链路层协议（OSI模式中的第二层），替代了原来非标准的第二层协议，即 SLIP。除了 IP 以外 PPP 还可以携带其它协议，包括 DECnet 和 Novell 的 Internet 网包交换（IPX）。

20. 网络按地理范围分

个域网、局域网、城域网、广域网

21. 保护频带 就是插入一些 空白的频段

见前题

22. 一个网络安全有哪些方面，还有个p2p协议

网络安全由于不同的环境和应用而产生了不同的类型。主要有以下几种：

1、系统安全

运行系统安全即保证信息处理和传输系统的安全。它侧重于保证系统正常运行。避免因为系统的损坏而对系统存储、处理和传输的消息造成破坏和损失。避免由于电磁泄露，产生信息泄露，干扰他人或受他人干扰。

2、网络的安全

网络上系统信息的安全。包括用户口令鉴别，用户存取权限控制，数据存取权限、方式控制，安全审计，计算机病毒防治，数据加密等。

3、信息传播安全

网络上信息传播安全，即信息传播后果的安全，包括信息过滤等。它侧重于防止和控制由非法、有害的信息进行传播所产生的后果，避免公用网络上大云自由传输的信息失控。

4、信息内容安全

网络上信息内容的安全。它侧重于保护信息的保密性、真实性和完整性。避免攻击者利用系统的安全漏洞进行窃听、冒充、诈骗等有损于合法用户的行为。其本质是保护用户的利益和隐私

p2p见文章 p2p详解

23. DNS DHCP DNS倒是记得是让网址转换IP地址的 映射IP地址 动态主机。。协议 DHCP是动态分配ip吗

DHCP动态主机配置协议

24. 流量控制在哪些层实现

传输层（TCP）、数据链路层(ARQ)

25. 频分复用 时分复用 波分复用 码分复用

频分复用：给每个信号分配唯一的载波频率并通过单一媒体来传输多个独立信号的方法。

时分复用：把多个信号复用到单个硬件传输信道，它允许每个信号在一个很短的时间使用信道，接着再让下一个信号使用。

波分复用：就是光的频分复用。用一根光纤同时传输多个频率很接近的光载波信号。

码分复用：码分复用是用一组包含互相正交的码字的码组携带多路信号。每一个用户可以在同样的时间使用同样的频带进行通信。由于各用户使用经过特殊挑选的不同码型，各用户之间不会造成干扰，因此这种系统发送的信号有很强的抗干扰能力。

26. CSMA/CD 协议 如果两端同时发送信息会出现什么情况，为什么？

两端都检测到冲突，均停止发送数据，等待一个随机时间再重发。

27. 电路交换，分组交换

见高分笔记P27

29. 简述下CSMA/CD协议的实现原理

实际上CSMA/CD的工作流程与人际间通话非常相似，可以用以下7步来说明。

第一步：载波监听，想发送信息包的节点要确保没有其他节点在使用共享介质，所以该节点首先要监听信道上的动静（即先听后说）。

第二步：如果信道在一定时段内寂静无声（称为帧间缝隙IFG），则该节点就开始传输（无声则讲）。

第三步：如果信道一直很忙碌，就一直监视信道，直到出现最小的IFG时段时，该节点才开始发送它的数据（有空就说）。

第四步：冲突检测，如果两个节点或更多的节点都在监听和等待发送，然后在信道空时同时决定立即（几乎同时）开始发送数据，此时就发生碰撞。这一事件会导致冲突，并使双方信息包都受到损坏。以太网在传输过程中不断地监听信道，以检测碰撞冲突（边听边说）。

第五步：如果一个节点在传输期间检测出碰撞冲突，则立即停止该次传输，并向信道发出一个“拥挤”信号，以确保其他所有节点也发现该冲突，从而摒弃可能一直在接收的受损的信息包（冲突停止，即一次只能一人讲）。

第六步：多路存取，在等待一段时间（称为后退）后，想发送的节点试图进行新的发送。

这时采用一种叫二进制指数退避策略（Binary Exponential Back off Policy）的算法来决定不同的节点在试图再次发送数据前要等待一段时间（随机延迟）。

第七步：返回到第一步。

实际上，冲突是以太网电缆传输距离限制的一个因素。例如，如果两个连接到同一总线的节点间距离超过2500米，数据传播将发生延迟，这种延迟将阻止CSMA/CD的冲突检测例程正确进行 [2] 。

30. 描述网络某一层的原理

31. 说一下路由器的原理

传统地，路由器工作于OSI七层协议中的第三层，其主要任务是接收来自一个网络接口的数据包，根据其中所含的目的地址，决定转发到下一个目的地址。因此，路由器首先去掉数据包的二层头，取出目的IP地址，在转发路由表中查找它对应的下一跳地址，若找到，就在数据包的帧格前添加下一个MAC地址，同时IP数据包头的TTL（Time To Live）域也减一，并重新计算校验和。当数据包被送到输出端口时，它需要按顺序等待，以便被传送到输出链路上。

计算机网络

1. 网络里时延和带宽的概念

时延是指一个报文或分组从一个网络的一端传送到另一个端所需要的时间。它包括了发送时延，传播时延，处理时延，排队时延。（时延=发送时延+传播时延+处理时延+排队时延）一般，发送时延与传播时延是我们主要考虑的。对于报文长度较大的情况，发送时延是主要矛盾；报文长度较小的情况，传播时延是主要矛盾。

带宽又叫频宽，是指在固定的的时间可传输的资料数量，亦即在传输管道中可以传递数据的能力。在数字设备中，频宽通常以bps表示，即每秒可传输之位数。在模拟设备中，频宽通常以每秒传送周期或赫兹 (Hz)来表示（指通过的频率的宽度）。

2. 网络拥塞

网络中存在太多的数据包导致数据包被延迟或丢失，从而降低了整个网络的传输性能，这种情况叫做拥塞。如果产生网络拥塞，则网络的性能明显下降，整个网络的吞吐量将随着输入负荷的增大而下降。

拥塞控制：可分为闭环控制和开环控制。开环控制是在设计网络时事先将有关拥塞的因素考虑到，力求网络在工作时不产生拥塞。闭环拥塞是基于反馈环路的概念。

拥塞控制的4种算法：

① 慢开始算法

② 拥塞避免算法

③ 快重传算法

④ 快恢复算法

3. CSMA/CD的原理（载波侦听多路访问/冲突检测方法）

工作原理：发送数据前，先侦听信道是否空闲，若空闲，则立即发送数据，在发送数据时，边发送边继续侦听，若侦听到冲突，则立即停止发送数据，等待一段随机时间，再重新尝试。（先听后发，边发边听，冲突停发，随机延迟后重发。）

4. 三网指哪三网？

电信网，广播电视网，互联网。

5. 组成网络协议的三个要素

① 语义：对构成协议元素的含义的解释；

② 语法：数据域控制信息的结构和格式；

③ 同步：规定事件的执行顺序。

6. 电路交换，报文交换，分组交换之间的区别以及联系

	电路交换	报文交换	分组交换
建立被双方独占物理通路 （建立连接）	需要	不要求	不要求
数据交换单位	比特流	报文	分组
传输方式	比特流直接到达	存储转发	存储转发
每个分组沿着规定路径	是		不是
分组按序到达	是		不是
优点	通信时延小； 实时性强； 适用范围广； 控制简单； 避免冲突。	无需建立连接； 动态分配路线； 可靠性高； 线路利用率高； 可提供多目标服务。	加速传输； 简化存储管理； 减少出错几率和重发数据量。
缺点	建立连接时间长； 信道利用率低； 缺乏统一标准； 灵活性差。	由于存储转发方式导致转发时延； 对报文大小没有控制，需要较大的存储缓存空间。	存在传输时延； 工作量大，可能出现分组失序，丢失等情况。

7. 分组交换的优点和缺点

与报文交换相比较，分组交换的优点和缺点如下。

优点：

① 加速传输：因为分组交换是逐个传输，所以可以使后一个分组的存储操作与前一个分组的转发操作并行，这种流水线式传输方式减少了报文的传输时间，此外，传输一个分组所需的缓冲区比传输一个报文所需的缓冲区小得多，这样因缓冲区不足而等待发送的几率及等待的时间也必然减少。

② 简化了存储管理：分组的长度固定，相应的缓冲区大小也固定。

③ 减少出错几率和重发数据量：因为分组较短，其出错几率必然减少，所以每次重发的数据量也就大大减少，这样不仅提高了可靠性，也减少了传输时延。

缺点：

① 存在传输时延：尽管与报文交换相比的传输时延较短，但是与电路交换相比仍然存在存储转发时延，而且对其结点交换机的处理能力有更高的要求。

② 当分组交换采用数据报服务时，可能出现失序、丢失或重复分组，分组到达的目的地的结点时，要对分组按编号进行排序工作，工作量较大。

8. 流量控制在哪些层实现？

流量控制就是要控制发送方数据传输的速率，使接收方来得及接收。

数据链路层：相邻结点的流量控制，

传输层：端到端的流量控制，利用滑动窗口机制在TCP连接上实现流量控制。

9. CDMA及原理

码分多路复用，既共享信道的频率，又共享时间，是一种真正的动态复用技术。

原理：

10. 二层交换机和三层交换机的区别

二层交换技术是发展比较成熟，二层交换机属数据链路层设备，可以识别数据包中的MAC

地址信息，根据MAC 地址进行转发，并将这些MAC 地址与对应的端口记录在自己内部的

一个地址表中。

三层交换机就是具有部分路由器功能的交换机

三层交换技术就是二层交换技术＋三层转发技术。传统交换技术是在OSI 网络标准模型第

二层——数据链路层进行操作的，而三层交换技术是在网络模型中的第三层实现了数据包的

高速转发，既可实现网络路由功能，又可根据不同网络状况做到最优网络性能。

11. 频分复用如何避免频带间的干扰，保护频带？

频带之间会有足够长的隔离频带

12. 停止等待协议

ACK

13. IPv4地址缺乏的解决办法以及IPv4的替代方案以及IPv4和IPv6如何相互通信？

NAT（私网地址的部署）

IPV6

表示方法

IPv6的长分布式结构图

IPv6的地址长度为128位，是IPv4地址长度的4倍。于是IPv4点分十进制格式不再适用，采用十六进制表示。IPv6有3种表示方法。

一、冒分十六进制表示法
　　格式为X:X:X:X:X:X:X:X，其中每个X表示地址中的16b，以十六进制表示，例如：
　　ABCD:EF01:2345:6789:ABCD:EF01:2345:6789
　　这种表示法中，每个X的前导0是可以省略的，例如：
　　2001:0DB8:0000:0023:0008:0800:200C:417A→ 2001:DB8:0:23:8:800:200C:417A

二、0位压缩表示法
　　在某些情况下，一个IPv6地址中间可能包含很长的一段0，可以把连续的一段0压缩为“::”。但为保证地址解析的唯一性，地址中”::”只能出现一次，例如：
　　FF01:0:0:0:0:0:0:1101 → FF01::1101
　　0:0:0:0:0:0:0:1 → ::1
　　0:0:0:0:0:0:0:0 → ::

三、内嵌IPv4地址表示法
　　为了实现IPv4-IPv6互通，IPv4地址会嵌入IPv6地址中，此时地址常表示为：X:X:X:X:X:X:d.d.d.d，前96b采用冒分十六进制表示，而最后32b地址则使用IPv4的点分十进制表示，例如::192.168.0.1与::FFFF:192.168.0.1就是两个典型的例子，注意在前96b中，压缩0位的方法依旧适用 [11] 。

报文内容

IPv6报文的整体结构分为IPv6报头、扩展报头和上层协议数据3部分。IPv6报头是必选报文头部，长度固定为40B，包含该报文的基本信息；扩展报头是可选报头，可能存在0个、1个或多个，IPv6协议通过扩展报头实现各种丰富的功能；上层协议数据是该IPv6报文携带的上层数据，可能是ICMPv6报文、TCP报文、UDP报文或其他可能报文。

IPv6的报文头部结构如图：

版本号	表示协议版本．值为6
流量等级	主要用于QoS
流标签	用来标识同一个流里面的报文
载荷长度	表明该IPv6包头部后包含的字节数，包含扩展头部
下一报头	该字段用来指明报头后接的报文头部的类型，若存在扩展头，表示第一个扩展头的类型，否则表示其上层协议的类型，它是IPv6各种功能的核心实现方法
跳数限制	该字段类似于IPv4中的TTL，每次转发跳数减一，该字段达到0时包将会被丢弃
源地址	标识该报文的来源地址
目的地址	标识该报文的目的地址

扩展头部：

IPv6报文中不再有“选项”字段，而是通过“下一报头”字段配合IPv6扩展报头来实现选项的功能。使用扩展头时，将在IPv6报文下一报头字段表明首个扩展报头的类型，再根据该类型对扩展报头进行读取与处理。每个扩展报头同样包含下一报头字段，若接下来有其他扩展报头，即在该字段中继续标明接下来的扩展报头的类型，从而达到添加连续多个扩展报头的目的。在最后一个扩展报头的下一报头字段中，则标明该报文上层协议的类型，用以读取上层协议数据 [12] 。

14. 传统的搜索引擎基本原理，基于内容的搜索？原理和实现？

搜索引擎的原理，可以分为四步：从互联网上抓取网页、建立索引数据库、在索引数据库中搜索排序、对搜索结果进行处理和排序。

从互联网上抓取网页：

利用能够从互联网上自动收集网页的蜘蛛系统程序，自动访问互联网，并沿着任何网页中所有URL爬到其他网页，重复这个过程，并把爬过的所有网页收集回来。

建立索引数据库：

由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息（包括网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其他网页的链接关系等），并根据一定的相关度算法进行大量的复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度（或重要性），然后利用这些相关信息建立网页索引数据库。

在索引数据库中搜索排序：

当用户输入关键词后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所用相关网页针对该关键词的相关度早已计算好，所以只需按照现成的相关数值排序，相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。

对搜索结果进行处理排序：

所有相关网页针对该关键词的相关信息在索引库中都有记录，只需综合相关信息和网页级别形成相关数值度，然后进行排序，相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。

15. 什么是非对称加密？什么是数据安全的特征？

对称加密与非对称加密

加密技术一般分为对称式加密以及非对称式加密两类。采用的比较广泛的是对称式加密，主要特点是加密和解密使用同一个密钥。而非对称式加密在进行加密时则使用了两个密钥，加密和解密过程中分别使用不同的密钥，这两个密钥分别为“公钥”以及“私钥”，想要能正常完成加密解密过程，就必需配对使用，而在使用过程中，“公钥”是公开的，“私钥”则必须由发送人保密，同时只能由持有人所有。对称式的加密方法如果用于通过网络传输加密文件，那么不管使用任何方法将密钥告诉对方，都有可能被窃听，而非对称式的加密方法则具有一定的优越性，因为它包含有两个密钥，且仅有其中的“公钥”是可以被公开的，接收方只需要使用自己已持有的私钥进行解密，这样就可以很好的避免密钥在传输过程中产生的安全问题。

数据安全的特征

1）机密性（Confidentiality）

保密性（secrecy），又称机密性，是指个人或团体的信息不为其他不应获得者获得。在电脑中，许多软件包括邮件软件、网络浏览器等，都有保密性相关的设定，用以维护用户资讯的保密性，另外间谍档案或黑客有可能会造成保密性的问题。

2）完整性（Integrity）

数据完整性是信息安全的三个基本要点之一，指在传输、存储信息或数据的过程中，确保信息或数据不被未授权的篡改或在篡改后能够被迅速发现。在信息安全领域使用过程中，常常和保密性边界混淆。以普通RSA对数值信息加密为例，黑客或恶意用户在没有获得密钥破解密文的情况下，可以通过对密文进行线性运算，相应改变数值信息的值。例如交易金额为X元，通过对密文乘2，可以使交易金额成为2X。也称为可延展性（malleably）。为解决以上问题，通常使用数字签名或散列函数对密文进行保护。

3）可用性（Availability）

数据可用性是一种以使用者为中心的设计概念，易用性设计的重点在于让产品的设计能够符合使用者的习惯与需求。以互联网网站的设计为例，希望让使用者在浏览的过程中不会产生压力或感到挫折，并能让使用者在使用网站功能时，能用最少的努力发挥最大的效能。基于这个原因，任何有违信息的“可用性”都算是违反信息安全的规定。因此，世上不少国家，不论是美国还是中国都有要求保持信息可以不受规限地流通的运动举行。

16. 网络安全有哪些方面

网络安全主要有系统安全、网络的安全、信息传播安全、信息内容安全。具体如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fieRFdoz-1586332627165)(http://pics7.baidu.com/feed/d8f9d72a6059252d420c48aa9305b73e5ab5b9ad.jpeg?token=daad683c9043353b04239883480158b8&s=706DB84430222D038D33530A0300F0D8)]

1、系统安全

运行系统安全即保证信息处理和传输系统的安全，侧重于保证系统正常运行。避免因为系统的崩演和损坏而对系统存储、处理和传输的消息造成破坏和损失。避免由于电磁泄翻，产生信息泄露，干扰他人或受他人干扰。

2、网络的安全

网络上系统信息的安全，包括用户口令鉴别，用户存取权限控制，数据存取权限、方式控制，安全审计。安全问题跟踩。计算机病毒防治，数据加密等。

3、信息传播安全

网络上信息传播安全，即信息传播后果的安全，包括信息过滤等。它侧重于防止和控制由非法、有害的信息进行传播所产生的后果，避免公用网络上大云自由传翰的信息失控。

4、信息内容安全

网络上信息内容的安全侧重于保护信息的保密性、真实性和完整性。避免攻击者利用系统的安全漏洞进行窃听、冒充、诈骗等有损于合法用户的行为。其本质是保护用户的利益和隐私。

维护网络安全的工具有VIEID、数字证书、数字签名和基于本地或云端的杀毒软体等构成。

1、Internet防火墙

它能增强机构内部网络的安全性。Internet防火墙负责管理Internet和机构内部网络之间的访问。在没有防火墙时，内部网络上的每个节点都暴露给Internet上的其它主机，极易受到攻击。这就意味着内部网络的安全性要由每一个主机的坚固程度来决定，并且安全性等同于其中最弱的系统。

2、VIEID

在这个网络生态系统内，每个网络用户都可以相互信任彼此的身份，网络用户也可以自主选择是否拥有电子标识。除了能够增加网络安全，电子标识还可以让网络用户通过创建和应用更多可信的虚拟身份，让网络用户少记甚至完全不用去记那些烦人的密码。

3、数字证书

CA中心采用的是以数字加密技术为核心的数字证书认证技术，通过数字证书，CA中心可以对互联网上所传输的各种信息进行加密、解密、数字签名与签名认证等各种处理，同时也能保障在数字传输的过程中不被不法分子所侵入，或者即使受到侵入也无法查看其中的内容。

17. 网络的分类

分类	作用范围	使用范围	拓扑结构
	局域网，城域网，广域网，互联网	公用网，专用网	星状，网状，总线，树形，令牌环

18. 有关于信道划分的问题

多路复用：当传输介质的带宽超过了传输单个信号所需的带宽时，通过在一条介质上同时携带多个传输信号的方法来提高传输系统的利用率。

多路复用技术能把多个信号组合在一条物理信道上进行传输，使多个计算机或终端设备共享信道资源，提高信道利用率。

频分多路复用FDM	所有用户在同样的时间占用不同的带宽资源 为了防止子信道之间的干扰，相邻信道之间要加入保护频带
时分多路复用 TDM，STDM 统计时分复用	所有用户在不用的时间占用相同的频带资源； 统计时分复用是一种动态的时间分配，又称异步时分复用。
波分多路复用 DWDM	每个用户在同一时间使用同样的频带进行通信
码分多路复用 CDMA	既共享信道频率，又共享时间。

信道共享技术：

信道共享技术又称为多点接入（multiple access）技术，包括随机接入和受控。

从层次上讲，信道共享是由数据链路层的媒体接入控制MAC子层来完成的。总的来说，在计算机网络中使用的信道共享技术可以分为三种，即随机接入、受控接入和信道复用。

① 随机接入，特点是所有的用户都可以根据自己的意愿随机地向信道上发送信息。当两个或两个以上的用户都在共享的信道上发送信息的时候，就产生了冲突(collision)，它导致用户的发送失败。随机接入技术主要就是研究解决冲突的网络协议。随机接入实际上就是争用接入，争用胜利者可以暂时占用共享信道来发送信息。随机接入的特点是：站点可随时发送数据，争用信道，易冲突，但能够灵活适应站点数目及其通信量的变化。典型的随机接入技术有ALOHA、CSMA、CSMA/CD。将会在后面章节中详细介绍。

② 受控接入，特点是各个用户不能随意接入信道而必须服从一定的控制。又可分为集中式控制和分散式控制。

集中式控制的主要方法是轮询技术，又分为轮叫轮询和传递轮询，轮叫轮询主机按顺序逐个询问各站是否有数据，传递轮询主机先向某个子站发送轮询信息，若该站完成传输或无数据传输，则向其临站发轮询，所有的站依次处理完后，控制又回到主机。

分散式控制的主要方法有令牌技术，最典型的应用有令牌环网，其原理是网上的各个主机地位平等，没有专门负责信道分配的主机，在环状的网络上有一个特殊的帧，称为令牌，令牌在环网上不断循环传递，只有获得的主机才有权发送数据。

③ 信道复用，指多个用户通过复用器(multiplexer)和分用器(demultiplexer)来共享信道，信道复用主要用于将多个低速信号组合为一个混合的高速信号后，在高速信道上传输。其特点是需要附加设备，并集中控制，其接入方法是顺序扫描各个端口，或使用中断技术。

19. 曾经问到过的协议

ICMP

ICMP（Internet Control Message Protocol）Internet控制报文协议。它是TCP/IP协议簇的一个子协议，用于在IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用。

响应请求

我们日常使用最多的ping，就是响应请求（Type=8）和应答（Type=0），一台主机向一个节点发送一个Type=8的ICMP报文，如果途中没有异常（例如被路由器丢弃、目标不回应ICMP或传输失败），则目标返回Type=0的ICMP报文，说明这台主机存在，更详细的tracert通过计算ICMP报文通过的节点来确定主机与目标之间的网络距离。 [5]

目标不可到达、源抑制和超时报文

这三种报文的格式是一样的，目标不可到达报文（Type=3）在路由器或主机不能传递数据报时使用，例如我们要连接对方一个不存在的系统端口（端口号小于1024）时，将返回Type=3、Code=3的ICMP报文，它要告诉我们：“嘿，别连接了，我不在家的！”，常见的不可到达类型还有网络不可到达（Code=0）、主机不可到达（Code=1）、协议不可到达（Code=2）等。源抑制则充当一个控制流量的角色，它通知主机减少数据报流量，由于ICMP没有恢复传输的报文，所以只要停止该报文，主机就会逐渐恢复传输速率。最后，无连接方式网络的问题就是数据报会丢失，或者长时间在网络游荡而找不到目标，或者拥塞导致主机在规定时间内无法重组数据报分段，这时就要触发ICMP超时报文的产生。超时报文的代码域有两种取值：Code=0表示传输超时，Code=1表示重组分段超时。 [5]

时间戳

时间戳请求报文（Type=13）和时间戳应答报文（Type=14）用于测试两台主机之间数据报来回一次的传输时间。传输时，主机填充原始时间戳，接收方收到请求后填充接收时间戳后以Type=14的报文格式返回，发送方计算这个时间差。一些系统不响应这种报文。

PPP

点到点协议（Point to Point Protocol，PPP）是为在同等单元之间传输数据包这样的简单链路设计的链路层协议。 [1] 这种链路提供全双工操作，并按照顺序传递数据包。设计目的主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机、网桥和路由器之间简单连接的一种共通的解决方案。PPP具有以下功能：

基于字符传输

（1）PPP具有动态分配IP地址的能力，允许在连接时刻协商IP地址；

（2）PPP支持多种网络协议，比如TCP/IP、NetBEUI、NWLINK等；

（3）PPP具有错误检测能力，但不具备纠错能力，所以ppp是不可靠传输协议；

（4）无重传的机制，网络开销小，速度快。

（5）PPP具有身份验证功能。

（6） PPP可以用于多种类型的物理介质上，包括串口线、电话线、移动电话和光纤（例如SDH），PPP也用于Internet接入。

DNS

域名系统（服务）协议（DNS）是一种分布式网络目录服务，主要用于域名与 IP 地址的相互转换，以及控制因特网的电子邮件的发送

DHCP

DHCP（动态主机配置协议）是一个局域网的网络协议。指的是由服务器控制一段lP地址范围，客户机登录服务器时就可以自动获得服务器分配的lP地址和子网掩码。默认情况下，DHCP作为Windows Server的一个服务组件不会被系统自动安装，还需要管理员手动安装并进行必要的配置。

DHCP（Dynamic Host Configuration Protocol，动态主机配置协议）通常被应用在大型的局域网络环境中，主要作用是集中的管理、分配IP地址，使网络环境中的主机动态的获得IP地址、Gateway地址、DNS服务器地址等信息，并能够提升地址的使用率。

DHCP协议采用客户端/服务器模型，主机地址的动态分配任务由网络主机驱动。当DHCP服务器接收到来自网络主机申请地址的信息时，才会向网络主机发送相关的地址配置等信息，以实现网络主机地址信息的动态配置。DHCP具有以下功能：

1. 保证任何IP地址在同一时刻只能由一台DHCP客户机所使用。

2. DHCP应当可以给用户分配永久固定的IP地址。

3. DHCP应当可以同用其他方法获得IP地址的主机共存（如手工配置IP地址的主机）。

4. DHCP服务器应当向现有的BOOTP客户端提供服务。

DHCP有三种机制分配IP地址：

1. 自动分配方式（Automatic Allocation），DHCP服务器为主机指定一个永久性的IP地址，一旦DHCP客户端第一次成功从DHCP服务器端租用到IP地址后，就可以永久性的使用该地址。

2. 动态分配方式（Dynamic Allocation），DHCP服务器给主机指定一个具有时间限制的IP地址，时间到期或主机明确表示放弃该地址时，该地址可以被其他主机使用。

3. 手工分配方式（Manual Allocation），客户端的IP地址是由网络管理员指定的，DHCP服务器只是将指定的IP地址告诉客户端主机。

三种地址分配方式中，只有动态分配可以重复使用客户端不再需要的地址。

DHCP消息的格式是基于BOOTP（Bootstrap Protocol）消息格式的，这就要求设备具有BOOTP中继代理的功能，并能够与BOOTP客户端和DHCP服务器实现交互。BOOTP中继代理的功能，使得没有必要在每个物理网络都部署一个DHCP服务器。RFC 951和RFC 1542对BOOTP协议进行了详细描述。

21. 计算机网络各层设备及工作原理总结

层	设备	工作原理	其他
物理层	集线器，中继器	中继器：作用就是讲已经衰竭得不完整的信号经过整理，重新产生出完整的信号再继续传送。（放大器放大的是模拟信号）	集线器不能分割冲突域
集线器Hub：即多端口的中继器，假设一台8个接口的集线器连接8台计算机，计算机1发送信息给计算机8，计算机1的网卡会将信息通过双绞线传送到集线器中，集线器将信息进行广播，其他7个端口的计算机接收到广播时，会对信息进行检查，如果是自己的则接受否则不予理睬。
数据链路层	交换机，网桥	网桥：网桥至少有两个端口，每个端口与一个网段连接，网桥每从一个端口接收到一个帧，就先暂存在缓存中，若该帧未出现差错，且欲发往的目的地MAC地址属于另一个网段（同一网段无需转发，应该丢弃），则通过查找转发表，从相应端口发出。
交换机：实质上是一个多端口网桥，每个端口都直接与主机或集线器相连，并且一般都工作在全双工方式。当主机需要通信时，交换机能同时连通许多对的端口，使每一对相互通信的主机都能像独占通信媒体一样，进行无冲突地传输数据，通信完成后断开连接、
网络层	路由器	路由器的主要作用是转发数据包，通过查询其的路由信息表，将每一个IP数据包由一个端口转发到另一个端口。

设备名称	隔离冲突域	隔离广播域
集线器
中继器
交换机
网桥
路由器

22.计算机网络协议总结（按层总结：什么层，协议，作用，特点等）

层	传输单位	任务	功能	设备	协议
物理层	比特	透明地传输比特流	为数据端设备提供传送数据通路	集线器 中继器
数据链路层	帧	将网络层传下来的IP数据报组成帧	① 链路的建立，拆除，分离； ② 帧定界和帧同步 ③ 差错检测	交换机 网桥	PPP、HDLC、ARQ
网络层	数据包	①将传输层传下来的报文段封装成分组 ②选择适当的路由，是传输层传下来的分组能够交付到目标主机	为传输层提供服务； 组包和拆包； 路由选择； 拥塞控制。	路由器	ICMP ARP RARP IP IGMP
传输层	报文段 TCP,UDP	负责主机两个进程之间的通信	为端到端提供可靠的传输服务； 为端到端连接提供流量控制、差错控制、服务质量等管理服务。		TCP UDP
会话层 表示层 应用层	应用层	提供系统与用户的接口	文件传输； 访问和管理； 电子邮件服务。		FTP、SMTP POP3、HTTP DHCP、RIP、BGP

计算机组成，微机原理，通信原理

1. RAM和ROM的原理和区别（在基本存储单元上存在本质区别）

RAM:

随机通道存储器（random access memory）。一般用来存放各种现场的输入输出数据、中间计算结果、与外存交换的信息以及作为堆栈。一般分为双极型RAM和MOS RAM（又分为静态SRAM、动态DRAM）。

双极型RAM以晶体管的触发器作为基本存储电路，所以管子多，速度快、功耗大、集成度较低、成本高，一般用于高速计算机或者cache。

MOS RAM一般分为静态SRAM和动态DRAM。静态RAM用由六管构成的触发器作为基本电路，集成度适中，功耗适中，速度较快，不需要刷新电路（为了维持数据，动态RAM中需要一个刷新电路，在短周期内对所有基本存储单元进行充电，维持电平状态，来达到数据的保存）。

动态DRAM基本存储电路用单管线路组成（电平靠电容存储，如一般计算机中的内存），集成度高，功耗低，成本比SRAM低，由于靠电容的电荷保持电平，所以需要刷新电路（典型要求每隔1ms刷新一次）。

总的说RAM使用晶体管打开或关闭通往位于交点处的电容器来访问电路。它有如下特性：A、易挥发B、速度快C、成本高，即不易制作大容量的RAM。所以这类存储器一般用在计算机设备的内存部分，而且往往容量不会很大。

ROM：

read-only memory，只读存储器。一般用来存放固定的程序以及存放各种常数、函数表。一般分为掩摸ROM、可编程的ROM（PROM）和可重复擦除的ROM三种（按出现时间顺序排列）。

**掩摸ROM：**由厂家固化一次性程序，不可擦写。原理是：由晶体管构成，‘0’：存储单元通过晶体管导通连地，上电后该单元视为‘0’电平。‘1’：与‘0’逻辑相反，存储单元没有晶体管接地。出现时间最早。

**PROM：**可编程rom，本身不带有程序，只允许用户进行一次擦写操作，出现时间较晚。

可擦写可编程rom：有紫外线擦除（EPROM，70年代初）、电擦除（EEPROM）以及FLASH（闪存）。他们都是可以多次重复擦写的ROM。

EPROM原理是通过击穿绝缘层向浮空栅注入电子进行写操作；利用紫外线使浮空栅电子泄露进行擦操作。

EEPROM：原理与EPROM相似，在绝缘层间加入隧道二极管，于是可以通过电场作用，使浮空栅带上电子或消去。

2. 一位全加器的真值表以及逻辑表达式

上图是一位全加器示意图：Ai、Bi是两个二进制加数，Ci-1是上一级加法器的进位，Si是本级一位加法输出，Ci是加法进位。真值表如下：

Si=Ai⊙Bi⊙Ci-1

Ci=（Ai⊙Bi）Ci-1+AiBi（⊙表示异或逻辑）

3. 什么是芯片组

**芯片组（Chipset）**是构成主板电路的核心。一定意义上讲，它决定了主板的级别和档次。它就是"南桥"和"北桥"的统称，就是把以前复杂的电路和元件最大限度地集成在几颗芯片内的芯片组。芯片组是整个身体的神经，芯片组几乎决定了这块主板的功能，进而影响到整个电脑系统性能的发挥，芯片组是主板的灵魂。芯片组性能的优劣，决定了主板性能的好坏与级别的高低。这是因为目前CPU的型号与种类繁多、功能特点不一，如果芯片组不能与CPU良好地协同工作，将严重地影响计算机的整体性能甚至不能正常工作。

北桥芯片**：**提供对CPU类型和主频的支持、系统高速缓存的支持、主板的系统总线频率、内存管理（内存类型、容量和性能）、显卡插槽规格，ISA/PCI/AGP插槽、ECC纠错等支持；

南桥芯片**：**提供了对I/O的支持，提供对KBC（键盘控制器）、RTC（实时时钟控制器）、USB（通用串行总线）、Ultra DMA/33(66)EIDE数据传输方式和ACPI（高级能源管理）等的支持，以及决定扩展槽的种类与数量、扩展接口的类型和数量（如USB2.0/1.1，IEEE1394，串口，并口，笔记本的VGA输出接口）等；

4. 触发器相关的问题

三类：电位触发、主从触发、边沿触发

5. 中断的软件实行过程

中断源产生中断请求，CPU一般要先屏蔽该中断源的中断，防止错误的中断嵌套->CPU对现场进行保存，存储断点程序地址并将当前数据压入栈中->PC指向对应的中断入口，转入执行中断向量指向的中断服务程序->完成中断响应后，恢复现场，程序回到断点处，将栈中的数据重新读出->重新开中断。

6. 查询传输和中断传输，解释比较

**中断传输：**中断式传送是指处理器进行的各种处理。执行主程序时，输入设备准备好数据，或者输出设备已把数据输出，向处理器发出中断申请，使处理器中止当前程序的执行，转向中断服务程序，读取输入设备的数据，或者把数据送往输出设备。

**无条件传送和查询传输：**程序控制传送分为无条件传送（同步传送）和程序查询传送（条件传送、异步传送）。无条件传送只对固定的外设（如开关、继电器、7段显示器等）在规定的时间用IN或OUT指令进行信息的传输，实质是用程序定时同步传送数据。条件查询的条件是在执行输入或输出指令前，要先查询接口中状态寄存器的状态。输入时，由它只是要输入的数据是否已准备就绪；而输出时，由它只是输出设备是否空闲，由此条件决定执行输入或输出。

可以看出，从CPU的角度看，中断的响应相对查询来说是被动的、实时的，如网络的通讯请求，键盘、鼠标的操作等等。查询则一般用于主动的、可控的场合，通常在需要输入/输出数据时，对外设的状态进行查询，以防冲突。而很多外设的速度是很慢的（如打印机），CPU就会长时间处于等待的状态，无法进行其他操作，这就降低了CPU的效率，所以检测到这类设备忙碌的状态时，我们会用设置中断的方法避免这种等待，提高CPU的使用率。

中断是难以或者无法预测的，查询的操作是用户在程序中制定的，所以一般是可以控制的。

7. 过程调用具体执行了哪些操作

1. 硬件接收到中断信号，立刻保存现场，并查找中断向量表，将CPU控制权转交给系统调用总入口程序。
2. 对于系统调用总入口程序，也要先保存现场，将参数保存在内核的堆栈中。然后查找系统调用表，将CPU控制权转交给对应的系统调用处理程序或者是内核函数。
3. 执行系统调用处理程序
4. 恢复现场，返回用户程序。

8. PC机的端口是同步的还是异步的？什么是异步？

USB好像是同步的。

PC机的串口是异步的，即UART，采用RS-232标准。

异步通信：它用一个起始位表示字符的开始，用停止位表示字符的结束来构成一帧。它的传输帧是由起始位、内容和停止位构成的。每个字符可能还包含有奇偶校验位。波特率一般在50-9600 baud 。数据信号传输速率单位是 字符/秒 或 bps 。

同步通信：为了提高速度，去掉异步通信中使用的起始位和停止位，而在数据块开始前使用一段同步字符指示通信开始，同步通信对整块数据进行传输，速度较快，通常为几十到几百Kbaud。

9. 控制单元设计··分为组合逻辑和微程序··两者区别··优缺点·

电路的输出仅由该时刻电路的输入决定的电路，称为组合逻辑电路。

上面那句是概念性的东西，具体在数字电路组合逻辑部分。

郎艳峰上的EDA技术用的FPGA就是组合逻辑控制的一种，不过那个太低端了。。

程序的特点是：为了达到一定目的，程序按照一定的逻辑关系一条一条地执行，程序执行的快慢取决于机器周期的快慢、CPU的性能以及软件算法的优劣等。

1、速度上：组合逻辑电路由用户制定好逻辑关系后，输入信号经过电路的响应，直接得出结果，很大程度上是纯硬件的响应，因此在时刻间隙内可以完成可能需要通过多条程序才能完成的算法，不难看出，组合逻辑电路设计的控制单元比程序控制的单元具有更快的处理速度，而且系统越复杂，组合逻辑在速度上的优势越明显。

2、复杂度上：组合逻辑电路是由设计者按照自己的设想将众多逻辑器件组合而成的，对于较为复杂的系统，设计一个逻辑电路往往需要庞大的工作量，检验和仿真等都是费时费力的工程。在这一点上，程控的方法显得方便的多，程序结构的有条不紊是它在设计复杂度上占优势的主要因素。一个无比复杂的逻辑结构可能只需要设计者为CPU设计一些精炼的算法就可以实现，在对处理速度没有十分苛刻的要求情况下，通过程序设计会大大地减轻设计者的工作量。

3、成本：一般来说，大型可编程逻辑器件的成本要比一些较为高端的处理器或单片机高得多，而且工作量一般比较大，花费的工比较多。

总的来说，工程设计上，要综合实际应用的要求和成本，设计者要尽量选择全方位的设计方案。

10. 关于IO接口的，微机原理中的内容，要仔细看下。

**接口：**接口是位于主机和外设之间的一种缓冲电路，包括了硬件电路和软件控制，现在接口通常为可编程的大规模集成电路芯片。

**端口：**接口电路通常有三种寄存器：数据输入输出缓冲寄存器、控制寄存器、状态寄存器。这些寄存器称为（数据、控制、状态）端口。对I/O设备的访问，就是通过对端口访问实现的，每个端口赋予一个唯一的地址码，称为端口地址。

**端口的编址：**独立编址和统一编址。统一编址是将端口当做存储器单元，与内存统一编址，内存和端口的操作指令是统一的，所以指令功能强，但是端口占用了存储器的地址空间，使存储器容量减少。

独立编址也称为I/O映射编址，即端口和内存分开各自独立地拥有自己的地址空间，端口不占用存储器空间。

80x86采用独立编址。

**I/O端口地址译码：**1、用逻辑门电路进行译码2、用译码器进行译码3、比较器译码4、PROM（可编程rom）和GAL（通用逻辑阵列）。

11. 中断（概念，补充：中断可不可以被打断，有哪些情况）

指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。

在响应中断时，CPU执行两个连续的中断响应周期，每个周期都输出中断响应信号/INTA，第一个周期CPU使0~15位的地址总线(8086有20根地址总线)浮空，第二个周期被响应的外设向数据总线输送一个字节的中断向量号，而后CPU读取中断向量号，转向中断服务程序，响应中断。

有些不可屏蔽中断是可以打断其它中断的。如掉电、复位等。

23. 简述RAM、ROM、PROM、EPROM、EEPPROM的区别（第一题说过了。。。）

24. 什么是指令，时钟，总线周期，有什么关系

我们把要求计算机执行的各种操作用命令的形式写下来，就是指令。

通常一条指令对应着一种基本操作，其具体的功能是由设计人员赋予它的指令系统决定的。一台计算机能执行什么样的操作，能做多少种操作，是由设计计算机时所规定的指令系统决定的。一条指令，对应着一种基本操作。计算机所能执行的全部指令，就是计算机的指令系统，这是计算机所固有的。

指令通常分为操作码和操作数两部分。操作码表示计算机执行什么操作；操作数指明参加操作的数的本身或操作数所在的位置。

时钟周期是计算机中最小、最基本的时间单位，在一个时钟周期内，CPU一般只能完成一个基本操作。

什么是总线周期，以及三者的关系如下：

执行一条指令的时间称为指令周期，每个指令周期中又划分为一个个总线周期。虽然各条指令的指令周期有很大的差别，但它们仍然是由以下一些基本的总线周期组成的：1、存储器读/写总线周期；2、输入输出端口（IO口）读/写总线周期；3、中断相应周期。

8086构架的CPU每个总线周期有四个子状态T1~4，每个状态时间为一个时钟周期（是8086处理动作的最小单位）

25. 80x86的硬件组成

采用冯·诺依曼体系构架，即数据和程序统一放在同一块存储器里。80X86CPU是由几个独立的不同功能部件构成的：执行部件、指令部件、总线部件和地址部件。其中，8086只有执行部件和总线部件。

8086是16位处理器，采用40引脚封装，分别有16位数据线，以及20位地址线（其中16根与数据线公用），可寻址1MB空间的内存。

中断信号线：INTR（输入）、NMI（输入）、/INTA（输出、三态）；

系统复位：RESET，输入；准备好：READY，输入；测试：/TEST，输入；

时钟：CLK，输入；

电源：Vcc；

底线：GND；

读选通：/RD，输出；

写选通：/WD，输出；

模式选择信号：MN/~MX，最小/最大工作模式控制信号，输入。高电平工作于最小模式，组成单处理器系统；低电平工作于最大模式，组成多处理器系统。

26. 80x86的寻址方式

IA-32结构的CPU通常有四种主要的寻址方式：立即数寻址，寄存器操作数寻址，（前面两类比较简单，跟单片机差不多），IO端口寻址（在第10题里说过）和存储器操作数寻址。以下是存储器操作数寻址方式详解：

8086采用段寻址方式，有4个16位段寄存器：CS：代码段寄存器；DS：数据段寄存器；SS：堆栈段寄存器；ES：附加段寄存器（第二个数据段）。

8086把1MB的存储空间分为若干段，每段用一个段寄存器标识。每个段的起始值（段基值）按如下方法得出：

段基值=（段寄存器内容）*16=（段寄存器内容）*10H (即左移四位)。

8086的物理地址形成方法：段地址：偏移；即在段基址的基础上加上偏移地址量。偏移地址量存放在IP（代码指针），SP（堆栈指针），SI（源变址寄存器），DI(目的变址寄存器)四个寄存器中，或使用一个有效地址EA，该EA地址的内容就是偏移量。

80286开始有了实地址、保护方式两种不同的存储器管理模式，往后的CPU物理存储空间逐渐加大，也都拥有这两种管理模式。实地址方式类似于8086类似的物理地址生成。保护方式下，CPU可提供一定大小的虚拟存储空间，这个大小一般比物理地址空间大得多。执行程序时，若相应的程序段未调入内存，则向操作系统发出中断，把所需要的程序段和数据从外存调入内存，所以用户可以不受实际物理空间大小的限制，有利于开发大规模的程序。

27. 条件查询的工作方式

程序控制传送分为无条件传送（同步传送）和程序查询传送（条件传送、异步传送）。条件查询的条件是在执行输入或输出指令前，要先查询接口中状态寄存器的状态。输入时，由它只是要输入的数据是否已准备就绪；而输出时，由它只是输出设备是否空闲，由此条件决定执行输入或输出。

28. call和return 具体做了哪些工作

CALL（LCALL）指令执行时，进行两步操作：

（1）将程序当前执行的位置IP，加1压入堆栈中；

（2）转移到调用的子程序。

RET指令：从堆栈的栈顶取得在执行call指令时压入的代码地址值，继续执行之前的程序。

29. DMA和中断数据传输有什么区别

中断虽然是对设备实时地进行了响应，但是还是需要通过CPU对数据进行读写操作，导致数据的传输速率受到影响，而且执行中断响应要执行多条指令，这样还是降低了CPU的效率。DMA是直接存储器访问技术，它可以避开CPU，让CPU暂停对总线的控制，独自占用总线达到对外设和内存之间的数据传输，传输结束时，释放总线并通知CPU重新控制总线。如此一来，数据的传输速率基本只受限于存储器的性能。

PC机中一般都设有DMA控制器来提高数据的吞吐率，减轻CPU负担，提高操作系统运行速度。

DMA的一般过程如下：

1、向CPU发出hold信号；

2、当CPU返回HLDA信号后，接管和控制总线，进入DMA方式；

3、发出地址信息，能对存储器寻址以及能修改地址指针；

4、发出读、写等控制信号；

5、决定传送的字节数，判断DMA传送是否结束；

6、发出DMA结束信号，使CPU恢复正常工作状态。

30. 选择回答了cache的相关知识

高速缓冲存储器：比主存储器体积小但速度快，用于保有从主存储器得到指令的副本。很可能在下一步为处理器所需的专用缓冲器。一般采用SRAM技术。

在计算机存储系统的层次结构中，介于中央处理器和主存储器之间的高速小容量存储器。它和主存储器一起构成一级的存储器。高速缓冲存储器和主存储器之间信息的调度和传送是由硬件自动进行的。

主要由三大部分组成：

Cache存储体：存放由主存调入的指令与数据块。

地址转换部件：建立目录表以实现主存地址到缓存地址的转换。

替换部件：在缓存已满时按一定策略进行数据块替换，并修改地址转换部件。

查看更多

计算机组成，微机原理，通信原理

1. 电子线路，集成电路设计流程

电子线路设计：审题并制定方案->借助CAD或者EDA技术进行模拟仿真->电子线路要进行器件选型->电子线路要制板->加工->测试->总结

集成电路设计：审题并制定方案->设计验证和基础器件设计->生产->测试->总结

2. 单片机和PC机的cpu区别

PC机的CPU是单纯的处理器，它提供的是丰富的I/O口资源和高速的处理速度，它本身没有太多资源，这让它无法单独运行，但是具有极高的可扩展性，结合大量外设（如存储器、DMA、各种控制器等）同它构成完整的系统能够发挥出它的巨大作用，一般用在高端的场合。如今的CPU主频可高达3G赫兹以上，功耗大，组成的设备体积大，功能强，资源多。它在系统中起数据处理和任务调度的作用。

单片机在一块芯片上集成了包括CPU、存储器、AD/DA在内的许多外设，CPU同外设的接口都由厂家统一规划，集成度高，性能稳定，使用者只需要操作CPU对各外设的寄存器进行操作即可。单片机的引脚多被外设占用，因此IO口的资源很有限，可扩展性不高，而且它片内的CPU性能一般不会太高，如今高端的单片机虽然运用32位处理器，但工作频率最高只有百兆赫兹，处理速度不快，适用于一些小体积、低功耗、低要求、低成本的场合。单片机在系统中一般作为核心的控制器，外围电路一般不需要添加很多其它设备。

PC的CPU一般采用冯·诺依曼结构，单片机中一般采用哈佛构架（程序和数据存放在不同的存储器中）。

3. N、P型半导体和PN结原理

**N****型半导体：**在本征半导体中掺入少量五价元素（如磷P），成为N型半导体。由于掺入杂质后，电离能力大大加强，电离产生自由电子，所以掺入的杂质称为施主杂质，留下的带正电的离子称为施主离子。这种掺有施主杂质的、以电子导电为主的半导体，称为N型半导体。N型半导体中，多子是自由电子，少子是空穴。

**P****型半导体：**在本征半导体中掺入少量三价元素（如硼B），成为P型半导体。如硼一类的三价元素，起着接受电子的作用，称为受主杂质，电离后不可移动的负离子称为受主离子。掺有受主杂质的半导体中，空穴的浓度远远大于自由电子的浓度，所以空穴成为多子，自由电子成为少子，这种掺有受主杂质的半导体称为P型半导体。

两种载流子的运动：扩散运动、漂移运动。扩散运动是载流子由高浓度向低浓度扩散引起的，这样形成的电流称为扩散电流。漂移运动是在电场的作用下，载流子沿着电场方向（自由电子逆电场方向）运动造成的，这样形成的电流称为漂移电流。

**PN****结原理：**P、N型半导体结合后，由于两边载流子相互吸引。在交界处附近，载流子都被束缚在晶体的晶格上无法参与导电，于是形成了一个电荷数目相等、极性相反的空间电荷区（耗尽层）。空间电荷区存在内建电场，电场的方向由N指向P（因为N中电离出电子，余下的是正离子，带正电）。由于这个内建电场的作用，两边多子的扩散受到抑制，而同时也出现了少子的漂移。当扩散电流和漂移电流达到平衡时，空间电荷区达到平衡状态，从而形成PN结。

PN****结单向导电原理：PN结是处于一个平衡的状态，这个状态的原因是由于内建电场的作用。所以很明显，如果在PN结的两端加上电压，将会打破这个平衡。1、正向电压（P->N，表示P接正极，N接负极）：正向电压与内建电场的方向相反，于是抑制了PN结两方少子的漂移运动，扩散电流大于漂移电流，产生正向电流。当正向电压加大时，势垒电场（内建电场）会进一步减小，正向电流进一步扩大。2、反向电压（N->P）：反之，当加上反向电压后，内建电场受到增强，势垒电压增大，漂移电流增大，但是由于漂移电流的产生源于PN结两边的少子，数量很少，所以该漂移电流也很小，PN结处于反向截止状态，这时电路中的电流称为反向电流。当反向电压不是很高时，几乎所有的少子均参与了漂移运动，所以当反向电压再变大时，反向电流几乎不增大，故反向电流又称为反向饱和电流。但PN结对温度比较敏感，如果温度上升，PN结中少子数量急剧增加，反向电流也会迅速变大。

4. 传递函数里并联环节的等效

传递函数（系统函数）有并联型，串联型和反馈型。并联型的n个系统函数等效于将这n个系统函数相加成一个系统函数，串联型等效于相乘。

5. 能控性、能观性概念（属于信号系统学科或控制学科）

Controllability：可控性。（起始状态一定，输入不一定的情况下）

​ 研究系统的输入控制系统状态的能力。

​ 给定起始状态，如果能找到容许的输入量（控制矢量），在有限时间内把系统的所有状态引向零状态，则称系统完全可控。若只有部分满足该条件，则称为不完全可控。（LTI线性时不变系统中，也指从零状态引向任一状态。）

Observability：可观性。（起始状态不一定，给定输入）

​ 研究系统的输出观测系统状态的能力。

​ 给定输入（控制）后，如果能再有限时间内根据系统输出唯一地确定系统的起始状态，则称系统完全可观。亦存在不完全可观。

6. AD转换后的精度由什么决定（这个没回答出来），DA转换的具体过程。

基准电压？PCB布线格局？转换时间？额额额额额额额。第一个不知道。。。

DAC主要由数字寄存器、模拟电子开关、位权网络、求和运算放大器和基准电压源组成。数据存入数字寄存器中，控制模拟电子开关通断，在位权网络中形成于输入电压（电流）成比例关系的比例结构，通过运放进行运算输出。（具体内容数电上有）

7. 老师看我考的是自动控制原理，问的我渐进稳定的问题。

渐进稳定嘛，就是一个反馈系统，它的输入响应一开始是呈减幅震荡的，但最终渐渐地趋向于一个稳定值，或者在这个值左右小幅震荡。比如说一个PID算法控制电机转速的系统，电机的转速就是渐进稳定，趋向于预定转速的。

8. 说一下什么是波长，波长的计算方法是什么。

波长λ是波在传播时，同一波线上两个相邻的、相位差为2π的质点之间的距离。λ=波速u*周期T

9. 多普勒（老师说看你物理学的不错）

波在波源移向观察者时接收频率变高，而在波源远离观察者时接收频率变低。或者说，当观察者向波源移动时，频率变高，反之亦然。

10. 无线通信的3种方式。（这个问的有歧义。。给两种答案）

1、点对点、广播（点对多点）、多点对多点（路由）。 （我觉得是= =`）

2、频分复用（FDM）、时分多址（TDMA）、码分多址（CDMA）。如果问到正交频分复用（OFDM），自求多福吧，呵呵。

11. 奈奎斯特定律

如果一个信号含有的最高的频率分量是Fh，在用频率为Fs的抽样信号对该信号进行采样时，采样后信号的频谱会作Fs周期的周期延拓，如果Fs<2*Fh的话，就会导致信号在频谱上出现混叠，这样就无法准确恢复出原信号。

奈奎斯特定律即：对连续信号采样时，抽样信号的频率要不小于被采样信号主瓣频率的两倍。即：

Fs >= 2 * Fh

12. 解释单工 全双工 半双工

单工：一方只能发送，一方只能接收。

半双工：在同一时间，只能够由一方发送，另一方接收。

全双工：通信双方可以同时向对方发送和接收数据。

13. 数据传输方式

基带传输/频带传输/数字传输

并行传输/串行传输

异步传输/同步传输

子相互吸引。在交界处附近，载流子都被束缚在晶体的晶格上无法参与导电，于是形成了一个电荷数目相等、极性相反的空间电荷区（耗尽层）。空间电荷区存在内建电场，电场的方向由N指向P（因为N中电离出电子，余下的是正离子，带正电）。由于这个内建电场的作用，两边多子的扩散受到抑制，而同时也出现了少子的漂移。当扩散电流和漂移电流达到平衡时，空间电荷区达到平衡状态，从而形成PN结。

PN****结单向导电原理：PN结是处于一个平衡的状态，这个状态的原因是由于内建电场的作用。所以很明显，如果在PN结的两端加上电压，将会打破这个平衡。1、正向电压（P->N，表示P接正极，N接负极）：正向电压与内建电场的方向相反，于是抑制了PN结两方少子的漂移运动，扩散电流大于漂移电流，产生正向电流。当正向电压加大时，势垒电场（内建电场）会进一步减小，正向电流进一步扩大。2、反向电压（N->P）：反之，当加上反向电压后，内建电场受到增强，势垒电压增大，漂移电流增大，但是由于漂移电流的产生源于PN结两边的少子，数量很少，所以该漂移电流也很小，PN结处于反向截止状态，这时电路中的电流称为反向电流。当反向电压不是很高时，几乎所有的少子均参与了漂移运动，所以当反向电压再变大时，反向电流几乎不增大，故反向电流又称为反向饱和电流。但PN结对温度比较敏感，如果温度上升，PN结中少子数量急剧增加，反向电流也会迅速变大。

4. 传递函数里并联环节的等效

传递函数（系统函数）有并联型，串联型和反馈型。并联型的n个系统函数等效于将这n个系统函数相加成一个系统函数，串联型等效于相乘。

5. 能控性、能观性概念（属于信号系统学科或控制学科）

Controllability：可控性。（起始状态一定，输入不一定的情况下）

​ 研究系统的输入控制系统状态的能力。

​ 给定起始状态，如果能找到容许的输入量（控制矢量），在有限时间内把系统的所有状态引向零状态，则称系统完全可控。若只有部分满足该条件，则称为不完全可控。（LTI线性时不变系统中，也指从零状态引向任一状态。）

Observability：可观性。（起始状态不一定，给定输入）

​ 研究系统的输出观测系统状态的能力。

​ 给定输入（控制）后，如果能再有限时间内根据系统输出唯一地确定系统的起始状态，则称系统完全可观。亦存在不完全可观。

6. AD转换后的精度由什么决定（这个没回答出来），DA转换的具体过程。

基准电压？PCB布线格局？转换时间？额额额额额额额。第一个不知道。。。

DAC主要由数字寄存器、模拟电子开关、位权网络、求和运算放大器和基准电压源组成。数据存入数字寄存器中，控制模拟电子开关通断，在位权网络中形成于输入电压（电流）成比例关系的比例结构，通过运放进行运算输出。（具体内容数电上有）

7. 老师看我考的是自动控制原理，问的我渐进稳定的问题。

渐进稳定嘛，就是一个反馈系统，它的输入响应一开始是呈减幅震荡的，但最终渐渐地趋向于一个稳定值，或者在这个值左右小幅震荡。比如说一个PID算法控制电机转速的系统，电机的转速就是渐进稳定，趋向于预定转速的。

8. 说一下什么是波长，波长的计算方法是什么。

波长λ是波在传播时，同一波线上两个相邻的、相位差为2π的质点之间的距离。λ=波速u*周期T

9. 多普勒（老师说看你物理学的不错）

波在波源移向观察者时接收频率变高，而在波源远离观察者时接收频率变低。或者说，当观察者向波源移动时，频率变高，反之亦然。

10. 无线通信的3种方式。（这个问的有歧义。。给两种答案）

1、点对点、广播（点对多点）、多点对多点（路由）。 （我觉得是= =`）

2、频分复用（FDM）、时分多址（TDMA）、码分多址（CDMA）。如果问到正交频分复用（OFDM），自求多福吧，呵呵。

11. 奈奎斯特定律

如果一个信号含有的最高的频率分量是Fh，在用频率为Fs的抽样信号对该信号进行采样时，采样后信号的频谱会作Fs周期的周期延拓，如果Fs<2*Fh的话，就会导致信号在频谱上出现混叠，这样就无法准确恢复出原信号。

奈奎斯特定律即：对连续信号采样时，抽样信号的频率要不小于被采样信号主瓣频率的两倍。即：

Fs >= 2 * Fh

12. 解释单工 全双工 半双工

单工：一方只能发送，一方只能接收。

半双工：在同一时间，只能够由一方发送，另一方接收。

全双工：通信双方可以同时向对方发送和接收数据。

13. 数据传输方式

基带传输/频带传输/数字传输

并行传输/串行传输

异步传输/同步传输

单工/半双工/全双工传输