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

一、算法设计题

1． 设单链表的表头指针为h , 结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc （h , n ）, 判断该链表的前n 个字符是否中心对称。例如xyx , xyyx 都是中心对称。

【答案】算法如下：

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

【答案】算法如下：

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

【答案】算法如下：

现要求将

放在将元素排序后的

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

4． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设，并同样以元素值的递增有序的单链表形计算法求出A 与B 的交集C ，要求C 另开辟存储空间。式存储。

【答案】算法如下：

5． （1）试分别找出满足下列条件的所有二叉树：（a ）前序序列和中序序列相同：（b ）前序序列和后序序列 相同；（c ）中序序列和后序序列相同。

，设计算法：从右向左依次将所有（2）已知非空二叉树的结点结构为（lchild , data , rchild ）叶子的数据值 放到向量（假定向量的空间大于叶子的总个数）中。

【答案】（1）满足条件的二叉树如下：

（a ）若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 （b ）若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

（c ）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 （2）算法如下：

//全局变量

//从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中

//中序遍历右子树

//叶结点

//中序遍历左子树

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

//设有向图有n 个顶点

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

【答案】算法如下：

到顶点

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

号

）

//Vi人队

到顶点

7． 设求按

是一个记录构成的数组，

是一个整数数组，其值介于1～100之间，现要

时，则要求将

的内容调整到

中

不存在路径

的内容调整A 中记录的次序，比如当

去。规定可使用的附加空间为

【答案】算法如下：