数据结构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 ）。 A8 B1 C9 D64操作系统中的作业管理是一种（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读和写 7CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用（ C ）。A并行技术 B通道技术 C缓冲技术 D虚存技术8用户要在程序一级获得系统帮助，必须通过（ C ）。 A进程调度 B作业调度 C系统调用 D键盘命令9死锁预防是保证系统不进入死锁状态的静态策略，其解决方法是破坏产生死锁的四个必要条件之一。下列方法中破坏了“循环等待”条件的是（ D ）。 A银行家算法 B一次性分配策略 C剥夺资源法 D资源有序分配法10在下列关于UNIX的论述中，（ D ）是不正确的。AUNIX是一个多道的分时操作系统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小于03在操作系统中引入“进程”概念的主要目的是（ B ）。A改善用户编程环境 B. 描述程序动态执行过程的性质 C. 使程序与计算过程一一对应 D. 提高程序的运行速度4进程的动态、并发等特征是利用（ A ）表现出来的。 A进程控制块 B数据 C程序 D程序和数据5UNIX系统中进程调度采用（ D ）。A先来先服务（FCFS） B时间片轮转法 C短作业优先法（SJF） D多级反馈队列轮转法6通常，采用紧缩法消除内存碎片的存储管理技术是（ C ）。A固定分区法 B动态分区法 C可重定位分区法 D对换技术7计算机系统产生死锁的根本原因是（ D ）。A资源有限 B进程推进顺序不当C系统中进程太多 DA和B8UNIX文件系统中采用的目录结构是（ D ）。A单级目录结构 B二级目录结构 C纯树型目录结构 D带链接的树型目录结构9SPOOLing技术可以实现设备的（ 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分）4321运行就绪阻塞1)引起各种状态转换的典型事件有哪些？1，就绪运行：CPU空闲，就绪态进程被调度程序选中。 2，运行就绪：正在运行的进程用完了本次分配给它的CPU时间片。 3，运行阻塞：运行态进程因某种条件未满足而放弃对CPU的占用，如等 待读文件。 4，阻塞就绪：阻塞态进程所等待的事件发生了，例如读数据的操作完成。2)下述三种状态变迁能否发生？为什么？21；32；41。 对于下述状态变迁：21：可以。运行进程用完了本次分配给它的时间片，让出CPU，从就绪队 列中选一个进程投入运行。32：不可以。任何时候一个进程只能处于一种状态，它既然由运行态变为 阻塞态，就不能再变为就绪态。41：可以。某一阻塞态进程等待的事件出现了，而且此时就绪队列为空，该进程进入就绪队列后马上又被调度运行。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）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？作业到达时间运行时间完成时间周转时间带权周转时间101010101.021417164.032313113.7平均周转时间12.3平均带权周转时间2.92设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道作业，它们的提交时间及执行时间（时间单位：小时）如下：作业号提交时间执行时间123410.010.210.410.52.01.00.50.3试计算采用先来先服务调度算法（FCFS）和最短作业优先调度算法（SJF）时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（12分）1解：（共12分）若采用先来先服务调度算法，则其调度顺序为1、2、3、4。（4分） 作业号提交时间 执行时间开始时间 完成时间 周转时间带权周转时间1 10.0 2.010.0 12.0 2.01.02 10.2 1.012.0 13.0 2.8 2.83 10.4 0.513.0 13.5 3.16.24 10.5 0.3 13.5 13.8 3.311.0平均周转时间T（2.02.83.l3.3）/42.8 （1分）平均带权周转时间W（l.02.86.211.0）/45.25 （1分）若采用短作业优先调度算法，则其调度顺序为1、4、3、2。（4分）作业号提交时间 执行时间开始时间 完成时间 周转时间带权周转时间1 10.0 2.0 10.0 12.0 2.01.04 10.5 0.3 12.0 12.3 1.8 6.03 10.4 0.5 12.3 12.8 2.4 4.82 10.2 1.0 12.8 13.8 3.6 3.6 平均周转时间T（2.0l.82.43.6）/42.45 （1分）平均带权周转时间 W（1.064.83.6）/43.85 （1分）2 若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。（8分）页号物理块号021321362解：（共8分，每个2分）本题中，为了描述方便，设页号为P，页内位移为D，则：对于逻辑地址1011PINT（10111024）0D1011 mod 10241011查页表第0页在第2块，所以物理地址为3059。对于逻辑地址2148PINT（2148/1024）2D2148 mod 1024100查页表第2页在第1块，所以物理地址为1124。对于逻辑地址4000PINT（40001024）3D4000 mod 1024928查页表第3页在第6块，所以物理地址为7072。对于逻辑地址5012PINT（50121024）4D5012 mod 1024916因页号超过页表长度，该逻辑地址非法。-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