第五章 树和二叉树
一．选择题
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．3 B．2 C．4 D．5
3．设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的左子树上的结点个数是（ ）
A．M1 B．M1+M2 C．M3 D．M2+M3 4。对于一棵具有n个结点、度为4的树来说，（ ） A．树的高度至多是n-3 B．树的高度至多是n-3
C．第i 层上至多有4*(i-1)个结点 D．至少在某一层上正好有4个结点 5．在下列存储结构中，（ ）不是树的存储形式
A．双亲表示法 B．孩子链表示法 C．孩子兄弟链表示法 D．顺序存储表示法 6．二叉树若用顺序方法存储，则下列4种运算中的（ ）最容易实现。 A．先序遍历二叉树 B．判断两个指定结点是不是在同一层上 C．层次遍历二叉树 D．根据结点的值查找其存储位置
7．一个完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A．250 B．501 C．254 D。505 8．在高度为h的完全二叉树中 （ ）
A．度为0的结点都在第h 层上 B．第 I (1<=i<=h)层上结点都是度为2的结点 C．第 I (1<=i<=h-1)层上有2i-1 个结点 D．不存在度为1的结点 9．若一刻二叉树具有10个度为2的节点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D． 不确定
10．若二叉树的中序遍历序列是abcdef，且c为根结点，则（ ） A．结点c有两个孩子 B．二叉树有两个度为0的结点 C．二叉树的高度为5 D．以上都不对
11．在任何一棵二叉树中，如果结点a 有左孩子b、右孩子c，则在结点的先序序列、中序序列、后序序列中，（ ）
A．结点b一定在结点a的前面 B．结点a一定在结点c的前面 C．结点b一定在结点c的前面 D．结点a一定在结点b的前面 12．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A．先序 B．中序 C．后序 D．按层次
13．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（ ）个结点。 A．13 B．12 C．26 D．25 二．填空题
1．非空二叉树共有（ ）种基本状态。
2．在高度为h（h>=0）的二叉树中至多有( ) 个结点，至少有（ ）个结点。 3．N个结点的二叉树中如果有m个树叶，则一定有（ ）个度为1的结点，（ ）个度为2的结点。
4 .在顺序存储的二叉树中，编号为i和j的两个结点处在同一层上的条件是（ ）
5．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的（ ）序列中的最后一个结点。
6．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（ ），各结点对应的哈夫曼编码为（ ）。 三．分析构造题
1．一棵树的边集为{
（3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？ （5）哪些是结点G的孩子？ （6）哪些是结点E的子孙？
（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是什么？ （9）树的深度是多少？
（10）以结点C为根的子树的深度是多少？ 2．画出下图4棵树分别对应的二叉树。
A
A A
A B C D
B B
C
3．画出下图中5棵二叉树对应的森林 A A A A
B C B B
C E F G H I J K A B C D E F
C C G H
I
J
4．有一份电文中共使用5个字符，A、B、C、D、E，它们的出现频率依次
A 为4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权值小于等
C B 于右子树根结点的权值的次序构造），并求出每个字符的哈夫曼编码。
5．对于右图所示的二叉树 F G （1）画出它的顺序存储结构图
I J （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个指针域是空的。 参考答案
一．C C A A D C B C B A C C D 二．1．4 2．2h-1 h 3．N-2m+1 m-1
4．?log2i???log2j?
5．先序序列
B D E I M A B B C C C E D F I J K G H
N F J A C G K H L 6． 69 010、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) 3 2．
A A B A 3．
4. A B A A B C A B C H F I B C D G J E C 0 11 0 c 1 6 0 1 a 4 b 7 27 1 16 1 e 9 a: 001 b: 10 c: 01 d: 000 e: 11
5．（1） A A （2） B I F C J G B C F G I J 5 0 d 2
6．设度为0、1、2的结点个数及总结点数分别为n0、n1、9． 36 0 1 n2和n，则有
14 22 N0=50，n=n0+n1+n2，n-1=n1+2*n2，由这三个式子得：
0 1 0 1 n2=49
7 13 9 故：n-1=n1+2*49 n=n1+99 所以当n1= 0时，n最0 1 7 少，即n至少有99个结点。
2 5 7．设满二叉树的高度为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)/2 8．HIDJKEBLFGCA 四．
1. int nodes(Btree *b) 2．Void swap1(BTNode *b,BTNode *&b1) { int num1,num2; { if (b==null) If( b==NULL) B1=null; Return(0); Else Else { 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．Void path(elemtype sqtree[],int k) Printf(“%c”,sqtree[i]); { int i=po(2,k)-1; //求2k-1 } While(i>1 && sqtree[i]==’’) i--; Printf(“\\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
整理上述两式可得到：n=B+1=n1+2n2+1
将n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1，整理后得n0= n2+1，故结论成立。 4．证明：设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为： 2k-1-1
k层满二叉树的结点总数为： 2k-1
显然有： 2k-1 - 1 < n ? 2k- 1 -> 2k- 1 ? n < 2k 取对数有：k -1 ? log2n < k
因为k是整数，所以k -1 =log2n ， k= ?㏒2n?+1。结论成立。
5．证明：用归纳法证明。N=1时，它有m个指针域是空的，成立。假设n=k时成立，即有k(m-1)+1个指针域是空的。
当n=k+1时，在原k个结点的树中增加一个结点，那么原k个结点中减少了一个指针域，但增加一个结点以后就增加了m 个指针域是空的。所以有k+1个结点的m次树的空指针域个数=k(m-1)+1-1+m=(k+1)(m-1)+1，结论得证。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第五章树和二叉树习题在线全文阅读。
相关推荐：