数据结构第六章树和二叉树练习及答案

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

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

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

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

A. la (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.4..专业知识编辑整理..11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

第六章树和二叉树一．选择题1. 以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。

图6-2 4 棵二叉树3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。

A. t->left == NULLB. t->ltag==1C. t->ltag==1 且t->left==NULL D .以上都不对4. 以下说法错误的是。

A.二叉树可以是空集B.二叉树的任一结点最多有两棵子树C.二叉树不是一种树D.二叉树中任一结点的两棵子树有次序之分5. 以下说法错误的是。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树7. 如图6-4所示二叉树的中序遍历序列是。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图6-4 1 棵二叉树8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

A. acbedB. decabC. deabcD. cedba9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。

A. 前序B.中序C. 后序D. 层次序10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。

数据结构-习题-第六章-树和二叉树E F D G A B / + + * - C * 第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/EC ．-+*ABC/DE D. -+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ）【南京理工大学1999 一、20（2分）】A. A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D.A*B+C/D*E+F-G4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T。

其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。

第六章树和二叉树试题一、单项选择题1.树中所有结点的度等于所有结点数加（）。

A. 0B. 1C. -1D. 22.在一棵树中，（）没有前驱结点。

A. 分支结点B. 叶结点C. 根结点D. 空结点3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。

A. 2B. 1C. 0D. -14.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。

A. nB. n-1C. n+1D. 2*n5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（）个结点。

A. 2iB. 2i+1C. 2i-1D. 2n6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。

假定空树的高度为-1。

A. 5B. 6C. 7D. 88.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。

假定树根结点的编号为0。

A. ⎣(n-1)/2⎦B. ⎣n/2⎦C. ⎡n/2⎤D. ⎣n/2⎦ -19.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。

假定根结点的编号为0A. 2iB. 2i-1C. 2i+1D. 2i+210.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号为（）。

A. ⎣(i+1)/2⎦B. ⎣(i-1)/2⎦C. ⎣i/2⎦D. ⎣i/2⎦-111.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（）结点。

A. 兄弟B. 子女C. 祖先D. 子12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。

A. 1B. 2C. 3D. 413.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（）。

第6章树和二叉树6.1知识点: 树和二叉树的基本概念一、填空题1.高度为h，度为m的树中至少有___________个结点，至多有______________个结点。

2.树的结点是由及若干指向其子树的组成；结点拥有的子树数称为；度为0的结点称为；度不为0的结点成为；树中结点的最大度数称为；树的最大层次称为_____________。

3.对于一棵具有n个结点的树，该树中所有结点的度数之和为___________。

4.如果结点A有3个兄弟结点，而且B是A的双亲，则B的度是___________。

5.二叉树是另一种树形结构，它的特点是。

6.一颗度数为k且有2k-1个结点的二叉树称为。

7.深度为k，且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为。

8.一棵深度为6的满二叉树有个分支结点和个叶子。

9.一棵具有257个结点的完全二叉树，它的深度为。

10.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

11.由3个结点可以构成__________种形态的的二叉树，可以构成种形态的树。

12.将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第1号，其他结点自上向下，同一层自左向右连续编号。

则第40号结点的双亲结点的编号为。

13.一棵高度为5的完全二叉树中，最多包含有____________个结点。

14.一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1=____________。

15.在高度为h（h>=0）的二叉树中至多可以有__________个结点，至少可以有___________个结点。

16.n个结点的二叉树最大高度是____________,最小高度是_______________。

二、选择题1.( ）不含任何结点的空树（）。

A.是一棵树B.是一棵二叉树C.是一棵树也是一棵二叉树D.既不是树也不是二叉树2.（）一棵度为4的树中度为1、2、3、4的结点个数为4、3、2、1，则该树的结点总数为（）。

树和二叉树习题及答案一、填空题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-1 2i-1二、单选题1、具有10个叶结点的二叉树中有 (B) 个度为2的结点。

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

《数据结构》期末复习题及参考答案 - 第6章 树和二叉树一、 选择题1、在二叉树的第I 层(I≥1)上最多含有结点数为（ ）A. 2IB. 2I-1-1C. 2I-1D. 2I -12、深度为6的二叉树最多有( )个结点A ．64 B.63 C.32 D.313、一棵树高为K 的完全二叉树至少有( )个结点A.2k –1B.2k-1 –1C.2k-1D.2 k4、有关二叉树下列说法正确的是（ ）A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为25、n 个结点的线索二叉树上含有的线索数为（ ）A. 2nB. n －lC. n ＋lD. n6、线性表和树的结构区别在于（ ）A ．前驱数量不同，后继数量相同B ．前驱数量相同，后继数量不同C ．前驱和后继的数量都相同D ．前驱和后继的数量都不同7、已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，则其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE8、设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)9、一棵具有 n 个结点的完全二叉树的树高度（深度）(符号⎣⎦x 表示取不大于x 的最大整数)是（ ）10、利用二叉链表存储树，则根结点的右指针是（）。

11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。

12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。

【课后习题】第6章树和二叉树网络工程2010级（）班学号：姓名：一、填空题（每空1分，共16分)1.从逻辑结构看，树是典型的。

