当前位置：问答库＞考研试题

一、算法设计题

1． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

2． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径

。

设有向图有n 个顶点

判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径

是队列，容量足够大，元素是顶点编号

人队

第 2 页，共 34 页

【答案】算法如下:

到顶点

不存在路径

3． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ，指针i 均后移

//算法结束

4． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。

【答案】算法如下:

//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和

C

//为C 申请结点空间

//C初始化为空表

第 3 页，共 34 页

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

//将小于0的结点链人B 表

//P指向新的待处理结点

//算法结束

5． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

二、应用题

6． 解答问题。设有数据逻辑结构为:

(1)画出这个逻辑结构的图示。

(2)相对于关系R ，指出所有的开始结点和终端结点。 (3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的正向邻接表和逆向邻接表。 【答案】(1)如图1所示:

图1

第 4 页，共 34 页