南理工历年真题(825)

1、南京理工大学2004 年硕士学位研究生入学考试试题第一部分数据结构（共35分） 一、选择题，在所给的四个选项中，选择一个最确切的（每小题1分，共10分）1. 设单循环链表中结点的结构为（data,next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，正确的操作是 。A) s=rear;rear=rear->next; free(s);B) rear=rear->next; free(s);C) rear=rear->next->next; free(s);D) s=rear->next->next; rear->

2、;next->next=s->next; free(s)2. 设输入序列为20，11，12，构造一棵平衡二叉树，当在树中插入值12时发生不平衡，则应进行的平衡旋转是 。A)LL B)LR C)RL D)RR3. 设有1000个无序的元素，希望用最快的方法选出前10个最小的数据，下面四种方法中最好的是 。A)冒泡 B)快速 C)堆 D)选择4. 下面程序的时间复杂性为。for (int i=0; i<m; i+) for (int j=0;j<n; j+) aij=i*j;A)0(n2) B)0(n*m) C) 0(m2) D)0(m+n)5. 关于下面的程序段，不正确的

3、说法是 。pb=pc=-1;for(int k=0; k<n; k+)if (Ak>0) B+pb=Ak; elseC+pc=Ak;A)其时间复杂性为0(n/2)B)它将数组A中的正数放到数组B中，将负数放在数组C中C)如果数组A中没有负数，程序执行后pc=-1D)如果数组A中没有正数，程序执行后pc=-16. 有三个数字1，2，3，将它们构成二叉树，中序遍历序列为1，2，3的不同二叉树有 种。A)5 B)6 C)7 D)87. 判断有向图是否有回路，除了可以用拓扑排序外，还可以用 。A)求关键路径的方法B)广度优先遍历算法C)求最短路径的方法D)深度优先遍历算法8. 在线索二叉树

4、中，下面说法不正确的是 。A)在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点B)线索二叉树是利用二叉树的n+1个空指针来存放结点前驱和后继信息的C)每个结点通过线索都可以直接找到它的前驱和后继D)在中序线索中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。9. 一棵有64片叶结点的完全二叉树，该完全二叉树最多有 结点。A)124 B)125 C)126 D)12710. 若从二叉树的任一结点出发到根的路径上所经过的结点序列是按关键字有序的，则该二叉树是 。A)二叉排序树 B)用二叉树形式存储的堆C)哈夫曼树 D)AVL树三、填空题（每个空格1分，共10分）

5、1. 在数据结构中，线性结构、树形结构和图形结构数据元素之间分别存在 、 、 和的联系。2. 一棵二叉树的结点数据采用顺序存储结构，存储在一维数组t 中，t=e,a,f,0,d,0,g,0,0,c,j,0,0,l,h,i,0,0,0,0,b(其中0代表空树)，c 在树中的层次为 。3. 下图中所示的AOE网的关键路径是（以<A、B>形式给出），其长度为 5. 将图中的弧看成边，以（A,B）形式给出图的最小生成树上的边是 。6. 从顶点A到F的最短路径长度是。四、算法（5分）树的存储结构如下：#define MAX_TREE_SIZE 100Typedef struct CTNode

6、 /孩子结点Int child; StructCTNode *next;*childPtr; Typedef struct Elemtype datachildPtr *firstchild; /孩子链表头指针*CTBox;Typedef struct CTBox nodes MAX_TREE_SIZE;Int n; /n为结点数*CTree写出求树的度的算法。第二部分操作系统（共35分）一、选择题，在所给的四个选项中，选择一个最确切的（每小题1分，共10分）1. 操作系统的主要作用是 。A)管理设备 B)提供操作命令C)管理文件 D)为用户提供使用计算机的接口，管理计算机的资源2. 在操作系

7、统术语中，C/S是 。A)浏览器/服务器B)网络OS C)实时OS D)分布式OS3. 与UNIX操作使用基本相同的操作系统操作系统是 。A)LINUX B)WindowsNT C)UNIX D)OS/24. 在操作系统中，并发性是指 。A)若干个事件在同一时刻内发生 B)事件的发生时间随机C)若干个事件在同一时间间隔内发生 D)事件驱动5. 特权指令是指 。A)机器指令 B)其执行可能有损系统的安全性C)控制指令 D)系统管理员可用的指令6. 在物理上，进程由所组成 。A)程序 B)命令 C)PCB、程序和数据 D)PCB和程序7. 操作系统中的三级调度是指 。A)处理机调度、资源调度和网络

