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

一、算法设计题

1． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

2． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和

为栈，容量足够大

分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

初始化

取出栈顶数据

在中序序列中査等于

.

根结点的值

无左子树

将建立左子树的数据入栈

第 2 页，共 37 页

的结点

无右子树

右子树数据入

结束

:

3． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

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

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

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

【答案】算法如下:

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

设P 指向二叉树的根结点

结束

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

后继结点

第 3 页，共 37 页

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

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

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

结库

.

5． 起泡排序算法是把大的元素向上移(气泡的上浮) ，也可以把小的元素向下移(气泡的下沉；请给出上浮和下沉过程交替的起泡排序算法。

【答案】算法如下:

相邻两趟向相反方向起泡的起泡排序算法，

起泡的上下界

设不发生交换

以上向下起泡

有交换，修改标志

change

修改界

气泡下沉，小元素上浮(向左

)

修改下界

二、应用题

6． 某网络中的路由器运行OSPF 路由协议, 下表是路由器R1维护的主要链路状态信息(LSI), 下图是根据下表及R1的接口名构造出来的网络拓扑。

表 R1所维护的LSI

第 4 页，共 37 页