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

一、应用题

1． 设二叉树BT 的存储结构如表：

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：

（1）画出二叉树BT 逻辑结构；

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列：

（3）画出二叉树的后序线索树。

【答案】（1）二叉树的逻辑结构如图1所示：

图1

（2）前序序列：ABCEDFHGIJ

中序序列：ECBHFDJIGA

后序序列：ECHFJIGDBA

（3）:二叉树的后续线索树如图2所示：

图2

2． 一个长度为的升序序列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 的较小一半，同时舍弃a 所在序列A 的较大一半。

③在保留的两个升序序列中求出新的中位数a 和b ，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。

（2）用C 语言算法描述如下：

//分别考虑奇数和偶数，保持两个子数组元素个数相等

//若元素个数为奇数个

//舍弃A 中间点以前部分且保留中间点

//舍弃B 中间点以后部分且保留中间点

}

//若元素个数为偶数个

//舍弃A 中间点及中间点以前部分

//舍弃B 中间点以后部分且保留中间点

//若元素个数为奇数个

//舍弃A 中间点以后部分且保留中间点

//舍弃B 中间点以前部分且保留中间点

//若元素个数为偶数个

//舍弃A 中间点以后部分且保留中间点

//舍弃B 中间点及中间点以前的部分

（3）说明算法的复杂性：算法的时间复杂度、空间复杂度分别是

3． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。

（2）快速排序，每划分一次书写一个次序。

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51:

第二趟：18，25，29， 47，10，12，51，58;

第三趟：10，12，18，25，29，47，51，58

（2）快速排序第一趟：10，18，25，12，29，58，51，47;

第二趟：10，18，25，12，29，47，51，88;

第三趟：10，12，18，25，29，47，51，88

（3）堆排序

建大堆：58，47，51，29，18，12，25，10;

①51，47，25，29，18，12，10，58;