下载文档原格式
张顺全计算机操作系统模拟试题（二）张顺全一、选择题（红色数字、符号是答案。
笔67－16）1. 在分时系统中，导致创建进程的典型事件是A 2；在批处理系统中导致创建进程的典型事件是B 2；由系统专门为运行中的应用进程创建新进程的事件是C 4。
（汤’165题5、汤’204）A：⑴用户注册⑵用户登录⑶用户记账⑷用户通信B：⑴作业录入⑵作业调度⑶进程调度⑷中级调度C：⑴分配资源⑵进程通信⑶共享资源⑷提供服务2. 从下面对临界资源的论述中，选出一条正确的论述，并在其前面打“√”。
（汤’165题6）⑴临界区是指进程中用于实现进程互斥的那段代码⑵临界区是指进程中用于实现进程同步的那段代码⑶临界区是指进程中用于实现进程通信的那段代码⑷临界区是指进程中用于访问共享资源的那段代码√⑸临界区是指进程中访问临界资源那段代码3. 在生产者－消费者问题中，应设置互斥信号量Mutex、资源信号量full和empty。
它们的初始值应分别是A 2、B 1和C 5。
（汤’165题9）A、B、C：⑴0 ⑵1 ⑶－1 ⑷－n ⑸+n4. 从下面预防死锁的论述中，选出一条正确的论述，并在其前面打“√”。
（汤’166题16、汤’204、汤六122－4）⑴由于产生死锁的基本原因是系统资源不足，因而预防死锁的有效方法，是根据系统规模，配置足够的系统资源⑵由于产生死锁的另一基本原因是进程推进顺序不当，因而预防死锁的有效方法，是使进程的推进顺序合法⑶因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的有效方法，是防止系统进入不安全状态√⑷可以通过破坏产生死锁的四个必要条件之一或其中几个的方法，来预防发生死锁5. 根据作业说明书中的信息对作业进行控制，称此种作业为A 4；用终端键盘命令直接控制作业运行的作业称为B 1。
（汤’170题1、笔67－17）A：⑴计算型作业⑵终端型作业⑶联机作业⑷脱机作业B：⑴联机作业⑵I/O型作业⑶批处理作业⑷脱机作业6. 作业由进入状态转变为后备状态，是由A 3完成的，由后备状态到运行状态B 2完成的。
2012操作系统复习大全2012.6.1概念题操作系统：是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。
多道程序设计：目的是为了进一步提高资源的利用率和系统吞吐量，采用后备队列，用户所提交的作业都先存放在外存上并排成一个队列，作业调度程序按一定算法从后备队列中选择若干个作业调入内存使它们共享CPU和系统中的各种资源。
微内核操作系统：足够小的内核、基于CS模式、应用“机制与策略分离”原理、采用面向对象技术的一种操作系统。
进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
管程：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
原语：由若干条指令组成，完成一定功能的一个过程。
是一种原子操作（Atomic Operation）。
所谓原子操作，是指一个操作中所有动作要么全做，要么全不做。
它是一个不可分割的基本单位，因此在执行过程中不允许被中断。
原子操作在管态下执行，常驻内存。
临界区：每个进程中访问临界资源的那段代码。
死锁：指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
死锁定理：S为死锁状态的充要条件是：当且仅当S状态的资源分配图是不可完全简化的。
该充要条件称为死锁定理。
虚拟存储器：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。
重定位：装入时对目标程序中指令和数据地址的修改过程。
静态重定位：地址变换通常是在装入时一次完成的，以后不再改变的重定位。
动态重定位：地址转换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。
紧凑：通过移动内存中的作业位置，以把原来多个分散的小分区拼接成一个大分区的方法，也叫“拼接”。
操作系统期末试题（A）卷课程名称《操作系统》任课教师签名出题教师签名审题教师签名考试方式（闭）卷适用专业计算机各专业考试时间（120 ）分钟一、单项选择题(每小题2分，共30分)1. 操作系统是对进行管理的软件。
A．软件 B．硬件 C．计算机资源 D．应用程序2. 实时操作系统必须在_______内完成来自外部的事件。
A．响应时间 B．周转时间 C．规定时间 D．调度时间3. 设有四个作业同时到达,每个作业的执行时间均为2小时,它们在一台处理机上按单道方式运行,则平均周转时间为。
A. 1小时B. 5小时C. 25小时D. 8小时4. 如果分时操作系统的时间片一定，那么则响应时间越长。
A．用户数越少 B．用户数越多 C．内存越少 D．内存越多5. 解决“碎片”问题最好的存储管理方法是。
A. 页式管理B. 段式管理C. 固定分区管理D. 可变分区管理6. 下列算法中用于磁盘移臂调度的是。
A. 时间片轮转法 B. LRU算法C. 最短寻道时间优先算法D. 优先级高者优先算法7. 为记录设备的情况，系统为每一类设备配置一张。
A. 系统设备表B. 设备控制表C. 逻辑设备表D. 设备开关表8. 进程从运行状态进入就绪状态的原因可能是。
A. 被选中占有处理机B. 等待某一事件C. 等待的事件已发生D. 时间片用完9. 进程控制块是描述进程状态和特性的数据结构，一个进程。
A.可以有多个进程控制块B.可以和其他进程共用一个进程控制块 C.可以没有进程控制块 D.只能有惟一的进程控制块10. 一作业9:00到达系统,估计运行时间为1小时。
若11:00开始执行该作业,其响应比是。
A. 2B. 1C. 3D. 0.511. 在动态分区分配方案中,某一作业完成后,系统收回其主存空间,并与相邻空闲区合并,为此需修改空闲区表,造成空闲区数减1的情况是。
A.无上邻空闲区,也无下邻空闲区B.有上邻空闲区,但无下邻空闲区C.有下邻空闲区,但无上邻空闲区D.有上邻空闲区,也有下邻空闲区12. 在一个单处理机系统中，若有5个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有个。
※特别章外部排序（2012版《数据结构高分笔记》更新补丁）·外部排序简介所谓外部排序，即对外存中的数据进行排序（相对于内部排序而言），也可以说是对文件中的数据进行排序。
有了内部排序算法，为什么还要外部排序？因为文件太大，内存放不下。
外排做法可以概括为一句话：将内存作为工作空间来调整外存中数据的位置。
具体可以分成以下三个要点：①文件在外存中的组织；②文件在内存中的排序；③文件在内外存之间的交换。
说明：本补丁是2012年数据结构考研大纲新增内容，虽然知识点不多，但由于第一年被列入考试范围，所以大家要重视。
·归并排序法归并排序法是外排序中最常用的方法，分为两个执行阶段。
第一阶段：将文件中的数据分段输入到内存中，在内存中用内排序方法对其分类，这样排序完的文件段称作归并段，然后将其写回外存中而在外存中形成了许多初始归并段。
第二阶段：对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。
说明：外排序中的归并排序法和内排序中的归并法是类似的，都是由小单元逐渐归并成单元的过程，注意对比，加深理解。
归并排序算法分两个阶段：1.初始归并段的形成其过程是根据缓冲区大小，由文件输入（由外存读入内存）记录，当记录充满缓冲区后，选择最小的（以递增排序为例）记录输出（由内存写出到外存），其空缺位置由下一个输入记录来取代，输出的记录成为当前初始归并段的一部分。
如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前部分归并段最大的记录要小（如例1中的关键字11，比15要小，不可能出现在当前归并段中），它将等待生成下一个归并段时提供选择。
反复进行上述操作，直到所有新输入的记录关键字都小于最后输出记录的关键字时（如步骤9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。
接着继续生成下一个归并段，直到全部记录都处理完毕为止。
第一章绪论大纲要求（一）操作系统的概念、特征、功能和提供的服务（二）操作系统的发展与分类（三）操作系统的运行环境１．内核态与用户态２．中断、异常３．系统调用（四）操作系统体系结构考点与要点分析核心考点1、（★★）操作系统的基本概念：操作系统的功能、特征和层次结构。
2、（★）操作系统的发展过程，操作系统的分类以及每类操作系统的特性。
3、（★★★）操作系统的软硬件运行环境：内核态与用户态的区别，中断与异常的区别，系统调用的概念。
4、（★）操作系统体系结构的基本概念。
基础要点1、▲现代操作系统的两个最基本的特征是并发和共享。
2、▲操作系统的五大功能是：处理机管理、存储器管理、信息管理、设备管理和提供用户接口（有的书上还提到了作业管理）。
3、▲从系统观点看，操作系统是计算机系统中的一个系统软件，其管理和控制计算机系统中的资源。
从用户的观点看，操作系统是用户与计算机之间的接口。
从软件观点看，操作系统是程序和数据结构的集合。
4、▲允许多个用户以交互方式使用计算机的操作系统称为分时操作系统；允许多个用户将多个作业交给计算机集中处理的操作系统称为批处理操作系统；能及时处理过程、控制数据并做出相应的操作的计算机系统称为实时操作系统。
5、批处理操作系统的主要缺点是缺少交互性。
虽然提高了计算机系统的工作效率，但用户不能直接干预作业的执行。
6、实时系统应具有两个基本特征：及时性和高可靠性。
即实时操作系统必须在规定时间内处理完来自外部的事件并且保证系统的安全性和稳定性，因此实时操作系统常用在订票系统、银行系统等对反馈时间及可靠性要求高的地方。
7、▲操作系统中采用多道程序设计技术后，提高了CPU和外部设备的利用率。
多道运行的特征之一是宏观上并行，它的含义是同时进入系统的几道程序都处于运行状态中，即它们先后开始了各自的运行，但都未运行完毕。
8、多道程序设计技术是指将一个以上的作业放入主存，并且同时处于运行状态，这些作业共享处理机和外围设备等资源。
一《计算机网络》考研大纲【考查目标】1. 掌握计算机网络的基本概念、基本原理和基本方法。
2. 掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理3. 能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用一、计算机网络体系结构（一） 计算机网络概述1. 计算机网络的概念、组成与功能2. 计算机网络的分类3. 计算机网络与互联网的发展历史4. 计算机网络的标准化工作及相关组织（二） 计算机网络体系结构与参考模型1. 计算机网络分层结构2. 计算机网络协议、接口、服务等概念3. ISO/OSI参考模型和TCP/IP模型二、物理层（一） 通信基础1. 信道、信号、宽带、码元、波特、速率等基本概念2. 奈奎斯特定理与香农定理3. 信源与信宿4. 编码与调制5. 电路交换、报文交换与分组交换6. 数据报与虚电路（二） 传输介质1. 双绞线、同轴电缆、光纤与无线传输介质2. 物理层接口的特性（三） 物理层设备1. 中继器2. 集线器三、数据链路层（一） 数据链路层的功能（二） 组帧（三） 差错控制1. 检错编码2. 纠错编码（四） 流量控制与可靠传输机制1. 流量控制、可靠传输与滑轮窗口机制2. 单帧滑动窗口与停止-等待协议3. 多帧滑动窗口与后退N帧协议（GBN）4. 多帧滑动窗口与选择重传协议（SR）（五） 介质访问控制1. 信道划分介质访问控制频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。
2. 随即访问介质访问控制ALOHA协议；CSMA协议；CSMA/CD协议；CSMA/CA协议。
3. 轮询访问介质访问控制：令牌传递协议（六） 局域网1. 局域网的基本概念与体系结构2. 以太网与IEEE 802.33. IEEE 802.114. 令牌环网的基本原理（七） 广域网1. 广域网的基本概念2. PPP协议3. HDLC协议4. ATM网络基本原理（八） 数据链路层设备1. 网桥网桥的概念；透明网桥与生成树算饭；源选径网桥与源选径算法。
2012年4⽉操作系统试题和答案全国2012年4⽉⾃学考试操作系统试题课程代码：02326⼀、单项选择题(本⼤题共20⼩题，每⼩题1分，共20分)1、IBM公司在他们的PC机、⼯作站和⼤型机上配置的UNIX被称为( C )A、4BSD UNIX C、AⅨB、XENIX D、Ultrix2、现代计算机系统中，最内层是硬件系统，最外层是使⽤计算机系统的⼈，介于它们之间的是( B )A、操作系统B、软件系统C、应⽤软件D、⽀撑软件3、存放当前从主存储器读出的指令的寄存器是( B )A、通⽤寄存器B、指令寄存器C、基址寄存器D、限长寄存器4、下⾯关于⾼速缓冲存储器的叙述中不正确的是( B )A、引⼊⾼速缓冲存储器，加快了程序的执⾏速度C、⾼速缓冲存储器的存取速度⽐主存储器快D、⾼速缓冲存储器的存储容量⽐主存储器⼩B、引⼊⾼速缓冲存储器，增加了主存储器的容量5、多道程序设计实际上______硬件中各种资源的并⾏⼯作能⼒。
( B )A、增加了B、利⽤并发挥了C、减少了D、模拟了6、关于进程与程序关系说法正确的是( D )D、不同进程可以包含相同的程序A、不同进程肯定包含相同的程序B、不同进程肯定包含不同的程序C、⼀个进程肯定包含多个程序7、属于进程控制的原语是( C )A、创建原语B、唤醒原语 E、等待原语C、阻塞原语D、撤销原语8、在不采⽤进程优先级的分时操作系统中，不会引起进程切换的是( C )A、⼀个进程从运⾏状态变成等待状态C、⼀个进程从等待状态变成就绪状态B、⼀个进程从运⾏状态变成就绪状态 D、⼀个进程完成⼯作后被撤消9、可变分区管理⽅法采⽤最优适应分配算法时，将空闲区按______登记到空闲区表中。
( )A、长度递增顺序B、长度递减顺序C、地址递增顺序D、地址递减顺序10、⽤户把作业划分成若⼲段，其中⼀个是主段。
在作业执⾏期间，让其主段保留在主存中，其它的段需要执⾏时再将其装⼊主存特定区域。
这种技术称为( )A、覆盖技术B、对换技术C、移动技术D、交换技术11、在页式虚存系统中，把以后不再访问的或距当前最长时间后再访问的那⼀页调出的页⾯调度算法是( )A、最佳调度算法(OPT)B、最近最久未使⽤调度算法(LRU)C、最近最不经常使⽤调度算法(LFU)D、先进先出调度算法(FIFO)12、页式虚存系统在地址转换时，地址转换机构根据当前执⾏的指令中的相对地址的页号查页表，若该页标志为“O”，则( )A、将页表中该页标志置为“l”B、形成缺页中断C、从页表中找出所在的块号D、启动磁盘读出该页信息13、⾯向⽤户，⽂件系统的最主要功能是实现( )A、⽂件的安全存储B、⽂件的操作C、⽂件的组织D、⽂件的按名存取14、UNIX⽂件系统的索引表采⽤的结构是( )A、位⽰图B、多级索引C、索引D、空闲块链15、假设读写磁头正在55号柱⾯上操作，现有访问柱⾯的要求，其次序为100、180、40、120、20。
※特别章外部排序（2012版《数据结构高分笔记》更新补丁）
·外部排序简介
所谓外部排序，即对外存中的数据进行排序（相对于内部排序而言），也可以说是对文件中的数据进行排序。
有了内部排序算法，为什么还要外部排序？因为文件太大，内存放不下。
外排做法可以概括为一句话：将内存作为工作空间来调整外存中数据的位置。
具体可以分成以下三个要点：
①文件在外存中的组织；
②文件在内存中的排序；
③文件在内外存之间的交换。
说明：本补丁是2012年数据结构考研大纲新增内容，虽然知识点不多，但由于第一年被列入考试范围，所以大家要重视。
·归并排序法
归并排序法是外排序中最常用的方法，分为两个执行阶段。
第一阶段：将文件中的数据分段输入到内存中，在内存中用内排序方法对其分类，这样排序完的文件段称作归并段，然后将其写回外存中而在外存中形成了许多初始归并段。
第二阶段：对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。
说明：外排序中的归并排序法和内排序中的归并法是类似的，都是由小单元逐渐归并成单元的过程，注意对比，加深理解。
归并排序算法分两个阶段：
1.初始归并段的形成
其过程是根据缓冲区大小，由文件输入（由外存读入内存）记录，当记录充满缓冲区后，选择最小的（以递增排序为例）记录输出（由内存写出到外存），其空缺位置由下一个输入记录来取代，输出的记录成为当前初始归并段的一部分。
如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前部分归并段最大的记录要小（如例1中的关键字11，比15要小，不可能出现在当前归并段中），它将等待生成下一个归并段时提供选择。
反复进行上述操作，直到所有新输入的记录关键字都小于最后输出记录的关键字时（如步骤9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。
接着继续生成下一个归并段，直到全部记录都处理完毕为止。
下面通过例题来具体说明一下。
例1.设输入文件的各个记录的关键字为：
15,19,04,83,12,27,11,25,16,34,26,07,10,90,06, ... ...
假设内存缓冲区可容纳4个记录，成初始归并段。
如下表所示，给出了生成初始归并段过程中各步的缓冲区内容和输出结果。
步
数
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
缓冲区内容15 15 15 11 1111111111 11 11 06 ......
19 19 19 19 25161616
16 16 16 16 ......
04 12 27 27 2727342626 26 26 26 ......
83 83 83 83 8383838307 10 90 90 ......
输出结果
04 12 15 19 25 27 34 83 07 10 11 06 ... ...
所生成的第一初始归并段所生成的第二初始归并段
... ...
初始归并段生成过程表（表中下划线数字即为生成下一归并段的候选数字）
2. k路归并
有了m个初始归并段（都是有序段），便可以进行k路归并了，即将k个初始归并段
归并产生一段，这样，m个初始归并段产生多个这样的段，然后对这些段再用同样的方法进行归并，如此往复，直到归并成一个段为止，这个段就是最后生成的归并段。
例2.一个文件，含有10000个记录，通过1.1中介绍的方法，得到10个初始归并段R1... R10,其中每一个段都含有1000个记录。
外存上的信息读/写是以物理块为单位进行的，假设每个物理块可以容纳200个记录，则每一趟归并需要进行50次读和50次写，4趟归并加上内部排序所需要进行的读/写使得在外排序中总共需要进行500次读/写。
对初始归并段做两两归并：
R1,R2 R3,R4 R5,R6 R7,R8 R9,R10 R1’ R2’ R3’ R4’ R5’
R1” R2” R3”
R1’’’ R2’’’
R1’’’’(有序文件)
每次都由m个归并段得到个归并段，这种归并方法称为2-路归并。
若对上例进行5-路归并则有：
R1,R2,R3,R4,R5 R6,R7,R8,R9,R10
R1” R2”
R1’’’(有序文件)
·归并排序时间复杂度分析
m个初始归并段进行k路归并，归并的遍数为。
为
理的时间，而归并遍数为，所。
图1
（2）第一次比较胜出者5与第三个叶子结点10比较，10为败者，5为胜者，因而10替换到5的位置，5作为胜者向上一级比较，如图2
图2
（3）同理，依次比较其他各叶子结点，最终得到第一棵败者树为：
图3
K路归并的败者树的深度⎡log2k⎤在每次调整查找下一个具有最小关键字记录时，最多做⎡log2k⎤次关键字比较。
因此，利用败者树在K个记录中选择最小者，时间复杂度为O(log2k)。
说明：败者树和其他选择树的原理都是一样的，比如之前堆排序中的堆。
做法都是先用一个较大的时间复杂度将待排元素建成一棵满足一定要求的树，然后就可以从中取出一个满足要求的元素，并将新来的元素放在刚取出元素的位置上；这样只会在一点上对树的结构造成破坏而不会造成全局的破坏，因此只需花较小的时间复杂度进行局部调整即可将被破坏的结构恢复正常，无需从新建树。
局部调整即可恢复结构从而降低时间复杂度，这就是选择树的精髓。
数据结构就是这样，其实各种乱七八糟的结构都是表象，浮云，其背后的本质就那么一点，懂了这个之后，数据结构学习就会很轻松，最后祝大家考研愉快。
习题心选：
一、选择题：
1.外排序是指（）
A.在外存上进行的排序方法。
B.不需要使用内存的排序方法。
C.数据量大，需要人工干预的排序方法。
D.排序前后数据在外存，排序时数据调入内存的排序方法。
2.文件有m个初始归并段，采用k路归并时，所需的归并遍数是（）
A.log2k
B.log2m
C.log k
m D.
1 2 3 4 5 6 7 8 9 10 11
缓冲区内容10 12 13 21 21 21 16 16 16 16 20 20 20 20 20 8 8 8
15 15 15 15 30 30 30 30
25 25 25 25 25 25 25 10 10
输出结果10 12 13 15 20 21 25 30 8 10 16
第一初始归并段第二初始归并段
本题简单，每次从缓冲区中选出最小且比当前归并段最大的元素还要大的输出，空出来的位置读入新的关键字（参照例1 解法）。
2.答：内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。
外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。
外部排序的效率主要取决于读写外存的次数，即归并的趟数。
因为归并的趟数s=⎡log k m⎤,其中，m是归并段个数，k是归并路数。
增大k和减少m 都可减少归并趟数。
应用中通过败者树进行多（k）路平衡归并和置换-选择排序减少m，来提高外部排序的效率。
