第四章练习题
1．对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则（A ）。
A．n0=n2+1 B．n2=n0+1 C．n0=2n2+1 D．n2=2n0+1
2．有m个叶结点的哈夫曼树所具有的结点数为（D ）。
A．m B．m+1 C．2m D．2m-1
3.在一棵度为3树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C ）个。
A.4 B.5 C.6 D.7
4．二叉树通常有 存储结构和 存储结构。顺序、链式
5．对于一棵满二叉树，若有m个叶子，则结点数为 ；若满二叉树的结点数为n，则其高度为 。2m-1 、log2（n+1）
6．森林的后序遍历序列正是相应二叉树的 遍历序列，森林的先序遍历序列正是相应二叉树的 遍历序列。中序 、先序
7．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为 ；若编号为i的结点有父结点，那么其父结点的编号为 。2i+1、[i/2]
8．已知一棵二叉树的前序序列是：ABCDEFG，这棵二叉树的中序序列是：CBDAEGF，请构造出该二叉树。
9．深度为k的二叉树，结点数最多有（ B ）。
A．2k B．2k -1 C．2k-1 D．2k-1-1
10. 在一棵度为3树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C ）个。先序中序后序遍历二叉树
A.4 B.5 C.6 D.7
11．具有65个结点的完全二叉树其深度为 （B ）。
A.8 B.7 C.6 D.5
12．设只包含根结点的二叉树的高度为0，则高度为k的二叉树最大结点数为 ，最小结点数为 。2k+1-1、k+1
13．在有n个结点的二叉链表中，指向孩子结点的指针有 个，空指针域有
个。 n-1、n+1
14．由一棵二叉树的前序序列和 序列可以确定这棵二叉树。设某二叉树的
后序遍历为ABKCBPM，则可知该二叉树的根为 。中序、M
15．设某通讯电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是16，5，9，3，20，1，试画出编码用的哈夫曼树。
编码用的哈夫曼树如图所示。
16.若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
if(!B1&&!B2) return 1;
if(!B1&&!B2) return 1;
else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
return 1;
return 1;
else return 0;
}//Bitree_Sim
17．在一棵度为3的树中，度为3的结点数为2，度为2的结点数为1，度为1的结点数为2，那么度为0的结点数为（ C ）
A. 4 B. 5 C. 6 D. 7
18. 有m个叶结点的哈夫曼树所具有的结点数为（ D ）
A．m B．m+1 C．2m D．2m-1
19. 某二叉树的前根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则后根遍历序列为 。由一棵二叉树的后根序列和 可唯一确定这棵二叉树。 LKJNOMI、中根序列
20．试分别出满足以下条件的所有二叉树：
（1） 二叉树的前根序列与中根序列相同；
（2） 二叉树的中根序列与后根序列相同；
（3） 二叉树的前根序列与后根序列相同。
（1） 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；
（2） 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；
（3） 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。
21．一棵深度为８（根的层次号为１）的满二叉树有（ B ）个结点。
Ａ. 256 Ｂ. 255 Ｃ.128 Ｄ. 127
22．含有n个结点的二叉树用二叉链表表示时，空指针域个数为（ C ）
A．n-1 B．n C．n+1 D．n+2
23．在有n个叶子结点的哈夫曼树中，其结点总数为 。 2n-1
24．在二叉链表中判断某指针p所指结点为叶子结点的条件是 。p->lchild=p->rchild=NULL
25. 试将右图所示的一棵二叉树还原成森林。
26．以数据集｛2，5，7，9，13｝为权值构造一棵哈夫曼（Huffman）树，并计算其带权路
径长度。
构造的哈夫曼树如图所示，其带权路径长度WPL=（2+5）×3+（7+9+13）×2=79
27．对于下面的二叉树，按后根遍历所得到的序列为( C )
A.ABCDEF B. BDCEFA
C.DBEFCA D. DBAECF
28．由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( D )
A.23 B. 37 C. 46 D.44
29．某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则前根序列遍历为( D )
A．acbed B．becab C．deabc D．cedba
30．用n个值构造一棵二叉排序树，它的最大高度为( B )
A. n/2 B. n C. D.
31.在一棵度为3树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为( B )个。
A. 4 B. 5 C. 6 D. 7
32．高度为n的完全二叉树最多有 个结点；最少有 个结点。2n-1; 2n-1+1
33． 遍历二叉排序树，可得到排好序的递增结点序列。中根
34．在树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着
和 的联系。1对N(一对多) 、 M对N(多对多)
35．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。
36. 设二叉树的二叉链表的类型定义如下：
typedef struct btnode *bitreptr;
struct btnode { elemtype data;
bitreptr lc,rc;}
bitreptr root;
试写出求二叉树中叶子数的算法。
typedef struct btnode *bitreptr;
struct btnode { elemtype data;
bitreptr lc,rc;
}
void count(bitreptr root, int *count)
if (root!=NULL)
{if ((root->lc==NULL)&&(root->rc==NULL))
*count++;
count(root->lc, count);
count(root->rc, count);
}
37．二叉树第i（i≥1）层上至多有（ C ）个结点。
A. 2i B. 2i C. 2i-1 D. 2i –1
38．如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为（B ）。
A. 3 B. 4 C. 5 D. 1
39. 在一棵度为3树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C ）个。
A.4 B.5 C.6 D.7
40．由a，b，c三个结点构成的二叉树，共有 5 种不同的结构。
41．在树形结构中，直接前驱和直接后继结点之间存在着 的联系。1：n
42. 由a，b，c三个结点构成的二叉树，共有 种不同的结构。5
43．按中序遍历二叉树，可以得到按值递增的关键码序列，在图中所示的二叉树中，检索关键字85的过程中，需与85进行比较的关键字序列为 。50、95、55、70、85
44.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。
45. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论