数据结构复习题-第6章答案2014-6-16

第6章 树和二叉树

一、选择题（每小题1分，共10分） 1.以下数据结构中，（ A ）是非线性数据结构。 A.树 B.线性表 C.队列 D.栈 2.在一棵二叉树中第五层上的结点数最多为（ B ）。 A.8 B.15 C.16 D.32

3. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。

A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。 A.9 B.11 C.15 D.不确定

5.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（ D ）。

A. LRN B. NRL C. RLN D. RNL 6.在下列存储形式中，哪一个不是树的存储形式？（ D ）

A.双亲表示法 B.孩子表示法 C.孩子兄弟表示法 D.顺序存储表示法 7.有n个叶子的哈夫曼树的结点总数为（ D ）。

A．不确定 B．2n C．2n+1 D．2n-1

8.设i为n个结点的完全二叉树结点编号，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ B ）

A.2i B.2i+1 C.2i-1 D.i+1

9. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）。

A.23 B.37 C.44 D.46

10.一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）。 A.

+1 B. log2n+1 C.

D. log2n-1

11.由权值分别为7，9，4，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。 A.36 B.60 C.48 D.53 12.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。 A. 24 B. 71 C. 48 D. 53 13.具有35个结点的完全二叉树的深度为( B )。 A. 5 B. 6 C. 7 D. 8

14.由权值分别为３,８,６,２,５的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）．

A．24 B．55 C．72 D．53

15.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( A )。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对

16.具有10个叶子结点的二叉树中有( B )个度为2的结点。 A．8 B．9 C．10 D．11

二、判断题（每小题1分，共10分）

1.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（对 ） 2.二叉树的遍历结果不是唯一的。（对 ） 3.二叉树中序线索化后，不存在空指针域。（对 ） 4.在二叉树的第i层上至少有2i-1个结点(i>=1)。（错 ）

5.设T为哈夫曼树，具有5个叶结点，树T的高度最高可以是4。(错 ) 6.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（错 ）

7.有n个叶子结点的哈夫曼树所具有的结点数为2n。（ 错 ）。 8.用树的前序遍历和中序遍历可以导出树的后序遍历。( 错 )

9．二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（ √ ） 10．度为2 的有序树是二叉树。（ × ）

11．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（ √ ） 12．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×）

13．若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（ × ） 14．在哈夫曼树中，权值最小的结点离根结点最近。( × ) 三、填空题（每空1分，共10分）

1.具有n个结点的完全二叉树的深度为 。

+1

2.设只含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为 ，最小结

k

点数为 。2-1、k

3.将一棵树转化为二叉树时，此二叉树的根节点的右子树为 。 空树

四、简答题（共10分）

1.满二叉树和完全二叉树有什么区别？

答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个叶子结点，满二叉树是完全二叉树的一个特例。 2.画出二叉树的五种基本形态。

答：二叉树的五种基本形态为： 3.在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。 4.什么是哈夫曼（Huffman）树？

答：设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则带权路径长度WPL最小的二叉树叫哈夫曼树或最优二叉树。

或者：又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。

五、应用题（共40分）

1.（8分）已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题： (1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？ (2)树的度是多少？各个结点的度是多少？

(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？ 2.用一维数组存放的一棵完全二叉树如下表所示

A B C D E F G H I J K L 写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序。 3.（5分）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，证明：n0=n2+1。 4.叙述并证明二叉树的性质3。 5.（8分）已知一棵二叉树如下，

（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。 （2）如果此二叉树由森林转换得到，请画出原森林中的各棵树。

6.（8分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ；中序：ABCDEFGHIJK。

7.有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。

8.（8分）二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG和CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。

9.（6分）二叉树的先序序列为EBADCFHGIKJ；二叉树的中序序列为ABCDEFGHIJK，请画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。

10.（8分）设一棵二叉树的先序、中序遍历序列分别为

先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C 请画出该二叉树，并将这棵二叉树转换成对应的树（或森林）。

11.（8分）设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。并写出后序和层次遍历序列。

12.（6分）设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 13.（8分）假设字符a,b,c,d,e,f,g,h的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11画出哈夫曼树并写出a,b,c,d,e,f,g,h的Huffman（哈夫曼）编码。

14.（8分）假设字符a,b,c,d,e,f的使用频度分0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。

15.（8分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.10,0.12,0.16,0.25,0.30，构造哈夫曼树并写出a,b,c,d,e,f的哈夫曼编码。

16.（6分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。 17.请画出下图所示的树所对应的二叉树。

答案：

18.（6分）请画出与下列二叉树对应的森林。

19.已知一棵树边的集合为{,,,,,,,, , ,,,}，请回答下列问题：

（1）哪个是根结点？（2）哪些是叶子结点？哪些是分支结点？（3）哪个是结点G的双亲结点？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？

（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是多少？（9）树的深度是多少？ （10）以结点C为根的子树的深度是多少？

20.假设在树中，结点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）树的度数是多少？

21.已知一棵树边的结点为（I,M），(I，N),(E，I),(B，E)，(B，D),(C，B),(G，L)，(G，K)，(A，G)，(A，F),(H，J)，(A，H)，(C，A)}，试画出这棵树，并回答下列问题：

(1)哪个是根结点？ (2)哪些是叶子结点？ (3)树的深度是多少？

六、算法题（共12分）

1.编写计算二叉树深度的算法(二叉树的深度也叫二叉树的高度)。 答：int Depth (BiTree T )

{ // 返回二叉树的深度 if (T ) {

depthLeft = Depth( T->lchild );//求左子树的深度 depthRight= Depth( T->rchild ); //求右子树的深度

depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);

//深度的最大值+1 }

else depthval = 0; return depthval;

}

2.编写算法：统计一个二叉树中所有叶子结点的数目。

答：void CountLeaf (BiTree T, int& count)

{//在实际使用时，count作为全局变量，其初始值为0 if ( T ) {

if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf

参考题：

3. 编写算法先序、中序、后序递归遍历二叉树的算法 4. 编写中序非递归遍历二叉树的算法。

5. 试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。

本文来源：https://www.bwwdw.com/article/k14d.html