一、数据结构部分：算法应用题 1. 已知二叉树的先(前)序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出此二叉树，并给出其后序遍历序列。 根据二叉树的先序遍历序列和中序遍历序列得到其图像如下所示，由此易知它的后序遍历序列为CEFDBHGA。

[考点] 本题考查二叉树的遍历。 2. 对关键字序列(712，817，611，213，904，106，45，598)进行堆排序，请给出调整后的初始最小堆。 调整后的初始最小堆如下所示：

[考点] 本题考查小根堆的构建。

[解析] 先将关键字序列按顺序排列成一颗完全二叉树，然后从后往前依次检查每个非叶子节点是否满足根结点小于左右孩子结点的特点。若不满足，则将左右孩子结点中最小的一个孩子与根结点交换，直至整颗树满足这一特点。调整初始小根堆的过程如下图所示：

阅读全卷     帮助     下载试卷