四、应用题 1. 有中缀表达式(15-（17-2）/5)*3， （1）求其后缀表达式；（2）请使用顺序栈进行后缀表达式运算，请做出该栈变化图。 36 2.某电文中由A、H、C、T、F字符构成，对应字符出现的频率为3、8、2、5、3， （1）请做出构建哈夫曼树的过程；（4分） （2）计算该哈夫曼树的WPL。（2分） 3. 有无向图G如下： 使用邻接表存储该图，请做出邻接表的存储逻辑图，并使用普利姆算法分步骤做出最小生成树。 4.有关键字45,4,33,23,67，18,78,65,50， （1）请构建对应的二叉排序树；（2分） （2）请做出删除关键字为67的结点后的二叉排序树。（2分） （3）计算（2）中二叉排序树的ASL。（2分） 5. 有排序码11,21,14,5,71,9，请使用堆排序法写出排序过程。

1. （1）中缀表达式(15-（17-2）/5)*3的后缀表达式为：15 17 2 - 5 / - 3 *

（2）使用顺序栈进行后缀表达式运算的栈变化图如下所示（其中第一行表示栈顶，最后一行表示栈底）：

入栈15：    15
入栈17：    15 17
入栈2：     15 17 2
执行减法：  15 15
入栈5：     15 15 5
执行除法：  15 3
执行减法：  12
入栈3：     12 3
执行乘法：  36

2. （1）构建哈夫曼树的过程如下所示：

首先将所有字符的出现频率从小到大排序，得到：A(3)、C(2)、F(3)、H(8)、T(5)。

接着取出频率最低的两个字符C和A，组成一棵二叉树，其根节点的权值为5。

     5
   /   \
  C(2)  A(3)

然后将剩下的字符F、H、T和上一步的二叉树进行同样的操作，得到下面的哈夫曼树：

                21
           /          \
         10(F)      11
                    /   \
                 5(C)  6
                         /    \
                      3(A)  3(H)
                            \
                             2(T)

（2）该哈夫曼树的WPL为：

WPL = 10×1 + 5×2 + 3×3 + 3×3 + 2×3 = 37

3. 使用邻接表存储该图的存储逻辑图如下所示：

   1 --- 2 --- 3
   |     |     |
   4 --- 5 --- 6

使用普利姆算法分步骤做出最小生成树的过程如下：

- 以1为起点，选择与其相邻的最小边4-1，将4和1加入最小生成树中，得到生成树{1,4}；
- 以1和4为起点，选择与它们相邻的最小边2-1和4-5，将2和5加入最小生成树中，得到生成树{1,4,2,5}；
- 以1、4、2和5为起点，选择与它们相邻的最小边3-2，将3加入最小生成树中，得到最终的生成树{1,4,2,5,3}。

最终的最小生成树的表示如下所示：

   1 --- 2 --- 3
    \   /     |
     \ /      |
      4 --- 5

4. （1）关键字45,4,33,23,67，18,78,65,50构建的二叉排序树如下所示：

            45
           /  \
          4    67
           \     \
            33   78
           /  \   /
          23  50 65

（2）删除关键字为67的节点后的二叉排序树如下所示：

            45
           /  \
          4    78
           \   / \
            33 50  65
           /
          23

（3）计算该二叉排序树的ASL的过程如下：

- 23在深度2处，出现概率为1/9；
- 33在深度3处，出现概率为1/9；
- 4在深度2处，出现概率为1/9；
- 50在深度3处，出现概率为1/9；
- 65在深度3处，出现概率为1/9；
- 78在深度2处，出现概率为2/9；
- 45在深度1处，出现概率为1；

因此，该二叉排序树的ASL为：

ASL = (2×1/9 + 3×2/9 + 2×1/9 + 3×1/9 + 3×1/9 + 2×2/9 + 1×1)/1 = 2.33

5. 使用堆排序法进行排序的过程如下所示：

首先将无序序列构建成一个最大堆，得到：71 21 14 5 11 9。

然后将堆顶元素71与堆底元素9交换位置，得到：9 21 14 5 11 71。

接着将前5个元素重新构建最大堆，得到：21 11 14 5 9。

将堆顶元素21与堆底元素9交换位置，得到：9 11 14 5 21。

将前4个元素重新构建最大堆，得到：14 11 5 9。

将堆顶元素14与堆底元素9交换位置，得到：9 11 5 14。

将前3个元素重新构建最大堆，得到：11 9 5。

将堆顶元素11与堆底元素5交换位置，得到：5 9 11。

最终得到有序序列：5 9 11 14 21 71。