8、调度 B)CPU调度、设备调度和存储器调度 C)作业调度、进程调度和资源调度 D)作业调度、进程调度和均衡负载调度8. 在操作系统中，设备独立性是指 。A)用户程序与设备无关 B)设备独立管理C)设备具有自治性 D)只有OS才有权启动设备9. 当发生中断后，进入中断处理的程序属于 。A)用户程序 B)可能是用户程序，也可能是OS程序C)OS程序 D)单独的程序，既不是用户程序，也不是OS程序10. 在设备管理中，设备映射表（DMT）的作用是 。A)管理物理设备 B)管理逻辑设备C)实现输入输出 D)建立逻辑设备与物理设备间的对应关系二、填空题（答题时，标明题号。每个空格1分，共10分）1、操作

9、系统的特征包括并发性、共享性、 、 、 。2、操作系统提供二种接口，即为用户提供 ，为程序用户提供 。3、在UNIX操作系统中，为块设备提供了二种读方式，分别是 和 。4、产生死锁的四个必要条件是互斥条件 、 、 、 。三、应用题（共15分）1、（7分）在UNIX 系统中，空闲磁盘空间的管理采用了成组链表法，试述成组链表法的实现方法。说明其优缺点。2、桌子有一个盘子，每一次只能放入一个水果。现有许多苹果和桔子。一家四口人各行其职，爸爸的动作是：负责取苹果，然后将苹果放入盘子中，并重复这二个动作。当取来一个苹果后，若盘子中允许放入水果，即盘子为空，则将苹果放入盘子中；否则等待，直等到盘子中能放入

10、苹果为至。妈妈的动作是：负责取桔子，然后将桔子放入盘子中，并重复这二个动作。当取来一个桔子后，若盘子中允许放入水果，则将桔子放入盘子中；否则等待，直等到盘子中能放入桔子为至。一个女儿的动作是：负责从盘中取苹果，然后吃苹果，并重复这二个动作。若盘子中有苹果，则取走苹果；否则等待，直等到盘子中有苹果为止。一个儿子的动作是：负责从盘中取桔子，然后吃桔子，并重复这二个动作。若盘子中有桔子，则取走桔子；否则等待，直等到盘子中有桔子为止。试用P、V操作写出他们四人之间的同步算法（8分）。提示：先分析四人之间的同步关系，然后写出同步算法。_南京理工大学2005 年硕士学位研究生入学考试试题一、数据结构部分（

11、共35分）（一）、选择（每项1分，共15分）1、快速排序算法在最好情况下的时间复杂度 。A)O(n) B) O(n2) C) O(log2n) D) O(logn)2、有n个顶点，e条边的图G采用邻接表存储，则拓扑排序算法的时间复杂度为 。A)O(n) B) O(n+e) C) O(n*e) D) O(n2)3、设双向循环链表中结点的结构有数据域data，指针域pre和next，链表不带头结点。若在指针p所指结点之后插入结点s，则应执行下列操作 。A)p->next=s; s->pre=p; p->next->pre=s; s->next=p->next;B

12、)p->next=s; p->next->pre=s; s->pre=p; s->next=p->next;C)s->pre=p; s->next=p->next; p->next=s; p->next->pre=s;D)s->pre=p; s->next=p->next; p->next->pre=s; p->next=s;4、输入序列为20，35，构造平衡二叉树，当在树中插入值30时发生不平衡，则应进行的平衡旋转是 。A)LL B) RL C) LR D) RR5、二叉树的先序和中序

13、遍历序列分别是ABCDEFGH,CBEDFAGH,则后序遍历序列是 A)HGFEDACB B) GHEDFCBA C) CEFDBHGA D) HGAFDEBC6、前序遍历和后序遍历相同的二叉树为前序遍历和中序遍历相同的二叉树为中序遍历和后序遍历相同的二叉树为 。A)一般二叉树B)空树或根结点无左孩子的二叉树C)空树或只有根结点的二叉树D)空树或根结点无右孩子的二叉树E)空树或缺左子树的单支二叉树F)空树或缺右子树的单支二叉树7、设Hash表的表长为14，Hash函数是H（key）=key%11，现表中已有15，38，61和84四个数，其余位置空。处理冲突采用线性探测再散列，现插入49，则它的

