2018年北京市培养单位空间应用工程与技术中心866计算机原理之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。
【答案】算法如下::
打印从根结点bt 到结点p 之间路径上的所有结点
.
是元素为二叉树结点指针的栈，容量足够大
是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同
步
根结点就是所找结点
左子女入栈，并置标记
找到结点P , 栈中元素均为结点P 的祖先
从根结点到P 结点的路径为
沿左分支向下
本题不要求输出遍历序列，
这里只出栈
沿右分支向下
结束算法
为叶结点
从根结点到P 结点的路径为
输出从根到叶子q 的路径上的所有袓先
2． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
且
满足下述性质
:
当且仅当存在某个顶点
22
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
第 2 页，共 38 页
3． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设
用
表示辅助地址表。初始时
减序) 算法的语句序列。
【答案】算法如下:
一趟排序无交换发生，结束
表示n 个结点的值，用
，在排序中，凡需对结点交换就用它的地址
来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递
4． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
第 3 页，共 38 页
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
5． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)
【答案】算法如下:
以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序
树
在调用时，
T=null
f 是P 的双亲
申请结点空间
根结点
左子女
右子树根结点的值大于等于根
结点的值
算法结束
中，试写出依次取A 中各值
构造一棵二叉排序
二、应用题
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的表。
第 4 页，共 38 页