下载文档原格式
计算机系操作系统期终测验(2003年1月)姓名学号一填充题(每格1分，共19分)1程序的并发执行与顺序执行时相比产生了一些新特征，主要是___________________、___________________和___________________。
2 某进程运行时需打印结果，在计算时，进程处于_______态。
在打印时，进程处于_______态。
打印结束后，进程处于_______态。
3 系统产生死锁的主要原因是：________________和___________________。
4 I/O软件可以分成四层，从硬件开始依次为：___________________、________________、__________________和______________________。
5 分布式系统中的进程通信可分成：___________________和___________________。
6 操作系统安全性中，安全机制主要包括：___________________、_________________、____________________和__________________________。
7文件是一种_____________，它提供了一种把信息保存在磁盘上而且便于以后读取的方法。
二名词解释(每个2分，共16分)1实时操作系统2 访管指令3 工作集4直接文件5 中断装置6 LRU7吞吐率8 多CPU中的群调度三简答题(每个4分,共20分)1 若一个操作系统中的所有进程因各种原因进入等待状态，系统还能正常工作吗?说明理由。
2 试举一个日常生活中的例子，说明多线程结构进程可以进一步提高系统的并发性。
3 为什么说进程的互斥也是一种同步?4 试述多道程序设计的特点和优缺点。
5 简述高级通信原语和低级通信原语的主要异同。
计算题(每个5分,共25分)1一个有快表的请页式虚存系统，设内存访问周期为1微秒，内外存传送一个页面的平均时间为5ms。
操作系统期终测验参考答案(2005年1月)姓名学号一.填充题(3+1+2+1+1+2，共10分)1.批处理系统主要解决吞吐量问题，分时系统主要解决交互性问题,实时系统主要解决响应时间问题。
2.在操作系统中，有一种虚拟化技术叫SPOOLing ，它是用空间换取时间的资源转换技术。
3.设有8页的逻辑空间，每页1024字节，它们被映射到32个页框的物理存储区中。
那么，逻辑地址的有效位是13位，物理地址至少是15位。
4.每个索引文件都至少有一张索引表，其中，每个表项应包括能标识该记录的记录键和物理地址。
5.某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台。
当N的取值不超过5 时，系统不会发生死锁。
6.从操作系统的运行方式看，可以把它分成：非进程内核模型、OS功能（函数）在用户进程内执行的模型和OS功能（函数）作为独立进程执行的模型。
二.简答题(每个3分,共18分)1．I/0软件分为四个层次：用户I/O软件、与设备无关的OS I/O软件、设备驱动程序以及I/O中断处理程序。
试说明以下各个工作是在哪一层完成的？（1）向设备寄存器发写命令；（2）设备缓冲区管理（3）设备状态跟踪。
（4）检查用户是否有权使用设备；（5）处理设备I/O中发生的故障（6）将二进制整数转化成ASCII码以便打印。
解：(1)在设备驱动程序。
(2)、(3)和(4) OS I/O软件。
(5) I/O中断处理程序(6)用户层I/O软件。
2. 为什么要在设备管理中引入缓冲技术？操作系统如何实现缓冲技术？解：(1)调节CPU和I/O设备之间速度不匹配的矛盾例如，如果不设缓冲，则程序输出时由于打印机速度跟不上而使CPU停下来等待，而在CPU计算时，打印机又因无数据输出而闲置。
有了缓冲区，则程序可把输出数据预先输到缓冲区后继续运行，而打印机可从缓冲区取数慢慢打印，从而，CPU和I/O设备之间速度不匹配的矛盾得到缓和。
(2)实现I/O设备之间的并行操作类似地，可以开出多缓冲，每个对应于一个设备，实现I/O设备和I/O设备之间的并行操作(3)减少内外(I/O)交换次数开设缓冲区后可以实现成组和分解操作，既减少了内外(I/O)交换次数，又充分利用了外存空间。
大学计算机考试题目及答案pdf一、单项选择题（每题2分，共20分）1. 在计算机科学中，冯·诺依曼体系结构的主要特点是：A. 程序存储B. 程序控制C. 数据存储D. 数据控制答案：A2. 下列哪个选项不是计算机硬件的组成部分？A. CPUB. 内存C. 操作系统D. 硬盘答案：C3. 在计算机操作系统中，进程和线程的主要区别在于：A. 进程是程序的执行，线程是程序的运行B. 进程是程序的运行，线程是程序的执行C. 进程是资源分配的单位，线程是CPU调度的单位D. 进程是CPU调度的单位，线程是资源分配的单位答案：C4. 计算机网络中，TCP/IP协议属于：A. 传输层协议B. 网络层协议C. 应用层协议D. 链路层协议5. 在HTML中，用于创建无序列表的标签是：A. <ul>B. <ol>C. <li>D. <dl>答案：A6. 下列哪个选项是C语言中定义字符串的正确方式？A. char str[] = "Hello";B. char str[] = 'Hello';C. int str[] = "Hello";D. int str[] = 'Hello';答案：A7. 在关系数据库中，用于选择数据的SQL语句是：A. SELECTB. INSERTC. UPDATED. DELETE答案：A8. 下列哪个选项不是计算机病毒的特征？A. 传染性B. 破坏性C. 免疫性D. 潜伏性答案：C9. 在数据结构中，二叉树的深度为k时，其节点数最多为：B. 2^(k-1)C. kD. k+1答案：A10. 在计算机系统中，用于表示存储容量的单位GB代表：A. 吉字节B. 吉比特C. 千兆字节D. 千兆比特答案：A二、多项选择题（每题3分，共15分）11. 下列哪些是计算机软件的分类？A. 系统软件B. 应用软件C. 硬件D. 操作系统答案：ABD12. 在计算机系统中，下列哪些属于输入设备？A. 键盘B. 鼠标C. 显示器D. 打印机答案：AB13. 在计算机网络中，下列哪些协议属于传输层协议？A. FTPB. HTTPD. IP答案：C14. 在C语言中，下列哪些关键字用于定义数据类型？A. intB. charC. floatD. void答案：ABCD15. 在数据库管理系统中，下列哪些操作用于修改数据？A. SELECTB. INSERTC. UPDATED. DELETE答案：BCD三、简答题（每题5分，共20分）16. 简述计算机操作系统的主要功能。
一、填空题1．在页面置换算法中可实现的最有效的一种称为LRU。
2．在成组链结法中，将第一组的空闲块号和该组的空闲块数目记入到内存的工作栈中，作为当前可供分配的空闲盘块号。
3．现代操作系统的两个重要特征是并发和共享。
4．在动态分区式内存分配算法中，倾向于优先使用低地址部分空闲区的算法是首次适应算法；能使内存空间中空闲区分布较均匀的算法是循环首次适应算法。
5．在分时系统中，当用户数目为100时，为保证响应时间不超过2秒，此时时间片最大应为20ms。
分时系统采用的调度方法是时间片轮转调度算法。
6.常用的进程通信方式有管道、共享存储区、消息机制和邮箱机制。
7.正在执行的进程等待I/O操作，其状态将由执行状态变为阻塞状态。
8．页是信息的物理单位，进行分页是出于系统管理的需要；段是信息的逻辑单位，分段是出于用户的需要。
9．存储管理中的快表是指联想存储器。
10．分段保护中的越界检查是通过段表寄存器中存放的段表长度和段表中的段长等数据项。
11．在请求调页系统中的调页策略有预调入策略，它是以预测为基础的；另一种是请求调入，由于较易实现，故目前使用较多。
12．若干个事件在同一时刻发生称为并行，若干个事件在同一时间间隔内发生称为并发。
13．使用缓冲区能有效地缓和I/O设备和CPU之间速度不匹配的矛盾。
14．用户编写的程序与实际使用的物理设备无关，而由操作系统负责地址的重定位，我们称之为设备无关性（设备独立性）。
15．用户是通过命令方式或者程序接口向计算机发出请求的。
16．在操作系统中的异步性主要是指在系统中进程推进的顺序是走走停停。
二、选择题1.为了对紧急进程或重要进程进行调度，调度算法应采用（B）。
A.先进先出调度算法B.优先数法C.最短作业优先调度D.定时轮转法2、若一个系统内存有64MB，处理器是32位地址，则它的虚拟地址空间为（B）字节。
A.2GBB.4GBC.100KBD.64MB3．外存（如磁盘）上存放的程序和数据（B）。
2022年南京大学软件工程专业《操作系统》科目期末试卷B（有答案）一、选择题1、某进程访问页面的序列如下所示。
若工作集的窗口大小为6，则在t时刻的工作集为（）。
A.（6，0，3，2）B. （2，3，0，4）C.（0，4，3，2，9）D.（4，5，6，0，3，2）2、CPU输出数据的速度远远高于打印机的速度，为解决这一矛盾，可采用（）。
A.并行技术B.通道技术C.缓冲技术D.虚存技术3、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少为多少位？内存空间有多大（）？A.逻辑地址至少为12位，内存空间有32KBB.逻辑地址至少为12位，内存空间有16KBC.逻辑地址至少为15位，内存空间有32KBD.逻辑地址至少为15位，内存空间有16KB4、操作系统采用分页存储管理方式，要求（）。
A.每个进程拥有一张页表，且进程的页表驻留在内存中，B.每个进程拥有一张页表，但只要执行进程的页表驻留在内存中C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中D.所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中5、当系统发生抖动（Trashing）时，可以采取的有效措施是（）。
I.撤销部分进程 II.增大磁做交换区的容量 III.提高用户进程的优先级A. 仅IB.仅IIC.仅IIID.仅I,II6、用户程序在口态下使用特权指令引起的中断属于（）。
A.硬件故障中断B.程序中断C.外部中断D.访管中断7、实时操作系统必须在（）内处理完来白外部的事件。
A.一个机器周期B.被控对象规定时间C.周转时间D.时间片8、（）结构的文件最适合于随机存取的应用场合。
A.流式B.索引C.链接D.顺序9、下面关于文件的叙述中，错误的是（）。
I.打开文件的主要操作是把指定文件复制到内存指定的区域II.对一个文件的访问，常由用户访问权限和用户优先级共同限制III.文件系统采用树形片录结构后，对于不同用户的文件，其文件名应该不同IV.为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件A.仅IB. 仅I、IIIC.仅I、III、IVD.I、II、III，IV10、下列选项中，降低进程优先权级的合理时机是（）。
一、填空题1．计算机操作系统是方便用户、管理和控制计算机系统资源的系统软件。
2.在多道程序环境中，用户程序的相对地址与装入内存后的实际物理地址不同，把相对地址转换为物理地址，这是操作系统的地址重地位功能。
3．操作系的动态分区管理内存分配算法有首次适应算法、循环首次适应算法、和最佳适应算法。
4．动态存储分配时，要靠硬件地址变换机构实现重定位。
5．在存储管理中常用虚拟存储器方式来摆脱主存容量的限制。
6．在请求页式管理中，当硬件变换机构发现所需的页不在内存时，产生缺页中断信号，中断处理程序作相应的处理。
7．置换算法是在内存中没有空闲页面时被调用的，它的目的是选出一个被淘汰的页面。
如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。
1．在段页式存储管理系统中，面向用户的地址空间是段式划分，面向物理实现的地址空间是页式划分。
9．文件的存储器是分成大小相等的物理块，并以它为单位交换信息。
10．通道是一个独立于CPU的专管I/O的处理机，它控制设备与内存之间的信息交换。
11．缓冲区的设置可分为单缓冲、双缓冲、循环缓冲和缓冲池。
其中关于缓冲池的操作有提取输入、提取输出、收容输入和收容输出。
12．操作系统为用户编程所提供的接口是系统调用。
13．文件的逻辑结构分为流式文件、顺序文件、索引文件和索引顺序文件。
14．进程由程序、数据和PCB组成。
15．一张1.44M的软盘，其FAT表占的空间为2.16K。
16．缓冲池包括空白缓冲队列、装满输入数据的缓冲队列和装满输出数据的缓冲队列三种队列。
17．在生产者—消费者问题中，消费者进程的两个wait原语的正确顺序为Wait(full)；和wait(mutex);。
18．段式管理中，提供二维维的地址结构。
以段为单位进行空间分配，每段分配一个连续内存区。
19．逻辑设备表（LUT）的主要功能是实现逻辑设备到物理设备的映射。
20．进程间通信的方式有管道、共享存储区和消息传递方式。
考试科目名称操作系统（A卷）考试方式：闭卷考试日期年月日教师系（专业）年级班级学号姓名成绩一、解释题（每小题1.5分）1.管程2.低级调度3.缺页中断4.分时系统5.全局页面替换6.反置页表7.目录文件8.文件动态共享二、简答题（每小题3分）1．试简要描述一个作业生命周期所经历的各阶段。
2．试简要分析采用测试与建立指令(Test and Set)进行临界区管理的缺点。
3．什么是文件的逻辑结构，逻辑结构有几种形式？4．试分析Hoare方法实现的管程中，wait和signal操作是否需要实现为原语，为什么？5．一个典型的文本打印页面包含100行，每行160个字符。
设想某一台打印机每分钟可以打印24页，并且将字符写到打印机数据寄存器的时间很短以致可以忽略。
如果打印每个字符都会引起一次中断，而进行中断服务要花费总计50us的时间，那么采用中断驱动的I/O 编程方式来控制打印机有没有意义？三、计算题（小题4+5+5+5+5分）1．假定磁盘一个磁道有6个扇区，一个扇区正好存放文件的一个逻辑记录。
设文件F有6个逻辑记录（记为R0，R1，…，R5），依次存放在同一磁道上，磁盘驱动器的转速为12ms/周。
现有读取记录的请求序列如下：读R0，读R2，读R4，读R1，读R3，读R5。
试估算：1）以先来先服务驱动调度时，需要多长时间。
2）如果优化驱动调度算法，可以用多长时间完成。
2. 某个文件系统的物理结构如下描述：物理磁盘块的大小为1024个字节，每个磁盘块号占4 个字节，为应对系统中存在大量小文件和少量大文件的需要，现采用一种顺序结构和多重索引结构混合的物理结构实现方案，即每8个磁盘块为一组，作为基本的分配单位（磁盘块组编号同样占4个字节）。
每个盘块组对应一个索引项，索引表的固定为10项，编号为0-9，其中0-7项为直接索引项，直接指向对应的盘块组号；第8项为二级索引，第一级索引项指向存放中间索引表的物理磁盘块，该磁盘块中存放了直接指向文件存放内容的磁盘块组；第9项为三级索引，前两次索引项指向存放的中间索引表的磁盘块，最后一次索引表指向文件存放的磁盘块组。
2022年南开大学软件工程专业《操作系统》科目期末试卷B（有答案）一、选择题1、下列关于设备驱动程序的叙述中，正确的是（）。
I.与设备相关的中断处理过程是由设备驱动程序完成的II.由于驱动程序与I/O设备（硬件）紧密相关，故必须全部用汇编语言书写III.磁盘的调度程序是在设备驱动程序中运行的IV.一个计算机系统配置了2台同类绘图机和3台同类打印机，为了正确驱动这些设备，系统应该提供5个设备驱动程序A. 仅I、IIIB. 仅II、IIIC.仅I、III，IVD. I、II、III、IV2、用户程序发出磁盘I/O话求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。
其中，计算数据所在磁盘的柱面号、磁号、扇区号的程序是（）。
A.用户程序B.系统调用处理程序C.设备驱动程序D.中断处理程序3、若用8个字（字长32位，H字号从0开始计数）组成的位示图管理内存，用户归还一个块号为100的内存块时，它对应位示图的位置为（）（注意：位号也从0开始）。
A.字号为3，位号为5B.字号为4，位号为4C.字号为3，位号为4D.字号为4，位号为54、操作系统采用分页存储管理方式，要求（）。
A.每个进程拥有一张页表，且进程的页表驻留在内存中，B.每个进程拥有一张页表，但只要执行进程的页表驻留在内存中C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中D.所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中5、要保证一个程序在主存中被改变了存放位置后仍能正确地执行，则对主存空间应采用（）技术。
A.静态重定位B.动态重定位C.动态分配D.静态分配6、执行系统调用的过程包括如下主要操作：①返回用户态②执行陷入（trap）指令③传递系统调用参数④执行相应的服务程序正确的执行顺序是（）A.②->③->①->④B.②->④->③->①C.③->②->④->①D.③->④->②->①7、假设5个进程P0、P1、P2、P3、P4共享3类资源R1、R2、R3.这些资源总数分别为18、6、22。
2022年南昌大学数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、所谓（），是指将一个以上的作业放入内存，并且同时处于运行状态。
这些作业，共享处理器的时间和外设及其他资源。
A.多重处理B.多道程序设计C.实时处理D.并行执行2、计算机开机后，操作系统最终被加载到（）。
A.BIOSB.ROMC.EPROMD.RAM3、某计算机系统中有8台打印机，有K个进程竞争使用，每个进，程最多需要3台打印机，该系统可能会发生死锁的K的最小值是（）A.2B.3C.4D.54、在下列操作系统的各个功能组成部分中，一定需要专门硬件配合支持的是（）。
I.地址映射II.进程调度III.中断系统IV.系统调用A.IB.I、IIIC. I、III、IVD.II、II5、在支持多线程的系统中，进程P创建的若干个线程不能共享的是（）A.进程P的代码段B.进程P中打开的文件C.进程P的全局变量D.进程P中某线程的找指针6、系统管理设备是通过一些数据结构来进行的，下前的（）不属于设备管理数据结构。
A.FCBB.DCTC.SDTD.COCT7、在如下儿种类型的系统中，（）采用忙等待I/O是合适的。
a.专门用来控制单1/0设备的系统b.运行…个单任务操作系统的个人计算机，c.作为一个负载很大的网络服务器的上作站A.aB.a.bC.b.cD.c8、为支持CD-ROM小视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（）。
A.连续结构B.链式结构C.直接索引结构D.多级索引结钩9、现有一个容量为10GB的磁盘分区，磁盘空间以簇（Cluster）为单，位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空问，即用.位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为（）A.80B.320C.80KD.320K10、在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。
考试科目名称 操作系统 （A 卷）考试方式： 闭卷 考试日期2013 年 7 月 7 日 教师 骆斌、葛季栋 系（专业） 软件学院软件工程 年级 2011级 班级 学号 姓名 成绩一、 选择题（本题满分50分，每小题2分）1. 系统调用是_______。
A ．用户编写的一个子程序 B.高级语言中的库程序C. 操作系统中的一条命令D.操作系统向用户程序提供的接口2. 页面替换算法_______有可能会产生Belady 异常现象。
A.FIFO B.LRUC.OPTD.Clock3. 假设表格中所描述的两个进程(P 和Q)并发执行，其中，a 、b 、c 、d 、e 是原语，A．a,b,c,d,eB. a,b,d,e,cC. a,d,e,c,bD. a,b,d,c,e4. _____操作系统允许在一台主机上同时联接多台终端，多个用户可以通过各自的终端同时交互使用计算机。
A. 网络 B. 分布式 C. 分时 D. 实时5. 现有三个同时到达的作业J1、J2和J3，其执行时间分别为T1、T2和T3，且T1<T2<T3。
系统采用短作业优先算法，则平均周转时间是_______。
A. T1+T2+T3 B. (T1+T2+T3)/3 C.(T1+2T2+3T3)/3 D.(3T1+2T2+T3)/3 6. Unix 系统中，文件的索引结构存放在____ ____中。
A ．超级块 B.inode 节点 C.目录项 D.空闲块7. 采用________不会产生内部碎片。
A.分页式存储管理B.段页式C.固定分区式存储管理D.分段式存储管理8. 采用分段存储管理的系统，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是________。
A.224 B.232 C.228D. 2169. 在UNIX 系统中运行以下程序，最多可再产生出____个进程?画出进程家属树。
main( ){fork( ); /*←pc(程序计数器)，进程A fork( ); fork( ); }A ．9 B.7 C.5 D.310. Linux 系统中的slab 分配器，采用____内存管理方式。
考试科目名称 操作系统 （A 卷）考试方式： 闭卷 考试日期2013 年 7 月 7 日 教师 骆斌、葛季栋 系（专业） 软件学院软件工程 年级 2011级 班级 学号 姓名 成绩一、 选择题（本题满分50分，每小题2分）1. 系统调用是_______。
A ．用户编写的一个子程序 B.高级语言中的库程序C. 操作系统中的一条命令D.操作系统向用户程序提供的接口2. 页面替换算法_______有可能会产生Belady 异常现象。
A.FIFO B.LRUC.OPTD.Clock3. 假设表格中所描述的两个进程(P 和Q)并发执行，其中，a 、b 、c 、d 、e 是原语，A．a,b,c,d,eB. a,b,d,e,cC. a,d,e,c,bD. a,b,d,c,e4. _____操作系统允许在一台主机上同时联接多台终端，多个用户可以通过各自的终端同时交互使用计算机。
A. 网络 B. 分布式 C. 分时 D. 实时5. 现有三个同时到达的作业J1、J2和J3，其执行时间分别为T1、T2和T3，且T1<T2<T3。
系统采用短作业优先算法，则平均周转时间是_______。
A. T1+T2+T3 B. (T1+T2+T3)/3 C.(T1+2T2+3T3)/3 D.(3T1+2T2+T3)/3 6. Unix 系统中，文件的索引结构存放在____ ____中。
A ．超级块 B.inode 节点 C.目录项 D.空闲块7. 采用________不会产生内部碎片。
A.分页式存储管理B.段页式C.固定分区式存储管理D.分段式存储管理8. 采用分段存储管理的系统，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是________。
A.224B.232C.228D. 2169. 在UNIX 系统中运行以下程序，最多可再产生出____个进程?画出进程家属树。
main( ){fork( ); /*←pc(程序计数器)，进程A fork( ); fork( ); }A ．9 B.7 C.5 D.310. Linux 系统中的slab 分配器，采用____内存管理方式。
2013南大计算机真题科目代码：845 满分：150一、单选（40题，每题2分，共80分）1、下面关于线性表的叙述中，不正确的是（）I线性表在链式存储时，查找第i个元素的时间同i的值成正比II线性表在链式存储时，查找第i个元素的时间同i的值无关III线性表在顺序存储时，查找第i个元素的时间同i的值成正比IV线性表在顺序存储时，查找第i个元素的时间同i的值无关A. I,IIB.II,IIIC.III,IVD.I,IV2、对n个关键码进行直接选择排序，在原关键码已经有序的情况下，关键码的比较次数为（）A.nB.n-1C.n(n-1)/2D.n(n-1)3、引入二叉线索树的目的是（）A.加快查找结点的前驱和后继的进度B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一4、可以判断出一个有向图是否有环（回路）的方法是（）A.深度优先遍历B.广度优先遍历C.求最短路径D.拓扑排序5、在哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）A.n-1B.n+1C.2n-1D.2n+16、下面关于广义表的说法中，不正确的是（）A.广义表的表头总是一个原子B.广义表的表尾总是一个广义表C.广义表适宜用链表存储结构D.广义表可以是一个多层次的结构7、具有n个关键字的有序表，折半查找的平均查找长度为（）A.O(n)B.O(n*n)C.O(log2 n)D.O(nlog2 n)8、哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k 个关键字对应的记录存入哈希表中，至少要进行的探测次数为（）A. k-1B.kC.k+1D.k（k+1）/29、数组A[0..6，0..9]的每个元素占2个字节，将其按列优先次序存储在起始地址为100的内存单元中，则元素A[7，8]的地址是（）A.210B.226C.234D.25610、一棵具有125个结点的完全二叉树的树高度（空树的高度为0）是（）A.5B.6C.7D.811、下面关于m阶B树说法中，正确的是（）I每个结点至少有两棵非空子树II树中每个结点至多有m-1个关键字III所有叶子在同一层IV当插入一个数据项引起B树结点分裂后，树长高一层A.I,II,IIIB.II,IIIC.II,III,IVD.I,IV12、某程序P由一个100条指令构成的循环程序段组成，该循环程序段共被执行200次，在计算机M中执行程序P用了40 000个时钟周期，M的主频为500MHz，则M在执行程序P时的MIPS数是（）A.0.5B.2C.250D.100013、已知float型变量采用IEEE 754单精度浮点标准表示。
NJU2013年计算机科学与技术基础试卷与答案科目名称：计算机科学与技术基础（算法导论、软件方法、操作系统、数据库）一、简单描述Quicksort算法的原理与过程。
概述（即给出结果和理由，不需要严格的数学证明）最坏情况以及平均情况的时间复杂性分析。
（15分）算法参考网址：（1）/xwdreamer/archive/2011/06/15/2297000.html（2）/feliciafay/article/details/6042034（3）/morewindows/archive/2011/08/13/2137415.html（4）算法演示：/kecheng1/site01/suanfayanshi/list.asp?id=71. Quicksort算法的原理Quicksort算法是由冒泡排序算法改进而得到的，其基本原理是：（1）在待排序的n个元素中任选一个元素作为基准（pivot），然后对数组a[n]进行分区操作，通过一趟排序之后将数组a[n]分割为独立的两部分，使得基准左边元素的值都不大于基准值、基准右边元素的值都不小于基准值，这时作为基本的元素排在这两部分的中间，并使得作为基准的元素调整到排序后的正确位置（或称为记录归位）。
（2）完成一趟快速排序之后，可采用递归方法对所得的两部分子数组分别重复上述快速排序，直至每部分内只有一个元素或元素为空为止，这时每个数组元素都将被排在正确的位置，整个数组达到有序。
因此，快速排序算法的核心是分区操作，即调整基准元素的位置以及调整调整返回基准的最终位置以便分治递归。
2. Quicksort算法的过程一趟快速排序的算法是：（1）设置两个变量start 、end ，排序开始的时候：start=1，end=N ；（2）以第一个数组元素作为关键数据，赋值给pivot ，即 pivot=arry[1]；（3）从end 开始向前搜索，即由后开始向前搜索（end--），找到第一个小于pivot 的值arry[end]，并与arry[start]交换,即swat(arry,start,end)；（4）从start 开始向后搜索，即由前开始向后搜索（start++），找到第一个大于pivot 的arry[start]，与arry[end]交换,即swat(arry,start,end);（5）重复第3、4步，直到 start=end ，这个时候arry[start]=arry[end]=pivot ，而pivot 的位置就是其在整个数组中正确的位置；（6）通过递归，将问题规模不断分解。
2022年南京大学软件工程专业《操作系统》科目期末试卷A（有答案）一、选择题1、一个多道批处理系统中仅有P1，和P2两个作业，P2比P1晚5ms到达。
它们的计算和I/O操作顺序如下：P1：计算60ms，I/O 80ms，计算20msP2：计算120ms，I/O 40ms，计算40ms。
若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。
A.240msB.260msC.340msD.360ms2、下列关于批处理系统的叙述中，正确的是（）I.批处理系统允许多个用户与计算机直接交互II.批处理系统分为单道批处理系统和多道批处理系统III.中断技术使得多道批处理系统的1/O设备可与CPU并行工作A.仅II、IIIB.仅IIC.仅I、IID. 仅I、III3、有5个批处理任务A、B、C、D、E几乎同时到达一计算中心。
它们预计运行的时间分别是10min，6min，2min、4min和8min。
其优先级（由外部设定）分别为3，5，2，1和4，这里5为最高优先级。
下列各种调度算法中，其平均进程周转时间为14min的是（）。
A.时间片轮转调度算法B.优先级调度算法C.先来先服务调度算法D.最短作业优先调度算法4、下面所列进程的3种基本状态之间的转换不正确的是（）A.就绪状态→执行状态B.执行状态→就绪状态C.执行状态→阻塞状态D.就绪状态→阻塞状态5、在下述父进程和子进程的描述中，正确的是（）A.父进程创建了子进程，因而父进程执行完后，子进程才能运行B.父进程和了进程可以并发执行C.撤销了进程时，应该同时撤销父进程D.撤销父进程时，应该同时撤销子进程6、用户程序发出磁盘1/0请求后，系统的正确处理流程是（）A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序7、下列天于管道（Pipe）通信的叙述中，正确的是（）A.一个管道可实现双向数据传输B.管道的容量仅受磁盘容量大小限制C.进程对管道进行读操作和写操作都可能被阻塞D.一个管道只能有一个读进程或一个写进程对其操作8、若文件f1的硬链接为f2，两个进程分别打开fl和f2，获得对应的文件描述符为fd1和fd2，则下列叙述中，止确的是（）I.fl和f2的读写指针位置保持相同II.fl和f2共享同个内存索引节点III.fdl 和fd2分别指向各自的用户打开文件表中的一项，A.仅IIB. 仅II、IIIC.仪I、IID. I、II和II9、驱动调度算法中，（）算法可能会随时改变移动臂的运动方向。
操作系统期终测验参考答案（2005年1月）二•简答题（每个3分，共18分）1. I/O 软件分为四个层次：用户I/O 软件、与设备无关的0S I/O 软件、设备驱 动程序以及I/O 中断处理程序。
试说明以下各个工作是在哪一层完成的？ （1） 向设备寄存器发写命令； （2） 设备缓冲区管理 （3） 设备状态跟踪。
（4） 检查用户是否有权使用设备； （5） 处理设备I/O 中发生的故障（6） 将二进制整数转化成ASCII 码以便打印。
解：（1）在设备驱动程序。
（2）、（3）和（4） OS I/O 软件。
（5） I /O 中断处理程序（6） 用户层I/O 软件。
2. 为什么要在设备管理中引入缓冲技术？操作系统如何实现缓冲技术？W-：（I ）调节CPU 和I/O 设备之间速度不匹配的矛盾 例如，如果不设缓冲，则程序输出时 由于打印机速度跟不上而使CPU 停下来等待，而在CPU 讣算时，打印机又因无数据输出而 闲宜。
有了缓冲区，则程序可把输岀数据预先输到缓冲区后继续运行，而打印机可从缓冲区 取数慢慢打印，从而，CPU 和"O 设备之间速度不匹配的矛盾得到缓和。
（2）实现I/O 设备之间的并行操作 类似地，可以开出多缓冲，每个对应于一个设备， 实现I/O 设备和I/O 设备之间的并行操作(3)减少内外(I/O)交换次数开设缓冲区后可以实现成组和分解操作，既减少了内外(I/O) 交换次题号—•三四五得分小计姓名学号（3+1+2+1+1+2,共 10 分） 1. 批处理系统主要解决乔吐量问题,分时系统主要解决交互性问题,实时系 统主要解决响应时间问题。
2. 在操作系统中，有一种虚拟化技术叫SPOOLing ,它是用空间换取时间的 资源转换技术。
3. 设有8页的逻借空间，每页1024字节，它们被映射到32个页框的物理存储区中。
那么，逻辑地址的有效位是旦位，物理地址至少是q 位。
4. 每个索引文件都至少有一张索引表，苴中，每个表项应包括能标识该记录的记录键 和物理地址。
南京大学计算机科学与技术系操作系统期末试卷（2003年12月28）一、简答题1、列出I/O控制方式。
2、列出文件的共享方式。
3、列出几种实时调度算法。
4、列举系统发生死锁的必要条件。
5、虚拟存储器的容量与什么有关?6、列出可变分区搜索分配算法。
7、列出影响缺页中断率的主要因素。
8、列出管程的主要特性。
二、问答题1、假设有一个操作系统采用层次结构组成，它运行在裸机上，并有以下层次组成：作业管理、设备管理、内存管理、命令管理、文件管理、进程调度及内核支撑功能，试给出一种由底向上的正确层次。
2、试从资源管理的观点，叙.述操作系统的功能和任务。
3、叙述操作系统中引入”进程”和”线程”的主要目的。
4、叙述进程通信及其分类。
5、叙述SPOOLING系统的技术特点、组成和数据结构。
6、叙述内存映射文件的基本原理和优点。
7、解释微内核与单内核操作系统，说明微内核结构设计的主要优点。
8、来自处理器和主存内部的中断称“异常”，列举它的分类及主要区别?三、计算题1、如果一个操作系统采用LFU页面置换算法的一个变种：每个页框对应一个计数器，用来计数曾经装入过一个页框的页面个数，当有多个候选淘汰页面所在的页框计数器具有相同的最小值时，按FIFO进行。
现在有一个进程分到了4个页框，则对如下页面走向求出缺页中断次数及淘汰的页号。
1 , 2 , 3 ,4 , 5 ,3 , 4, 1, 6,7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 7, 22、假定在某移动臂磁盘上，刚刚处理了访问38号柱面的请求，目前正在40号柱面读信息，并且有下述请求序列等待访问磁盘。
试分别使用电梯调度算法和最3、某多道程序设计系统供用户使用的主存为100K，磁带机2台，打印机1台。
采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。
现有作业序列如下：作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU时间。
2022年南京师范大学计算机科学与技术专业《操作系统》科目期末试卷B（有答案）一、选择题1、某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为1024B.每个盘块索引号占用4B，请问在该文件系统中，最大文件的大小最接近的是（）A.8GBB.16GBC.32GBD.2TB2、位示图可用于（）A.实现文件的保护和保密B.文件目录的查找C.磁盘空间的管理D.主存空间的共享3、有若干并发进程均将一个共享变量count的值加1 次，那么有关count中的值说法正确的是（）。
1）肯定有不止确的结果2）肯定有止确的结果3）若控制这些并发进程互斥执行count加1操作，count中的值正确A.1）和3）B.2）和3）C.3）D.1）、2）、3）的说法均不正确4、在多进程的系统中，为了保证公共变量的完整性，各进程应互斥进入临界区。
所谓临界区是指（）。
A.一个缓冲区B.一段数据区C.同步机制D.一段程序5、进程和程序的本质区别是（）A.前者分时使用CPU，后者独占CPUB.前者存储在内存，后者存储在外存C.前者在一个文件中，后者在多个文件中D.前者为动态的，后者为静态的6、假定有个请求分页存储管理系统，测得系统各相关设备的利用率为：CPU为10%，磁盘交换区为99.7%：其他1/O设备为5%。
试问：下面（）措施可能改进CPU的利用率？I.增大内存的容量II.增人磁盘交换区的容量III.减少多道程序的度数IV.增加多道程序的度数V.使用更快速的磁盘交换区VI.使用更快速的CPUA.I、II、III、IVB.I、IIC.II、III、VD. II、VI7、下面有关外层页表的叙述中错误的是（）。
A.反映在磁盘上页面存放的物理位置B.外层页表是指页表的页表C.为不连续（离散）分配的页表再建立一个页表D.若有了外层页表，则需要一个外层页表寄存器就能实现地址变换8、下列选项中，操作系统提供给应用程序的接口是（）。
A.系统调用B.中断C.库函数D.原语9、下列选项中，会导致用户进程从用户态切换到内核态的操作是（）I.整数除以零 II.sin函数调用 III.read系统调用A.仅I、IIB.仅I、IIIC.仅II、IIID. I、II和II10、某进程的段表内容见表，当访问段号为2、段内地址为400的逻辑地址时，进行地址转换的结果是（）。
南京大学数学系操作系统试卷参考答案学号姓名专业年级日期得分一、单项选择题1、通常把操作系统看作是一种(1) 软件。
(1) 系统(2) 支援(3) 维护(4) 应用2、对出现的中断事件是由(1) 进行处理的。
(1) 操作系统(2) 硬件(3) 用户程序(4) 解释程序3.. (2) 中断事件是不应该屏蔽的。
(1) 程序(2) 访管(3) 时钟(4) 输入输出4、分页式存储管理中，地址转换工作是由(1) 完成的。
(1) 操作系统(2) 硬件(3) 编译程序(4) 应用程序5、采用固定分区方式管理主存时，每个分区的大小是(3) 。
(1) 一致的(2) 随作业个数而变化(3) 可以不同但预先固定(4) 可以不同但根据作业长度固定6、采用多道程序设计能(3) 。
(1) 缩短每道程序的执行时间(2) 增加平均周转时间(3) 提高并发挥并行能力(4) 降低对处理机调度的要求7、一个作业一般可以分成几个必须顺序处理的工作步骤，而这些工作步骤是由(4) 。
(1) 操作系统规定(2) 编译系统规定(3) 装入程序规定(4) 用户指定8、磁盘是共享设备，因此，每一时刻(4) 进程与它交换信息。
(1) 可有任意多个(2) 限定几个(3) 可以不同(4) 最多有1个9、采用树形目录结构后，不同用户对同一个文件定义的文件名(3) 。
(1) 应该相同(2) 不能相同(3) 可以不同(4) 应该不同10、若用户总是要求用随机存取方式查找文件记录时，则采用索引结构比采用链接结构(2) 。
(1) 困难(2) 方便(3) 一样(4) 有时方便有时困难11、进程的并发(并行)执行是由(1) 引起的。
(1) 多道程序设计(2) 进程状态变化(3) 资源不足(4) 调度策略12、一个等待分配处理机的进程，它的状态应该是(2) 。
(1) 等待(2) 就绪(3) 运行(4) 任意13、使用PV操作后(1) 系统死锁。
(1) 仍可能出现(2) 不会出现(3) 能检测(4) 能解除14、不同的进程它们所包含的程序(2) 。
(1) 必定不同(2) 可以相同(3) 应该相同(4) 应该不同15、分时系统对响应时间性要求比实时系统(1) 。
(1) 低(2) 高(3) 严格(4) 一样二、填空题1、由于硬件采用了中断技术和通道技术使得中央处理机（CPU）与各种外设具有了并行工作的能力。
2、一个用高级语言编写的用户作业，在计算机上运行时一般要分成三个作业步，第一步先进行编译，第二步进行连接装配，第三步进行执行后就产生作业执行结果。
3、操作系统是用PCB 标识进程的存在和记录进程的有关信息。
4、系统中存在多个进程时，这些进程对资源的使用存在着不同的相互制约关系，制约关系可归结为两种，一种是互斥(竞争) 关系，另一种是同步(协作) 关系。
5、如果要保证任何时刻都是最高优先级进程在处理机上运行，那么，应该采用优先权调度算法进行进程调度。
6、采用动态重定位可变分区管理技术，硬件一定要提供地址重定位和保护作为支持。
7、为了管理系统中的外围设备，往往对每一台设备事先确定一个编号，以识别各台设备，这些编号称为设备的物理号；而用户在请求使用设备时，由用户给出的编号称设备的逻辑号。
8、当用户已经读取了磁盘上的某个文件信息后，认为该文件不必再保存了。
那么，他可以先调用关闭文件操作，然后再调用撤销文件操作。
这时，系统会将该文件撤消。
三、简答题1、操作系统中为什么要引入“进程”概念？在多道程序环境下，程序可以并发执行，一个程序的任意两条指令之间都可能发生随机事件而引发程序切换。
因而，每个程序的执行都可能不是连续的。
此外，程序的并发执行又引起了资源共享和竞争的问题，造成了各并发执行的程序间可能存在制约关系，程序和计算不再一一对应。
系统需要一个既能描述程序动态执行过程，又能用来共享资源的一个单位，操作系统引入的这个单位就是进程。
2、什么叫文件的存储结构？用户组织的逻辑上的文件以不同方式保存到物理存储设备的存储介质上去，所以，文件的物理存储结构是指逻辑文件在物理存储空间中的存放方法和组织关系。
有两类方法可用来构造文件的物理存储结构。
第一类称计算法，如直接寻址文件、计算寻址文件，顺序文件等。
第二类称指针法，如索引文件、索引顺序文件、连接文件、倒排文件等。
3、叙述记录的成组和分解操作。
文件的若干个逻辑记录合并成一组，写入到磁盘上的一个物理块中叫记录成组，成组操作一般先在输出缓冲区内进行，凑满一块后才将缓冲区内的信息写到存储介质上。
反之，当存储介质上的一个物理记录读进输入缓冲区后，把文件的逻辑记录从块中分离出来的操作叫记录的分解。
记录的成组和分解操作不仅节省存储空间，还能减少输入输出操作次数，从而，提高系统效率。
4、文件目录的表目中应包含哪些基本内容？文件目录的表目又称文件控制块FCB(File Control Block)，一般应该包括以下内容：●有关文件存取控制的信息：如文件名、用户名、文件主存取权限、授权者存取权限：文件类型和文件属性，如读写文件、执行文件、只读文件等。
●有关文件结构的信息：文件的逻辑结构，如记录类型、记录个数、记录长度、成组因子数等。
文件的物理结构，如文件所在设备名，文件物理结构类型，记录存放在外存的相对位置或文件第一块的物理块号，也可指出文件索引的所在位置等。
●有关文件使用的信息：已打开该文件的进程数，文件被修改的情况，文件最大和当前大小等。
有关文件管理的信息：如文件建立日期、文件最近修改日期、文件访问日期、文件保留期限、记帐信息等。
有了文件目录后，就可方便地实现文件的“按名存取”。
5、在进行作业调度时，经常会采用短作业优先调度算法和最高响应比优先调度算法，指出这两种算法各自的优点。
短作业优先SJF算法是以进入系统的作业所要求的CPU时间长短为标准，总是选取估计计算时间最短的作业投入运行。
SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS 好。
响应比最高者优先算法既考虑作业等待时间，又考虑作业的运行时间，这样既照顾了短作业又不使长作业的等待时间过长，改进了调度性能，使作业”饥饿”现象不会发生。
6、组成操作系统的构件有哪些？简单说明之。
通常把组成操作系统程序的基本单位称作操作系统的构件。
构成操作系统的基本单位除内核之外，主要有进程、线程和管程。
内核不是进程，它对硬件处理器及有关资源进行首次改造，是为进程运行提供基本功能和基本操作支持的一组程序模块，有了内核的支撑，进程运行环境得到改善，安全性得到保证，系统效率就能提高。
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。
是操作系统进行资源分配和多道程序管理的基本单位。
由于它既能描述程序动态执行过程，又能解决系统资源的共享性问题。
所以，操作系统很早就引入多进程的概念。
线程是在进程内部划分的更小的执行和调度单元，这些单元共享进程资源以便于通信和切换，降低系统的时空开销。
管程是管理共享资源的一种同步机制，它使得原来分散在进程中的临界区集中了起来统一控制和管理，方便了对共享资源的使用，对管程的调用表示对共享资源的请求与释放。
由于管程的引入，使并发进程之间的相互作用更为清晰，更容易编写出正确的并发程序。
四、应用题假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息，(2) 最短寻找时间优先算法分别列出实际处理上述请求的次序。
答：(1)电梯调度算法查找次序为：80、90、102、160、188、190、58、40、32，查找总柱面数为：268。
(2)最短查找优先查找次序为：80、90、102、58、40、32、160、188、190，查找总柱面数为：250。
五、进程同步1、用PV操作为工具，正确解决五个哲学家吃通心面问题。
var fork i :array[0..4] of semaphore;fork i := 1;cobeginprocess Pi // i=0,1,2,3beginL1:思考;P(fork[i]); //i=4 P(fork[0])P(fork[i+1] mod 5); P(fork[4])吃通心面;V(fork[i]);V(fork[i+1] mod 5);goto L1;end;coend.2、假定有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数，当缓冲器中无数时，进程R可以把从输入设备上读入的数存放在缓冲器B中，若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。
同时规定：进程R必须等缓冲器中的数被取出后才能再存入一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空的缓冲器中取数。
请用管程实现正确管理。
解:TYPE R-W1-W2=MONITORVAR buf:integer;SW1,SW2,SR:codition;int SW1_count,SW2_count,SR_count;turn:{p,q,r};DEFINE RPUT,W1GET,W2GUT;USE wait,signal,check,release;procedure RPUT(var data:integer;);begincheck(IM);if turn !=p then wait(SR, SR_count ,IM);buf:=data;if data/2=1 then turn:=q;signal(SW1, SW1_count,IM);else turn:=r; signal(SW2,IM);release(IM);endprocedure W1GET(var data:integer;);begincheck(IM);if turn !=q tnen wait(SW1, SW1_count,IM)data:=buf;turn:=p;signal(SR, SR_count ,IM)release(IM);endprocedure W2GET(var data:integer;);begincheck(IM);if turn !=r tnen wait(SW2, SW2_count,IM);data:=bufturn:=p;signal(SR, SR_count ,IM);release(IM);endbeginSR:=0;SW1:=0;SW2:=0;turn:=p;endmain(){ cobeginprocess Rx:=integer;beginLP:从文件读入一个数据到x;PPUT(x);goto LP;endprocess W1x:=integer;beginLQ:W1GET(x);打印奇数x;goto LQ;endprocess W2x:=integer;beginLR:RGET(x);打印偶数x;goto LR;end}coend。
