数据结构3套卷子合集带答案.doc

操作系统（专科）模拟题-1

一、单项选择题（每题2分，共 20 分）
1、分时系统中，一旦有处理请求和要求处理的数据时，CPU就应该立即处理该数据并将结果及时送回。下面属于分时系统的是（ D ）。
A．计算机激光照排系统 B．办公自动化系统
C．计算机辅助设计系统 D．航空订票系统
2、一个进程被唤醒意味着（ B ）。
A．该进程重新占有了CPU B．进程状态变为就绪
C．它的优先权变为最大 D．其PCB移至就绪队列的队首
3、进程的动态、并发等特征是利用（ D ）表现出来的。
A．程序 B．数据 C．程序和数据 D．进程控制块
4、在操作系统中，JCB是指（ C ）。
A．文件控制块 B．进程控制块
C．作业控制块 D．程序控制块
5、在UNIX系统中，目录结构采用（ D ）。
A． 单级目录结构 B．二级目录结构
C．单纯树形目录结构 D．带链接树形目录结构
6、设备的打开、关闭、读、写等操作是由（ D ）完成的。
A．用户程序 B．编译程序
C．设备分配程序 D．设备驱动程序
7、可由CPU调用执行的程序所对应的地址空间为（ C ）。
A．符号名空间 B．虚拟地址空间
C．物理地址空间 D．相对地址空间
8、采用SPOOLing技术的目的是（ A ）。
A．提高独占设备的利用率 B．提高主机效率
C．减轻用户编程负担 D．提高程序的运行速度
9、避免死锁的一个著名的算法是（ B ）。
A．先入先出法 B．银行家算法 C．优先级算法 D．资源按序分配法
10、在微内核结构的现代操作系统中，进程（ C ）。
A．失去作用 B．只是调度运行的单位
C．只是资源分配的单位 D．既是资源分配的单位，又是调度运行的单位
---------------------------------------------------------------------------------------------

1．分布式操作系统与网络操作系统本质上的不同在于（ D ）。
A．实现各台计算机之间的通信
B．共享网络中的资源
C．满足较大规模的应用
D．系统中若干台计算机相互协作完成同一任务
2．进程与程序之间有密切联系，但又是不同的概念。二者的一个本质区别是（ A ）。
A． 程序是静态概念，进程是动态概念
B． 程序是动态概念，进程是静态概念
C．程序保存在文件中，进程存放在内存中
D．程序顺序执行，进程并发执行
3．在9个生产者，6个消费者共享容量为8的缓冲区的生产者-消费者问题中，互斥使用缓冲区的信号量S的初始值为（ B ）。
A．8 B．1 C．9 D．6
4．操作系统中的作业管理是一种（A ）。
A．宏观的高级管理 B．宏观的低级管理
C．系统刚开始加电 D．初始化引导完成
5．把逻辑地址转变为内存的物理地址的过程称作（ D ）。
A．编译 B．连接
C．运行 D．重定位
6．用ls命令以长格式列目录信息时，若某一文件的特征在文件列表中按如下顺序显示在屏幕上：
drwxrw-r-- 2 user gk 3564 Oct 28 10:30 /user/asD.h
则同组人的访问权限是（ D）。
A．读和执行 B．读或执行
C．写和执行 D．读和写
7．CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用（ C ）。
A．并行技术 B．通道技术
C．缓冲技术 D．虚存技术
8．用户要在程序一级获得系统帮助，必须通过（ C ）。
A．进程调度 B．作业调度
C．系统调用 D．键盘命令
9．死锁预防是保证系统不进入死锁状态的静态策略，其解决方法是破坏产生死锁的四个必要条件之一。下列方法中破坏了“循环等待”条件的是（ D ）。
A．银行家算法 B．一次性分配策略
C．剥夺资源法 D．资源有序分配法
10．在下列关于UNIX的论述中，（ D ）是不正确的。
A．UNIX是一个多道的分时操作系统
B．管道机制是UNIX贡献之一
C．提供可动态装卸的文件系统是UNIX的特色之一
D．路径名是UNIX独有的实现文件共享的机制
---------------------------------------------------------------------------------------------
1．操作系统的基本职能是（ A ）。
A． 控制和管理系统内各种资源，有效地组织多道程序的运行
B． 提供用户界面，方便用户使用
C． 提供方便的可视化编辑程序
D． 提供功能强大的网络管理工具
2．如果进程PA对信号量S执行P操作，则信号量S的值应（ B ）。
A．加1 B．减1 C．等于0 D．小于0
3．在操作系统中引入“进程”概念的主要目的是（ B ）。
A．改善用户编程环境 B. 描述程序动态执行过程的性质
C. 使程序与计算过程一一对应 D. 提高程序的运行速度
4．进程的动态、并发等特征是利用（ A ）表现出来的。
A．进程控制块 B．数据 C．程序 D．程序和数据
5．UNIX系统中进程调度采用（ D
）。
A．先来先服务（FCFS） B．时间片轮转法
C．短作业优先法（SJF） D．多级反馈队列轮转法
6．通常，采用紧缩法消除内存碎片的存储管理技术是（ C ）。
A．固定分区法 B．动态分区法
C．可重定位分区法 D．对换技术
7．计算机系统产生死锁的根本原因是（ D ）。
A．资源有限 B．进程推进顺序不当
C．系统中进程太多 D．A和B
8．UNIX文件系统中采用的目录结构是（ D ）。
A．单级目录结构 B．二级目录结构
C．纯树型目录结构 D．带链接的树型目录结构
9．SPOOLing技术可以实现设备的（ C ）分配。
A．独占 B．共享 C．虚拟 D．物理
10．设备的打开、关闭、读、写等操作是由（ C ）完成的。
A．用户程序 B．编译程序
C．设备驱动程序 D．设备分配程序

