计算机复试面试基础知识（八股文）（数据库、数据结构、操作系统、计网、机组等）

数据库绪论 简述三层模式，两层映射，分别有什么作用？ 模式（逻辑模式）：描述数据库中所有数据的逻辑结构和特征，数据库系统模式结构的中间层，不涉及数据的物理存储细节，也与具体的应用程序开发工具语言无关。 外部模式（用户模式）：用户可以看到和使用的局部数据的逻辑结构和特征描述，与应用程序相关的数据的逻辑表示，模式的子集，数据库可以有多个外部模式。 内部模式（存储模式）：对数据物理结构和存储模式的描述是数据库中数据的表示，如存储模式按属性升序存储、索引等。 外部模式图像：当模式发生变化时，数据库管理员可以相应地改变外部模式图像，使应用程序不需要修改。确保数据和程序的逻辑独立性。 模式中的模式图像：当数据库的存储结构发生变化时，数据库管理员会相应地改变模式中的模式图像，以保持模式不变，从而保证数据和程序的物理独立性。 三级模式允许用户逻辑抽象地处理数据，而不关心计算机中数据的具体表示和存储。两级图像确保了数据库系统中的数据具有较高的逻辑和物理独立性。

2、说出至少三种数据库类型（层次，网状，关系）并简要解释了一下 层次模型:各种实体和实体之间的联系用树形结构表示，有的只有一个节点没有双亲节点(根节点)，有的只有一个双亲节点。只能直接表示一对多的联系。 优点:效率高，结构清晰，性能优于关系数据库，不低于网状。 缺点:现实世界中很多接触都不是层次性的，比如节点之间的多对多接触，一个节点有多个父母的情况很难表达。

网格模型：对于非层次关系的连接，非树形结构非常不直接，网格模型可以很好地表示，允许一个以上的节点没有父母，一个节点也可以有多个父母，可以更直接地描述现实世界。 优点：更直接地描述现实世界，性能更好，访问效率更高。 缺点：结构复杂，不利于掌握。用户还必须了解系统结构的细节，这增加了编程的负担。

关系模型：一般来说，关系是一个标准的二维表，实体或实体之间的关系用关系来表示，数据的检索和更新结果也是关系。 优点：概念单一，用户易于理解和使用，访问路径对用户透明，具有更高的数据独立性和安全性，简化程序员的工作。 缺点:查询效率往往不如格式化数据模型。为了提高性能，增加开发DBMS难度。

关系数据库 3.简要介绍关系与关系模式的区别。 关系的本质是一个二维表，关系模式是对关系的描述，关系是关系模式在某一时刻的状态或内容。 由于关系操作不断更新数据库中的数据，关系模式是静态的、稳定的，而关系是动态的、不断变化的。 一般来说，关系是一个二维表，关系模式是表格的描述（表头），关系名称是表名，元组是一行，属性是列，重量是记录中的列值。

4.什么是关系数据库？关系和二维表有什么区别？ 关系数据库，是建立在关系数据库模型基础上的数据库，借助于集合代数等概念和方法来处理数据库中的数据。 在关系模型中，数据结构表示为二维表，关系表示为二维表（但不是任何二维表）。表中的第一行通常称为属性名，表中的每个元组和属性不可分割，元组的顺序无关紧要。

5.数据库主键的完整性(实体完整性、参考完整性、用户自定义)和约束性 实体完整性：如果主码由多个属性组成，则关系的主码不能取空值。实体以主码作为唯一标志。 参考完整性:一段关系中的外码，或取空值(如果属性组全为空)，或等于其参考的关系的主码值。 用户自定义完整性：对特定关系数据库的约束。

