第5章-树和二叉树-自测题

一、 单项选择题（每题2分，共26分）1) 树最适合用来表示（ C ）A ．有序数据元素 B.无序数据元素C. 元素之间具有分支层次关系的数据D.元素之间无联系的数据2) 如图所示的4棵二叉树中，（ C ）不是完全二叉树。

3) 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法（ B ）A. 正确B.错误4) 如图1-1所示二叉树的中序遍历序列是（ B ）。

A. abdgcefhB. dgbaechfC. gdbehfcaD. abcdefgh5) 如果是T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的（ A ）。

A. 先序B. 中序C. 后序D. 层次序6) 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ D ）。

A. 空或只有一个结点B. 完全二叉树C. 二叉排序树D. 高度等于其结点数7) 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

结论（ A ）是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同。

B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同。

（a ） （b ） 9 （d ）C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同。

D. 以上都不对8) 如图所示的T2是由森林T1转换而来的二叉树，那么森里T1有（ C ）个叶子结点。

A. 4B. 5C. 6D. 79) 深度为5的二叉树至多有（ C ）个结点。

A. 16B. 32C. 31D. 1010) 在一非空二叉树的中序遍历序列中，根结点的右边（ A ）。

A. 只有右子树上的所有结点B. 只有右子树的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点11) 设n ，m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（ C ）。

树与二叉树练习题（五）习题2010-05-25 17:27:01 阅读55 评论0 字号：大中小1. 己知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可以不用递归且不用栈来完成？请说明原因。

2．具有n个结点的满二叉树的叶子结点的个数是多少？说明理由。

3．列出先序遍历能得到ABC序列的所有不同的二又树。

4．画出同时满足下列两个条件的两棵不同的二叉树：(1) 按先序遍历二叉树顺序为ABCDE；(2) 高度为5，其对应的树（森林）的高度最大为4。

5．对于表达式(a-b+c)*d／(e+f)(1) 画出它的中序二叉树，并标出该二叉树的前序线索；(2) 给出它的前缀表达式和后缀表达式。

6．试找出分别满足下列条件的所有二叉树：(1) 先序序列和中序序列相同；(2) 中序序列和后序序列相同；(3) 先序序列和后序序列相同。

7. 阅读下列算法的描述，根据算法的要求，在相应的空格处写出正确合理的语句。

后序遍历二叉树的非递归算法，bt是二叉树的根，S是一个栈，MaxSize是栈的最大容量。

typedef s truct N ode{BTNode *[Max Size+1];int top;} stac k ty p;v oi d PostOrder(BTNode *bt){BTNode *p, *q = bt;stac k typ S;int fl ag;S.top = -1;do{while(q != NULL){S.top++;if(S.top > MaxSize){printf("Stac k F ull!");ex it(0);}elseS.data[S.top] = q;_______①_____;}flag = 1;p = NULL;while(S.top != -1 && flag){q = S.data[S.top];if(_________②__________){printf(q->data);S.to--;p = q;}else {_________③__________;flag = 0;}}}while(__________④__________);}8. 具有n个结点的完全二又树，已经顺序存储在一维数组A[n]中，下面算法是将A中顺序存储变成二叉链表存储的完全二又树。

第五章树和二叉树必会题一.填空1. 树结构体现了数据元素间一对多的关系。

在树中除根结点外，其余结点有且仅有一个双亲；除叶子结点外，其余结点可能有多个孩子。

2. 树的遍历方法主要有先序遍历、中序遍历和后序遍历。

3. 树中某结点在第k层，则该结点的子树的根在k+1层。

4. 二叉树的第i层上至多有2i-1个结点。

5. 深度为h的二叉树至多有2h-1个结点。

6. 完全二叉树中结点间编号的关系：若某结点的编号为i，若有双亲，则其双亲的编号为i/2；若有左孩子，则其左孩子的编号为i*2；若有右孩子，则其右孩子的编号为i*2+1。

7. 把一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

8. 完全二叉树就是在同高度的满二叉树的最大层上从右向左连续删除若干结点所构成。

9. 任意一棵哈夫曼树的带权路径长度都等于其所有非叶子结点的权值之和。

10. 树中的结点数比边数多1。

11. 二叉树可以采用顺序存储结构，也可以采用链式存储结构。

12. 哈夫曼树是带权路径长度最短的树。

13. 已知二叉树先根遍历的序列为“CDHAFEGB”, 中根遍历的序列为“HDFAECBG”, 则后根遍历的序列为“_HFEADBGC_”。

14. 已知完全二叉树有1024个结点, 则该二叉树的深度为__11___。

15. 已知一颗哈夫曼树有4个叶子结点，则该树一共有7个结点。

16. 设一棵树用括号表示法记作A(C,D(E,F,G),H(I,J))，则该树有9个结点，树的深度为3，树的度为3。

17. 若用二叉链表存储二叉树，则有n个结点的二叉树共有2n个指针域，其中有n-1个指针域非空，n+1个指针域为空。

18. 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为6。

二.判断题1. 二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。

（√）2. 二叉树是度为2的有序树。

一、填空题1. 不相交的树的聚集称之为森林。

2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。

3. 深度为k的完全二叉树至少有2 k-1个结点。

至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。

4. 在一棵二叉树中，度为零的结点的个数为n，度为2的结点的个数为n2，则有n= n2+1。

5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n（n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1） /2个非终端结点。

6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。

7. 哈夫曼树是带权路径最小的二叉树。

8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。

9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。

10. 树被定义为连通而不具有回路的（无向）图。

11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。

12. 高度为k，且有个结点的二叉树称为二叉树。

2k-1 满13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。

