《2022年山东科技大学数据结构与操作系统真题及参考答案.docx》由会员分享，可在线阅读，更多相关《2022年山东科技大学数据结构与操作系统真题及参考答案.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据构造局部一、简答题10 分，每题 5 分1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？P6 解：数据元素之间的关系在计算机中有四种不同的表示方法：(1) 挨次存储方法。数据元素挨次存放，每个结点只含有一个元素。存储位置反映数据元素间的规律关系。存储密度大，但有些操作(如插入、删除)效率较差。(2) 链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素 间的规律关系。这种操作不要求存储空间连续，便于进展插入和删除等操作，但存储空间利用率较低。另外，由于规律上相邻的数据元素在存储空间上不肯定相邻，所以不能对其进展随机存取。(3) 索引存储方法。除数据
2、元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。(4) 哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有 限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能挨次存储，也不能折半存取。2、对于堆排序法，快速排序法和归并排序法，假设仅从节约存储空间考虑，则应当首先选取其中哪种方法？其次选取哪种方法？假设仅考虑排序结果的稳定性，则应中选取其中哪种方 法？假设仅从平均状况下排序最快这一点考虑，则应中选取其中哪些方法？P289答：假设只从存储空间考虑，则应首先选取
3、堆排序方法，其次选取快速排序方法，最终选取归并排序方法；假设只从排序结果的稳定性考虑，则应选取归并排序方法； 假设只从平均状况下最快考虑，则应选取快速排序方法；假设只从最坏状况下最快并且要节约内存考虑，则应选取堆排序方法。二、应用题55 分1、证明：同一棵二叉树的全部叶子结点，在前序序列、中序序列以及后序序列中都按一样的相对位置消灭即先后挨次一样。8 分例如先序 abc，后序 bca，中序 bac。(P128)答：【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右挨次来遍历的，因此所 有叶子都按一样的相对位置消
4、灭。2、设有正文 AADBAACACCDACACAAD，字符集为 A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。10 分(P144;P148)3、对于以下图完成以下指定操作。12 分(1)从顶点A 动身，求它的深度优先生成树。(P167;) (2)从顶点E 动身，求它的广度优先生成树。(P169;)(3)依据普利姆(Prim) 算法，求它的最小生成树。(P173)4. 设哈希(Hash)表的地址范围为 017，哈希函数为：H (K)=K MOD 16, K 为关键字，用线性探测再散列法处理冲突，输入关键字序列 : (10,24,32,17,31,30,46,47,40,63,49
5、)构造哈希表，试答复以下问题：15 分P257(1) 画出哈希表示意图。(2) 假设查找关键字 63，需要依次与哪些关键字比较?(3) 假设查找关键字 60，需要依次与哪些关键字比较?(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。答：1画表如下2 查找 63,首先要与H(63)=63%16=15 号单元内容比较，即 63 vs 31 ,no;然后顺移，与 46,47,32,17,63 相比，一共比较了 6 次！（3） 查找 60,首先要与 H(60)=60%16=12 号单元内容比较，但由于 12 号单元为空应当有空标记，所以应当只比较这一次即可。（4） 对于黑色数据元素，
6、各比较 1 次；共 6 次；对红色元素则各不一样，要统计移位的位数。“63”需要6 次，“49”需要3 次，“40” 需要 2 次，“46”需要 3 次，“47”需要 3 次，ASL=1/11623317/111.555. 奇偶交换排序如下所述：对于初始序列 A1，A2,An,第一趟对全部奇数 i1=iAi+1，则将两者交换；其次趟对全部偶数 i2=iAi+1，则将两者交换；第三趟对全部奇数 i1=in； 第四趟对全部偶数i2=inext;if(p=NULL | p-next=NULL)return OK;/空表和表中只有一个结点时，不用逆置。while(p-next!=NULL) q= p-
7、next;p-next=q-next; /删除结点 q，但未释放q-next=L-next;L-next=q; /将 q 插入头结点之后return OK;/reverse2、二叉树承受二叉链表存储构造，设计算法统计二叉树的深度二叉树的最大层数和宽度二叉树中全部层中结点的最大个数。15 分标准答案：求树的高度思想：对非空二叉树，其深度等于左子树的最大深度加 1。Int Depth(BinTree *T)int dep1,dep2; if(T=Null)return(0); elsedep1=Depth(T-lchild); dep2=Depth(T-rchild); if(dep1dep2)r
8、eturn(dep1+1); elsereturn(dep2+1);求树的宽度思想：按层遍历二叉树，承受一个队列 q，让根结点入队列，最终出队列， 假设有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。int Width(BinTree *T)int front=-1,rear=-1;/*队列初始化* int flag=0,count=0,p;/* p 用于指向树中层的最右边的结点，标志 flag 记录层中结点数的最大值。*if(T!=Null)rear+; qrear=T; flag=1; p=rear;while(frontlchild!=Null)rear+;qrear=T-l
9、child; count+;if(T-rchild!=Null)rear+;qrear=T-rchild; count+;if(front=p)/* 当前层已遍历完毕*/if(flagcount) flag=count; count=0;p=rear;/* p 指向下一层最右边的结点*/* endwhile*/ return (flag);操作系统局部一： 简洁题 共27分 1：操作系统的四个根本特征是什么？并请分析它们之间的关系。本小题 3 分 (P15)答:操作系统的特征有并发,共享,虚拟和异步性.它们的关系如下:(1) 并发和共享是操作系统最根本的特征.为了提高计算机资源的利用率,操作系
10、统必定要承受多道程序设计技术,使多个程序共享系统的资源,并发的执行.(2) 并发和共享互为存在的条件.一方面,资源的共享以程序(进程)的并发执行为条件,假设系统不允许程序并发执行,自然不存在资源的共享问题;另一方面,假设系统不能对资源共享实施有效治理,协调好各个进程对共享资源的访问,也必将影响到程序的并发执行,甚至根本无法并发执行.(3) 虚拟以并发和共享为前提条件.为了使并发进程能更便利,更有效地共享资源,操作系统常常承受多种虚拟技术来在规律上增加 CPU 和设备的数量以及存储器的容量,从而解决众多并发进程对有限的系统资源的竞争问题.(4) 异步性是并发和共享的必定结果.操作系统允很多个并发
11、进程共享资源,相互合作,使得每个进程的运行过程受到其他进程的制约,不再“一气呵成“,这必定导致异步性特征的产生.2：请简述进程和程序的差异、进程和线程的差异。本小题 6 分(P37;P72) (定义： 程序只是一组指令的有序集合，二 进程是具有肯定独立功能的程序关于某个数据集合上的一次运行活动， 是系统进展资源安排和调度的一个独立单位；三 线程是进程的一个实体,是 CPU 调度和分派的根本单位,它是比进程更小的能独立运行的根本单位.线程自己根本上不拥有系统资源,只拥有一点在运行中必不行少的资源(如程序计数器,一组存放器和栈),一个线程可以创立和撤销另一个线程；)进程和程序区分和联系1)程序只是
12、一组指令的有序集合，它本身没有任何运行的含义，它只是一个静态的实体。而进程则不同，它是程序在某个数据集上的执行。进程是一个动态的实体，它有自己的生命周期。反映了一个程序在肯定的数据集上运行的全部动态过程。2)进程和程序并不是一一对应的，一个程序执行在不同的数据集上就成为不同的进程，可以用进程掌握块来唯一地标识每个进程。而这一点正是程序无法做到的，由于程序没有和数据产生直接的联系，既使是执行不同的数据的程序， 他们的指令的集合照旧是一样的，所以无法唯一地标识出这些运行于不同数据集上的程序。一般来说，一个进程确定有一个与之对应的程序，而且只有一个。而一个程序有可能没有与之对应的进程 (由于它没有执
13、行),也有可能有多个进程与之对应(运行在几个不同的数据集上)。3)进程还具有并发性和交往性，这也与程序的封闭性不同。进程与线程区分与联系(1) 划分尺度:线程更小，所以多线程程序并发性更高；(2) 资源安排：进程是资源安排的根本单位，同一进程内多个线程共享其资源； (3)地址空间：进程拥有独立的地址空间，同一进程内多个线程共享其资源； (4)处理器调度：线程是处理器调度的根本单位；(5)执行：每个线程都有一个程序运行的入口，挨次执行序列和程序的出口， 但线程不能单独执行，必需组成进程，一个进程至少有一个主线程。简而言之 , 一个程序至少有一个进程,一个进程至少有一个线程。3：处理死锁的根本方法
14、有哪几种？并请分析它们的优缺点。本小题 4 分P105(1) 预防死锁-事先预防法破坏一个或几个产生死锁的必要条件。实现简洁，常用资源利用率和系统吞吐量低；(2) 避开死锁-事先预防法利用算法动态安排资源防止系统进入担忧全状态。实现较难，资源利用率和系统吞吐量较高；(3) 检测死锁-允许运行中发生死锁准时检测到死锁及其有关进程和资源 ； 实现很难，资源利用率和系统吞吐量高。(4) 解除死锁-与检测死锁配套使用，挂起或撤销相关进程，回收资源并重安排检测和解除。实现很难，资源利用率和系统吞吐量高。4：“依据链接时间的不同，可把链接分为三种”，请问是哪三种？并请分析 DLL方式的优点。本小题 4 分
15、程序的链接 P120；P121 静态链接，装入时动态链接，运行时动态链接。DLL 是 Dynamic Link Library 的缩写，意为动态链接库。在 Windows 中，很多应用程序并不是一个完整的可执行文件，它们被分割成一些相对独立的动态链接库，即 DLL 文件，放置于系统中。当我们执行某一个程序时，相应的 DLL 文件就会被调用。一个应用程序可有多个 DLL文件，一个DLL 文件也可能被几个应用程序所共用，这样的DLL 文件被称为共享 DLL 文件。DLL 方式的优点：（1） 便于修改和更。（2） 便于实现对目标模块的共享。5：什么是 SPOOLING 技术？一个 SPOOLING
16、系统主要由哪几局部组成？本小题 4 分P190SPOOLing 是 Simultaneous Peripheral Operation On-Line 即外部设备联机并行操作的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术， 通常称为“假脱机技术”。1、输入井输出井2、输入缓冲区和输出缓冲区3、输入 SPi 和输出 SPo参考资料：SPOOLing 技术如何使一台打印机虚拟成多台打印机？答：将一台独享打印机改造为可供多个用户共享的打印机，是应用 SPOOLing 技术的典型实例。具体做法是：系统对于用户的打印输出，并不真正把打印机安排给该用户进程，而是先在输出井中申请一个空闲盘块
17、区，并将要打印的数据送入其中；然后为用户申请并填写恳求打印表，将该表挂到恳求打印队列上。假设打印 机空闲，输出程序从恳求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进展打印，直到打印队列为空。 6：连续安排、链接安排和索引安排是外存治理中常用的安排方式。请分析三者的优点和缺点。本小题 6 分连续安排P214优点：1挨次访问简洁2挨次访问速度快缺点：1要求有连续的存储空间2必需事先知道文件的长度链接安排P215优点：1不需要安排连续的空间 2消退了外部碎片 3可动态安排盘块，无需事先知道文件的大小。4文件增删改便利缺点：1对随机访问低效2牢靠性较差3存在内部碎片索引安排 (P221)
18、优点：1支持直接访问2不会产生外部碎片缺点：1可能花费较多的外存空间二：算法和计算题共33分1：设A、B 两进程共用一个缓冲区 Q 进展通信，A 向 Q 写入信息，B 则从 Q 读出信息。为了保证进程A、B 之间的通信顺当进展，某同学设计了一个如以下图所示的算法，该算法使用一个信号量S 进展进程 A、B 之间的同步。请问，该算法是否正确?假设有错，请指出缘由并予以改正。此题 10 分生产者-消费者问题P58解：这个算法不对。由于 A、B 两进程共用一个缓冲区 Q，假设 A 先运行，且信息数量足够多， 那么缓冲区 Q 中的信息就会发生后面的冲掉前面的，造成信息丧失，B 就不能从Q 中读出完整的信
19、息。进展改正： A、B 两进程要同步使用缓冲区 Q。为此，设立两个信号量： empty 表示缓冲区 Q 为空，初值为 1；full 表示缓冲区 Q 为满，初值为 0。算法框图如下图。2：某虚拟存储器的用户空间共有 32 个页面，每页 1KB，而主存为 16KB。假定某时刻系统为用户的第 0、1、2、3 页安排的物理块号为 5、10、4、7，而该用户作业的长度为 6 页。请问：此题总计 10 分提示：请留意规律地址是由哪两局部组成的虚拟存储器 P1411） 十六进制的规律地址也称为虚拟地址0A5C 对应的物理地址是什么？2 分(P130)2） 假设要访问的十六进制的规律地址是 103C，那么会消
20、灭什么现象？操作系统是如何处理这种现象的，并请说明处理过程。6 分P145缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进展访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。缺页中断作为中断，它们同样需要经受诸如保护cpu 环境、分析中断缘由、转入缺页中断处理程序进展处理、恢复cpu 环境等几个步骤。3） 假设要访问的十六进制的规律地址是 1A5C，那么会消灭什么现象？ 2 分3：假设磁盘有 200 个磁道，磁盘恳求队列中都是随机恳求，它们依据到达的次序分别处于 55、58、39、18、90、160、150、38、184 号磁道上，当前磁头在100 号磁道上，并向磁道
21、号增加的方向移动。请给出按着FCFS、SSTF 算法进展磁盘调度时的次序，并计算平均寻道长度。此题 7 分P194分析：FCFS 算法按进程恳求访问磁盘的先后次序进展效劳;SSTF 算法优先为距离当前磁头所在磁道最近的恳求进展效劳;SCAN 算法则优先为在磁头当前移动方向上、与当前磁头所在磁道最近的恳求进展效劳;CSAN 算法类似于 SCAN 算法,但它规定磁头只能作单向移动。答:磁盘调度的次序以及它们的平均寻、道长度如表6.1 所示。表 6.1 磁盘调度的次序以及平均寻道时间FCFSSSTFSCANCSCAN被访问的 移动的下一个磁 磁道数道号被访问的 移动的下一个磁 磁道数道号被访问的下一
22、个磁道号移的磁数动道被访问的 移动的下一个磁 磁道数道号554590101505015050583583216010160103919553184241842418213916909418166907238158323820160701820553391150101501323916551638112160103815831841461842418209032平均寻道长度:55.3 平均寻道长度:27.6 平均寻道度:27.8平均寻道长度:35.84：随着 CPU 速度的不断提升，IO 设备的速度渐渐成为系统性能的瓶颈之一。请分析、说明现代操作系统是如何缓解这一问题的，并列举多个解决方案。此题 6 分(SPOOLing 技术？P189;多通道？；这个真不会，看书总结)