2.设一棵完全二叉树具有999个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个度为1的结点。

3.由n个权值构成的哈夫曼树共有个结点。

4.在线索化二叉树中，T所指结点没有左子树的充要条件是。

5.在非空树上，_____没有直接前趋。

6.深度为k的二叉树最多有结点，最少有个结点。

7.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为且小于n时，结点i的右兄弟是结点，否则结点i没有右兄弟。

8.N个结点的二叉树采用二叉链表存放，共有空链域个数为。

9.一棵深度为7的满二叉树有___ ___个非终端结点。

10.将一棵树转换为二叉树表示后,该二叉树的根结点没有。

11.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的遍历结果是一样的。

12.一棵Huffman树是带权路径长度最短的二叉树，权值的外结点离根较远。

二、判断题（如果正确，在对应位置打“√”，否则打“⨯”。

每题0.5分，共5分)1.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。

2.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。

3.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。

4.度≤2的树就是二叉树。

5.一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。

6.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

7.不存在有偶数个结点的满二叉树。

8.满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。

9.已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树；10.已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；三、单项选择（请将正确答案的代号填写在下表对应题号下面。

第六章 树和二叉树一、选择题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【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D 3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③B ．②③④C ．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定 【南京理工大学2000一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T 。

其余结点分成为m （m>0）个(（2）)的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T的子结点（1≤i ≤m ）。

第 6 章树和二叉树1．选择题（ 1）把一棵树变换为二叉树后，这棵二叉树的形态是（）。

A．独一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子（ 2）由 3 个结点能够结构出多少种不一样的二叉树？（）A． 2 B ． 3 C ． 4 D． 5（ 3）一棵完整二叉树上有1001 个结点，此中叶子结点的个数是（）。

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

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

(1=<k=<h)k-1B kCh-1 hA． m ． m-1 ． m D．m-1（ 6）利用二叉链表储存树，则根结点的右指针是（）。

A．指向最左孩子 B ．指向最右孩子 C ．空 D ．非空（ 7）对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采纳（）遍历实现编号。

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

A．前序B．中序C．后序D．按层次（9）在以下储存形式中，（）不是树的储存形式？A．双亲表示法 B ．孩子链表表示法 C ．孩子兄弟表示法D．次序储存表示法（ 10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树必定满足（）。

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

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

一、单选题1、已知一算术表达式的中缀形式为 A-B/C+D*E，前缀形式为+-A/BC*DE，其后缀形式为( )。

A.ABC/-DE*+B.AB/C-D*E+C. A-BC/DE*+D. ABCDE/-*+正确答案：A2、有关二叉树下列说法正确的是（）。

A.二叉树中任何一个结点的度都为2B.一棵二叉树的度可以小于2C.二叉树中每个结点的度都为2D.二叉树中至少有一个结点的度为2正确答案：B3、在一棵高度为k的满二叉树中，结点总数为（）。

A.2k-1B. 2k-1C. 2k-1+1D.2k正确答案：B4、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。

A.不确定B.60C.59D.61正确答案：C解析：任意二叉树中，n0=n2+15、高度为7的完全二叉树，最少有（）个结点。

