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。给出每一趟排序的结果。
相关推荐：
loading