数据库语言SQL 6、什么是DDL、DML、DCL？(数据库语言有哪些？ 语言的数据定义（DDL）：Create、Drop、Alter 数据操作语言（DML）：Insert、Update、Delete 语言的数据控制（DCL）：Grant、Revoke 数据查询语言：Select

7.什么是视图，有什么作用？数据库的哪一层？ 视图：从一个或几个基本表中导出的表是一个虚拟表。数据库只存储视图的定义，而不存储视图对应的数据。数据仍然放置在原始的基本表中。基本表数据通过视图查询发生变化，

数据库设计 8.简要介绍数据库设计的几个阶段 需求分析：详细调查现实世界中需要处理的对象，充分了解各种需求，并在此基础上确定新系统的功能。 概念结构设计：经常采用自顶向下需求分析，自底向上概念结构设计。对需求分析收集到的数据进行分类组织形成实体、实体的属性，确定实体之间联系，设计分E-R图纸。逐一设计分E-R图片，最后将所有分数E-R图集成为一个系统E-R图。 逻辑结构设计：一般来说E-R图向关系模型转换，实体型转换为关系模式。一对一连接可以独立或与任何一端合并，一对多连接可以独立或与N端对应的关系模式合并，多对多连接可以独立转换为关系模式。标准化数据模型，并根据具体需要设计相应的视图。 数据库物理设计：关系模式访问方法的选择，如索引、簇、哈希等存储方法。数据库的访问结构也应确定。目前，许多计算机都有多个磁盘或磁盘阵列，因此表和索引可以放置在不同的磁盘上。磁盘驱动器在查询过程中并行工作，可以改善物理IO读写效率，也可以将较大的表放在两个磁盘上，以加快存取速度。 实施和维护数据库：如备份和恢复等待。

9、什么是E-R图 E-R图：在概念结构设计中，对需求分析收集的数据进行分类组织，形成实体属性，确定实体之间的联系和设计E-R图。

10、分别解释1NF、2NF、3NF、BCNF、4NF 范式：关系数据库中的关系应满足一定的要求，不同的范式应满足不同程度的要求。 标准化：通过模式分解，一种低级范式关系模式可以转化为几种高级范式关系模式的集合。 1NF：满足最低要求的称为第一范式，每个重量必须是不可分割的数据项。 2NF：消除关系中的部分函数依赖称为第二范式，部分函数依赖是非主属性不完全依赖代码。 3NF：每个非主属性既不部分依赖代码，也不传输依赖代码。 BCND：所有的非主属性都完全依赖于每个代码的函数，没有任何属性完全依赖于任何非代码属性，也就是说，除了代码之外没有决定性因素。

并发控制数据库 什么是事物，并发控制是为了保证事物？ 事情:是一系列的数据操作，要么完全不做，要么完全不可分割。运行过程中发生的故障不能继续执行，全部回滚到开始状态。 多个用户在并发控制中访问数据库时，可能会同时访问多个数据。如果没有控制，就会破坏事物的一致性。为了保证事物的一致性，并发控制。

12、ACID(事物的四个性质) A原子：要么做，要么不做。 C一致性:如果运行中出现故障，必须回滚。数据不能不一致。比如两个人转钱，一半坏了，两个人都没钱。 I隔离:一件事不能被其他事物干扰。 D可持续性：一旦事物提交，他对数据库的变化应该是永久的。下一个操作和故障不应该对刚才的结果产生任何影响。

线性表 15.当地逆置单链表 摘下头结点，然后从第一节点开始，头插法建立单链表，直到最后一节点。

16.什么能实现单链表？ 指向结构向结构的指针。结构中有两个成员。每个节点分为数据域和指针域。除最后一个节点外，每个节点指针域指向下一个节点的地址和最后一个节点指针域NULL。 该操作也可以通过结构体数组进行模拟。数组中的每个下标都对应于一个数据元素和游标。游标是数组中下一个元素的下标。未使用的数组元素被用作备用链表。下标为0的元素游标存储备用链表第一节点的下标。数组最后一个元素游标存储第一个有效值元素的下标相当于头结点的作用游标为0表示指向为空。

栈和队列 17、实现一个队列的方法？为什么队列的顺序存储需要留一个空位？循环有什么好处？ 链式存储：把链表改装一下，加尾指针作为队列的尾部可以插入节点，头指针可以删除节点，相当于出队。 顺序存储：正常的顺序存储想要利用空出的空间就必须移动元素，不移动还会浪费空间，循环队列可以解决这个问题，把这段连续的地址空间，想象成逻辑上的环，所以只要有空闲空间就能使用。 但是当front和rear指针相等的时候有两种情况，一种是满，一种是空，为了区分这种情况，保留一个元素空间，我们假定当rear+1与front相等队列就满了。而空的时候是rear等于front。又因为是环也可能存在rear>front的情况，所以取模操作。 另外计算队列长度的时候，rear>front队长为rear-front，但当rear<front队长为两段相加，所以通用公式为（rear-front+队列的总长度）%队列总长度

树与二叉树 18、什么是完全二叉树？ 完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

19、什么是二叉排序树，简述它的查找过程，二叉排序树的时间复杂度，遍历后得到什么样的序列？ 二叉排序树是一种二叉树，具有了一些独特性质，若左子树不为空，则左子树上所有节点的值均小于它的根节点的值，右子树不为空，则右子树上所有节点的值均大于它的根节点的值，而且它的左右子树也是二叉排序树。构造一个二叉排序树是为了提高动态查找中插入和删除的速度。 查找过程：递归查找二叉排序树中是否存在要查关键字，若成功则指针指向该数据元素的节点，返回成功，如果关键字小于树中这个节点，则去它左子树中继续查找，大于则去右子树中查找。如果树中没有要查的关键字，则指针指向访问的上一个节点，以便于插入。 插入过程：如果当查找失败且指针p为空，则新建根节点，如果要插入的关键字小于p指向节点的数据，则插入到左孩子，否则右孩子。 删除过程：1叶节点直接删除2只有左或右子树删了接下面3左右子树都有的，找到要删除的节点的直接前驱或后继，用这个节点替换要删除的节点，然后在删除这个节点。 二叉排序树，以链接的方式存储，有在执行插入或删除操作时候不用移动元素的优点，插入删除性能较好，而查找的时间复杂度取决与二叉排序树的形状。中序遍历后得到升序系列，所以也称为二叉排序树。

20、什么是平衡二叉树？ 为了解决二叉查找树，查找时间依赖于形状的问题，平衡二叉树就是在建立二叉排序树的时候，对它做了一定的限制，使它保持平衡，使每一个节点的左子树和右子树的高度差至多为1。 具体做法：找出距离插入节点最近且平衡因子绝对值大于一的节点，把它当为根的子树叫做最小不平衡子树，进行相应旋转，使之平衡。 插入节点：LL型，向右旋转。RR型，向左旋转。RL型，先右转，再左转。LR型，先左转，再右转。

21、什么是哈夫曼树？哈夫曼树的作用是什么？ 哈夫曼树：带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积，带权路径长度WPL最小的二叉树称作哈夫曼树。 构造过程：把带有权值的叶子节点按照从小到大的顺序排列成一个有序序列，取出前两个最小权值的节点作为一个新节点的两个子节点，左孩子一般比右孩子小，新节点权值为两个叶子的和，将新节点插入刚才有序序列适当位置，重新选出头两个最小的，重复上面过程。 哈夫曼编码：为了解决当年远距离电报的数据传输的最优化问题，发明了哈夫曼编码，比如多英文文章传输，假设每个字母固定用一个二进制串表示，文章很长那传送的串会非常长。但英文字母每个字母出现的频率是不一样的，所以可以根据字母频率设定权值，用哈夫曼树来规划它们，构造哈夫曼树以后，把左分支用0表示，右分支用1表示，然后从根到叶子所经过的路径的数字用来编码，当双方约定好同样的哈夫曼树后，发送信息的时候能明显减少串长度。

图的应用 22、什么是有环图，连通图，强连通图？ 连通图：无向图任意两点都是连通的，图中极大连通子图（极大子图还是连通的）成为连通分量。 强连通图：有向图从vi到vj和从vj到vi都存在路径称为强连通图，有向图中极大连通子图称作强连通分量。 连通图的生成树：是一个极小连通子图，含有图中全部n个顶点，但只有足以构成一棵树的n-1条边，少于是非连通图，多余必定构成环。 有向树：有向图中一顶点入度为0，其余入度为1 第一个顶点到最后一个顶点相同的路径称为环或回路。序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单环。

操作系统概述 35、操作系统用到了那些数据结构？举例说明 进程调度后备队列，先进先出算法 短进程优先算法用了堆 动态分区分配，首次适应算法。在此算法中，空闲区链按起始地址递增顺序排列，在进行内存分配时，从链首开始顺序查找，直到找到一个能满足其大小要求的空闲区为止。循环首次适应算，循环链表。 目前广泛流行公用缓冲池，池中的缓冲区可供多个进程共享。它把相同类型的缓冲区链成一个队列 索引顺序文件：记录分组，索引表中为每组中的第一个记录建立一个索引项，组与组之间关键字必须有序，组中关键字可以无序。通过索引表找到所在组。 散列文件：没有 顺序特征。 文件分配磁盘块方式：链接分配，索引分配。 系统调用的过程？操作系统的组成？ 内核提供一系列具备预定功能的多内核函数，通过一组称为系统调用（system call)的接口呈现给用户。系统调用把应用程序的请求传给内核，调用相应的的内核函数完成所需的处理，将处理结果返回给应用程序。 系统调用通常包括：进程控制、文件系统控制、内存管理、网络管理，进程通信等。 基本功能：处理机管理，处理器的分配和运行实施有效的管理，如进程控制，同步，通信，调度。存储器管理，对内存分配、保护、扩充。设备管理，对计算机系统内的所有设备实施有效管理，比如设备分配，缓冲和虚拟，设备传输控制，设备独立性。文件管理，有效的支持文件的存储、检索和修改等操作，解决文件的共享、保护问题，比如文件存储空间管理、目录管理、文件操作管理。用户接口，方便用户使用操作系统，通常有命令接口，程序接口，图形接口。

