国家开放大学(中央广播电视大学)2022年秋季学期开放本科期末考试操作系统(半开卷)

试卷代号:1251

座位号|丨|国家开放大学（中央广播电视大学）2022年秋季学期“开放本科”期末考试操作系统试题（半开卷）2023年1月题号

一

二

三

四

总分分数得分评卷人-------一、选择题（选择一个正确答案的代码填入括号中，每小题2分，共

30分）1.在计算机系统中,控制和管理各种资源、有效地组织多道程序运行的系统软件称作（）。A.

管理信息系统

B.文件系统C.操作系统

D.数据库管理系统2.以下著名的操作系统中，属于多用户、多进程、多任务分时系统的是（

）。A.

DOS系统

B.UNIX系统C.WindowsNT系统

D.

OS/2系统3.在实时系统中，一旦有处理请求和要求处理的数据时，CPU就应该立即处理该数据并将结果及时送回。下面属于实时系统的是（A.航空订票系统C.计算机辅助设计系统

）。B.办公自动化系统D.计算机激光照排系统4.引入多道程序的目的在于（A.充分利用存储器

）。B.C.

提高实时响应速度充分利用CPU,减少CPU等待时间D.有利于代码共享,减少主、辅存信息交换量7335.若P、V操作的信号量S初值为2,当前值为一1,则表示有（

）个等待进程。A.0C.26.在操作系统中，作业处于（A.后备C.提交7.作业调度的关键在于（A.有一个较好的操作环境C.用户作业准备充分8.

B.1D.3）状态时，已处于进程的管理之下。B.执行D.完成）。B.选择恰当的进程管理程序D.选择恰当的作业调度算法

有三个作业同时到达,J1,J2,J3的执行时间分别为D,T2工，且T,<T2<T3,它们在一台处理机上按单道方式运行,釆用短作业优先算法，则平均周转时间是（A."T2+T3C.TI/3+2XTZ/3+T39.分区管理要求对每一个作业都分配（A.若干地址不连续C.若干连续的页面

B.（卩+"丁3）/3D.T1+2XT2/3+T3/3）的内存单元。B.地址连续D.若干不连续的页面

）。10.除操作系统占用的内存空间之外，所剩余的全部内存只供一个用户进程使用，其他进程都放在外存上，这种技术称为（A.覆盖技术C.对换技术

）。

B.虚拟技术D.物理扩充11.文件系统为每个文件建立一张指示逻辑记录和物理记录之间的对应关系表，由此表和文件本身构成的文件是（A.连续文件C.串连文件

）。

B.索引文件D.逻辑文件12.使用绝对路径名访问文件是从（734

）开始按目录结构访问某个文件。A.根目录C.父目录

D.用户主目录

B.当前目录

73513.

A.I/O端口C.数据通道

通道是一种（）。

B.I/O专用处理机D.软件工具14.采用SPOOLing技术的目的是（A.提高主机效率C.减轻用户编程负担15.以下不属于分布式系统特征的是（A.分布性C.全局性

B.提高独占设备的利用率D.提高程序的运行速度B.并行性D.可定制性得.分评卷土二、判断题（正确的划错误的划X,每小题2分，共10分）16.操作系统是整个计算机系统的控制管理中心，它对其它软件具有支配权利。因而，操作系统建立在其它软件之上。（

）17.中断处理一般分为中断响应和中断处理两个步骤，前者由软件实施，后者由硬件实施。（

）18.虚拟存储方式下，程序员编制程序时不必考虑主存的容量，但系统的吞吐量在很大程度上依赖于主存储器的容量。（

）19.文件系统采用二级文件目录可以解决不同用户间的文件命名冲突。（

）20.利用共享分配技术可以提高设备的利用率，使得打印机之类的独占设备成为可共享的、快速I/O设备。（

）得分评卷人----------------三、简答题（每小题5分，共40分）21.操作系统主要有哪些类型的体系结构？Linux系统采用哪种结构？22.在操作系统中为什么要引入进程概念？23.处理机调度一般可分为哪三级？其中哪一级调度必不可少？24.一般中断处理的主要步骤是什么？73625.对换技术如何解决内存不足的问题？26.什么是文件的共享？文件链接如何实现文件共享？27.设置缓冲区的原则是什么？28.嵌入式操作系统的最大特点是什么？举例说明。得分评卷人----四、应用题（每小题10分，共20分）29.