14、位置是 。A)8 B)3 C)5 D)98、对于无向图的生成树，下列说法不正确的是 。A)生成树是遍历的产 B)从同一顶点出发所得的生成树相同C)生成树是图的极小连通子图 D)不同遍历方法所得到的生成树不同9、有向图G=(V,A),其中V=a,b,c,d,e,A=<a,b>,<a,c>,<d,c>,<d,e>,<b,e>,<c,e>,对该图 进行拓扑排序，下面序列中哪一个不是拓扑序列 。A)a,d,c,b,e B)d,a,b,c,e C)a,b,d,c,e D)a,b,c,d,e10、下列排序算法中， 排序在一趟结束后不一

15、定能选出一个元素放在其最终位置上。A)希尔 B)冒泡 C)选择 D)直接插入11、对线性表进行二分查找时，要求线性表必须 。A)以顺序方式存储 B)以链接方式存储C)以顺序方式存储，且数据有序 D) 以链接方式存储，且数据有序12、稀疏矩阵一般的压缩存储方法有 。A)三元组和二维数组 B)散列和十字链表C)三元组和散列 D)三元组和十字链表13、链表不具有的特点是 。A)可以随机访问任一元素 B)插入和删除不需要移动元素C)不必事先估计存储空间的大小 D)所需空间与线性表的长度成正比（二）、填空（每空1分，共15分）1、有一个无头结点的单链表，结点有数据域data，指针域next,表头指针为h

16、， 通过遍历链表，将链表中所有的链接方向逆转。要求逆转后的链表的表头指针h 指向原链表的最后一个结点。算法如下所示，请在空格处填入正确的语句。Void Inverse(&h)If ( )return; p=h->next; pr=NULL; while ( )h->next=pr; pr=h;h=p; ;h->next=pr;/ Inverse2、3阶B树如下，画出删除60后的B树 3、已知一组数列为13，5，6，17，32，15，用这组数构成的哈夫曼树的带权路径长度为 。4、AOE网中的 路径称为关键路径。5、表达式a*(b+c)-d/e*f的后缀表达式是 。6、已

17、知带权连通图G(V,E)如下：图的最小生成树 ；去掉图中的权值，图G用邻接矩阵存储。给出从顶点1出发的深度优先搜索序列 和广度优先搜索序列 。7、序列46，55，13，42，94，5，17，70，构造出的大顶堆的序列是 。8、设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点至少 ,至多为 。9、二叉树按某种顺序线索化后，任一结点均有指向前趋和后继的线索，这种说法正确的吗？ 。10、循环队列是队列的一种 存储结构。（三）、算法（5分） 用类_C/C+设计算法，判断一个带表头结点的双向循环链表DL(DuLinkList)是否对称相等。（比如，表（25，34，34，25）和表（25，3，25

18、）为对称的） 其中结点结构为：structNodeEIemTypedata;/ElemType 代表某种抽象数据类型Node *Llink,Rlink;二、操作系统部分（共35分）（一）、单项选择题（每题1分，共15分）1、进程与程序之间有密切联系，但又是不同的概念。二者的一个本质区别是 。A)程序是静态概念，进程是动态概念 B) 程序是动态概念，进程是静态概念C)程序保存在文件中，进程存放在内在中 D)程序顺序执行，进程并发执行2、下列进程状态的转换中，哪一个是不正确的 。A)就绪->运行 B)运行->就绪 C)就绪->阻塞 D)阻塞->就绪3、以下存储管理技术中，支

19、持虚拟存储器的技术是 。A)请求分页技术 B)可重定位分区法C)动态分区法 D)对换技术4、系统出现死锁的原因是 。A)进程进入临界区 B)有多个封锁的进程同时存在C)若干进程因竞争资源无休止地循环等待，且都不释放已占有的资源D)资源数大大少于进程数，或进程同时申请的资源数大大超过资源总数5、进程所请求的一次打印输出结束后，将使进程状态从态变为态 。A)运行就绪 B)运行阻塞 C)就绪运行 D)阻塞就绪6、UNIX系统中，空闲文件存储区的管理采用的是 。A)位图法 B)空闲块表法 C)成组链接法 D)单块链接法7、一种既有利于短小作业又兼顾到长作业的作业调度算法是 。A)先来先服务 B)轮转

