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

9

第1步

第2步

第5步

第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

F

H

J G

K

注意下面的考法：

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

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新(13)全文阅读和word下载服务。