假定在单CPU条件下有下列要执行的作业，如下表所示。作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。①用一个执行时间图描述在釆用非抢占式优先级算法时这些作业的执行情况。②针对上面算法，计算作业的周转时间、平均周转时间、带权周转时间和平均带权周转时间。作业12345

运行时间101215

优先级31342注:优先级数值大的作业其优先级高。30.

考虑下述页面走向：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6当内存块数量为3时，试问最近最少使用置换算法（LRU）的缺页次数是多少？（注意，所有内存块最初都是空的，所以凡第一次用到的页面都产生一次缺页。并给出解题过程。）737试卷代号：1251国家开放大学（中央广播电视大学）2022年秋季学期“开放本科”期末考试操作系统试题答案及评分标准（半开卷）（供参考）2023年1月一、选择题（选择一个正确答案的代码填入括号中，每小题2分，共30分）1.C6.B11.B

2.B7.D12.A

3.A8.D13.B

4.C9.B14.B

5.B10.C15.D二、判断题（正确的划"，错误的划X,每小题2分，共10分）16.X

17.X

18.J

19.7

20.X三、简答题（每小题5分，共40分）21.一般说来，操作系统有四种结构：整体结构、层次结构、虚拟机结构、客户机一服务器结构。Linux系统釆用的是整体结构。22.在操作系统中，由于多道程序并发执行时共享系统资源，共同决定这些资源的状态，因此系统中各程序在执行过程中就出现了相互制约的新关系，程序的执行出现“走走停停”的新状态。这些都是在程序的动态过程中发生的。用程序这个静态概念已不能如实反映程序并发执行过程中的这些特征。为此，人们引入“进程”这一概念来描述程序动态执行过程的性质。23.处理机调度一般可分为高级调度（作业调度）、中级调度和低级调度（进程调度）。其中进程调度必不可少。24.一般中断处理的主要步骤是：保存被中断程序的现场，分析中断原因，转入相应处理程序进行处理，恢复被中断程序现场（即中断返回）。25.在多道程序环境中可以采用对换技术。此时，内存中保留多个进程。当内存空间不足以容纳要求进入内存的进程时，系统就把内存中暂时不能运行的进程（包括程序和数据）换出到外存上，腾出内存空间，把具备运行条件的进程从外存换到内存中。26.文件的共享是指系统允许多个用户（进程）共同使用某个或某些文件。文件链接是给文件起别名，即将该文件的目录项登记在链接目录中。这样,访问该文件的路径就不只一条。不同的用户（或进程）就可以利用各自的路径来共享同一文件。73827.设置缓冲区的原则是:如果数据到达率与离去率相差很大，则可釆用单缓冲方式；如果信息的输入和输出速率相同（或相差不大）时，则可用双缓冲区；对于阵发性的输入、输出，可以设立多个缓冲区。28.嵌入式操作系统的最大特点就是可定制性，即能够提供对内核进行配置或剪裁等功能，可以根据应用需要有选择地提供或不提供某些功能，以减少系统开销。如从应用领域角度看，可以分为面向信息家电的嵌入式操作系统，面向智能手机的嵌入式操作系统，面向汽车电子的嵌入式操作系统，以及面向工业控制的嵌入式操作系统等。四、应用题（每小题10分，共20分）29.解：（共10分）①非抢占式优先级的执行时间图，如下图所示。（4分）作业1

作业4作业3

作业5

作业20②计算过程如下表所示。（6分）

1011

13

1819作业12345

到达时间01234

运行时间101215

完成时间1019131118

周转时间101811814

带权周转时间1.018.05.58.02.8平均周转时间平均带权周转时间

12.27.0630.

解：（共10分）使用最近最少使用置换算法LRU,内存块为3,共产生缺页中断15次。页面

1

2

3

4

21

5

6

2

1

23

7

6

32

1

236块11块2块3

12

123

423

421

521

561

562

162

132

732

736

236

31

2

236缺页

缺缺缺缺

缺缺缺缺缺

缺缺缺

缺缺

缺（给出解题过程给5分，结果正确5分）739试卷代号：1252

座位号匚口国家开放大学（中央广播电视大学）2022年秋季学期“开放本科”期末考试数据结构（本）试题2023年1月题号