Huffman14. 在一棵根树中，树根是为零的结点，而为零的结点是结点。

入度出度树叶15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。

结点树根16. 满二叉树是指高度为k，且有个结点的二叉树。

二叉树的每一层i上，最多有个结点。

2k-12i-1二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。

(A)8 (B)9 (C)10 (D)112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。

国开程序设计基础第5章自测试题及答案一、选择题（每题10分，共80分）试题 1数据的存储结构分为两种，它们是______。

正确答案是：顺序存储和链式存储试题 2如果在内存中采用链式保存线性表，则元素之间的逻辑关系通过______。

正确答案是：保存在元素中的指针表示先后次序试题 3进行顺序查找的条件是______。

正确答案是：数据不需要有序，也不限制存储方式试题 4队列的最主要特点是______。

正确答案是：先进先出试题 5如果在具有层次结构的一组元素中，存在着一对一的关系，我们可以认为这样的数据的逻辑类型就是______。

正确答案是：线性结构试题 6在任意二叉树中，如有N个叶子结点，M个度为_____①_______ 的节点，则必有_____②_____。

正确答案是：①2 ② N=M+1试题 7若按照一定的顺序依次访问树中的每一个结点，而且每个结点只被访问一次，则称这样的操作为______。

正确答案是：遍历试题 8对如图所示的二叉树进行先序遍历的顶点序列是_____①_______，后序遍历时得到的顶点序列是_____②_____。

正确答案是：①ABDEC ②EDBCA二、判断题（每题10分，共20分）试题 9图是由一个可以为空的顶点集合和一个描述顶点之间的关系——边（或者是弧）的集合组成，记为：G=（V，E）。

正确答案是“错”。

试题 10二叉树是n（n≥1）个结点的有限集合，它或为空树（n=1），或由一个根结点和两棵被分别称为左子树和右子树的互不相交的二叉树构成。

正确答案是“错”。

第 5 章树和二叉树1970-01-01第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

第五章树和二叉树一．选择题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．53．设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。

与森林F对应的二叉树根结点的左子树上的结点个数是（）A．M1 B．M1+M2 C．M3 D．M2+M34。

对于一棵具有n个结点、度为4的树来说，（）A．树的高度至多是n-3 B．树的高度至多是n-3C．第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。

5058．在高度为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．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

习题5 树和二叉树一、选择题：1．在具有n个结点的完全二叉树中，结点i（i>1）的父结点是（）A．2i B．不存在C．2i+1 D．⌊ i/2⌋2. 有m个叶结点的哈夫曼树所具有的结点数为（）A．m B．m+1 C．2m D．2m - 13. 下列陈述中正确的（）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分4. 以二叉链表作为二叉树的存储结构，在具有ｎ个结点的二叉链表中(n>0)，空链域的个数为（）A．2n - 1 B．n - 1 C．n + 1 D．2n + 15. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）A．99 B．98 C．50 D．486. 在一棵具有五层的满二叉树中，结点总数为（）A．31 B．32 C．33 D．167. 在一棵二叉树中，第5层上的结点数最多为（）A．8 B．15 C．16 D．328. 由二叉树的（）遍历，可以惟一确定一棵二叉树A．前序和后序B．前序和中序C．后序D．中序9. 具有35个结点的完全二叉树的深度为（）。

A.5B.6C.7D.810. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是（）。

A．E B. F C. G D. J11. 由4个结点构造出的不同的二叉树个数共有（）。

A．8 B. 10 C．12 D．1412. 在完全二叉树中，如果一个结点是叶子结点，则它没有（）。

A.左孩子结点B. 右孩子结点C.左、右孩子结点D.左、右孩子结点和兄弟结点13. 深度为6的二叉树最多有（）个结点。

A．64 B．63 C．32 D．3114. 二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild=NULL时，则（）。

习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为()。

A.向量B.树 C图 D.二叉树2．树最合适用来表示()。

A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的()。

(2b(3d,3e),2c)B.a(b(D,e),c)C.a(b(d,e),c)D.a(b,d(e),c)4.高度为h的完全二叉树至少有()个结点，至多有()个结点。

A.2h_lB.h C．2h-1 D.2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为()。

A.2iB.2i-lC.2i+lD.2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ()。

A.3B.4C.5D.67.深度为5的二叉树至多有()个结点。

A.31B.32C.16D.108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为()个。

A.15B.16C.17D.479.题图6-1中，()是完全二叉树，()是满二叉树。

10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为()。

A.5B.6C.7D.812.一棵有124个叶结点的完全二叉树，最多有()个结点。

第5章树和二叉树一．选择题（1）由3 个结点可以构造出多少种不同的二叉树（ D ）A．2 B．3 C．4 D．5（2）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A．250 B． 500 C．254 D．501（3）一个具有1025个结点的二叉树的高h为（）。

A．11 B．10 C．11至1025之间 D．10至1024之间（4）深度为h的满m叉树的第k层有（）个结点。

(1=<k=<h)A．m k-1 B．m k-1 C．m h-1 D．m h-1（5）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历（6）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次（7）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。

A．所有的结点均无左孩子 B．所有的结点均无右孩子C．只有一个叶子结点 D．是任意一棵二叉树（8）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A．空或只有一个结点 B．任一结点无左子树C．高度等于其结点数 D．任一结点无右子树（9）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

A．X的双亲 B．X的右子树中最左的结点C．X的左子树中最右结点 D．X的左子树中最右叶结点（10）引入二叉线索树的目的是（）。

A ．加快查找结点的前驱或后继的速度B ．为了能在二叉树中方便的进行插入与删除C ．为了能方便的找到双亲D ．使二叉树的遍历结果唯一二． 简答题（1）试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同?2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。