二、判断题（选择你认为正确的叙述划Ö，认为错误的划´并说明原因。每题2分，共10分）
1、UNIX操作系统是采用微内核方法实现结构设计的。（ X ）
2、进程和程序是两个截然不同的概念。（ V ）
3、在虚拟存储系统中，操作系统为用户提供了巨大的存储空间。因此，用户地址空间的大小可以不受任何限制。（ X ）
4、在采用树型目录结构的文件系统中，各用户的文件名必须互不相同。（X ）
5、用户程序应与实际使用的物理设备无关，这种特性就称作设备无关性。（ V ）
---------------------------------------------------------------------------------------------

1． 系统发生死锁时，其资源分配图中必然存在环路。因此，如果资源分配图中存在环路，则系统一定出现死锁。（ X ）
2． 进程控制块（PCB）是专为用户进程设置的私有数据结构，每个进程仅有一个PCB。（ X ）
3． 一个进程在执行过程中可以被中断事件打断，当相应的中断处理完成后，就一定恢复该进程被中断时的现场，使它继续执行。（ X ）
4． 虚拟存储器不是物理上扩大内存空间，而是逻辑上扩充了内存容量。（ V ）
5． 在采用树型目录结构的文件系统中，各用户的文件名必须互不相同。（ X ）
---------------------------------------------------------------------------------------------
1．进程控制块（PCB）是专为用户进程设置的私有数据结构，每个进程仅有一个PCB。（ X ）
2．平均周转时间和周转时间与选用的调度算法有关。（ V ）
3．利用交换技术扩充内存时，设计时必须考虑的问题是：如何减少信息交换量、降低交换所用的时间。（ V ）
4． 在UNIX系统中，常采用单空闲块链接法来实施存储空间的分配与回收。（ X ）
5． P、V操作不仅可以实现并发进程之间的同步和互斥，而且能够防止系统进入死锁状态。（ X ）