20、C)最高响应比优先 D)均衡调度8、在单处理器的多进程系统中，进程什么时候占用处理器和占用多长时间，取决于 。A)进程相应的程序段的长度 B)进程总共需要运行时间多少C)进程自身和进程调度策略 D)进程完成什么功能9、若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区是由 个临界区构成。A)1 B)3 C)5 D)610、一进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁必要条件的 。A)互斥条件 B)请求和释放条件 C)不剥夺条件 D)环路等待条件11、通常不采用 方法来解除死锁。A)终止一个死锁进程 B)终止所有死锁进程 C)从死锁进程处抢夺资源D)从非死锁进程处抢

21、夺资源12、处理器执行的指令分成两类，其中一类称为特权指令，它只允许使用 。A)操作员 B)联机用户 C)操作系统 D)目标程序13、操作系统中设备管理的功能主要包括：实现物理输入/输出操作设备分配和 。A)安装设备 B)维护设备 C)缓冲区管理 D)设备调度14、文件的物理结构通常有如下几种 。A)记录式文件、流式文件 B)连续文件、链接文件、索引文件C)顺序文件、索引文件、顺序索引文件 D)目录文件、数据文件15、在页式管理中，每个页表中的每个表项实际上都是用于实现 。A)内在单元 B)静态重定位 C)动态重定位 D)加载程序（二）、填空题（每空1分，共12分）1、如果淘汰算法不合理，那么

22、有可能刚被调出的一页马上又要求被调入。内存和外存这种频繁地来回调入调出页面的现象称为（1） 。2、某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内地址。则这样的地址结构：（1）一页有（2） 字节（2）逻辑地址可有（3） 页（3）一个作业最大的使用空间是（4） 字节3、在一个采用页式虚拟存储管理的系统中，某进程依次要访问的字地址序列（逻辑地址）是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字， 请回答下列问题：A、按FIFO调度算法将产生（5） 次缺页中断，依次淘汰的页

23、号为（6） B、按LRU调度算法将产生（7） 次缺页中断，依次淘汰的页号为（8） 4、若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76， 假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。A、先来先服务算法（9） B、最短寻道时间优先（10） 5、进程的（11） 和（12） 反映了进程间直接制约和间接制约的关系。（三）（8分）有三个人A、B、C，其中A负责采购原材料并放入仓库1（该库只能放一件原材料），B从库1取出原材料并加工成产品后放入库2（该库也只能放一件产品），C从库2取出商品后销售。试说明：

24、（1）为了实现并必发，需要几个信号灯，功能和初值是什么？（3分）（2）利用P、V（wait、signal）操作写出并发流程。（3分）南京理工大学2006 年硕士学位研究生入学考试试题三、操作系统部分（共50分。若选择此部分，请在答题纸上注明）（一）单项选择题（每小题1分，共20分）1、某虚存系统有3页初始为空的页框，若采用先进先出的页面淘汰算法，则在下列的页面需求提出时，会产生 次缺页中断？ 页面需求是：1，2，3，4，1，2，5，1，2，3，4，5A)6 B)7 C)8 D)92、下列算法中用于磁盘移臂调度的是 。A)时间片轮转法 B)优先级高者优先算法C)最短寻找时间优先算法 D)LRU算

25、法3、位示图方法可用于 。A)盘空间的管理 B)盘的驱动调度C)文件目录的查找 D)页式虚拟存贮管理中的页面调度4、如果进程信号量S执行V操作，则信号量S的值将 。A)加1 B)减1 C)等于0 D)大于05、下面说法错误的有 。（1）分时系统中，时间片越小越好。（2）银行家算法是防止死锁发生的方法之一。（3）若无进程处于运行状态，则就绪队列和等待队列均为空。A)（1）（2） B)（2）（3） C)（1）（3） D)（1）（2）（3）6、引入多道程序设计技术的主要目的在于 。A)减少存储器碎片 B)充分利用处理机，减少处理机空闲时间C)有利于代码共享 D)充分利用外围设备7、当出现 情况时，系

