南昌大学计算机应用历年试题.南昌大学2001年攻读硕士学位研究生入学考试试题报考专业:计算机应用考试科目:操作系统(A)一. 判断题(共15分,每题1分,答对的得1分;不答的不给分)1.要想有效地使用多重处理系统,必须采用多道程序设计技术.而多道程序设计也一定要求有多重处理系统的支持.2.对批处理作业,必须提供相应的作业控制信息.3.采用分时操作系统的计算机系统中,用户可以独占计算机操作系统中的文件系统.4.并发性是指若干事件在同一时间间隔内发生.5.不同的进程所执行的程序代码一定不同.6.在请求段页式系统中,以段为单位管理用户的虚空间,以页为单位管理内存空间.7.临界区是指进程中用于实现进程互斥的那段代码.8.Spooling系统就是脱机I/O系统.9.在磁带上的顺序文件中插入新的记录时,必须复制整个文件.10.用户进程是通过请求系统进程的运行而得到系统服务的.11.信号量的初值必须是大于零的整数.12.在银行家算法中,并非所有的被拒绝的请求都会产生死锁.13.虚拟设备是指把一个物理设备变换成多个对应的逻辑设备.14.覆盖技术是现代大型操作系统所使用的主要技术.15.通道是一种通用处理机.二. 填空题(共20分,每空1分)1.现代操作系统的基本特征是程序的并发性,共享性和不确定性.其中操作系统的不确定性表现在两个方面,它们是: ( )和( ).2..一个作业的建立过程包括两个子过程,一个是( ),另一个是( ).3.把一个具有独立功能的程序独占处理机直至得到最终结果的过程称为( ).4.原语可分为两类:一类是机器指令级的,其特点是( )另一类是功能级的,其特点是( )5.在进程通信中,消息的一般形式为四个部分组成.即( ),( )( )和( ).6.平均带权周转时间可用来衡量某种调度算法对( )的调度性能.7.每个进程都拥有自已的虚拟存储器.且虚虚拟存储器的容量是受计算机的( )和( )确定.8.由于缓冲区是临界资源,所以对缓冲区或缓冲队列的操作必须( ).9.在最先适应算法中,要求空闲分区按( ) 顺序接成空闲争区链;在最佳造应算法中,要求空闲分区按( )顺序链接成空闲分区链;在最坏适应算法中,要求空闲分区按( )顺序链接成空闲分区链.10.如果逻辑性地址空间由256 页构成,每一页的长度为2048,则二进制的逻辑地址有( )位.11.把作业地址空间中使用的逻辑地址变成内存中物理地址的过程称为( ).回复:南昌大学计算机应用历年试题.南昌大学2001年攻读硕士学位研究生入学考试试题报考专业:计算机应用考试科目:操作系统(A)三.问答题. (共26分)1. 进程调度的功能是什么?什么叫动态优先数调度法?(5分)2. 设备管理程序的功能是什么?通过什么技术能把独享设备改为可共享的设备? (5分)3. 试说明静态分页管理中分页地址映射的基本原理. (5分)4.说明作业调度,中级调度和进程调度的区别,并分析下述问题应由哪一级调度程序负责.(6分)(1) 在可获得处理机时,应将它分给哪个就绪进程;(2) 在短期繁重负载下,应将哪个进程暂时挂起.5.在用户和操作系统之间存在那几种类型的接口,它们的主要功能是什么? (5分)四.某采用页式存储管理的系统,把主存分成大小为256的相等长度的块,有一个用户要把一个256*256的数组初始化为0,在分页时把数组中的每一行放在一页中.假定分给用户可用来存放数组信息的工作区只有一块(即只能放数组中的一行元素).用户编制了如下两个不同的程序来实现数组的初始化:(1) var A:array[1..256] of array[1..256] of integer;for j:=1 to 256 dofor i:=1 to 256 doA[i][j]:=0;(2) var A:array[1..256] of array[1..256] of integer;for i:=1 to 256 dofor j:=1 to 256 doA[i][j]:=0;问当分别运行这两个程序时,在实现数组初始化的过程中各会产生多少次缺页中断.(本题6分)五.为了实现文件的共享,办法之一是把文件目录分成基本文件目录和符号文件目录.现设目录文件存放在磁盘上, 盘块长度为1024字节;每个文件说明占48个字节,其中,文件符号名占6字节,内部标识符ID占2字节,请回答下列问题:(1) 设一个目录文件原来共有256个目录表目,请求出未分解和分解后的平均访盘次数?(2) 若某个目录文件未分解时需用N个盘块存放文件目录表目,而分解后只需用M个盘块存放符号文件目录表目.请求出未分解和分解后的平均访盘次数?并分析N与M应满足什么关系时分解才有意义?(本题8分)六.假定有三个进程R.W1.W2共享一个缓冲器B,而B中每次只能存放一个数.当缓冲器中无数时,进程R可以从输入设备上读入的数存放到缓冲器B中.若存放到缓冲器中的数是奇数,则允许进程W1将其取出打印; 若存放到4. 采用多道程序设计,能充分发挥处理器的使用效率,缩短每个算题的周转时间.5. 若无进程处于运行状态,则就绪队列和等待队列均空.6. 近似LRU算法中,对每页都设置一个”页面访问位”,当替换一页的时候,总是选择访问位为0的淘汰.7. 页式虚拟存储器管理中,地址变换是在作业装入的时候完成的.8. 文件的存取方法是由文件的性质和用户使用文件的情况来确定的.9. 设备驱动程序是一种系统例程.设备动程序使用I/O指令来访问硬件,这些指令一般情况下能被用户进程执行.10. 作业就是用户提交给系统的程序.三. 填空题.( 每小题2分,共20分)1.批处理系统的主要优点是( )和( ).2.程序并发执行时的特征是( ). ( ).( )和独立性.3.进程的五大特征是( ).( ) ( ) .( )和结构特征.3.信号量被广泛用于三个目的是( ).( ) 和描述前趋关系.4.产生死锁的原因是( ).5.用户接口通常分为( )和( ).6.建造支持虚拟存储器的系统,应有三个物理基础支持,它们是( ).( )和地址变换机构.7.分页式虚拟存储空间中,当发现某页不在( )的时候,将由( )产生缺页中断,当没有空闲主存块时,需要用调度算法进行页面( ),如呆这时没有选择好一种好的调度算法,就会产生( )现象.8.文件的符号名与物理地址之间的转换是通过( )来实现的.9.文件的物理组织有四种类型:( ),( ),( )和Hash文件.10.在挂起队列的调度策略中,SSTF,策略可能会引起进程( )的问题,因此,要对SSTF,策略进行必要的修改,其关键是要记住( )的方向.(1) 为描述读者的动作,应编写几个程序,应设置几个进程?进程和程序之间的对应关系如何?(2) 试用P.V操作描述这些进程间的同步关系.2. 下面是两个并发执行的进程.它们能正确执行吗?若不能, 试举例说明,并修改之.(9分)ParbeginVar x :integer;Process P1Var y,z:integer;BeginX:=1;Y:=1;If x>=1 then y:=y+1;Z:=y;End;Process P2Var t,u:integer;BeginX:=1;t:=1;If x<1 then t:=t+1;u:=t;End;Parend;3. 设磁盘共有200个柱面,柱面编号为0-199,当前存取壁的位置在125 柱面上,并且刚刚完成了对128号柱面的服务请求,在此之前如果存在以下的请求服务序列:75, 182, 90, 110, 170, 150, 102, 68, 42试问: 为完成上述请求, 下列算法存取臂移动顺序如何?移动的总量是多少?(1) 先来先服务(FCFS)(2) 最短寻找时间优先(SSTF)(3) 循环扫描法(SCAN)(9分)4.某计算中心于上午9:30响应表中A,B,C三个作业,试问采用(1)短作业优先和(2)高响应比优先算法调度时, 各自完成时间, 请写出计算步骤, 然后填入下表中作业提交时间估算时间完成时间等待时间A 8:30 130分钟B 8:50 15分钟C 9:20 70分钟要求: 完成时间按格式”小时:分钟”填入;等待时间按”分钟”填入.(6分)5,若采用页式管理系统,一个程序的页面走向为: 4,3,2,1,4,3,5,4,3,2,1,5,并采用FIFO和近似LRU页面置换算法,回复:南昌大学计算机应用历年试题.南昌大学2003年攻读硕士学位研究生入学考试试题报考专业:计算机应用考试科目:数据结构操作系统(A)数据结构部分一. 单项选择题.(每题2分,共8分)1.对由n个记录组成的文件排序,如果n较小(n<50)且记录的规模较大,则采用( )排序方法节省时间.A.直接插入B.直接选择C.快速D.堆2.假定有K个关键字互为同义词,若用线性探测法把这些同义词存入散列表中,至少要进行( )次探测.A. KB. K2(K的平方)C.1/2K(K-1)D.1/2K(K+1)3.二维数组a[0…8, 1…10]按行存放时元素a[8, 5]的起始地址与按列存放时元素( )的起始地址相同.A. a[8,5]B. a[3,10]C. a[5,8]D. a[0, 9]4.有6个元素按6,5,4,3,2,1的顺序进栈,下列( )不是合法的出栈序列.A. 5,4,3,6,1,2B. 4,5,3,1,2,6C. 3,4,6,5,2,1D. 2,3,4,1,5,6二.填空题(每题3分,共12分)1. (假定该后继结点存在):的中序(对放序)后继结点q设P指向二叉树中某个S结点,结点有二个指针域lchild与rchild分别指向该结点的左,右孩子,则执行下列语句可找到结点P.rchild; ______________q:=p2. 高度为6的AVL树至少有________结点.(设空二叉树高度为0)3. 用数组Q[0..n-1]存放循环队列, f, r分别为队头,队尾指针,则队列长度的计算公式是__________. 队列长度的最大值是____________.4. 高度为h的完全二叉树上至少有_______个结点, 至多有_______个结点.三. 简答与画图题(共24分)1. 设二叉树的后根序列为HDEBIFGCA, 中根序列是DHBEAIFCG, 画出此二叉树和它所对应的森林.(9分)2. 顺序查找,二分法查找和分块查找三种方法对查找表中元素各有什么要求? 平均的查找长度各是多少?(假设查找表的长度为n.) (9分)3. 图的广度遍历算法中既可以在一个点入队时对其访问,也可以在顶点出队时对其访问,请问前一种方法有何优点?后一种方法可能产生什么问题?并以下图为例说明.(6分)V0V1 V2………VnVn+1四. 算法题.(共31分)1. 清除重复结点. 单链表中数据域的值相同的结点称为重复结点.如线性表(2,1,1, 3,2,1,) 清除重复结点后为(2,1, 3).试用C语言写一函数清除单链表head中的重复结点,并指出每个工作指针的作用.( 15分)2. 找第k项. n个元素的第k项是把它们从小到大的排序后的第k个元素.如(16,12,99,95,18,87,10) 的第4项是18.假定n个整数放在数组a [1..n] 中,试写一算法,不经对整个数组排序,找到第k项.并写出此算法在最好和最坏情况下的时间复杂度. (提示,利用快速排序中的划分方法.) (16分)4. 位示图5. 设备驱动程序一. 简答题(每题4分,共20分)1. 操作系统的基本特征是什么?2. 什么叫联想存储器?设CPU给出有效地址为(P.D),其中P表示页号,D表示页内位移量,试说明利用联想存储器实现动态地址变换的过程.3. 文件存储空间管理有哪几种常用的方法?4. 试给出两种I/O调度算法,并说明为什么在I/O调度中不能采用时间片轮转法?5. 试说明信号量的物理意义?三.单项选择题(每题1分,共10分)1. 存储器的段页式管理中,每次从主存中取出一条指令或一个操作数,需要( )次访问主存.A.1B.2C.3D.42.设有n个进程共用一个相同的程序段(临界区),如果每次最多允许m个进程(m<n)同时进入临界区.则信号量的初始值为( ).A.nB.mC.m-nD.n-m3.在操作系统中,一方面每个进程具有独立性,另一方面进程之间又具有相互制约性.对于任何两个并发进程,它们( )A. 必定无关B.必定相关C.可能相关D.可能相同4.一个虚拟存储器系统中,设主存的容量为16MB,辅存的容量为1GB,而地址寄存器的位数32位.在这样的系统中,虚存的最大容量是( ).A.1GBB.16MBC.1GB+16MBD.4GB5.采用直接存取法来读写磁盘上的物理记录时,效率最高的是( )A.连续结构的文件B.索引结构的文件C.链接结构文件D.其他结构文件6.下列算法中可用于进程调度,磁盘调度,I/O调度的是( )A.先来先服务B. SSTF服务C.时间片轮转D.优先级高者优先7.通道又称I/O处理机,它能完成( )之间的信息传输.A.主存与外设B.CPU与外设C.外设与外设D.主存与CPU8.死锁的4个必要条件无法破坏的是( ).A.互斥条件B.请求与保持条件C.非抢夺条件D循环等待条件9.文件系统采用多级目录结构后,对于不同用户的文件,其文件名( ).A.应该相同B.应该不同C.可以不同,也可以相同D.受系统约束10最容易开成很多小碎片的可变分区分配算法是( ).A.首次适应算法B.最佳适应算法C.最坏适应算法D.以上算法都不会四,改错题(划出下列句子中的错误的地方并改正,简单的否定无分.每小题2分,共10分)1. 进程有三个状态:运行态,就绪态和等待态.2. 在分区存储管理方案中,作业的大小只受主存加辅存之和大小的限制,可以实现虚拟存储.3. 如果CPU正在执行一个P操作的时候,一个最高级中断到来,那么中断处理进程会抢夺CPU.4. 为了正确地按名存取,操作系统规定不同的文件均不能有相同的文件名.5. 通常,一个CPU可以连接多个通道,一个通道可以连接多个设备控制器,一个设备控制器可连接多台外围设备.五,计算题(25分)1. 设有两个优先权相同的进程,P1,P2如下,令信号量S1,S2的初值均为0,已知Z=2,试问,P1,P2执行结束后,X=?,Y=?,Z=? (6分)进程P1 进程P2. .. .. .Y:=1; X:=1;Y:=Y+Z; X:=X+1;V(S1); P(S1);Z:=Y+1; X:=X+Y;P(S2); V(S2);Y:=Z+Y; Z:=X+Z;. .. .. .2. 设在单机系统内存中存放三道程序A,B和C,按A,B,C的优先次序运行,其内部计算机I/O操作的时间分配如下图所示.程序A 计算30m->I/O 40ms->计算10ms程序B 计算60m->I/O 30ms->计算10ms程序C 计算20m->I/O 40ms->计算20ms试画出按多道运行时的时间关系图(设有两个通道,取名为通道1, 通道2,调度程序的执行时间忽略不计),并计算完成这三道程序共花多少时间及比单道程序运行节省多少时间.(9分)3. 桌子有一个盘子,每次只能放入一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子,女儿专等吃盘中的苹果,儿子专等吃盘中的桔子.试用P, V操作写出他们能正确同步的并发程序.(10分).第一章操作系统引论1. 操作系统的形成(了解)2. 操作系统的基本类型(识记)3. 操作系统的特征和功能(理解)4. 操作系统的发展(了解)第二章进程的管理(重点)1. 前趋图(了解)2. 进程的基本概念(理解)3. 进程控制(理解)4. 进程同步(理解)5. 经典进程同步问题(掌握, 会应用)6. 进程通信(了解)7. 进程调度(理解)8. 死锁(理解)第三章作业管理1. 作业的管理与调度(理解)2. 用户与操作系统之间的接口(了解)3. 命令接口(了解)4. 程序接口(了解)5. 作业控制(了解)第四章存储器的管理1. 引言(理解)2. 单用户系统的存储器管理(掌握)3. 多用户系统的存储器管理(掌握)4. 覆盖与交换(理解)5. 分页式存储管理(掌握)6. 分段存储管理(掌握)(不含动态链接)7. 段页式存储管理(掌握)第五章I./O设备的管理1. 设备管理的任务和功能(识记)2. 处理输入输出请求的步骤(了解)3. 输入输出控制系统(了解)4. 设备驱动程序(理解)5. 挂起队列的调度策略(理解0hsy2004 2004-6-22 02:53 回复:南昌大学计算机应用历年试题.南昌大学2001年攻读硕士学位研究生入学考试试题报考专业:计算机应用考试科目:数据结构(A)一. 选择题(每题选择一个答案, 将序号填入下划线处,每题2分,共10分)1. 假定初始序列是递增的,并且按递增序排列,则( )排序方法花时间最少.A.快速B. shellC.直接插入D.冒泡2. 二维数组a[0..8, 1..10]按行存放时元素a[ 8,5 ]的起始地址与按列存放时元素( )的起始地址相同.A. a [8,5]B. a [3,10]C. A[5,8]D. A[0,9]3. 有一棵平衡二叉树,根结点为A,A的右孩子为B,B的左孩为叶结点C,当A,B二结点的平衡因子分别为( )时,在结点C下, 插入一个新结点后得到的新树是不平衡的.A. 0,0B. 1,0C. –1,0D. 0,14.在循环链表中设立一个头结点的理由是( ).A.便于找到链表的首结点B.可以用头结点记录链表长度C.可以使得作插入,删去时不必顾及插入的或删去的结点是否链表的首结点.D.可以把首结点与尾结点公开5.非空的广义表可与有根有序的有向图对应,如果一个有根的有向图中含有回路,那么它对应的广义表是( )A.线性表B.纯表C.再入表D.递归表二.填空题(每题2分,共10分)1. 有20个元素的有序表按二分法查找,假定查找每个元素的概率是相等的,则查找成功的平均比较次数为________次.2. 链接栈的结点有二个域: info, link ,栈顶指针为st, 下列程序段可以把元素x压入栈内:.inf=x; ______; new(p); p3. 一个好的散列函数的标准是________________.4. 一个循环队列用数组Q[0..100]存贮其元素, 已知队头,队尾指针分别为80与50, 则当前队列中有_______个元素.5. 用200个不同的数来构造二叉排序树, 其高度不会超过_______,但也不会少于_______(假定空二叉树的高度为0).回复:南昌大学计算机应用历年试题.南昌大学2001年攻读硕士学位研究生入学考试试题报考专业:计算机应用考试科目:数据结构(A)四.算法设计题(共50分)1. 求带权有向图中每对结点之间的最短路径的Floyd算法如下:(1)(Path数组置初态)for I:= 1 to n dofor j:= 1 to n doif adj[I,j]< then path[I,j]:=(1)else path[I,j]:=(2);(2)(求最短路径)for k:= 1 to n dofor I:= 1 to n dofor j:= 1 to n doif adj[I,j]>adj[I,k]+adj[k,j] thenbegin adj[I,j]:=(3);path[I,j]:=(4) end请你解答如下问题(1)完成上述算法填空. (2)矩阵adj 的初值是什么?算法结束时,adj[I,j] 和path[I,j]的值表示什么意义?(14分)2. 写出按对放序线索化以t 为根指针的二叉树的非递归算法.假定用负指针表示线索,并且对栈的基本运算均可调用(12分)3. 写一算法,重排实型数组R[1..n]中元素的顺序,使得所有负数均排在非负数之前.(要求:不排序,附加空间0(1))(10分)4. 有一个带有头结点的循环双链表,表头指针为head,结点有四个域,data ,flreg ,llink ,rlink ,其中flreg记录结点数据的访问次数.假定链表的结点已按访问次数不增序排列.(1)画出此链表的结构示意图.(2)写一算法查找链表中是否有值为x的结点,如有,则让该结点的访问次数加1 ,并且要使链表仍保持不增序,如没有,则不作任何工作.(14分)4. 执行期间不允许中断,作为原语的程序段不允许并发执行.5. 发送进程名,接收进程名,数据,有关数据的操作6. 不同作业流7. 地址结构,寻址方式8. 互斥9. 地址由小到大, 分区由小到大, 分区由大到小10. 1911. 重定位(地址变换)三.1. 进程的调度功能:(1) 记录系统中所有进程的情况.(1分)(2) 选择占有处理机的进程.(1分)(3) 进行进程上下文的切换.(1分)优先数调度法是根据进程的优先级别俩进行调度的.一般分为静态优先数和动态优先数两种调度法.动态优先数是指随着时间的推移,要对各进程的优先数重新计算.动态优先数调度性能高,系统效率也较高.(2分)2. 设备管理程序的功能是:(1) 提供和进程管理系统的接口.(1分)(2) 进行设备的分配. (1分)(3) 实行设备和设备,设备和CPU之间的并行操作. (1分)(4) 进行缓冲区的管理. (1分)通过Spooling技术可将独享设备改为可共享的设备. (1分)3. (1)取出指令的有效地址.(2)根据作业的页大小或存储块的大小,计算该有效地址对应的页号和页内位移量.(3)通过页号到作业的页表中查到对应的块号.(4)通过块号和页内位移量计算有效地址所对应的内存物理地址.(5) 通过物理地址到内存取指令或取数.4. 作业调度主要的任务是按一定的原则对外存输入井上的大量后备作业时行选择,给选出的作业分配内存,输入输出设备等必要的资源,并建立相应的进程,以使该作业的进程获得竞争处理机的权利,同时还负责回收系统的资源.(2分)交换调度主要任务是按照给定的原则和策略,将处于外存交换区中的就绪状态或等待状态的进程调入内存,或把处于内存就绪状态或内存等待状态的进程交换到外存交换区.进程调度主要任务是按照某种策略和方法选取一个就绪进程占用处理机.(1分)(1) 属于进程调度一级(1分)(2) 属于交换调度一级(1分)5. 操作系统为用户提供了两类接口.一个是系统为用户提供的各种命令接口;另一个是系统调用. (1分)使用操作命令进行作业控制有两种方式:脱机方式和联机方式.脱机方式利用作业控制语言来编写表示用户控制意图的作业控制程序即作业说明书.联机控制方式是指用户使用系统提供的操作命令和系统会话,交互地控制程序执行和管理计算机系统.(2分)系统调用是操作系统提供给编程人员的唯一接口.编程人员利用系统调用,在源程序一级动态请求和释放系统资源,调用系统中已有的系统功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等.(2分)四. 第一个程序的使用顺序是按列进行的,所以缺页次数为256*256=65536次第二个程序的使用顺序与存储顺序一致,所以缺页次数为256次.(解释各1分,结论各2 分)hsy2004 2004-6-23 01:11 回复:南昌大学计算机应用历年试题.南昌大学2001年攻读硕士学位研究生入学考试试题报考专业:计算机应用考试科目:操作系统(A)参考答案五. 未分解的访盘次数为:一个盘块占1024div48=21个目录,所以256的目录要占256div21+1=13(块),平均访盘次数=(13+1)/2=7次.分解后: 一个盘块占1024div 8=128个目录,所以256个目录占256div 128=2个盘块.平均访盘次数=(1+2)/2+1=2.5次.一般地,若某个目录文件用N个盘块存放文件目录表目,必用M个盘块存放符号文件目录表目,则查找该目录文件中的一个文件目录表目而引起的访盘次数从(N+1)/2变为(M+1)/2+1.于是:当N-M>2时,访盘次数减少.当N-M=2时,访盘次数相等.当N-M<2时,访盘次数增加.六. (参考答案)定义三个信号量:(2分)S: 表示是否可以把数存入缓冲嚣,由于缓冲器中每次只能放一个数,所以它的初始值为”1”SO: 表示缓冲嚣中是否有奇数,初始值为”0”,表示无奇数.SE: 表示缓冲嚣中是否有偶数,初始值为”0”,表示无偶数.并发程序如下(类PASCAL语言描述)(8分)beginS ,SO ,SE : semaphore ;S:=1;SO:=0;SE:=0;CobeginProcess RX:intrger;beginL1: 从输入设备上读一个数:X:=读入的数;P(S);B:=x;If B=奇数then V(SO)Else V(SE);Goto L1;End;Process W1Y:intrger;beginL2: P(SO);Y:=B;V(S);打印y中数;Goto L2;End;Process W2Z:intrger;beginL3: P(SE);Z:=B;V(S);打印z中数;Goto L3;End;Coend;End;七. (参考答案)定义三个信号量:(3分)customers=0; //顾客等待服务的信号量barbers=0; //理发师等待顾客的信号量mutex=1; // 互斥信号量(对共享变量操作)一个计数共享变量(1分)waiting=0; 等待理发的顾客数一个常量CHAIRs表示椅子总数(1分)程序如下:(10分)Process barberbeginwhile true dobeginP(customers); 顾客数为零,则入睡 P(mutex); 进入临界区Waiting:=waiting-1; 减少顾客数 V(barbers); 理发师准备理发V(mutex);Cut_hair(); 理发End;End;Process customerbeginP(mutex); 进入临界区If (waiting<CHAIRs)beginWaiting=waiting+1; 增加等待的顾客数。