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

一、应用题

1． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？

【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。

2． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。

【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。

3． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

4． 在某程序中，有两个栈共享一个一维数组空间的栈底。

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句

出栈主要语句

分别是两个栈

（2）

5． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS 。

（2）依此二叉排序树，如何得到一个从大到小的有序序列？ （3）画出在此二叉排序树中删除“66”后的树结构。 【答案】（1）构造的二叉排序树如图1所示：

图1 二叉排序树

（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。

（3）如图2所示：

图2

6．

设与记录

对应的关键字分别是

进行交换。

之前全部记录

（其

的关键字一定

如果存在

和

使得

且

成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括为又因

7． 一个长度为

在

之前且

则

故

即说明

和

【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极

是反序；设对于

和

）中关键字最大为

，故经过起泡排序前i-2次比较后，

必定交换，证毕。

和Rf 为反序，由此可知

的升序序列S , 处在第「L/2」个位置的数为S 的中位数。例如，若序列

Sl= （11，13, 15, 17，19），则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= （2, 4, 6, 8, 20）, 则S1和S2的中位数是11。现有两个等长升序序列A 和B ，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。

【答案】（1）算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b 。 ① 若a=b，则a 或b 即为所求的中位数。

② 否则，若a

所在序列B 的较大一半。若a>b，中位数只能出现（b ，a ）范围内，舍弃b 所在序列B 的较