《软件工程—复试总结分析.doc》由会员分享，可在线阅读，更多相关《软件工程—复试总结分析.doc（40页珍藏版）》请在三一办公上搜索。
1、软件工程复试总结一、 数据库部分数据库绪论1、 简述三层模式、两级映射，分别有什么作用？模式（逻辑模式）：是数据库中全体数据的逻辑结构和特征的描述，是数据库系统模式结构的中间层，即不涉及数据的物理存储细节，也与具体应用程序开发工具语言无关。外模式（用户模式）：是用户能看见和使用的局部数据的逻辑结构和特征描述，是与某一应用有关的数据的逻辑表示，是模式的子集，一个数据库可以有多个外模式。内模式（存储模式）：数据物理结构和存储方式的描述，是数据在数据库内部的表示方式，如存储方式是按照某个属性升序存储，什么索引等。外模式模式映像：当模式发生改变，数据库管理员对外模式模式映像作相应改变，可使外模式不变，
2、从而应用程序不用修改。保证数据与程序的逻辑独立性。模式内模式映像：当数据库的存储结构改变了，由数据库管理员对模式内模式映像作相应改变，可以保持模式不变，从而应用程序也不必改变，保证了数据与程序的物理独立性。三级模式使用户能逻辑地抽象地处理数据而不关心数据在计算机内具体表示方式与存储方式，两级映像保证了数据库系统中的数据有较高的逻辑独立性和物理独立性。2、 说出至少三种数据库类型（层次，网状，关系）并简要解释了一下层次模型：用树形结构来表示各类实体以及实体间的联系，有且只有一个节点没有双亲节点（根节点），其他的都有且只有一个双亲节点。只能能直接表示的是一对多联系。优点：效率高结构清晰，性能优于关
3、系数据库，不低于网状。缺点：现实世界很多联系都不是层次的，如节点间多对多联系，还有一个节点具有多个双亲的情况都不好表示。网状模型：对于非层次关系的联系，用层次表示非树形结构是很不直接的，网状模型可以很好的表示，它允许有一个以上的节点没有双亲，一个节点也可以有多个双亲，可以更直接地描述现实世界。优点：更直接描述现实世界，性能也较好，存取效率也较高。缺点：结构比较复杂不利于掌握，用户编程还得了解系统结构细节，加重了编程的负担。关系模型：通常来看关系就是一张规范二维表，实体还是实体间的联系都用关系来表示，对数据的检索和更新结果也是关系。优点：概念单一，用户易懂易用，而且存取路径是对用户透明的，从而有
4、更高的数据独立性和安全性，也简化程序员的工作。缺点：查询效率往往不如格式化数据模型，为了提高性能，增加开发DBMS难度。关系数据库3、 简述关系与关系模式的区别。关系实质是一张二维表，关系模式是对关系的描述，关系是关系模式在某一时刻的状态或内容。关系模式是静态的、稳定的，而关系是动态的，随时间不断变化的，因为关系操作不断更新数据库中的数据。通俗的说：关系是一张二维表，关系模式是表格的描述（表头），关系名是表名，元祖是一行，属性是列，分量一条记录中的一个列值。4、 什么是关系数据库？关系和二维表有什么区别？关系数据库，是建立在关系数据库模型基础上的数据库，借助于集合代数等概念和方法来处理数据库中
5、的数据。在关系模型中，数据结构表示为一个二维表，一个关系就是一个二维表（但不是任意一个二维表都能表示一个关系。表中的第一行通常称为属性名，表中的每一个元组和属性都是不可再分的，且元组的次序是无关紧要的。5、 关系的完整性（实体完整性、参照完整性、用户自定义）和数据库主键的约束性实体完整性：关系的主码不能取空值，如果主码由若干属性组成都不能为空。实体以主码作为唯一性标识。参照完整性：一个关系中的外码，或者取空值（若属性组全为空），或者等于它参照的那个关系的主码值。用户自定义完整性：针对具体关系数据库的约束。数据库语言SQL6、 什么是DDL、DML、DCL？（数据库语言有哪几种？）数据定义语言（
6、DDL）：Create、Drop、Alter数据操纵语言（DML）：Insert、Update、Delete数据控制语言（DCL）：Grant、Revoke数据查询语言：Select7、 什么是视图，有什么作用？在数据库哪层？视图：是从一个或几个基本表导出的表，是一个虚表，数据库只存放视图的定义，不存放视图对应的数据，数据仍放在原来的基本表，基本表数据改变，通过视图查询也改变了，作用：1、能够简化用户操作，使数据库看起来更简单，清晰，简化查询操作。2、更安全，机密数据不出现在不应该看到这些数据的用户视图上。3、重构数据库时候，改变视图不用修改程序，使数据具有逻辑独立性。数据库设计8、 简述数据
7、库设计的几个阶段需求分析：详细调查现实世界要处理的对象，充分了解各种需求，在此基础确定新系统的功能。概念结构设计：经常采用自顶向下需求分析，自底向上概念结构设计。对需求分析收集到的数据进行分类组织形成实体、实体的属性，确定实体之间联系，设计分E-R图。逐一设计分E-R图，最后将所有分E-R图综合成一个系统的E-R图。逻辑结构设计：一般来讲把E-R图向关系模型转换，一个实体型转换为一个关系模式。一个一对一联系可以独立也可以和任意一端合并，一个一对多联系可以独立也可以和N端对应的关系模式合并，一个多对多联系独立转换为一个关系模式。对数据模型规范化，还根据具体需求设计相应的视图。数据库物理设计：关系
8、模式存取方法的选择，比如索引、聚簇、哈希等存储方式。还应该确定数据库的存取结构，目前许多计算机有多个磁盘或磁盘阵列，因此可以将表和索引放在不同的磁盘上，在查询时磁盘驱动器并行工作，可以提高物理IO读写效率，也可以将比较大的表放在两个磁盘上，以加快存取速度。数据库的实施与维护：比如备份与恢复等待。9、 什么是E-R图E-R图：实体-联系图，在概念结构设计中，对需求分析收集到的数据进行分类组织形成实体、实体的属性，确定实体之间联系，设计E-R图。10、 分别解释1NF、2NF、3NF、BCNF、4NF范式：关系数据库中的关系是要满足一定要求的，满足不同程度的要求的为不同范式。规范化：一个低一级范式
9、关系模式通过模式分解可以转化为若干个高一级范式的关系模式的集合。1NF：满足最低要求的叫第一范式，每一个分量必须是一个不可分的数据项。2NF：消除关系中的部分函数依赖就称为第二范式，部分函数依赖就是非主属性不完全依赖于码。3NF：每一个非主属性既不部分依赖于码，也不传递依赖于码。 BCND：所有非主属性对每一个码都是完全函数依赖，没有任何属性完全依赖于非码的任何属性，就是除了码外一定不能有决定因素。数据库并发控制11、 什么是事务，并发控制是保证事务的？事务：是一系列的数据操作，这些操作要么全不做，要么全做，不可分割。运行过程中发生某种故障不能继续执行，全部回滚到开始状态。并发控制中多个用户存
10、取数据库时候可能会产生多个事务同时存取同一个数据的情况，不加控制就会破坏事务的一致性，为了保证事物的一致性所以进行并发控制。12、 ACID（事物的四个性质）A原子性：要么都做，要么都不做。C一致性：如果运行中发生故障，必须回滚。不能让数据不一致。比如两人转钱，一半坏了，不一致俩人都没有钱。I隔离性：一个事物不能被其他事物干扰。D持续性：事物一旦提交，他对数据库的改变就应该是永久的。接下来的操作和故障不应该对刚才结果有任何影响。13、 数据库中锁有什么作用？什么是只读锁、什么是只写锁？一个事物对数据加锁可以保证事物的四个特性，加锁后其他事物不能更新此数据对象，不会产生数据不一致性。写锁（排他锁
11、/ X锁）：加写锁其他事物不能在对这个数据加任何类型锁，释放之前不能读取和修改。读锁（共享锁/ S锁）：事物对数据加读锁，其他事物可以读但不可以修改，可以加读锁不能加写锁。14、 什么是触发器，有什么作用？用户定义在关系表上的一类由事件驱动的特殊过程，一旦定义了，用户对表的增、删、改操作均有数据库系统自动激活相应触发器触发器可以分为语句触发器和行级触发器，触发器动作体是一个匿名PL/SQL过程块，语句级触发器可以在语句执行前或后执行，而行级触发在触发器所影响的每一行触发一次。行触发器用户可以用new和old引用数据，语句级不能。二、 数据结构部分线性表15、 单链表的就地逆置将头结点摘下，然后
12、从第一节点开始，头插法建立单链表，直到最后一个节点为止。16、 单链表可以用什么实现？指向结构体的指针实现，结构体中有两个成员，每个节点分为数据域和指针域，除了最后一个节点，每个节点指针域都指向下一个节点的地址，最后一个节点指针域指向NULL。也可以用结构体数组模拟这种操作，数组中每个下标都对应一个数据元素和游标，游标是下一个元素在数组中的下标，把未被使用的数组元素作为备用链表，下标为0的元素游标存放备用链表第一个节点的下标。数组最后一个元素游标存放第一个有效数值元素的下标，相当于头结点作用，游标为0表示指向为空。栈和队列17、 实现一个队列的方法？为什么队列的顺序存储需要留一个空位？循环有什
13、么好处？链式存储：把链表改装一下，加尾指针作为队列的尾部可以插入节点，头指针可以删除节点，相当于出队。顺序存储：正常的顺序存储想要利用空出的空间就必须移动元素，不移动还会浪费空间，循环队列可以解决这个问题，把这段连续的地址空间，想象成逻辑上的环，所以只要有空闲空间就能使用。但是当front和rear指针相等的时候有两种情况，一种是满，一种是空，为了区分这种情况，保留一个元素空间，我们假定当rear+1与front相等队列就满了。而空的时候是rear等于front。又因为是环也可能存在rearfront的情况，所以取模操作。另外计算队列长度的时候，rearfront队长为rear-front，但
14、当rearfront队长为两段相加，所以通用公式为（rear-front+队列的总长度）%队列总长度树与二叉树18、 什么是完全二叉树？完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。19、 什么是二叉排序树，简述它的查找过程，二叉排序树的时间复杂度，遍历后得到什么样的序列？二叉排序树是一种二叉树，具有了一些独特性质，若左子树不为空，则左子树上所有节点的值均小于它的根节点的值，右子树不为空，则右子树上所有节点的值均大于它的根节点的值，而且它的左右子树也是二叉排序树。构造一个二叉排序树
15、是为了提高动态查找中插入和删除的速度。查找过程：递归查找二叉排序树中是否存在要查关键字，若成功则指针指向该数据元素的节点，返回成功，如果关键字小于树中这个节点，则去它左子树中继续查找，大于则去右子树中查找。如果树中没有要查的关键字，则指针指向访问的上一个节点，以便于插入。插入过程：如果当查找失败且指针p为空，则新建根节点，如果要插入的关键字小于p指向节点的数据，则插入到左孩子，否则右孩子。删除过程：1叶节点直接删除2只有左或右子树删了接下面3左右子树都有的，找到要删除的节点的直接前驱或后继，用这个节点替换要删除的节点，然后在删除这个节点。二叉排序树，以链接的方式存储，有在执行插入或删除操作时候
16、不用移动元素的优点，插入删除性能较好，而查找的时间复杂度取决与二叉排序树的形状。中序遍历后得到升序系列，所以也称为二叉排序树。20、 什么是平衡二叉树？为了解决二叉查找树，查找时间依赖于形状的问题，平衡二叉树就是在建立二叉排序树的时候，对它做了一定的限制，使它保持平衡，使每一个节点的左子树和右子树的高度差至多为1。具体做法：找出距离插入节点最近且平衡因子绝对值大于一的节点，把它当为根的子树叫做最小不平衡子树，进行相应旋转，使之平衡。插入节点：LL型，向右旋转。RR型，向左旋转。RL型，先右转，再左转。LR型，先左转，再右转。21、 什么是哈夫曼树？哈夫曼树的作用是什么？哈夫曼树：带权路径长度为
17、从该节点到树根之间的路径长度与节点上权的乘积，带权路径长度WPL最小的二叉树称作哈夫曼树。构造过程：把带有权值的叶子节点按照从小到大的顺序排列成一个有序序列，取出前两个最小权值的节点作为一个新节点的两个子节点，左孩子一般比右孩子小，新节点权值为两个叶子的和，将新节点插入刚才有序序列适当位置，重新选出头两个最小的，重复上面过程。哈夫曼编码：为了解决当年远距离电报的数据传输的最优化问题，发明了哈夫曼编码，比如多英文文章传输，假设每个字母固定用一个二进制串表示，文章很长那传送的串会非常长。但英文字母每个字母出现的频率是不一样的，所以可以根据字母频率设定权值，用哈夫曼树来规划它们，构造哈夫曼树以后，把
18、左分支用0表示，右分支用1表示，然后从根到叶子所经过的路径的数字用来编码，当双方约定好同样的哈夫曼树后，发送信息的时候能明显减少串长度。图的应用22、 什么是有环图，连通图，强连通图？连通图：无向图任意两点都是连通的，图中极大连通子图（极大子图还是连通的）成为连通分量。强连通图：有向图从vi到vj和从vj到vi都存在路径称为强连通图，有向图中极大连通子图称作强连通分量。连通图的生成树：是一个极小连通子图，含有图中全部n个顶点，但只有足以构成一棵树的n-1条边，少于是非连通图，多余必定构成环。有向树：有向图中一顶点入度为0，其余入度为1第一个顶点到最后一个顶点相同的路径称为环或回路。序列中顶点不
19、重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单环。23、 图的存储方式有哪些简要叙述（邻接矩阵和邻接表）？邻接矩阵：将顶点和边分别存储，顶点用一维数组存储，边用二维数组。可以根据这个二维数组获取图中的信息。比如判定两顶点是否有边，只需读取二维数组值。想知道某个顶点的度就是将这一行的值相加。求他的临界点也只需遍历一行，值为1的就是。无向图的边数组是对称的，有向图入度看列，出度看行。邻接表：对于边数较少，顶点较多的图，如果还用邻接矩阵那是对空间的极大浪费，所以用邻接表，顶点还是一维数组存储，此外数组每一个数据元素还存储指向第一个邻接点的指针，以便于
20、查找边的信息，图中每个顶点的所有邻接点构成一个链表。边表每个节点存储这个顶点在顶点表中的下标，和一个指向下一个节点的指针。想知道某顶点的度，就查找这个顶点的边中节点的个数，要判断是否存在边也只需遍历相应边表。但是对于有向图能得到每个顶点出度，为了便于确定入度可以再建立一个逆邻接表。24、 什么是DFS，遍历后形成什么？时间和空间复杂度多少？遍历节点顺序是否唯一？DFS：图的深度优先遍历，是一种递归过程，是对树的先序遍历的推广，从某个顶点开始访问，然后对尚未访问的邻接点出发，继续深度优先遍历，直到所有和初始顶点路径相通的顶点都被访问到。对于非连通图，只需对它的连通分量分别进行DFS。BFS：图的
21、广度优先遍历，类似于树的层序遍历，先初始化一辅助队列，从某个顶点开始访问，访问节点后入队，队列不为空则队列元素出队列，然后判断当前出队列顶点邻接点是否访问过，没有则访问入队，重复这一过程。25、 什么是迪杰斯特拉算法？用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。并不是一下子就求出最短路径，而是一步步求他们之间顶点的最短路径，在这个过程中都基于已经求出的最短路径的基础上。26、 什么是拓扑排序？什么图可以拓扑排序？这种用顶点表示活动，用弧来表示活动间的优先关系的有向图叫做顶点表示活动的网络简称为AOV网。通常，在AOV网中，将所有活动排列成
22、一个拓扑序列的过程叫做拓扑排序，而且每个顶点出现且只出现一次，若顶点a在序列中排在顶点b前面，则在图中不存在从顶点b到顶点a的路径。(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。27、 什么是普里姆算法？什么是克鲁斯卡尔算法？最小生成树：权值之和最小的那颗生成树称为最小生成树。普里姆算法：在所有“其一个顶点已经落在生成树上，而另一
23、个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止克鲁斯卡尔：新建一个图G，G中拥有原图中相同的节点，但没有边，将原图中所有的边按权值从小到大排序，从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中，重复，直至图G中所有的节点都在同一个连通分量中。28、 什么是关键路径？用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网。在项目管理中，关键路径最长的那个路径，决定了整个项目的最短完成时间。把关键路径上的活动成为关键活动，关键活动影响了整个工程的时间，即如果关键活动不能按时完成
24、的话，整个工程完成时间就会受到影响。事件最早发生时间：从开始顶点到下一个顶点最长路径长度。它决定了它后面的活动的最早发生时间。事件最迟发生时间：工程不推迟的前提，该事件最迟必须发生的时间，从后往前计算，边值最小的。活动的最迟发生时间：活动终点所表示事件最迟发生时间与该活动所需时间之差。 查找与排序29、 什么是折半查找？时间复杂度多少？前提条件是什么？过程如何？1.必须采用顺序存储结构 2.必须按关键字大小有序排列。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键
25、字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。时间复杂度：其算法复杂度为O（log n）30、 什么是哈希表?什么是冲突？普通的查找方法，查找关键字都需要比较，时间较长，而哈希表的方法是欲查找关键字的存储位置是由某个函数计算出来的，它把记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字对应一个存储位置。这种关系称为散列函数。查找步骤：存储数据时候存储在通过散列函数计算的地址，当查找记录时通过同样的散列函数计算地址。适用情况：一个关键字对应很多不适合，范围查找不适合，排序也不可能。冲突：
26、两个不同的关键字用散列函数计算出了相同的存储地址称为冲突。处理冲突的方法： 开放定址法：空闲地址，同义词表项可以存，非同义词也可以。 1.线性探测法：有冲突就顺序查看下一个单元，可能造成堆积。平方探测法：1方，-1方，2方，-2方。这个不堆积但是只能探测一半。再散列：用别的函数再试试。伪随机数法： 拉链法：把所有同义词存在一个线性链表中。31、 什么是折半插入排序？时间空间复杂度多少？正常插入排序插入时候，从后往前查找待插入位置，而折半插入是用折半的方法找到插入的位置，然后插入。仅仅是减少了比较元素的次数，时间复杂度仍为O（N方）32、 什么是快速排序？时间空间复杂度多少？简述基本过程一般用第
27、一个元素用作基准数，但如果是有序花费时间将是二次。一般可以使用三数取中值分割法。快速排序是对冒泡排序的改进，属于交换排序，基本思想基于分治法，在待排序表中取一个元素作为基准，通过一趟排序将待排序表划分为独立的两部分。左边部分小于基准，右边大于，这个过程称为一趟排序，而后分别递归地对两个子表重复上述过程，直到每部分内只有一个元素或为空，即所有元素放在最终位置上。当ij 时且 j对应的值大于基准跳过，碰到小于基准停下来，i小于j且i从前向后跳过小于基准的值。如果i小于j，交换然后缩小区间（i+，j- -) 继续 回到开始但前提i小于j33、 什么是堆？有什么用？什么是堆排序？堆可以看成是一棵完全二
28、叉树，如果任意一节点都小于它的子孙，称为小项堆，任意节点大于它子孙称为大顶堆。作用：可以对一组数据进行排序。大数据中找出最大的几个值，用堆比较快。堆排序：构造堆先自下往上调整，如果建立大根堆，从下往上，从右往左，每个有孩子的节点（如果从数组角度是n/2处向前到1）的关键字小于左右子树中关键字大者，则交换。反复利用上述调整堆的方法建堆，直到根节点。这样将R1.n构造为初始堆，将当前初始堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。与直接选择区别：直接选择排序中，为了从R1.n中选出关键字最小的记录，必须进行n-1次比较，然后在R2.n中选出关键字最小的记录，又需
29、要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。34、 你认为哪种排序算法最优？没有最好，只有最适合，若n较小，用简单的排序算法较好比如简单选择，直接插入，如果数据初始状态已经按关键字基本有序，则选用直接插入或冒泡较好。如果n较大应该考虑用那几个时间复杂度较好的算法，快速排序是被认为是目前基于比较的内部排序算法中最好的方法，当待排序关键字是随机分布时，快速排序的平均时间最短。如果对负辅助空间有限制则可以考虑堆排序，另
30、外求大数据的最大的几个数，堆排序最适合。如果要求排序稳定可以考虑归并排序。如果n很大，记录的关键字位数较少且可以分解，采用基数排序较好。当记录本身信息量很大，为了避免移动，可以考虑链表。三、 操作系统部分操作系统概述35、 操作系统用到了那些数据结构？举例说明进程调度后备队列，先进先出算法短进程优先算法用了堆动态分区分配，首次适应算法。在此算法中，空闲区链按起始地址递增顺序排列，在进行内存分配时，从链首开始顺序查找，直到找到一个能满足其大小要求的空闲区为止。循环首次适应算，循环链表。目前广泛流行公用缓冲池，池中的缓冲区可供多个进程共享。它把相同类型的缓冲区链成一个队列索引顺序文件：记录分组，索
31、引表中为每组中的第一个记录建立一个索引项，组与组之间关键字必须有序，组中关键字可以无序。通过索引表找到所在组。散列文件：没有顺序特征。文件分配磁盘块方式：链接分配，索引分配。系统调用的过程？操作系统的组成？内核提供一系列具备预定功能的多内核函数，通过一组称为系统调用（system call)的接口呈现给用户。系统调用把应用程序的请求传给内核，调用相应的的内核函数完成所需的处理，将处理结果返回给应用程序。系统调用通常包括：进程控制、文件系统控制、内存管理、网络管理，进程通信等。基本功能：处理机管理，处理器的分配和运行实施有效的管理，如进程控制，同步，通信，调度。存储器管理，对内存分配、保护、扩充
32、。设备管理，对计算机系统内的所有设备实施有效管理，比如设备分配，缓冲和虚拟，设备传输控制，设备独立性。文件管理，有效的支持文件的存储、检索和修改等操作，解决文件的共享、保护问题，比如文件存储空间管理、目录管理、文件操作管理。用户接口，方便用户使用操作系统，通常有命令接口，程序接口，图形接口。36、 什么是微内核？ 什么是shell？操作系统：操作系统是控制和管理整个计算机系统硬件和软件资源，并合理组织调度计算机的工作和资源分配。进程管理 存储管理 设备管理 文件管理微内核：操作系统的一种体系结构，将最基本的功能保留在内核，基于客户服务器模式的微内核结构，将操作系统划分两大部分，微内核和服务器，
33、把操作系统绝大部分功能都放在服务器中实现，交互借助于微内核通信。优点：每个服务进程允许在独立用户进程中，即每个服务器失败不会引起系统其他服务器崩溃，可靠性好。还具有良好的灵活性，可以方便增删服务功能，便于维护修改服务器代码不会影响其他部分，适合分布式处理的计算环境。缺点：效率不高，所有用户进程都要通过微内核相互通信。Shell：编程人员通过系统调用，api接口来使用操作系统提供的功能，普通用户不编程，所以操作系统给普通用户提供一个shell与用户交互，shell就是覆盖在操作系统上的一个用户界面，可以是图形的比如window，也可以是文本，比如linux，用户可以输入命令操作系统，不是进行直接
34、系统调用。进程管理37、 作业与进程的区别一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成的某项任务，是要求计算机所做工作的集合。38、 进程和程序有什么区别？进程是程序及其数据在计算机上的一次运行活动，是一个动态概念，而程序是一组有序的指令集合，是一种静态的概念进程是程序的一次执行过程它是动态地创建和消亡的具有一定的生命周期是暂时存在的，程序则是一组代码集合，是永久存在可长期保存的。进程可以创建进程，程序不能创建新程序。39、 进程和线程有什么区别？什么是进程树？进程是资源拥有的基本单位，线程是独立调度的基本单位，而不用有系统资源，当可访问其隶属进程的
35、系统资源，不仅进程之间可以并发，同一进程内的多个线程也能，进一步提高了并发度，由于创建和撤销进程系统都要为之分配或回收资源，保存当前环境等开销远大于创建或撤销线程。进程树是一个形象化的比喻，比如一个进程启动了一个程序，而启动的这个进程就是原来那个进程的子进程，形成的一种树形的结构。40、 简述进程的状态与转换新建完进程分配了必要资源，进入就绪状态，这时只需要得到处理就进程就能运行，进入运行状态后，需要等待某个资源进入阻塞状态，资源到位了进入就绪队列等待处理机。运行完事进入终止状态，资源回收。41、 进程间的通信有几种方式？共享存储：在通信进程之间存在一块可直接访问的共享空间，通过对这段空间的读
36、写实现进程之间的信息交换，在对共享空间进行写/读操作时，需要使用同步互斥工具。消息传递：数据交换是以格式化的消息为但单位，操作系统提供的消息传递方式，有直接通信方式和间接通信方式。管道通信：管道就是连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，向管道提供输入的发送进程以字符流形式将大量数据送入管道，接受管道输出的进程，则从管道中接受数据，为了协调双方通信，管道机制需提供互斥、同步和确定对方的存在。42、 什么叫饥饿？段作业优先算法时候，长作业一直得不到处理机43、 进程的调度算法有哪些?分别简述先来先服务，缺点短作业可能等待很长时间，平均响应时间很慢。短任务优先算法：平均响应时间
37、最优，分为抢占和非抢占，容易饿死长任务。高响应比：优先权=等待时间+要求服务时间/要求服务时间既照顾了短作业，又不会使长作业得不到服务。分时（时间片）：选择适当时间片，过大退化成FCFS过小切换所用时间多。优先级：静态优先级不变，动态优先级，执行了降低优先级。多级反馈队列调度算法：设置多个就绪队列，并为各个队列赋予不同优先级，第一个队列优先级最高，依次降低，各队列中进程内时间片的大小也不相同，最高优先级的时间片最小，依次升高。当一个进程进入内存后，先进入优先级最高队尾，等待调度，当运行时候如果在该时间片结束，便可撤离了，没完成就进入第二个队列末尾等待，依次进行，如果在最后一个队列执行一次还没完
38、成，就在这队列继续排队。仅当第一队列空闲时候，调度程序才会调度第二队中进程运行，优先级高的队列空闲，优先级低才会被调度，如果优先级低的队列正在执行，优先级高队列有进程进入，则调度程序把正在执行的进程放在这队的末尾，优先级高的先执行。实时最早截止时间优先（EDF）：开始截止时间确定优先级。最低松弛度优先（LLF）：根据任务紧急程度来确定优先级。44、 什么是软实时，什么是硬实时？硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统不能实现它的预期目标。 软实时系统的时限是一个柔性灵活的，它可以容忍偶然的超时错误。失败造成的后果并
39、不严重，仅仅是轻微的降低了系统的吞吐量。45、 什么是PV操作？简述PV操作要点及注意事项。信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号量的变量及对它进行的两个原语操作p操作和v操作，这两个操作是不可中断的程序段，称为原语。P原语操作的动作是：信号量减1；若减1后仍大于或等于零，则进程继续执行；若减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中V原语操作的动作是：信号量加1；若相加结果大于零，则进程继续执行；若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程。信号量必须成对使用。且在P,V愿语执行期间不允许有中断的发生。P,V原语不但可以解决进程管理当
40、中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。同步时候信号量初始为0，互斥时候为1。46、 什么是死锁？有什么解决办法？死锁：多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。原因：是资源的争夺，或进程推进顺序非法。必要条件：资源为临界资源、进程所获得资源在用完之前不可强行夺走，只能主动释放，进程已经保持了至少一个资源，但有提出了新的资源请求，但该资源以被占用了，循环等待条件，存在一种进程资源的循环等待链。预防死锁：这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。但是
41、由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。避免死锁：该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。检测死锁：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死
42、锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。内存管理47、 简述内存的连续分配管理方式固定分区分配，划分若干个固定大小区域，建立分区说明表，容易产生内部碎片。动态分区分配，又称可变分区分配，是一种动态划分内存的分区方法。不预先划分，而是在进程装入内存时候，根据进程大小动态的建立分区。并使分区大小正好适合进程的需要。因此系统中分区的大小数目是可变的。会产生外部碎片。可用紧凑技术解决，不时的动态整理。首次适应，空闲分区以地址递增次序链接，找到一个能满足要求的分区。最佳适应：分区按容量递增形成分区链。最
43、坏适应：分区按容量递减形式分区链。临近适应：循环首次适应，从上次查找结束位置开始继续查找。48、 程序装入和链接。编译：将源代码编译成若干个目标模块链接：链接程序将编译后形成的目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。链接分为静态，装入时动态，运行时动态装入：由装入程序装入模块装入内存中运行。分为绝对装入，可重定位，静态重定位一次性完成，动态重定位。49、 常用内存保护方法有哪些？页表机制里，页表寄存器中有页表起始地址，和页表长度，比较页号和页表长度如果大于页表长度则产生越界中断。50、 什么是交换技术？什么是覆盖技术？及其区别覆盖：把一个用户空间分成一个固定分区和若干个覆盖
44、区，活跃部分放入固定区，其余部分先放即将访问的进覆盖区，其他需要时候在调入覆盖原有的段。交换：把处于等待状态的程序从内存移到外存，腾出空间这叫换出，然后把准备好竞争CPU运行的程序从外存调入内存，这叫换入。51、 什么是拼接技术？就是紧凑技术：动态分区分配回收时候，将其余空闲分区合并为一个大的空闲分区。52、 简述内存的非连续非配管理方式（段、页）非连续分配根据分区大小是否固定分为，分页存储管理和分段存储管理。分页存储管理方式又根据是否要把作业的所有页面都装入内存分为基本分页存储方式，和请求分页存储方式基本分页存储管理方式：把主存空间分为大小相等且固定的块，相对较小，作为主存的基本单位，每个进
45、程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。与固定分区技术的区别是块的大小相对于分区较多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行，只会在最后一个不完整块产生内部碎片。进程在执行过程中需要申请主存空间，就是要为每个页面分配主存中的可用叶框，这就产生了页和叶匡的一一对应。页面大小要适中，太小页表长，页内碎片增大，降低内存的利用率。一般每页大小4KB，所以页内偏移量12位，页号20位，地址最多2的20此方页。页表：为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程创建一张页表，记录页面在内存中对应的物理块号，页表一般在内存中。页表作用
46、是实现从页号到物理块号的映射。页表寄存器PTR存放页表在内存地址，和页表长度。进程未执行放在进程控制块中，执行存入。TLB快表：若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存，一次是访问页表，确定物理地址，一次是取数据和指令。这显然比通常执行指令慢一倍，所以增加一个具有并行查找能力的高速缓存存储器-快表。又称联想寄存器，用来存放当前访问的若干表项，比较的时候是将页与块表中的所有页号同时进行比较，找到取出，如果没有则访问主存中页表，读出后同时放入快表中，以便后面可能再次访问，但若块表以满则按着一定算法对旧页表进行替换。页表占空间太大可以用两级页表，进程执行只需调入最高级页表就可
47、以，进程的页表和进程本身的页面，可以再后面的执行中再调入。分段管理：分页是从计算机角度考虑设计，提高内存利用率，而且通过硬件机制，对用户完全透明，分段管理方式的提出考虑了用户程序员以满足编程方便，信息保护和共享等多方面需求。段内要求连续，段间不要求连续，作业地址空间是二维的。最大段长64KB，段号为16位，段内偏移量为16位。段式系统中段号和段内偏移量必须由用户显示提供。段表映射了逻辑空间和内存空间。段表项记录了起址和段长。分段系统共享是通过两个作业的段表中相应表指向被共享的段的同一个物理副本实现的。不能修改的代码称为纯代码和可重入代码这样代码不能修改数据是可以共享的。段页式：将两种存储管理方法结合起来，形成了段页式存储管理方式。作业地址空间首先分成若干逻辑段，每段都有自己段号，然后每一段分成若干大小固定的页。对内存空间管理仍然和分页一样。逻辑地址三部分，段号，页号，偏移量。段表项报考段号，页表长度，页表起始地址。页表项包括页号和块号。53、 简述虚拟存储器的原理传统存储管理方式一次性，驻留性不换出。局部性原理，空间局部性，一旦程序访问了某个存储单元，在不久之后，其附近的存储单元页将被访问，指令通常说顺序存放，顺序执行的，数据也一般以数组等方式簇聚存储的。时间局部性，某一指令一旦执行，不久以后该指令可能再次执