26、统可能产生死锁。A)进程释放资源 B)一个进程进入死循环C)多个进程竞争，资源出现了循环等待 D)多个进程竞争共享型设备8、现代操作系统中，文件系统都有效地解决了重名（即允许不同用户的文件可以具有相同的文件名）问题。系统是通过 来实现这一功能的。A)重名翻译机构 B)建立索引表 C)树型目录结构 D)建立指针9、下列作业调度算法中，具有最短的作业平均周转时间的是 。A)短作业优先法 B)先来先服务法 C)优先数法 D)时间片轮转法10、为两个相互独立源程序进行编译的两个进程，它们之间的关系正确的是 。A)可以并发执行，两者逻辑上有依赖关系B)可以并发执行，两者逻辑上无依赖关系C)不可以并发执行

27、，但两者逻辑上有依赖关系D)不可以并发执行，因为两个进程运行的是同一个编译程序11、有若干并发进程均将一个共享变量count中的值减1一次，那么有关count中的值说法正确的是 。（1）肯定有不正确的结果（2）肯定有正确的结果（3）若控制这些并发进程互斥执行count加1操作，count中的值正确A)（1）（3） B)（2）（3） C)（3） D)（1）（2）（3）的说法均不正确12、某进程由于需要从磁盘上读入数据而处于阻塞状态。当系统完成了所需的写盘操作后，此时该进程的状态将 。A)从就绪变为运行 B)从运行变为就绪C)从运行变为阻塞 D)从阻塞变为就绪13、进程状态从就绪态到运行态的转化工

28、作是由 完成的。A)作业调度 B)中级调度 C)进程调度 D)设备调度14、银行家算法可以实现死锁的 。A)预防 B)避免 C)检测 D)恢复15、以下存储管理技术中，支持虚拟存储器的技术是 。A)动态分区法 B)可重定位分区法 C)请求分页技术 D)对换技术16、计算机系统产生死锁的根本原因是 。A)资源有限 B)进程推进顺序不当 C)系统中进程太多 D)A和B17、在操作系统中，并发性是指 。A)若干个事件在不同时刻发生B) 若干个事件在同一时刻发生C) 若干个事件在同一时间间隔内发生D) 若干个事件在不同时间间隔内发生18、关于请求分页存储管理说法不正确的是 。A)程序空间页的大小与计算

29、机物理块的大小总是一致的B) 页地址变换机构必须由相应的硬件支持C) 将用户地址空间分为页号和页内偏移对用户是感觉不到的D) 在请求调页的系统中，用户程序必须全部装入主存19-20、现代操作系统中一般已有线程管理，此时，申请资源的基本单位是 ，CPU得到执行的基本单位是 。A)模块 B) 作业 C) 线程 D) 管程 E)进程 F)类程 E）例程（二）填空（每空1分，共5分）1、程序运行时，在一段时间内常常是集中地访问内在某一部分地址空间，这种行为称之为程序的（1） 。2、如果淘汰算法不合理，那么有可能刚被调出的一页马上又要求调入。内存和外存这种频繁地来回调入调出页面的现象称为（2） 。3、在

30、多进程的系统中，为了保证临界资源的完整性，各进程应互斥的使用它， 在操作系统中，这段程序（代码）称为（3） 。4、特权指令只能在（4） 态下执行，若在（5） 态下执行则被认为是非法指令。（三）解答题（共16分）1、（5分）某虚拟存储器的用户编程空间共32个页面，每页为1kb，内存为16kB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页物理块号051102437则（1）（2分）此时，指令中地址空间至少需要多少位？（2）（3分）逻辑地址0A5C（十六进制）所对应的物理地址是什么（用十进制表示）？2、（5分_）假定一磁盘200个磁道，编号是0至199，在完成了磁道143（之

31、前访问的是磁道100）处的请求后，请求的队列先后次序为：86，147，91，177，94，150，102，175，130。当用FCFS（先来先服务），最短寻道时间优先（SSTF） 和扫描（SCAN,也称为电梯调度）来安排磁头移动时，其移动的总量分别是 ， ， 。用SCAN时，130道前访问的是 道，SSTF时91道前访问的是 道。3、（6分）系统有三个进程Read,Writel,Write2共享一个整数缓冲器b,b中每次只能存放一个整数。Read进程每次启动输入设备输入一个整数到b。若b中是奇数，则由进程Writel将其取出打印；若b中是偶数，则由进程Write2将其取出打印。规定输入与打印整

