广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新

10．堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶

子结点”上。（ × ） 了解堆排序过程

三、简答题（每小题5分，共30分）

1、对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。 4，5，6，7，1O，12，15，18，23

4，5，6，7，1O，12，15，18，23

9

4 5 6 13 7 10 19 25 33 12 15 18 9 13 5 6 7 第1步

第2步

4 第5步

第3步 第4步 42 23 19 58 25 33 12 15 18 23 10 9 4 5 6 13 7 10 12 15 18 4 第6步 第7步 5 6 7 第8步

以上是Huffman树的构造过程，考试时需要先在草稿上一步一步构造，只需要把最后的Huffman树写出来就可以。每个叶子结点的路径长度就是从根结点开始到叶子结点的树枝条数，如4的路径长度是4,23的是2等。 叶子的带权路径长度=权值*路径长度

树的带权路径长度=所有叶子结点的带权路径长度之和 WPL=4*4+5*4+10*3+23*2+6*4+7*4+12*3++15*3+18*3=。。。。 算一下，就知道结果了。

2、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求

出空格处的内容，并画出该二叉树。

先序： A B D F K I（前为左和后为右） C E H J G 中序：D B K F I (左) A（右） E J C G 后序： D K I F B H J E G C A(根)

步骤：先序（根-左-右）， 中序（左-根-右）， 后序（左-右-根）： 1） 从后序 K F B H J G A（根），知道A是根结点

2） 从中序，知道左子树和右子树D K F I （左）A（右） E J C 3） 从先序知道B是左子树的根结点A B

4） 从中序D B知道D是B的左孩子，K F I是B的右子树上结点

5） 从后序F B知道F是B的右子树上根结点，根据中序K F I知道K是左，I是右 先序序列得出：

先序： A B D F K I（前为左和后为右） C E H J G

6） 从先序C E知道A的右子树根结点是C，从中序得知C只有一个右结点。 从先序C E H J G得知必为G，再结合先序，中序序列得出 中序: D B K F I (左) A（右） H E J C G 然后，后序序列得出：

后序： D K I F B H J E G C A(根) 这树就出来了:

B为A左子树的根，D为B的左子树，F为B的右子树的根，K为F的左，I为F的右。 C为A右子树的根，G为C的右子树，E为C的左子树的根，H为E的左，J为E的右。

A

B D F

I H

E J C G

K

注意下面的考法：

3、设有序列：{11，30，5，6，23，17，29，37，4，13，33}，用希尔排序法进行

排序，设d1=5，d2=3，d3=1。给出每一趟排序的结果。