三、 填空题（每空2分，共30分）
1、操作系统的基本特征是____并发、__共享__ 和__异步性（次序无关）_________。
2、对信号量S每执行一次P操作，则信号量S的值就____减1_____。当S的值___小于0_____时，执行P操作的进程的状态就置为阻塞态，把相应的PCB连入该信号量队列的___末尾___，并且该进程放弃处理机，由__进程调度程序___调度合适进程。
3、把逻辑地址转变为内存的物理地址的过程称作_______重定位_____，它分为两种形式，在现代操作系统中都采用______动态重定位_________形式来实现这种地址转换。
4、 在UNIX文件系统中，文件的路径名有两种表示形式，它们是__绝对路径名（或全路径 名）__和____相对路径名____，其中前者的路径名以“/”开始。
5、死锁产生的四个必要条件是 互斥条件 、 不可抢占条件 、 占有且申请条件 和
循环等待条件 四种。

1．在UNIX系统中，基本的文件类型分为____普通文件____文件、_____目录文件_____文件和 ____特别文件___文件，　所有的I/O设备按其物理特性分为___字符设备_____设备和___块设备____设备。
2．操作系统的基本特征是____并发、___共享、和__异步性___.
3．通常，线程的定义是-进程中执行运算的最小单位/执行处理机调度的基本单位_。在现代操作系统中，资源的分配单位是__进程__，而处理机的调度单位是____线程___, 一个进程可以有__多个_线程。
4． 处理机调度可分为三级，它们是___高级调度__、___中级调度___和__低级调度（或进程调度）___； 在一般操作系统中，必须具备的调度是___进程调度___。
5．操作系统的设备管理应具备的主要功能是__监视设备状态、进行设备分配、完成I/O操作____和 __缓冲管理与地址转换____。
6．对信号量S每执行一次P操作，则信号量S的值就___减1___。当S的值___小于0___时，执行P操作的进程的状态就置为阻塞态，把相应的PCB连入该信号量队列的__末尾__，并且该进程__放弃__处理机，由__进程调度程序__调度合适进程。
7．把逻辑地址转变为内存的物理地址的过程称作__重定位__，它分为_静态重定位__和_动态重定位___两种形式，在现代操作系统中都采用_动态重定位__形式来实现这种地址转换。
8．在UNIX系统中，对文件进行控制和管理的数据结构称作____I节点__________。

1．操作系统一般为用户提供了三种界面，它们是_命令界面 图形界面 _和 系统调用界面
2．进程间相互合作的关系是_____同步___关系，而对资源争用的关系是______互斥 __关系。若干进程使用同一临界资源时必须______ 互斥____执行。
3．处理机调度可分为三级，它们是___高级调度_，__中级调度___和___低级调度_；在一般操作系统中，必须具备的调度是_进程调度_____。
4．一般说来，用户程序中所使用的地址是_______逻辑地址______，而内存中各存储单元的地址是____物理地址________；将前者转变为后者的过程称作_________重定位
____。
5．在段页式存储管理系统中，面向 用户 的地址空间是段式划分，面向 物理实现 的地址空间是页式划分。

四、 解答题（共20分）
1、什么是操作系统？它的主要功能是什么？（8分）
1、操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的
系统软件（或程序集合），是用户与计算机之间的接口。
操作系统的主要功能包括：存储器管理，处理机管理，设备管理，文件管理以及用户接
口管理。
2、 在存储管理中，什么是分页？什么是分段？二者有何主要区别？
2、答（共8分）
将一个进程的逻辑地址空间划分成若干个大小相等的部分，每一部分称作页面。（1分）
分段是一组逻辑信息的集合，即一个作业中相对独立的部分。（1分）
分页和分段的主要区别是：页是信息的物理单位，段是信息的逻辑单位；页的大小是由
系统固定的，段的长度因段而异，由用户决定；分页的作业地址空间是一维的，分段的
作业地址空间是二维的。（6分）
3、SPOOLing系统的主要功能是什么？（4分）
3、答：SPOOLing系统的主要功能是：将独占设备改造为共享设备，实现了虚拟设备功能。）
--------------------------------------------------------------------------------------------------------------------
1．什么是临界区？进程进入临界区的调度原则是什么？
在每个进程中访问临界资源的那段程序叫临界区。
进程进入临界区的调度原则是：
①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。
　　 ②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区， 则
其它所有试图进入临界区的进程必须等待。
　　 ③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。
④如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
2． 什么是中断？中断处理的一般过程分为哪几个阶段？（共5分）
所谓中断是指CPU对系统发生的某个事件做出的一种反应：CPU暂停正在执行的程序，保留现场后自动地转去执行相应的处理程序，处理完该事件后再返回断点继续执行被“打断”的程序。（1分）
中断处理的一般过程分为以下阶段：保存现场，分析原因，处理中断，返回断点。

