数据结构第六章(树)习题答案(上)

作者名：不详　来源：网友提供 06年6月8日

一、基础知识题

6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回答下列问题：

(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?

(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?

(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?

6.2 一棵度为2的有序树与一棵二叉树有何区别?

答：一棵度为二的有序树与一棵二叉树的区别在于，有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。

6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

答： 答：三个结点的树如下：只有两种形态

○A ○A
/ \ |
○ ○ ○
|
○

三个结点的二叉树如下所示：有五种形态：

(1) (2) (3) (4) (5)

○A ○A ○A ○A ○A
/ \ / / \ \
○ ○ ○ ○ ○ ○
/ \ / \
○ ○ ○ ○

6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?

6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：

(1)各层的结点数目是多少?

(2)编号为i的结点的双亲结点(若存在)的编号是多少?

(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?

(4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?

解：
(1) 设层号为h的结点数目为m=k^(l-1)
(2) 编号为i的结点的双亲结点的编号是：：|_(i+k-2)/k_|(不大于(i+k-2)/k的最大整数。也就是(i+k-2)与k整除的结果.以下/表示整除。

(3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;
(4) 编号为i的结点有右兄弟的条件是(i+1)/k==(i+2)/k (整除) 并且i!=1
右兄弟的编号是i+1.

6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?

解：高度为h的完全二叉树至少有2^(h-1)个结点，至多有2^h-1个结点(也就是满二叉树)。

6.7 在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针?

解：空指针的个数为：n(k-1)+1;

6.8 假设二叉树包含的结点数据为1，3，7，12。

(1)画出两棵高度最大的二叉树；

(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。

解 解：(1)高度最大的两棵二叉树如图：

○1 ○1
/ \
○3 ○3
/ \
○7 ○7
/ \
○2 ○2
/ \
○12 ○12

(2)两棵完全二叉树如下：

○12 ○12
/ \ / \
○7 ○3 ○7 ○3
/ \ / \
○1 ○2 ○2 ○1

6.9试找出分别满足下面条件的所有二叉树：

(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；

(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。

6.10 试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。

评：此题测试我们对完全二叉树的掌握情况和两种存储方法的运用。
解：

6.11 分别写出图6.30(下图)所示各二叉树的前序、中序和后序序列。

6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。

(1)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。

(1)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。

6.13 对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。

6.14试画出图6.30(下图)所示各二叉树的前序、中序和后序线索树及相应的线索链表。

6.15 在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助?

答：分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。

6.16 对图6.31所示的森林：

(1)求各树的前序序列和后序序列；

(2)求森林的前序序列和后序序列；

(3)将此森林转换为相应的二叉树；

(4)给出(a)所示树的以亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?

解：
(1) (a)的前序序列：ABCDEF 后序序列：BDEFCA
(b)的前序序列：GHIJK 后序序列：IJKHG
(c)的前序序列：LMPQRNO 后序序列：QRPMNOL

(2) 此森林的前序序列： ABCDEFGHIJKLMPQRNO
此森林的后序序列： BDEFCAIJKHGQRPMNOL

(3) 此森林转化为二叉树的过程见动画：

6.17 画出图6.32(下图)所示的各二叉树所对就的森林。

6.17：解：各二叉树所对应森林如下：
-----------------------------
(a) ○A
-----------------------------
(b) ○A
｜
　 ○B
　 ｜
　 ○C
-----------------------------
(c) ○A ○B ○C
-----------------------------
(d) ○A ○C
/
○B
-----------------------------------------------
(e) ○A ○C ○F ○I
/ \ /
○B ○E ○L
/ | \
○D○H○K
/ |
○G ○J
------------------------------------------------

6.19 在什么样的情况下，等长编码是最优的前缀码?

6.20 下述编码哪一组不是前缀码?

{00,01,10,11},{0,1,00,11},{0,10,110,111}

6.21 假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.

(1)为这8个字母设计哈夫曼编码。

(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?

这道题原来做错了的，多亏了网友 会( briers@sina.com )热心指正，在此晓津要谢谢这位学友.

6.21 解：哈夫曼编码图见题图
根据上图可得编码表：
a:1001
b:01
c:10111
d:1010
e:11
f:10110
g:00
h:1000

(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均码长是等长码的87%。

所以平均压缩率为13%。