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

本文格式为Word版，下载可任意编辑——2023年山东科技大学数据结构与操作系统数据结构与操作系统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分）

1E3BG2326DA5635

H4C2F

广度优先探寻序列:(P167)

ABCDEFGHBDF^CG^EH^C^E^FG^H^^A-->B-->C-->D-->E-->F-->G-->H克鲁斯卡尔算法，求最小生成树:(P173)

B2A3

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分）

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）