2021年山东科技大学数据结构与操作系统

/42021年山东科技大学数据结构与操作系统数据结构与操作系统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、某带权有向图及它的邻接表如下图所示，试写B2A34、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序、冒泡排序等。设一数组中原有数据如下：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分）C3DH1E3G22F4答题要求：用自然语言说明所采用算法的思想；给出每个算法所需的数据结构定义，并做必要说明；③用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）进程是具有一定独