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

一、算法设计题

1． 写出按后序序列遍历中序线索树的算法。

【答案】算法如下:

求结点t 最左子孙的左线索

沿左分支向下

求结点t 最右子孙的右线索

沿右分支向下

若t 是

后序遍历中序线索二叉树

bt

沿左分支向下

左孩子为线索，右孩子为链，相当从左返回

P 为叶子, 相当从右返回

访问结点

修改P 指向双亲

是左子女，用最右子孙的右线索找双亲

.

转向当前结点右分支

结束

第 2 页，共 34 页

的右孩子，返回1, 否则返回

2． 对给定关键字序号j(1

录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。

例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下；

在后半部分继续进行划分

在前半部分继续进行划分

3． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下:

在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回

确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情

况

返回第一邻接点，

和

中必有一个等于

i

取第一个边结点

4． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为:

线性表可能达到的最大长度}；

第 3 页，共 34 页

【答案】算法如下:

//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值

//当査找失败时，low ＝high ＋

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

//插入元素x ，线性表长度增

1

//结束过程creat

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

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

【答案】(1)满足条件的二叉树如下:

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

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

全局变量

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

第 4 页，共 34 页

中序遍历右子树