数据结构应用题练习VIP专享VIP免费

1、假设一棵二叉树的层序序列是ABCDEFGHIJ 和中序序列是DBGEHJACIF,请画出该树。 21 、有一个完全二叉树按层次顺序存放在一维数组中，如下所示： 请指出结点P 的父结点，左子女，右子女。 3、给出下列二叉树的先序序列。 4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。 答案：二叉树形态 AFHGDECB （2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。 ABFD(CEHGAEDCBHGFAEDCBHGFn u ll (1) (2) 1、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L 中序序列：D,J,G,B,E,H, A,C,K,I,L,F。 i. 写出该二叉树的后序序列； ii. 画出该二叉树； iii. 求该二叉树的高度(假定空树的高度为－1)和度为 2、度为 1、及度为 0 的结点个数。 该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。 该二叉树的形式如图所示： 该二叉树高度为：5。 度为 2 的结点的个数为：3。 度为 1 的结点的个数为：5。 度为 0 的结点个数为：4。 5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答案： A B J K I F C G E D L H 21561 11 87341 23 0 WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69 6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。 答案：(1)树形态： 32551 01 99761 33 2 (2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79 （3） 假设用于通信的电文仅由8 个字母组成，字母在电文中出现的频率分别为0 .0 7 ，0 .1 9 ，0 .0 2 ，0 .0 6 ，0 .3 2 ，0 .0 3 ，0 .2 1 ，0 .1 0 。 ① 试为这8 个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码 先将概率放大100 倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32 （100） （40） （60） 19 21 32 （28） （17） （11） 7 10 6 （5） 0 1 0 1 0 1 1 9 2 1 3 2 0 1 0 1 0 1 7 1 0 6 0 1 2 3 2 3 方案比较： 方案1的W PL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0...