36、什么是微内核？ 什么是shell？ 操作系统：操作系统是控制和管理整个计算机系统硬件和软件资源，并合理组织调度计算机的工作和资源分配。进程管理 存储管理 设备管理 文件管理 微内核：操作系统的一种体系结构，将最基本的功能保留在内核，基于客户服务器模式的微内核结构，将操作系统划分两大部分，微内核和服务器，把操作系统绝大部分功能都放在服务器中实现，交互借助于微内核通信。优点：每个服务进程允许在独立用户进程中，即每个服务器失败不会引起系统其他服务器崩溃，可靠性好。还具有良好的灵活性，可以方便增删服务功能，便于维护修改服务器代码不会影响其他部分，适合分布式处理的计算环境。缺点：效率不高，所有用户进程都要通过微内核相互通信。 Shell：编程人员通过系统调用，api接口来使用操作系统提供的功能，普通用户不编程，所以操作系统给普通用户提供一个shell与用户交互，shell就是覆盖在操作系统上的一个用户界面，可以是图形的比如window，也可以是文本，比如linux，用户可以输入命令操作系统，不是进行直接系统调用。

进程管理 37、作业与进程的区别 一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成的某项任务，是要求计算机所做工作的集合。

38、进程和程序有什么区别？ 进程是程序及其数据在计算机上的一次运行活动，是一个动态概念，而程序是一组有序的指令集合，是一种静态的概念 进程是程序的一次执行过程它是动态地创建和消亡的具有一定的生命周期是暂时存在的，程序则是一组代码集合，是永久存在可长期保存的。 进程可以创建进程，程序不能创建新程序。

39、进程和线程有什么区别？什么是进程树？ 进程是资源拥有的基本单位，线程是独立调度的基本单位，而不用有系统资源，当可访问其隶属进程的系统资源，不仅进程之间可以并发，同一进程内的多个线程也能，进一步提高了并发度，由于创建和撤销进程系统都要为之分配或回收资源，保存当前环境等开销远大于创建或撤销线程。 进程树是一个形象化的比喻，比如一个进程启动了一个程序，而启动的这个进程就是原来那个进程的子进程，形成的一种树形的结构。