32、数的个数和次序完全一致。要求：（1）（4分）完善如下程序，在下列A1、A2、B1、B2处填入有关语句，并说明物理意义。S,SO,SE:semaphore;B:integer;S:=1 S=0; SE:=0; Read进程；do 从输入设备读一整数到X:P(S);b=X; if(b=奇数)V(SO);else V(SE);while(1);Writel进程： Write2进程：do do(A1); (B1);Y=b; Z=b;(A2); (B2);print Y; print Z;while(1); while(1) (2)说明信号量S,SO,SE作用及它们的初值的物理意义。（1分）（3）Rea

33、d进程中V(SO)与V(SE)对谓，程序功能将发生什么变化。（1分）（四）叙述题（共9分）1、（4分）在采用等长时间片轮转处理机调度算法的分时操作系统中，各终端用户所占有的时间片必定是相同的。这种说法对吗？为什么？2、（5分）请叙述虚拟存储管理方案的基本工作原理、页表的内容、缺页中断处理及可能遇到的性能问题和解决方法。南京理工大学2007 年硕士学位研究生入学考试试题一、数据结构部分（共50分）（一）填空（每个空格1.5分，共15分）1 、无向图G= （ V,E ） ， 其中： V=a,b,c,d,e,f E=（a,b）,(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)对

34、该图进行深度优先遍历，得到的顶点序列正确的是（1） 。2、该算法为简单选择排序算法。void sort(Linklist &H)q=H;while(q) r=q;(2) ; while(p)if ( (3) ) r=p; p=p->next;q->datar->data; (4) ;while(q)/sort3、满7叉树上的叶子结点数n0和非叶结点数n1之间的关系是： （5） 。4、3阶B树如下，画出删除24后的B树（6）5、设单循环链表中结点的结构为（data,next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行的

35、操作为（7） 6、输入序列为8，6，4，10，12，9，7，构造一棵哈夫曼树，该哈夫曼树的带权路径长度WPL为（8） 7、写出表达式a*(b+c)-d的后缀表达式（9） 8、有序表为5，8，10，15，32，41，45，62，75，77，82，95，100，用二分查找值为82的数据时，需要比较（10） 次。（二）简答（16分，每小题4分）1、拓扑排序算法。2、Prim算法。3、说出二叉树的五种形式。4、二叉树中序遍历的递归算法。（三）（9分）输入关键字序列8，6，4，10，12，9，71、（5 分）构造一棵二叉平衡（AVL）树，画出树的生成过程和所进行的平衡操作。2、（4分）将上述关键字序列作

36、为初始序列，写出冒泡排序一趟后的序列。（四）算法题（本题10分）：用类C写一算法，把一个用数组表示的线性表转换成双向循环链表。所用数据类型定义如下：typedefstruct EelemType*elem; int length;int listsize;sqList;typedef structDulNode ElemType data;Struct DulNode *prior;Struct DulNode *next;DulNode, *DuLinkList;三、操作系统部分（共50分。若选择此部分，请在答题纸上标明）（一）单项选择题（每小题1分，共20分）1、在下列性质中，不是分时系统

37、特征的是 。A)交互性 B)独立性 C)多路性 D)成批性2、引入多道程序设计的主要目的在于 。A)有利于代码共享，减少主、辅存信息交换量B)提高实时响应速度C)充分利用CPU，减少CPU等待时间D)充分利用存储器3、在下面的进程状态转换过程中，可能发生的转换有 。（1）运行就绪（2）运行阻塞（3）阻塞运行（4）运行终止A）（2）（3）（4） B）（1）（2）（3） C）（1）（2）（4） D）（2）（4）4、分时系统中，一个运行进程用完了分给它的时间片后，还未完成计算任务， 它的状态将变为 。A）就绪 B）阻塞 C）运行 D）挂起5、在非剥夺调度方式下，运行进程执行V原语后，其状态。A）不变

38、 B）要变 C）可能要变 D）可能不变6、对于大量缓冲区的管理，采用多个生产者-多个消费者方式解决同步或互斥时， 通常需要用个信号量 。A）2 B）3 C）4 D）57、一个正在访问临界资源的进程由于申请等待I/O操作而被中断时 。A）可以允许其他进程进入与该进程相关的临界区B）不允许其他进程进入任何临界区C）可以允许其他就绪进程抢占处理器，继续运行D）不允许任何进程抢占处理器8、如果信号量的当前值为-2，则系统中在该信号量上等待的进程数目是 。A）2 B）3 C）4 D）59、下面的情况中，进程调度可能发生的时机有 。（1）正在执行的进程运行完毕（2）正在执行的进程提出I/O请求后进入等待状