3. 进程和程序的主要区别是什么？ （共 7 分）
进程是动态的，程序是静态的；进程具有并发性，而程序具有顺序性；进程具有独立性，是资源分配和调度的基本单位，而程序无此特性；进程和程序间没有一一对应关系；进程异步运行，会相互制约，程序不具备此特性答：

1． 什么是操作系统？（4分）
操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

2． 在进程状态转换图如下图所示，请说明： （7分）

4
3
2
1
运行
就绪
阻塞

1)引起各种状态转换的典型事件有哪些？
1，就绪→运行：CPU空闲，就绪态进程被调度程序选中。
2，运行→就绪：正在运行的进程用完了本次分配给它的CPU时间片。
3，运行→阻塞：运行态进程因某种条件未满足而放弃对CPU的占用，如等
待读文件。
4，阻塞→就绪：阻塞态进程所等待的事件发生了，例如读数据的操作完成。

2)下述三种状态变迁能否发生？为什么？
2→1；3→2；4→1。
对于下述状态变迁：
2→1：可以。运行进程用完了本次分配给它的时间片，让出CPU，从就绪队
列中选一个进程投入运行。
3→2：不可以。任何时候一个进程只能处于一种状态，它既然由运行态变为
阻塞态，就不能再变为就绪态。
4→1：可以。某一阻塞态进程等待的事件出现了，而且此时就绪队列为空，
该进程进入就绪队列后马上又被调度运行。

3.虚拟存储器的基本特征是什么？虚拟存储器的容量主要受到哪两方面的限制？虚拟存储器的基本特征是：（每个1分）
①虚拟扩充，即不是物理上而是逻辑上扩充了内存容量；　　
②部分装入，即每个作业不是全部一次性地装入内存，而是只装入一部分；
③离散分配，即不必占用连续的内存空间，而是“见缝插针”；
④多次对换，即所需的全部程序和数据要分成多次调入内存。
虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制。

4.计算机系统中产生死锁的根本原因是什么？一般解决死锁的方法有哪三种？
计算机系统中产生死锁的根本原因是：资源有限且操作不当。（1分）一般解决死锁的方法有：死锁的预防、死锁的避免、死锁的检测与恢复等三种
----------------------------------------------------------------------------------------------------------------

五、 应用题（共20分）
1．假定在单CPU条件下有下列要执行的作业：
作业
运行时间
优先级
1
10
2
2
4
3
3
3
5
作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。
（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。
非抢占式优先级算法 (3分)
作业1 作业3 作业2
| | | | t
1 10 13 17

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？
和
（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？
作业
到达时间
运行时间
完成时间
周转时间
带权周转时间
1
0
10
10
10
1.0
2
1
4
17
16
4.0
3
2
3
13
11
3.7
平均周转时间
12.3
平均带权周转时间
2.9

2．设UNIX文件系统中的目录结构如下图所示：
¡

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ usr
bin dev etc lib lost+found mnt tmp …
¡ mengqc ¡ liu
…
sub1¡
…
… m1.c m2.c

file_a

(1) 设当前工作目录是/usr，那么，访问文件file_a的绝对路径名和相对路径名各是什么？
访问文件file_a的绝对路径名是： /usr/mengqc/sub1/file_a
访问文件file_a的相对路径名是： mengqc/sub1/file_a

(2) 现在想把工作目录改到liu，应使用什么命令（写出完整命令行）？
cd /usr/liu 或者 cd liu