A.127B.128C.63D.64正确答案：D解析：前6层都是满的，最后一层（第7层）近1个结点。

可保证题目条件。

6、高度为7的二叉树，最少有（）个结点。

A.7B.127C.13D.64正确答案：A解析：每层只有1个结点。

共7个即可构成一个高度为7的二叉树。

7、对任意一棵有n个结点的树，这n个结点的度之和为( )。

A.n-1B.2*nC.n+2D.n正确答案：A解析：所有结点的度之和为分支个数，分支个数即为结点个数-18、在下列存储形式中，（）不是树的存储形式。

A.双亲表示法B.孩子-兄弟表示法C.孩子链表表示法D.顺序存储表示法正确答案：D9、对二叉树中的结点进行编号，要求根结点的编号最小，左孩子结点编号比右孩子结点编号小。

则应该采用（）遍历方法对其进行编号。

A.层次B.先序C.后序D.中序正确答案：B10、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。

A. 59B.61C.60D.不一定正确答案：A11、树的后根遍历，相当于对应二叉树的（）遍历。

A.中序B.后序C.层次D.先序正确答案：A二、判断题1、完全二叉树一定存在度为1的结点。

第六章 树和二叉树一、选择题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【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③B ．②③④C ．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定 【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T 。

其余结点分成为m （m>0）个(（2）)的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T的子结点（1≤i ≤m ）。

数据结构（本）单元6树和二叉树单元测试（题+答案）题目1、假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。

A. 15B. 16C. 47D. 17题目2、已知某二叉树的后续遍历序列是dabec，中序遍历是debac，则它的先序遍历序列是（）。

A. cedbaB. decabC. acbedD. deabc题目3、二叉树第k层上最多有（）个结点。

A.B.C.D. 2k题目4、二叉树的深度为k，则二叉树最多有（）个结点。

A.B.C. 2kD. 2k-1题目5、设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（）。

A. debacB. debcaC. abedcD. abdec题目6、设某一二叉树中序遍历为badce，后序遍历为bdeca，则该二叉树先序遍历的顺序是（）。

A. debacB. decabC. adbecD. abcde题目7、树最适合于用来表示（）。

A. 元素之间有包含和层次关系的数据B. 元素之间无前驱和后继关系的数据C. 顺序结构的数据D. 线性结构的数据题目8、一棵非空的二叉树，先序遍历与后续遍历正好相反，则该二叉树满足（）。

A. 任意二叉树B. 无左孩子C. 只有一个叶子结点D. 无右孩子题目9、设a，b为一棵二叉树的两个结点，在后续遍历中，a在b前的条件是（）。

A. a在b左方B. a在b右方C. a在b上方D. a在b下方题目10、权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（）。

A. 29B. 18C. 19D. 28题目11、如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

A. 哈夫曼树B. 平衡二叉树C. 二叉树D. 完全二叉树题目12、下列有关二叉树的说法正确的是（）。

A. 完全二叉树中，任何一个结点的度，或者为0或者为2B. 二叉树中度为0的结点的个数等于度为2的结点的个数加1C. 二叉树的度是2D. 二叉树中结点个数必大于0题目13、二叉树是非线性数据结构，所以（）。

一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。

【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。

【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。

本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。

虽然解法也对，但步骤多且复杂，极易出错。

6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。

【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。

6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。

【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。

若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。

6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。

数据结构树和二叉树习题及答案集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D )A ．-A+B*C/DE B. -A+B*CD/E C ．2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ）①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③B ．②③④C ．②④D ．①④4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。

A ．M1B ．M1+M2C ．M3D ．M2+M36. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D )A ．不确定B ．2nC ．2n+1D ．2n-17．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点A ．2hB ．2h-1C ．2h+1D ．h+18. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ）A ．⎣logn ⎦+1B ．logn+1C ．⎣logn ⎦D ．logn-19．深度为h 的满m 叉树的第k 层有（ A ）个结点。

(1=<k=<h)A ．m k-1B ．m k -1C ．m h-1D ．m h -110. 一棵树高为K 的完全二叉树至少有（ C ）个结点A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k11. 利用二叉链表存储树，则根结点的右指针是（ C ）。

习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F 对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。