40、简述进程的状态与转换 新建完进程分配了必要资源，进入就绪状态，这时只需要得到处理就进程就能运行，进入运行状态后，需要等待某个资源进入阻塞状态，资源到位了进入就绪队列等待处理机。运行完事进入终止状态，资源回收。

41、进程间的通信有几种方式？ 共享存储：在通信进程之间存在一块可直接访问的共享空间，通过对这段空间的读写实现进程之间的信息交换，在对共享空间进行写/读操作时，需要使用同步互斥工具。 消息传递：数据交换是以格式化的消息为但单位，操作系统提供的消息传递方式，有直接通信方式和间接通信方式。 管道通信：管道就是连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，向管道提供输入的发送进程以字符流形式将大量数据送入管道，接受管道输出的进程，则从管道中接受数据，为了协调双方通信，管道机制需提供互斥、同步和确定对方的存在。

42、什么叫饥饿？ 短作业优先算法时候，长作业一直得不到处理机

43、进程的调度算法有哪些?分别简述 先来先服务，缺点短作业可能等待很长时间，平均响应时间很慢。 短任务优先算法：平均响应时间最优，分为抢占和非抢占，容易饿死长任务。 高响应比：优先权=等待时间+要求服务时间/要求服务时间既照顾了短作业，又不会使长作业得不到服务。 分时（时间片）：选择适当时间片，过大退化成FCFS过小切换所用时间多。 优先级：静态优先级不变，动态优先级，执行了降低优先级。 多级反馈队列调度算法：设置多个就绪队列，并为各个队列赋予不同优先级，第一个队列优先级最高，依次降低，各队列中进程内时间片的大小也不相同，最高优先级的时间片最小，依次升高。当一个进程进入内存后，先进入优先级最高队尾，等待调度，当运行时候如果在该时间片结束，便可撤离了，没完成就进入第二个队列末尾等待，依次进行，如果在最后一个队列执行一次还没完成，就在这队列继续排队。仅当第一队列空闲时候，调度程序才会调度第二队中进程运行，优先级高的队列空闲，优先级低才会被调度，如果优先级低的队列正在执行，优先级高队列有进程进入，则调度程序把正在执行的进程放在这队的末尾，优先级高的先执行。 实时最早截止时间优先（EDF）：开始截止时间确定优先级。 最低松弛度优先（LLF）：根据任务紧急程度来确定优先级。 44、什么是软实时，什么是硬实时？ 硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统不能实现它的预期目标。 软实时系统的时限是一个柔性灵活的，它可以容忍偶然的超时错误。失败造成的后果并不严重，仅仅是轻微的降低了系统的吞吐量。

45、什么是PV操作？简述PV操作要点及注意事项。 信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号量的变量及对它进行的两个原语操作p操作和v操作，这两个操作是不可中断的程序段，称为原语。 P原语操作的动作是：信号量减1；若减1后仍大于或等于零，则进程继续执行；若减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中V原语操作的动作是：信号量加1；若相加结果大于零，则进程继续执行；若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程。 信号量必须成对使用。且在P,V愿语执行期间不允许有中断的发生。P,V原语不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。同步时候信号量初始为0，互斥时候为1。

46、什么是死锁？有什么解决办法？ 死锁：多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。原因：是资源的争夺，或进程推进顺序非法。 必要条件：资源为临界资源、进程所获得资源在用完之前不可强行夺走，只能主动释放，进程已经保持了至少一个资源，但有提出了新的资源请求，但该资源以被占用了，循环等待条件，存在一种进程资源的循环等待链。 预防死锁：这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。 避免死锁：该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 检测死锁：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。 解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。

内存管理 47、简述内存的连续分配管理方式 固定分区分配，划分若干个固定大小区域，建立分区说明表，容易产生内部碎片。 动态分区分配，又称可变分区分配，是一种动态划分内存的分区方法。不预先划分，而是在进程装入内存时候，根据进程大小动态的建立分区。并使分区大小正好适合进程的需要。因此系统中分区的大小数目是可变的。会产生外部碎片。可用紧凑技术解决，不时的动态整理。 首次适应，空闲分区以地址递增次序链接，找到一个能满足要求的分区。 最佳适应：分区按容量递增形成分区链。 最坏适应：分区按容量递减形式分区链。 临近适应：循环首次适应，从上次查找结束位置开始继续查找。 48、程序装入和链接。 编译：将源代码编译成若干个目标模块 链接：链接程序将编译后形成的目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。链接分为静态，装入时动态，运行时动态 装入：由装入程序装入模块装入内存中运行。分为绝对装入，可重定位，静态重定位一次性完成，动态重定位。 49、常用内存保护方法有哪些？ 页表机制里，页表寄存器中有页表起始地址，和页表长度，比较页号和页表长度如果大于页表长度则产生越界中断。

50、什么是交换技术？什么是覆盖技术？及其区别 覆盖：把一个用户空间分成一个固定分区和若干个覆盖区，活跃部分放入固定区，其余部分先放即将访问的进覆盖区，其他需要时候在调入覆盖原有的段。 交换：把处于等待状态的程序从内存移到外存，腾出空间这叫换出，然后把准备好竞争CPU运行的程序从外存调入内存，这叫换入。

