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

一、算法设计题

1． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。

【答案】算法如下:

//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面

//设链表有头结点

//q指向待处理结点

//P记数据域值最大的结点

//将P 摘下

//插人P 结点

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

【答案】算法如下:

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

C

//为C 申请结点空间

//C初始化为空表

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

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

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

//算法结束

3． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

4． 编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。

图

【答案】算法如下:

//将自然数

，按" 蛇形M 填入n 阶方阵A 中

//i，j 是矩阵元素的下标，k 是要填入的自然数

//从右上向左下填数

//副对角线及以上部分的新i ，j 坐标

//副对角线以下的新的i ，j 坐标

//从左下向右上

//最外层

while

5． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

.

二、应用题

6． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如0-2-7-9-11) 表示进行作业的路径。

完成此工程的关键路径是(A)完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的事件的充裕天数是(E)。