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

一、算法设计题

1． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。

【答案】算法如下:

求以双亲表示法作为存储结构的树的深度

深度加1, 并取新的双亲

最大深度更新

返回树的深度

’结束Depth

2． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。

【答案】算法如下:

判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论

中序遍历左子树

中序遍历的第一个结点不必判断

前驱指针指向当前结点

不是完全二叉树

中序遍历右子树

算法结束

判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回

false

若左右子树均为二叉

排序树

左子树中的最大值和右子树中

的最小值

不是二叉排序树

结束

求二叉树左子树的最大值

返回机器最小整数

求二叉树右子树的最小值

返回机器最大整数

3． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

【答案】算法如下:

在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，

将其

插入到二叉排序树中

f 指向当前结点的査找值为x 的结点，

双亲

无值为x 的结点，插入之

査询成功，值域为x 的结点的count 增

1

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

【答案】算法如下:

。现要求将K n 放在将元素排序后

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

5． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

) 小元素。

二、应用题

6． 己知n 阶下三角矩阵A(即当i ＜j 时，有序分配方式时在B 中确定元素

) ，按照压缩存储的思想，可以将其主对角线以

下所有元素(包括主对角线上元素) 依次存放于一维数组B 中，请写出从第一列开始采用列序为主

的存放位置的公式。

第1列有n 个元素，第j 列有n ﹣j ＋1个

在第j 列上的位置是为i

在一维数组B 中的存储位置k 与i 和j 的关

【答案】2阶下三角矩阵元素

﹣j ＋1。所以n 阶下三角矩阵A 按列存储，其元素系为:

元素，第1列到第j ﹣1列是梯形，元素数为(n＋(n﹣j ＋2)(j﹣1)/2，而