一

二

三

四

总分分数得分评卷人----------------------、单项选择题（每小题2分，共30分）1.栈和队列的共同特点是（）。构

A.C.都是先进后出

元素都可以随机进出B.都是操作受限的线性结D.都是先进先出2.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行:p—（structnode*）malloc（sizeof（structnode）；p-〉data=a；和（）0A.p->nex—top;top—p；

B.top-〉next=

p—top；C.top=top-〉next；p=top；

D.pnext=top；p—top；3.设头指针为head的非空的单向链表，指针p指向尾结点，则通过以下操作（其成为单向循环链表。

）可使A.存储结构C.数据元素的存储A.p->next=NULL;C.p->next=head；4.一种逻辑结构（

）。

B.逻辑结构D.给数据元素分配存储空间B.head~p；D.p—head；740

A.只能有唯一的存储结构

B.可以有不同的存储结构C.与存储该逻辑结构的计算机相关

D.是指某一种数据元素的性质5-把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（

）。6.

图状结构中数据元素的位置之间存在（）的关系。A.一对一B.一对多C.多对多D.每一个元素都有一个且只有一个直接前驱和一个直接后继7.—个单链表中，在p所指结点之后插入一个s所指的结点时，可执行：s->next=p->谯乂1:；和（）。A.s=p->next；C.p=s->next；8.序依次进栈，则该栈的不可能输出序列是（交替进行）。A.18,16,14,12C.18,16,12,14

B.p-〉next=s->next；D.p->next=s；B.12,14,16,18D.14,12,18,16

元素12,14,16,18顺）。（进栈出栈可以9.设有一个30阶的对称矩阵A（第一个元素为an）,釆用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a912在一维数组B中的下标是（）oA.41C.18

B.32D.3810.设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（

）。A.15C.14

B.22D.2411.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（

）。

741A.2iC.2i+l12.-棵具有16个结点的完全二叉树，共有（A.7C.6742

B.2i-lD.2i+2）层。（设根结点在第一层）B.5D.413.如图1所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种A.abecdfgC.aebcfgd14.字符串"DABcdabcd321ABC”的子串是（A.“cd32”C.“aBcd"

B.acfebgdD.aedfcgb)oB.“ABcD"D.“321a"15.如图2所示，若从顶点a出发,按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（顶点序列为（

）。）oA.abcdfgeB.abcdfegC.acbfedgD.abcfgde741评卷人---------------二、填空题(每小题2分，共24分)16.对稀疏矩阵进行压缩存储，可釆用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有

列。17.在单向链表中，q指向P所指结点的直接后继结点，要删除q所指结点，可以用操作=q->next；。18.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和

三项信息。19.队列的操作特点是后进

。20.n个元素进行冒泡法排序，通常需要进行21.中序遍历二叉排序树可得到一个22.广义表(c,a,(a,b),d,e,((i,j),k))的长度是23.广义表的(c,a,(a,b),d,e,((i,j),k))深度是

趟冒泡。的序列。。。24.循环队列在规定少用一个存储空间的情况下，队空的判定条件为25.c语言中，字符串“E”存储时占

个字节。26.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2,则该树共有个叶结点。27.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较742

次。得—分卷入-

三、综合题(每小题15分，共30分)28,设查找表为(1,10,11,14,23,27,29,55,68),元素的下标依次为1,2,3,.......................,9。(1)(2)(3)

画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)。说明成功查找到元素14,需要依次经过与哪些元素的比较？共几次比较？求在等概率条件下,成功査找的平均比较次数？29.(1)以3,4,5,8,9,作为叶结点的权，构造一棵哈夫曼树。(2)(3)

给出相应权重值叶结点的哈夫曼编码。n个叶结点的哈夫曼树，总共有多少个结点？得分评卷人----四、程序填空题(每空2分，共16分)30.

以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型，BT指向根结点)。voidInorderCstructBTreeNode*BT)(i£(BT!=NULL){(1);Inorder(BT->right)；｝利用上述程序对图3进行遍历,结果是

;(2)74331.

以下冒泡法程序对存放在a：l],aC2],……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。voidbsort(NODEa口，intn){NODEtemp；inti,j,flag；for(j=l；(1){flag—0；for(iF;(2)if(a[i].