第6章 二叉树与树
一、回答题
1. 图6-1所示的树的叶子结点、非中端结点、每个结点的度及树的深度各是多少？
图6-1 树
2. 已知一棵树边的集合表示为：{ ( 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) 树的深度是多少？各个结点的层数是多少？
(4) 对于结点G，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别
是哪些结点？
3. 如果一棵度为m的树中，度为1的结点数为n1，度为2的结点数为n2，……，度为m
的结点数为nm，那么该树中含有多少个叶子结点？有多少个非终端结点？ A
B E C D
F G H J I 4. 任意一棵有n个结点的二叉树，已知有m个叶子结点，能否证明度为2结点有m-1个？
5. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，那么
该树含有的叶子结点的数目是多少？
6. 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？
7. 对于3个结点A、B、C，可以过程多少种不同形态的二叉树？
8. 深度为5的二叉树至多有多少个结点？
9. 任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序是发生改变？不
发生改变？不能确定？
10. 设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是什么？
11. 已知某二叉树的后续遍历序列是dabec，中序遍历序列是debac，那么它的前序遍历
序列是什么？
12. 对一棵满二叉树，m个树叶，n个结点，深度为h，则n、m和h之间的关系是什么？
数据结构复习题：树和二叉树
填空题
1、对于一棵具有n个结点的树，则该树中所有结点的度之和为______。 2、在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：
n0=__________。
3、在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为__________， 若
它存在左孩子，则左孩子结点的下标为__________，若它存在右孩子，则右孩子结点的下标
为___________。 4、在一棵二叉排序树中，按__________遍历得到的结点序列是一个有序序列。
5、由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为
_________。
6、有如下递归函数:
int dunno (int m) {
int value;
if (m==0)
value=3;
else value=dunno(m-1)+5;
return (value);
}
执行语句printf("%d\n",dunno(3))；的结果是________。
7、所谓稀疏矩阵指的是______的矩阵。 8、一个稀疏矩阵Am*n采用三元组表示后,若把三元组中有关行下标与列下标的值互换,并把
m和n的值互换,则就完成了Am*n的转置运算。这句话______正确的。
9、若稀疏矩阵采用三元组压缩方法存储,只要把每个元素的行下标和列下标互换,就成了对该
矩阵的转置运算,这种观点______(正确或错误).
10、在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵____________。 11、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个____________。
12、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明
____________，若元素的值小于根结点的值，则继续向____________查找，若元素的值大于
根结点的值，则继续向____________查找。
树、图 习题
一、选择题 1 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为
( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
2 一个具有1025个结点的二叉树的高h为（ ）
A．11 B．10 C．11至1025之间 D．10至1024之间 3 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该
二叉树根的右子树的根是： （ ）
A、 E B、 F C、 G D、 H
4 引入二叉线索树的目的是（ ）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一
5 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森
林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A．M1 B．M1+M2 C．M3 D．M2+M3
6 有n个叶子的哈夫曼树的结点总数为（ ）。 A．不确定 B．2n C．2n+1 D．2n-1
7 一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A．0 B．1 C．n-1 D．n
8 无向图G=(V,E),其中：
V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
9 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={,,,,,,,,},G的拓扑序列
是（ ）。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
严蔚敏《数据结构(c语言版)习题集》标准答案树和二叉树文库
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
3 第六章 树和二叉树
6.33
int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
if(u==v) return 1;
else
{
if(L[v])
if (Is_Descendant(u,L[v])) return 1;
if(R[v])
if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
}
return 0;
}//Is_Descendant_C
6.34
int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
for(p=u;p!=v&&p;p=T[p]);
if(p==v) return 1;
else return 0;
}//Is_Descendant_P
6.35
这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.
6.36
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
if(!B1&&!B2) return 1;
else
if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