39、态（3）就绪队列中某个进程的优先级高于当前正在运行进程的优先级（4）有某个进程从阻塞状态转换成就绪状态A）（1）（2）（3） B）（1）（2）（3）（4） C）（1）（2）（4） D）（1）（3）（4）10、主要在分时系统中使用的一种调度算法是 。A）先来先服务 B）短作业优先 C）时间片轮转法 D）优先数法11、在死锁预防方法中，系统要求所有进程在运行前一次性的申请在整个运行过程中所需要的全部资源，得到满足后才得以运行，并在运行期间不允许提出资源请，这种方法破坏产生死锁必要条件中的 。A）互斥条件 B）请求和保持条件 C）不剥夺条件 D）环路等待条件12、在多道程序系统中，由于可共享的资源不

40、足，可能会出现死锁。有时，不恰当的 也可能引起死锁。A）进程调度算法 B）资源分配方法 C）进程推进顺序 D）进程优先权13、在页式管理中，每个页表中的表项实际上是用于实现 。A）内存单元 B）静态重定位 C）动态重定位 D）加载14、有关资源分配图中存在环路和死锁关系正确的说法是 。A）图中无环路则系统可能存在死锁 B）图中有环路则系统肯定存在死锁C）图中有环路则系统可能存在死锁，也可能不存在死锁 D）以上说法都不对_15、设有12个同类资源可供四个进程共享，目前剩余资源数为2。现资源分配情况如下：进程 已占用资源数 最大需求数 本次申请P1 2 4 2P2 3 6 3P3 4 7 3P4

41、1 4 3当进程P1，P2，P3，P4又都相继提出上面的申请要求，为使系统不致死锁，应满足的要求 。A）P1 B）P2 C）P3 D）P416、下面关于虚拟存储器的论述中，正确的是 。A）要求作业运行前，必须全部装入内存，且在运行中必须常驻内存B）要求作业运行前，不必须全部装入内存，且在运行中不必常驻内存C）要求作业运行前，不必须全部装入内存，但在运行中必须常驻内存D）要求作业运行前，不必须全部装入内存，但在运行中不必常驻内存17、在现代操作系统中，为了提高操作系统的可适应性和可扩展性，都实现了 ，使得用户所编写的程序与实际使用的物理设备无关。A）虚拟设备 B）缓冲管理 C）设备独立性 D）设

42、备分配18、如果文件系统中有两个文件重名，不应采用 。A）单级目录结构 B）两级目录结构C）树型目录结构 D）多级目录结构19、特权指令 。A）是可能影响系统安全的一类指令B）既允许操作系统程序使用，又允许用户程序使用C）是管态和目态运行的基本单位D）是一种存储保护方法20、并发性是指若干事件在 发生。A）同一时刻 B）同一时间间隔内 C）不同时刻 D）不同时间间隔内（二）填空（每空1分，共8分）1、虚拟设备是通过（1） 技术把独享设备变成能为若干用户共享的设备。2、UNIX系统采用的空闲盘块管理方法是（2） 。3、用户进程从目态（常态、用户态）转换为管态（特态、系统态）的唯一途径是（3） ，

43、当该用户进程需要使用打印机进行输出时，进程的状态由（4） 变为（5） ，在打印结束后，会产生一个打印中断，此时进程的状态会变为（6） 。4、在磁盘调度策略中有可能使I/O请求长期等待的调度算法是（7） 。5、在操作系统中，用户界面指的是命令接口、程序接口和（8） 。（三）解答题（共14分）1、（3分）在一个请求页式存储管理系统中，某作业所涉及的页面依次为3，2，1，4，4，5，3，4，3，2，1，5，并已知分给该作业的主存物理块是3，则按照FIFO调度算法将产生 次缺页中断。按照LRU调度算法将产生 次缺页中断。按照OPT调度算法将产生 次缺页中断。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）2、（3分）设某移动头磁盘共有200道，编号为0-199，磁头当前处在130道上， 且正向0 磁道方向移动，对于如下盘请求序列：70，1