51、什么是拼接技术？ 就是紧凑技术：动态分区分配回收时候，将其余空闲分区合并为一个大的空闲分区。

52、简述内存的非连续非配管理方式（段、页） 非连续分配根据分区大小是否固定分为，分页存储管理和分段存储管理。分页存储管理方式又根据是否要把作业的所有页面都装入内存分为基本分页存储方式，和请求分页存储方式 基本分页存储管理方式：把主存空间分为大小相等且固定的块，相对较小，作为主存的基本单位，每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。与固定分区技术的区别是块的大小相对于分区较多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行，只会在最后一个不完整块产生内部碎片。 进程在执行过程中需要申请主存空间，就是要为每个页面分配主存中的可用叶框，这就产生了页和叶匡的一一对应。页面大小要适中，太小页表长，页内碎片增大，降低内存的利用率。一般每页大小4KB，所以页内偏移量12位，页号20位，地址最多2的20此方页。 页表：为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程创建一张页表，记录页面在内存中对应的物理块号，页表一般在内存中。页表作用是实现从页号到物理块号的映射。页表寄存器PTR存放页表在内存地址，和页表长度。进程未执行放在进程控制块中，执行存入。 TLB快表：若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存，一次是访问页表，确定物理地址，一次是取数据和指令。这显然比通常执行指令慢一倍，所以增加一个具有并行查找能力的高速缓存存储器–快表。又称联想寄存器，用来存放当前访问的若干表项，比较的时候是将页与块表中的所有页号同时进行比较，找到取出，如果没有则访问主存中页表，读出后同时放入快表中，以便后面可能再次访问，但若块表以满则按着一定算法对旧页表进行替换。 页表占空间太大可以用两级页表，进程执行只需调入最高级页表就可以，进程的页表和进程本身的页面，可以再后面的执行中再调入。 分段管理：分页是从计算机角度考虑设计，提高内存利用率，而且通过硬件机制，对用户完全透明，分段管理方式的提出考虑了用户程序员以满足编程方便，信息保护和共享等多方面需求。段内要求连续，段间不要求连续，作业地址空间是二维的。最大段长64KB，段号为16位，段内偏移量为16位。段式系统中段号和段内偏移量必须由用户显示提供。段表映射了逻辑空间和内存空间。段表项记录了起址和段长。分段系统共享是通过两个作业的段表中相应表指向被共享的段的同一个物理副本实现的。不能修改的代码称为纯代码和可重入代码这样代码不能修改数据是可以共享的。 段页式：将两种存储管理方法结合起来，形成了段页式存储管理方式。作业地址空间首先分成若干逻辑段，每段都有自己段号，然后每一段分成若干大小固定的页。对内存空间管理仍然和分页一样。逻辑地址三部分，段号，页号，偏移量。段表项报考段号，页表长度，页表起始地址。页表项包括页号和块号。 53、简述虚拟存储器的原理 传统存储管理方式一次性，驻留性不换出。局部性原理，空间局部性，一旦程序访问了某个存储单元，在不久之后，其附近的存储单元页将被访问，指令通常说顺序存放，顺序执行的，数据也一般以数组等方式簇聚存储的。时间局部性，某一指令一旦执行，不久以后该指令可能再次执行，数据被访问过，不久以后数据有可能再次被访问。原因是程序有循环。基于局部性原理，在程序装入时候，可以将程序的一部分装入内存，其余部分留在外存，就可以启动程序执行，在程序执行过程中，访问的信息不存在内存，由系统将所需的部分调入内存然后继续执行程序，另一方面将暂时不使用的内存换出道外存。从而腾出空间存放将要掉入内存的信息，这样系统好像为用户提供了一个比实际内存大的多的存储器，称为虚拟存储器。 实现：请求分页，请求分段，请求段页式存储管理 硬件支持：内存外存，也表机制，中断机构，地址变换机构。 请求分页管理方式：建立在基本分页管理方式，为了支持虚拟存储器功能，增加了请求调页和页面置换功能。每当要访问的页面不在内存时候，便产生了一个缺页中断，请求操作系统将所缺的页面调入内存，此时将缺页进程阻塞，调完唤醒，内存有空闲块则分配，将要掉入的页装入该块，并修改页表中相应表项，若此时没有空闲块，则按着一定算法置换。修改过还写回，与一般中断比可以再指令执行期间产生和处理中断信号。 54、简述各种页面置换算法（LRU、CLOCK）LRU是如何实现的？ 最佳，以后不会使用的淘汰。不可能实现。 先进先出：优先淘汰最早进入内存的页面。 最近最久未使用LRU置换算法：淘汰最近最长时间未访问过的页面，该算法未每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时候选择现有页面中值最大的。需要栈支持。可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。 Clock算法：LRU接近最佳置换算法，性能好但是开销大，FIFO简单但是性能差，CLOCK算法比较小的开销接近LRU的性能，最近未用（NRU），给每一帧关联一个附加位，称为使用位，当某一页首次装入主存，该帧使用位设置1，随后再被访问页被置1，替换算法把候选帧集合看成一个循环缓冲区，并且有一个指针与之关联， 当某一页被替换时该指针被设置成指向缓冲区的下一帧。当需要替换一页时候，操作系统扫描缓冲区，以查找使用位为0的一帧，每当遇到为1的改0，如果所有都为0则替换第一个，所有都为1则全改0一圈回来后替换第一个，由于循环检查各页情况，所以CLOCK。 优化：加一个修改位，改了的为1， 系统先找没访问过页没修改过的，不对使用位修改，找不到的找没访问，改了的，这次过去使用位改0，找不到，回原点从新来，这回一定能找到了。由于修改的页面需要写回。这样节省时间。

