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

一、算法设计题

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

【答案】算法如下:

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

沿左分支向下

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

沿右分支向下

若t 是

后序遍历中序线索二叉树

bt

沿左分支向下

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

P 为叶子, 相当从右返回

访问结点

修改P 指向双亲

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

.

转向当前结点右分支

结束

第 2 页，共 37 页

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

2． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。

【答案】算法如下:

r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储

本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后

当前元素是红色

当前元素是白色

当前元素是蓝色

3． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。

【答案】算法如下:

//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐

//滤掉s1左端空格

("字符串s1为空串或空格串\n")；exit(0)；

}

//字符串S1向字符串S2中

复制

(”字符串s1没有

//P指针也后退

//往后査找一个非空格字符作为串S2的尾字

符

("s1串没有

//字符串s2最后一个非空字符

//置S2字符串结束标记

//将s1串其余部分送字符串

S3

//置串S3结束标记

第 3 页，共 37 页

个有效字符\n"，n) ；exit(0)；

}

//若最后一个字符为空格，

则需向后找到第一个非空格字符

个两端对齐的字符串exit(0)；

}

4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。

【答案】算法如下:

在增加双亲指针

和标志域

的二叉树中，不用栈后序遍历二叉树

) 区分在遍

历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍

向左

向右

访问根结点

找被访问结点的双亲

结束

5． 已知深度为h 的二叉树，以一维数组应的算法。

【答案】算法如下:

作为其存储结构，试编写一算法，求该二叉

树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度

记叶结点数

若结点无孩子，则

是叶子

存储在数组后一半的元素是叶结点

二、应用题

第 4 页，共 37 页