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的过程如下：1 2 3顺序入栈，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 – c d / e f”对应的后缀式，画出其相应的二叉树，并画出该二叉树的中序线索树。（10分）（P129）

3、某带权有向图及它的邻接表如下图所示，试写出它的广度优先搜索序列，并根据克鲁斯卡尔算法，求它的最小生成树。（10分）

1 E 3 B G 2 3 2 6 D A 5 6 3 5

H 4 C 2 F

广度优先搜索序列:(P167)

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

B 2 A 3

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

C 3 D H 1 E 3 G 2 2 F 4 答题要求：

①用自然语言说明所采用算法的思想；

②给出每个算法所需的数据结构定义，并做必要说明； ③用C语言写出对应的算法程序，并做必要的注释。 1、已知有一个单向循环链表，其每个结点中含三个域：prior, data 和next，其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为空（NULL），试编写算法将此单向循环链表改为双向循环链表，即使prior成为指向前驱结点的指针域。（15分）

2、编写算法，在二叉树中求位于中序序列中第k个位置的结点的值。（15分）(P129)

分析：实际上是在考察中序遍历，然后在中序遍历中加上一个count变量，用来计数以确定是第几个位置。（一下代码参见P131）

TElemType InOrderTraverse(Bitree T, Status( * visit)(TElemType e)){

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))

Return error;

//出栈一个数，统计count加1； Count++;

If(Count>=k){//当统计个数到了k个时，返回所对应的数。

Return p->data; }

p=p->rchild; } } }

《操作系统》部分 （60分）

四、简答题（每小题6分，共30分）

1、什么是操作系统？操作系统的主要功能有哪些？

操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。

主要功能:

处理机的管理、存储器的管理、设备的管理、文件的管理、接口的管理 （参考题目：

什么是操作系统？它有什么基本特征？

答：操作系统是为了达到方便用户和提高资源利用率的目的而设计的，控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合，它具有并发、共享、虚拟、异步性四个基本特征。）

2、何谓进程？进程控制块的作用和包含的信息是什么？ （P41）

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位；

进程控制块的作用：使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

包含的信息：

本文来源：https://www.bwwdw.com/article/36f.html