55、什么是TLB（快表）？有什么用？原理？ TLB块表：若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存，一次是访问页表，确定物理地址，一次是取数据和指令。这显然比通常执行指令慢一倍，所以增加一个具有并行查找能力的高速缓存存储器–快表。又称联想寄存器，用来存放当前访问的若干表项，比较的时候是将页与块表中的所有页号同时进行比较，找到取出，如果没有则访问主存中页表，读出后同时放入快表中，以便后面可能再次访问，但若块表以满则按着一定算法对旧页表进行替换。

IO管理和文件 56、什么是设备无关性？ 应用程序独立于具体使用的物理设备。为了实现设备独立性，在程序中使用逻辑设备名来请求，使用某类设备，在系统中设置逻辑设备表。用于将逻辑设备名映射为物理设备名。这样多个进程可以分时使用同一个设备了。

57、磁盘调度算法有哪些？ 先来先服务：仅适用于请求磁盘IO的进程数目较少的场合最简单的一种磁盘调度算法，根据进程请求访问磁盘的先后次序进行调度。优点：简单，公平，每一个请求的进程都能够得到处理，不会出现长期得不到处理的进程。缺点：未对寻道进行优化，致使平均寻道时间可能较长。 最短寻道时间优先：该算法选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短优点：较FCFS有更好的寻道性能缺点：可能导致老进程饥饿，可能会出现磁臂黏着 扫描算法：也叫电梯调度算法在SSTF算法基础上优化而得到，可以防止老进程饥饿。该算法不仅考虑到被访问磁道和当前磁头之间的距离，更优先考虑的是磁头当前的移动方向。(应该选取同方向且距离最近的磁道访问。)优点：磁头双向移动，不会产生饥饿，平均寻道时间短。缺点：可能会出现磁臂黏着 循环扫描算法：为了减少延迟，CSCAN规定磁头单向移动，当从里到最外后，磁头立即返回到最里的欲访问磁道，然后继续向外。优点：磁头单向移动，不会产生饥饿，平均寻道时间短。 58、文件共享的方式又哪些？ 硬连接：基于索引节点的共享方式，诸如文件的物理地址以及其他的文件属性等信息，不再是放在目录项中，而是放在索引节点中。文件目录只设置文件名以及指向相应索引节点的指针，索引节点还应有一个链接计数。 软连接：符号链为让B共享用户A的一个共享文件F，可以由系统创建一个LINK类型的新文件也取名为F，并将文件F写入用户B的目录中，指向这个链接文件，其实就是快捷方式。 59、文件分配方式有哪些？ 连续分配：每个文件在磁盘上占一组连续块，支持顺序访问和直接访问，优点是简单，存取速度快。缺点是文件长度不宜动态增加。增加需大量移动。 链接分配：采取离散分配，消除外部碎片，提高了磁盘利用率，根据当前需要分配必需的盘块，当文件动态增长时，可以动态再为它分配盘块。隐式链接：每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都由指向下一个盘块的指针。显示连链接：把指针显式存放在内存中一张连接表中，该表在整个磁盘设置一张，每个表项中存放链接指针，即下一个盘块号。显著提高了检索速度，大大减少了访问磁盘的次数，由于分配给文件的所有盘块号都放在该表中，故称该表为文件分配表（FAT） 索引分配：把每个文件的所有盘块号都集中放在一起构成索引块表。为了处理大文件，可以链接多个索引块，也可以多层索引。 混合索引：把多种索引分配方式相结合的分配方式。 60、文件存储空间管理 空闲表法：与内存动态分配相似 空闲链表法：将所有空闲盘区拉成一条空闲链。 位示图：磁盘上每个盘块都有一个二进制位与之对应

61、简述缓冲池原理 缓冲池：由多个系统公用的缓冲区组成，缓冲区按其使用情况可以形成三个队列，空缓冲队列、装满输入数据的缓冲队列（输入队列）和装满输出数据的队列（输出队列），还有四个缓冲区：用于收容输入数据缓冲区、用于提取输入数据的工作缓冲区、用于收容输出数据的工作缓冲区以及用于提取输出数据的工作缓冲区。 当输入进程需要输入数据时，从空缓冲队列队首摘下一个空缓冲区，把它作为收容输入工作缓冲区，然后把输入数据输入其中，装满后再挂到输入队列末尾。当计算机进程要输入数据时，便从输入队列取得一个空缓冲区作为提取输入工作缓冲区，计算进程从中提取数据，数据用完后再将它挂到空缓冲队列尾。当计算机进程需要输入数据时，便从空缓冲队列的队首取得空缓冲区，作为收容输出工作缓冲区，当其中装满输出数据后，再将它挂到输出队列队尾。当要输出时，有输出进程从输出队列中取得一个装满输出数据的缓冲区，作为提取输出工作缓冲区，提取完挂到空缓冲队列队尾。

