2018年贵州师范大学物理与电子科学学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
2． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
第 2 页，共 33 页
若t 是的右孩子，返回1, 否则返回
后序遍历中序线索二叉树
bt
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
转向当前结点右分支
结束
3． 设要求按
是一个记录构成的数组，
是一个整数数组，其值介于1〜100之间，现
的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]
中去。规定可使用的附加空间为O(1)。
【答案】算法如下:
//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序
//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整
//B[j]和B[k]交换
//r0是数组A 的元素类型，A[j]和A[k]
交换
//完成了一个小循环，第i 个已经安排好
//算法结束
4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
第 3 页，共 33 页
) 区分在遍
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
向左
访问根结点
找被访问结点的双亲
结束
5． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
向右
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
整型
，值是
设元素类型为
二、应用题
6． 下列广义表，可以唯一对应一棵二叉树的有（ ）。并归纳出唯一对应的条件。
(1)(A(B(D，E) ，C(F))) (2)(A(B(D，E) ，C)) (3)(A)
(4)(A(B(C，D(E))))
(5)（ ）
【答案】唯一对应一棵二叉树的有(2)、(3)和(5)。唯一对应的条件:空表、只有一个元素的表、每个子表个数是零或是2的表。
7． 证明任一结点个数为n 的二叉树的高度至少为0(
) 。
。解此不等式，并考虑
。
【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低髙度是h ，则n 应满足h 是整数，则有
，即任一结点个数为n 的二叉树的高度至少为
第 4 页，共 33 页