(3) 如果用 ls –l /usr/mengqc命令列出指定目录的内容，其中有如下所示的一项：
- r w – r - - - - - 2 mengqc …… m2.c
那么，该文件m2.c对文件主、同组用户、其他用户分别规定了什么权限？
文件主权限是： 可读、可写，但不可执行
同组用户权限是：只可读
其他用户权限是：无（即：不能读、写或执行）

1．在单CPU环境下，设有4道作业，它们的提交时间及执行时间（时间单位：小时）如下：
作业号
提交时间
执行时间
1
2
3
4
10.0
10.2
10.4
10.5
2.0
1.0
0.5
0.3
试计算采用先来先服务调度算法（FCFS）和最短作业优先调度算法（SJF）时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（12分）
1．解：（共12分）
若采用先来先服务调度算法，则其调度顺序为1、2、3、4。（4分）
作业号 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间

1 10.0 2.0 10.0 12.0 2.0 1.0
2 10.2 1.0 12.0 13.0 2.8 2.8
3 10.4 0.5 13.0 13.5 3.1 6.2
4 10.5 0.3 13.5 13.8 3.3 11.0
平均周转时间T＝（2.0＋2.8＋3.l＋3.3）/4＝2.8 （1分）
平均带权周转时间W＝（l.0＋2.8＋6.2＋11.0）/4＝5.25 （1分）
若采用短作业优先调度算法，则其调度顺序为1、4、3、2。（4分）
作业号 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间
1 10.0 2.0 10.0 12.0 2.0 1.0
4 10.5 0.3 12.0 12.3 1.8 6.0
3 10.4 0.5 12.3 12.8 2.4 4.8
2 10.2 1.0 12.8 13.8 3.6 3.6
平均周转时间 T＝（2.0＋l.8＋2.4＋3.6）/4＝2.45 （1分）
平均带权周转时间 W＝（1.0＋6＋4.8＋3.6）/4＝3.85 （1分）

2． 若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。（8分）
页号
物理块号
0
2
1
3
2
1
3
6

2．解：（共8分，每个2分）
本题中，为了描述方便，设页号为P，页内位移为D，则：
对于逻辑地址1011
P＝INT（1011／1024）＝0
D＝1011 mod 1024＝1011
查页表第0页在第2块，所以物理地址为3059。
对于逻辑地址2148
P＝INT（2148/1024）＝2
D＝2148 mod 1024＝100
查页表第2页在第1块，所以物理地址为1124。
对于逻辑地址4000
P＝INT（4000／1024）＝3
D＝4000 mod 1024＝928
查页表第3页在第6块，所以物理地址为7072。
对于逻辑地址5012
P＝INT（5012／1024）＝4
D＝5012 mod 1024＝916
因页号超过页表长度，该逻辑地址非法。
----------------------------------------------------------------------------------------------------------------------

1、有三个用户进程A、B和C，在运行过程中都要使用系统中的一台打印机输出计算结果。
（1）试说明A、B、C进程之间存在什么样的制约关系？
(1) A、B、C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。(2分)

（2）为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。（共8分）
（2）mutex：用于互斥的信号量，初值为1。（2分）
各进程的代码如下 ：（4分）
进程A 进程B 进程C
... … ...
... … ...
P(mutex) P(mutex) P(mutex)
申请打印机 申请打印机 申请打印机
使用打印机 使用打印机 使用打印机
V(mutex) V(mutex) V(mutex)
… … …

2、对于如下的页面访问序列：
1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
当内存块数量为3时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。共12分））
2、答：（共12分）
使用FIFO算法：
1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
1 1 1 4 4 4 5 5 5
2 2 2 1 1 1 3 3
3 3 3 2 2 2 4
共产生缺页中断9次。（4分），依次淘汰的页是1、2、3、4、1、2。
使用LRU算法：
1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
1 1 1 4 4 4 5 3 3 3
2 2 2 1 1 1 1 4 4
3 3 3 2 2 2 2 5
共产生缺页中断10次。，依次淘汰的页是1、2、3、4、5、1、2。

11