计算机网络概述 62、三网融合，指哪三网？ 电信网络：主要业务是电话，传真等。 有线电视网络：单向电视节目传输网络。 计算机网络：我们现在用的很多的局域网和Internet等。

63、组成网络协议的三个要素 语法：用户数据与控制信息的结构和格式 语义：需要发出何种控制信息，完成何种动作以，解释比特流每一部分的意义 时序：对事件实现顺序的详细说明

64、OSI参考模型和TCP/IP模型有几层，简述各层原理及作用，TCP/IP有哪些协议？ OSI物理层，透明的传输比特流。 数据链路层，两个相邻节点间的链路上，透明地传送帧中的数据，数据传送时，数据链路层将网络层交下来的IP数据包组成帧，每个帧包括数据和必要控制信息，以使得接收端能够知道从哪开始和结束，进行硬件地址寻址进行硬件地址寻址，还使接收端能检测到所收到的帧中有无差错，有就丢失。 网络层，为分组交换网上的不同主机提供通信服务，把运输层产生的报文段或用户数据报封装成分组，关键问题是逻辑地址寻址，实现不同网络之间的路径选择。 运输层，运输层负责端到端的通信，对一个主机同时运行的多个进程提供服务，这是复用，运输层把收到的信息分别交付给上面应用层相应进程，为高层提供可靠透明有效的数据传输服务，实现进程到进程的传输管理，差错控制，流量控制等。 会话层（Session Layer）：建立、管理、终止会话。（在五层模型里面已经合并到了应用层） 表示层（Presentation Layer）：数据的表示、安全、压缩。（在五层模型里面已经合并到了应用层） 应用层 (Application)： 网络服务与最终用户的一个接口。协议有：HTTP FTP TFTP SMTP SNMP DNS TCP/IP协议不是TCP和IP这两个协议的合称，而是指因特网整个TCP/IP协议族。TFTP，HTTP，SNMP，FTP，SMTP，DNS，Telnet ，TCP，UDPIP，ICMP，OSPF，EIGRP，IGMP,RIP，PPP，MTU，ARP，RARP

65、计算机网络通信过程，什么是同步通信和异步通信？ 同步通信：同步通信是一种比特同步通信技术，要求发收双方具有同频同相的同步时钟信号，只需在传送报文的最前面附加特定的同步字符，使发收双方建立同步，此后便在同步时钟的控制下逐位发送/接收。 异步通信：相对于同步通信，异步通信在发送字符时，所发送的字符之间的时隙可以是任意的。但是接收端必须时刻做好接收的准备，发送端可以在任意时刻开始发送字符，因此必须在每一个字符的开始和结束的地方加上标志，即加上开始位和停止位，以便使接收端能够正确地将每一个字符接收下来。

66、各设备（集线器、交换机、路由器）在那层工作，分别是什么？ 中继器：中继器从一个网络电缆里接收信号， 放大它们，将其送入下一个电缆。 集线器：相当于多接口中继器，可将各节点连接成一个局域网，但任何时刻都只能有一个节点通过公共信道发送数据。逻辑上仍然是一个总线网，使用CSMA/CD协议。不能隔离碰撞域。不能连接不同技术和速率的网络。 网桥：相比较而言，网桥对从关卡上传下来的信息更敏锐一些。网桥是一种对帧进行转发的技术，根据MAC分区块，可隔离碰撞。网桥将网络的多个网段在数据链路层连接起来。 交换机：工作在数据链路层相当于多端口的网桥，允许端口之间建立多个并发连接，实现多个节点之间并发传输，每个端口所占带宽不会因为端口数量增加而减少 路由器：使用物理层或数据链路层的中继系统时只是把一个网络扩大了，而从网络层的角度看，它仍然是通一个网络，一般并不称之为网络互连，网络互联通常是指用路由器进行网络互联和路由选择。

67、网络按地理位置划分为几种？分别介绍 广域网WAN，城域网MAN，局域网LAN，个人区域网WPAN

物理层 68、什么是基带信号？什么是宽带信号？什么是模拟信号？什么是数字信号？ 基带信号：将数字信号1或0直接用不同的电压来表示，然后送到电路上去传输。 宽带信号：将基带信号调制后形成的频分复用模拟信号。由于基带信号经过调制，其频谱移动到较高的频率处。由于每一路基带信号的频谱都被移动到不同的频段上，因此合在一起后并不会互相干扰，这样可以在一条电缆中传送多路的数字信号，因而提高了线路的利用率。 模拟信号：连续信号，例如：话音信号和广播信号 数字信号：离散信号，二进制代码0、1组成的信号

