第五章树和二叉树习题

本文格式为Word版，下载可任意编辑——第五章树和二叉树习题第五章树和二叉树

一．选择题

1．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）

A．4个B．5个C．6个D．7个

2．某二叉树结点的中序序列为a、b、c、d、e、f、g，后序序列为b、d、c、a、f、g、e，则其左子树中结点数目为（）

A．3B．2C．4D．5

3．设森林F中有三棵树，第一、其次和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的左子树上的结点个数是（）

A．M1B．M1+M2C．M3D．M2+M34。对于一棵具有n个结点、度为4的树来说，（）A．树的高度至多是n-3B．树的高度至多是n-3

C．第i层上至多有4*(i-1)个结点D．至少在某一层上正好有4个结点5．在以下存储结构中，（）不是树的存储形式

A．双亲表示法B．孩子链表示法C．孩子兄弟链表示法D．顺序存储表示法6．二叉树若用顺序方法存储，则以下4种运算中的（）最简单实现。A．先序遍历二叉树B．判断两个指定结点是不是在同一层上C．层次遍历二叉树D．根据结点的值查找其存储位置

7．一个完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．501C．254D。5058．在高度为h的完全二叉树中（）

A．度为0的结点都在第h层上B．第I(1=0）的二叉树中至多有()个结点，至少有（）个结点。3．N个结点的二叉树中假使有m个树叶，则一定有（）个度为1的结点，（）个度为2的结点。

4.在顺序存储的二叉树中，编号为i和j的两个结点处在同一层上的条件是（）

5．若一个二叉树的叶子结点是某子树的中序遍历序列中的最终一个结点，则它必是该子树的（）序列中的最终一个结点。

6．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（），各结点对应的哈夫曼编码为（）。三．分析构造题

1．一棵树的边集为{,,,,,,,,,,,,},画出这棵树，并回复以下问题：（1）哪个是根结点？（2）哪个是叶子结点？

（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？

（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？

（10）以结点C为根的子树的深度是多少？2．画出下图4棵树分别对应的二叉树。

A

AA

ABCD

BB

C

3．画出下图中5棵二叉树对应的森林AAAA

BCBB

CEFGHIJKABCDEF

CCGH

I

J

4．有一份电文中共使用5个字符，A、B、C、D、E，它们的出现频率依次

A为4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权值小于等

CB于右子树根结点的权值的次序构造），并求出每个字符的哈夫曼编码。

5．对于右图所示的二叉树FG（1）画出它的顺序存储结构图

IJ（2）将它转换成森林

6．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？7．具有n个结点的满二叉树的叶子结点的个数是多少？

8．用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。写出后序遍历该二叉树的访问结点序列。

9．以数据集{2，5，7，9，13}为权值构造一棵哈夫曼树，并计算其带权路径长度。四．算法设计题

1．二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树的所有结点数。

2.二叉树采用链式存储结构，设计一个算法把树b的左、右子树进行交换，要求不破坏原二叉树。

3．已知一棵高度为k的具有n个结点的二叉树，按顺序方式存储，编写将二叉树中最大序号叶子结点的祖先结点全部打印输出的算法。五．证明题

1．在二叉树的第i层上至多有2i-1个结点(i≥1)。2．深度为k的二叉树至多有2k-1个结点（k≥1）3．对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。4．具有n个结点的完全二叉树的深度为?㏒2n?+1。

5．在具有n(n>=1)个结点的m次树中，有n(m-1)+1个指针域是空的。参考答案

一．CCAADCBCBACCD二．1．42．2h-1h3．N-2m+1m-1

4．?log2i???log2j?

5．先序序列

BDEIMABBCCCEDFIJKGH

NFJACGKHL6．69010、011、10、11、00三．1．

(1)A(2)D、M、N、F、J、K、L(3)C(4)A、C(5)J、K(6)I、M、N

(7)D,G、H(8)2，5(9)5(10)32．

AABA3．

4.ABAABCABCHFIBCDGJEC0110c1601a4b7271161e9a:001b:10c:01d:000e:11

5．（1）AA（2）BIFCJGBCFGIJ50d2

6．设度为0、1、2的结点个数及总结点数分别为n0、n1、9．3601n2和n，则有

1422N0=50，n=n0+n1+n2，n-1=n1+2*n2，由这三个式子得：

0101n2=49

7139故：n-1=n1+2*49n=n1+99所以当n1=0时，n最017少，即n至少有99个结点。

257．设满二叉树的高度为h，则：总结点数n=1+2+4++2^(h-1)=2*2(h-1)-1，WPL=（2+5）*3+（7+9+13）*2=97而该满二叉树的叶子结点个数为2^（h-1）=(n+1)/28．HIDJKEBLFGCA四．

1.intnodes(Btree*b)2．Voidswap1(BTNode*b,BTNode*{if(b==null)If(b==NULL)B1=null;Return(0);ElseElse{b1=(BTNode*)malloc(sizeof(BTNode));{num1=nodes(b.lchile);B1.data=b.data;Num2=nodes(b.rchile);Swap1(b.lchild,b1.rchild);Return(num1+num2+1);Swap1(b.rchild,b1.lchild);}}}}

3．Voidpath(elemtypesqtree[],intk)Printf(“%c〞,sqtree[i]);{inti=po(2,k)-1;//求2k-1}While(i>1Printf(“\\n〞);While(i>1)}{i=i/2;

五．

1．当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。假设i=k时结论成立，即第k层上结点总数最多为2k-1个。现证明当i=k+1时，结论成立：

由于二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。

2．由于深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为：

?i?1k第i层上的最大结点个数=

?i?1k2i-1=2k-1

故结论成立。

3.证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数。由于二叉树中所有结点的度小于等于2，所以有n=n0+n1+n2

设二叉树中分支数目为B，由于除根结点外，每个结点均对应一个进入它的分支，所以有：n=B+1。又由于二叉树中的分支都是由度为1和度为2的结点发出，所以分支数目为：B=n1+2n2