2012年山东科技大学数据结构与操作系统--真题及参考答案

数据结构与操作系统Z试卷《数据结构》部分（90分）一、简答题（20分，每题5分）1、请给出四种数据结构基本类型。答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构：（1）集合。。。（2）线性结构。。。（3）树形结构。。。（4）图状结构或网状结构。。。2、简述栈和队列的区别。（P44;P58）区别和联系：从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。3、什么是关键路径？(P183)在AOE网中，有些活动可以并行地运行，最短完成时间应是从源点到汇点的最长路径长度（指路径上所有权值之和），称这样的路径为关键路径。4、插入类排序有哪几种？其中，哪些是不稳定的排序算法？(P265)二、应用题（40分）1、如果进栈的序列是12345，请给出所有3、4先出栈的序列（3在4之前出栈）。（5分）(P)【解答】34215，34251，34521(可以参考下面这个题：【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出进栈或出栈的序列)。【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。得到325641的过程如下：123顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。)2、给出先缀表达式“-+a*b–cd/ef”对应的后缀式，画出其相应的二叉树，并画出该二叉树的中序线索树。（10分）（P129）3、某带权有向图及它的邻接表如下图所示，试写出它的广度优先搜索序列，并根据克鲁斯卡尔算法，求它的最小生成树。（10分）广度优先搜索序列:(P167)A--B--C--D--E--F--G--H克鲁斯卡尔算法，求最小生成树:(P173)4、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序、冒泡排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。（15分）(必须对算法的具体步骤有详细的了解，认真看看书吧P263)（①）排序的结果为：12，13，15，18，20，60（②）排序的结果为：13，15，18，12，20，60（③）排序的结果为：13，15，20，18，12，60【参考答案】①快速排序②冒泡排序③直接插入排序三、算法设计题（30分）ABC^BCDEFGHDE^F^CFG^EH^G^HG^^BCEAGDFH233512346526BCEAGDFH23312342答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③用C语言写出对应的算法程序，并做必要的注释。1、已知有一个单向循环链表，其每个结点中含三个域：prior,data和next，其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为空（NULL），试编写算法将此单向循环链表改为双向循环链表，即使prior成为指向前驱结点的指针域。（15分）2、编写算法，在二叉树中求位于中序序列中第k个位置的结点的值。（15分）(P129)分析：实际上是在考察中序遍历，然后在中序遍历中加上一个count变量，用来计数以确定是第几个位置。（一下代码参见P131）TElemTypeInOrderTraverse(BitreeT,Status(*visit)(TElemTypee)){InitStack(S);p=T;Count=0;While(p||!StackEmpty(S)){If(p){Push(S,p);p=p-lchild;}Else{Pop(S,p);If(!visit(p-data))Returnerror;//出栈一个数，统计count加1；Count++;If(Count=k){//当统计个数到了k个时，返回所对应的数。Returnp-data;}p=p-rchild;}}}《操作系统》部分（60分）四、简答题（每小题6分，共30分）1、什么是操作系统？操作系统的主要功能有哪些？操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。主要功能:处理机的管理、存储器的管理、设备的管理、文件的管理、接口的管理（参考题目：什么是操作系统？它有什么基本特征？答：操作系统是为了达到方便用户和提高资源利用率的目的而设计的，控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合，它具有并发、共享、虚拟、异步性四个基本特征。）2、何谓进程？进程控制块的作用和包含的信息是什么？（P41）进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位；进程控制块的作用：使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。包含的信息：进程标识符，处理机状态，进程调度信息，进程控制信息3、产生死锁的必要条件是什么？处理死锁的基本方法有哪些？必要条件：(1）互斥条件（2）请求和保持条件（3）不剥夺条件（4）环路等待条件基本方法:（1）预防死锁（2）避免死锁（3）检测死锁（4）解除死锁4、何谓虚拟存储器？它有哪些特征？（P143）虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体的说，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储器的基本特征是：(P144)多次性，对换性，虚拟性。（补充：①离散分配，即不必占用连续的内存空间；②部分装入，即每个作业不是全部一次性地装入内存，而是只装入一部分；③多次对换，即所需的全部程序和数据要分成多次调入内存④虚拟扩充，即不是物理上而是逻辑上扩充了内存容量；另外：虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制。）5、Spooling系统由几部分组成？它有哪些特征？（P190）答：Spooling系统由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程共3部分组成。Spooling系统的特点有：(P191)（1）提高了I/O速度。I/O操作时针对输入井和输出井，避免了操作低速I/O设备的速度不匹配。（2）将独占设备改造为共享设备。Spooling系统没有为任何进程实际分配设备，只是在输入井或输出井中为进程分配一个存储区和建立一张I/O请求表。（3）实现了虚拟设备功能。宏观上有多个进程在同时使用一台独占设备，但对于每一个进程而言，他们认为自己独占了一个设备。五、算法和计算题（每小题10分，共30分）1.使用P、V操作描述读者-写者问题。要求允许几个阅读者可以同时读该数据集，而一个写着不能与其他进程（不管是写者还是读者）同时访问该数据集。（P63）答：【分析】读者-写者问题是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只要求读数据（称为Reader），另一些进程则要求修改数据（称为Writer）。就共享数据而言，Reader和Writer是两种不同类型的进程。一般地，两个或两个以上的Reader进程同时访问共享数据时不会产生副作用，但若某个Writer和其他进程（Reader或Writer）同时访问共享数据时，则可能产生错误。为了避免错误，同时尽可能地让读者进程和写者进程并发运行，只要保证任何一个写者进程能与其他进程互斥访问共享数据即可。这个问题称为读者-写者问题。【解答】P、V操作是定义在信号量s上的两条原语，它是解决进程同步与互斥的有效手段。定义下列信号量：互斥信号量rmutex，初值为1，用于使读者互斥地访问读者计数器，共享变量rcount；互斥信号量wmutex，初值为1，用于实现写者之间以及写者与读者之间互斥地访问共享数据集。用信号量和P、V操作描述读者-写者问题如下：Beginrmutexwmutex:semaphore;rcount:Integer;rmutex=wmutex=1;rcount=0;CobeginProcessprocedureReaderbeginP(rmutex);//保护rcountrcount:=rcount+1ifrcount=lthenP(wmutex);//保证没有writer在写V(rmutex);Performreadoperations;P(rmutex);rcount:=rcount-1;ifrcount=OthenV(wmutex);//没有reader时，允许writer写操作V(rmutex);endProcessprocedureWriterbeginP(wmutex);performwriteoperations;V(wmutex);endCoendEnd2.假定在某移动臂磁盘上，刚刚访问了75号柱面的请求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：请求次序12345678访问的柱面号736810012060108850试用：（1）电梯调度算法；（2）最短寻找时间优先算法，分别列出实际处理上述请求的次序。（1）36412587(2)12587364(参考题目及解析：假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面上读信息，并有下列请求序列等待访问磁盘：请求序列：l2345678欲访问的柱面号：16040190188905832102试用(1)电梯调度算法；(2)最短查找时间优先算法，分别排出实际处理上述请求的次序。答：(1)电梯调度算法是从移动臂当前位置开始，沿臂的移动方向取选择离当前移动臂最近的柱面访问，如果该方向上没有访问请求，则改变臂的方向再选择。从题中可以看出，先访问的是75柱面，正在访问80柱面。显然移动臂当前的移动方向是从小柱面号到大柱面号。所以采用电梯调度算法，先依次访问的应该是90、102、160、188、190号柱面，之后掉转方向去依次访问58、40、32号柱面。(2)最短查找时间优先算法每次总是让查找时间最短的请求先执行，不管它是不是先访问的，也不管它在什么方向上。所谓查找时间最短的是指移动臂从当前位置移动要访问的若干个位置中移动距离最短的位置上所花的时间。针对本题，依次先处理的是90、102号柱面后，磁头当前离58号柱面有44个柱面的距离，而离160号柱面有58个柱面的距离，显然要先访问58号柱面，依次下去访问的应该是40、32、160、188、190号柱面。(1)用电梯调度算法处理次序是5、8、1、4、3、6、2、7。(2)用最短查找时间优先算法处理的次序5、8、6、2、7、l、4、3。)3.在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示：作业提交时间运行时间18:001.028:500.5039:000.2049:100.10试计算一下三种作业调度算法的平均周转时间T和平均带权周转时间W：（1）先来先服务；（2）短作业优先；（3）响应比高者优先；解：作业I的周转时间Ti＝作业I的提交时间－作业I的完成时间＝作业I的运行时间＋作业I的等待时间作业I的带权周转时间Wi＝Ti/作业I的