69、简述电路交换、报文交换、分组交换，比较优缺点 电路交换：源节点和目的节点之间建立一专用通路，用于传送数据，包括建立连接，传输数据，断开连接，优点：延迟小。缺点：利用率低 报文交换：将数据加上源地址，目的地址等信息，封装成报文，存储转发每个报文可以单独选择到达目的节点的路径，优点利用率较好，缺点是增加了资源开销，和缓冲延迟，缓冲难以管理，因为报文大小不确定。 分组转发：将数据分成较短的固定长度的数据块，每个块上加上目的地址，源地址等辅助信息组成分组，以存储转发的方式传输，除具备报文的优点，还有缓冲易于管理，平均延迟更小。 70、分组交换的方式有哪些？ 数据报方式：不需要建立连接，发送方可以随时发，接收方也可以随时接受，网络尽最大努力交付传输，不保证可靠性，分组中有发送端和接受端完整地址，以便独立传输。 虚电路方式：将数据报方式与电路交换给结合起来，建立逻辑上的虚电路。与物理电路不同，节点可以共用，不时真实建立物理连接了。 71、什么是信宿和信源？ 信源：在通信中，向另一部件(信宿)发出信息的部件。 信宿：从另一部件(信源)接收信息的部件 72、简述单工，半双工，全双工 单工：信息在两点之间只能单方向发送的工作方式。 半双工：信息在两点之间能够在两个方向上进行发送，但不能同时发送的工作方式。 全双工：通信允许数据在两个方向上同时传输 73、异步通信的信源和信宿没有时钟同步信号，怎么解决这个问题？ 采用曼彻斯特或者差分曼彻斯特。简述这两个的原理

数据链路层 74、比较一下BSC协议和HDLC协议 BSC是面向字符的同步控制协议而HDLC是面向比特的同步控制协议，BSC使用字符填充的首尾定界符法。该法用一些特定的字符来定界一帧的起始与终止.协议依赖特定字符集，HDLC使用比特填充的首尾定界符法。该法以一组特定的比特模式(如01111110)来标志一帧的起始与终止。协议不依赖特定字符集。 由于BSC是一个半双工协议，它的链路传输效率很低。HDLC支持全双工通信，传输效率高。

75、数据链路层的作用 链路管理：链路的建立、维持、释放。 帧定界：又称帧同步，指接收方能从接收到的比特流中准确提取数据帧。 流量控制：发送与接收数据同步 差错控制：采用编码技术(如CRC)来检测或纠正传输中的错误。其中前向纠错具有检测与纠错的功能、开销大。差错检测只检错，不纠错，并通知发送方重传出错帧。 进行硬件地址寻址 进行硬件地址寻址

76、列举数据链路层的协议，至少两个 HDLC：是一个在同步网上传输数据、面向比特的数据链路层协议，该协议不依赖于任何一种字符编码集，数据报文可透明传输，用于实现透明传输的0比特填充法易于硬件实现，全双工通信，较高的数据链路传输效率。 PPP：是使用串行线路通信的面向字节的协议，协议应用在直接连接的两个节点的链路上，主要用来通过拨号或专线方式建立点对点连接发送数据，因特网用户连接到ISP就是使用PPP协议。PPP协议功能帧定界，以便接受端能找到帧的开始和结束位置，在同一条物理链路上支持多种网络层的协议，差错检测。Ppp协议将一个IP数据报封装成帧，既支持异步也支持同步面向比特流，还有一个用来建立、配置和测试数据链路连接的链路控制协议LCP，和一套网络控制协议NCP，其中的每一个协议支持不用的网络层协议。

77、什么是流量控制？在那几层有流量控制？ 数据链路层：流量控制设计对链路上的帧的发送速率的控制，以使接收方有足够的缓冲空间来接受每一个帧。由接收方控制发送方的速率，常见方式有停止等待协议，发送方每发送一帧，都要等待接受对方应答，之后才能发送下一帧，接收方每接受一帧都要反馈一个应答信号，如果没有应答一直等待，效率很低。 滑动窗口，在任意时刻发送方都维持一组连续连续的允许发送的帧的序号，称为发送窗口，同时接收方页维持一组连续允许接受的帧序号，称为接受窗口，发送窗口用来对发送方进行流量控制，发送窗口大小代表还没有收到对方确认情况下，发送方最多还可以发送多少数据帧，接受窗口为了控制可以接收哪些数据帧而不可以接收哪些帧。当接收方收到的数据帧是接受窗口内的序号才收。不是丢弃。发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口都没确认就停止发送，直到接收方发送来的确认帧使窗口移动才可以发送。数据链路层滑动窗口大小是固定的。 自动重传请求ARQ有三种： 单帧滑动窗口（停止等待协议），可保证有序。后两种后退N帧ARQ和选择重传ARQ是滑动窗口与请求重发的结合。由于窗口尺寸足够大，帧可以再线路上连续流动，又称连续ARQ。 后退N帧ARQ：接收窗口等于1。允许发送方可以连续发送信息帧，但是，一旦某帧发生错误，必须重新发送该帧及其后的n帧。这种方式提高了信道的利用率，但允许已发送有待于确认的帧越多，可能要退回来重发的帧也越多。 选择重传ARQ：当发送方接收到接收方的状态报告指示报文出错，发送方只发送传送发生错误的报文。 数据链路层可靠传输只有超时重传。传输层TCP连接中传送的数据流中每一个字节都编上一个序号，确认号是期望收到对方的下一个报文段的数据的第一个字节的序号。超时重传和冗余确认（ACK），可以缩短时间发送方收到同一个报文段的三个冗余确认，就重传，也成为快重传。 传输层TCP流量控制：接收方根据自己接受缓存的大小，动态调整发送方的发送窗口大小，这就是接受窗口rwnd，来限制发送方向网络注入报文的速率，同时发送方根据其对当前