数据结构-习题-第六章-树

第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的结点数为n 1，度为2的结点数为n 2，……，度为m 的结点数为n m ，那么该树中含有多少个叶子结点？有多少个非终端结点？ABECDFGHJI4. 任意一棵有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 之间的关系是什么？ 13. 对图6-2(a)和(b)所示的二叉树，它们的经过先序、中序和后序遍历后得到的结点序列分别是什么？画出它们的先序线索二叉树和后序线索二叉树。

习题六树和二叉树一、单项选择题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 层上最多含有结点数为（）I I-1 I-1 IA．2IB ．2I-1-1 C ．2I-1D ．2I-110．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

《数据结构与算法》第二部分习题精选一、下面是有关二叉树的叙述，请判断正误（）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（）2.二叉树中每个结点的两棵子树的高度差等于1。

（）3.二叉树中每个结点的两棵子树是有序的。

（）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

（）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（√）10. 具有12个结点的完全二叉树有5个度为2的结点。

二、填空1．由３个结点所构成的二叉树有种形态。

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

3．一棵具有２５７个结点的完全二叉树，它的深度为。

4.设一棵完全二叉树有700个结点，则共有个叶子结点。

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

6.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。

7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。

因而二叉树的遍历次序有六种。

最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。

这三种方法相互之间有关联。

若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。

8.中序遍历的递归算法平均空间复杂度为。

9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。

数据结构-树习题第六章树⼀、选择题1、⼆叉树的深度为k，则⼆叉树最多有（ C ）个结点。

A. 2kB. 2k-1C. 2k-1D. 2k-12、⽤顺序存储的⽅法，将完全⼆叉树中所有结点按层逐个从左到右的顺序存放在⼀维数组R[1..N]中，若结点R[i]有右孩⼦，则其右孩⼦是（B ）。

A. R[2i-1]B. R[2i+1]C. R[2i]D. R[2/i]3、设a,b为⼀棵⼆叉树上的两个结点，在中序遍历时，a在b前⾯的条件是（ B ）。

A. a在b的右⽅B. a在b的左⽅C. a是b的祖先D. a是b的⼦孙4、设⼀棵⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树先序遍历序列为（）。

A. adbceB. decabC. debacD. abcde5、在⼀棵具有5层的满⼆叉树中结点总数为（A）。

A. 31B. 32C. 33D. 166、由⼆叉树的前序和后序遍历序列（ B ）惟⼀确定这棵⼆叉树。

A. 能B. 不能7、某⼆叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左⼦树中结点数⽬为（ C ）。

A. 3B. 2C. 4D. 58、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。

A. 67B. 68C. 69D. 709、将⼀棵有100个结点的完全⼆叉树从根这⼀层开始，每⼀层上从左到右依次对结点进⾏编号，根结点的编号为1，则编号为49的结点的左孩⼦编号为（ A ）。

A. 98B. 99C. 50D. 4810、表达式a*(b+c)-d的后缀表达式是（ B ）。

A. abcd+-B. abc+*d-C. abc*+d-D. -+*abcd11、对某⼆叉树进⾏先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。

A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、树最适合⽤来表⽰（ C ）。

一、基础知识题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个结点仅有一个孩子，则该二叉树的总结点数是多少。

第六章树和二叉树试题一、单项选择题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 ) )，则该二叉树的高度为（）。

第六章树一．名词解释：1 树 2。

结点的度 3。

叶子 4。

分支点 5。

树的度6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树21 哈夫曼树二、填空题1、树（及一切树形结构）是一种“________”结构。

在树上，________结点没有直接前趋。

对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2、一棵树上的任何结点（不包括根本身）称为根的________。

若B是A的子孙，则称A是B的________3、一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。

4、二叉树第i(i>=1)层上至多有______个结点。

5、深度为k(k>=1)的二叉树至多有______个结点。

6、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。

满二叉树也是______二叉树，但反之不然。

8、具有n个结点的完全二叉树的深度为______。

9、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：（1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。

（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。

（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。

10.二叉树通常有______存储结构和______存储结构两类存储结构。

11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。

第6章树和二叉树一、选择题1．不含任何结点的空树（）。

A. 是一棵树B. 是一棵二叉树C. 是一棵树也是一棵二叉树;D. 既不是树也不是二叉树2. 一棵有n个结点的树的所有结点的度数之和为（）。

A. n-1B. nC. n+1D. 2n3. 在二叉树中某一个结点的深度为3，高度为4，则该树的高度是（）。

A. 5B. 6C. 7D. 84. 设高度为h的二叉树中只有度为0和度为2的结点，则该树的结点数至多为（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h+15. 设高度为h的二叉树中只有度为0和度为2的结点，则该树的结点数至少为（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h+16. 高度为h的满二叉树中有n个结点，其中有m个叶结点，则正确的等式是（）。

A. h+m=nB. h+m=2nC. m=h-1D. n=2h-17．二叉树是非线性数据结构，所以（）。

A. 它不能用顺序存储结构存储B. 它不能用链式存储结构存储C. 顺序存储结构和链式存储结构都能存储D. 顺序存储结构和链式存储结构都不能使用8. 一棵完全二叉树有25个叶结点，则该树最少有（）个结点。

A. 48B. 49C. 50D. 519. 假设一个三叉树的结点数为36，则该树的最小高度为（）。

A. 2B. 3C. 4D. 510. 设二叉树有n个结点，则二叉链表中非空指针数为（）。

A. n-1B. nC. n+1D. 2n11. 先序序列和中序序列正好相反的二叉树是（）。

A. 完全二叉树B. 满二叉树C. 左单枝树D. 右单枝树12. 后序序列和中序序列正好相反的二叉树是（）。

A. 完全二叉树B. 满二叉树C. 左单枝树D. 右单枝树13．把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A. 唯一的B. 有多种C. 有多种，但根结点都没有左孩子D. 有多种，但根结点都没有右孩子14. 将一棵树T转换为孩子—兄弟链表表示的二叉树H，则T的后根序遍历是H 的（）。

第6章习题一、填空1．结点数为7的二叉树的高度最矮是，最高是。

2．给定二叉树的结点数，要使树高为最大，那么该树应该是形状。

3．给定二叉树的结点数，要使树高为最矮，那么该树应该是形状。

4．如果一棵满二叉树的深度为6，那么它共有个结点，有个叶结点。

5．有15个结点的二叉树，最少有个叶结点，最多有个叶结点。

6．由n个带权值的叶结点生成的哈夫曼树，最终共有个结点。

7．将一棵完全二叉树按层次进行编号。

那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是；如果有右孩子，则右孩子的编号应该是。

8．若二叉树共有n个结点，采用二叉链表存储结构。

那么在所有存储结点里，一共会有个指针域，其中有个指针域是空的。

9．深度为5的二叉树，至多有个结点。

10．在二叉树中，有一个结点具有左、右两个孩子。

那么在中序遍历序列里，它的右孩子一定排在它的边。

二、选择1．在所给的4棵二叉树中，不是完全二叉树。

2．把一棵深度为3的左单支二叉树改造成完全二叉树时，要增添个空结点。

A．10 B．8 C．6 D．43．设有一棵5个结点的二叉树，其先序遍历序列为：A-B-C-D-E，中序遍历序列为：B-A-D-C-E，那么它的后序遍历序列为。

A．A-B-D-E-C B．B-D-E-C-AC．D-E-C-A-B D．A-B-C-D-E4．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是。

A．无左、右孩子B．有左孩子，无右孩子C．有右孩子，无左孩子D．有左、有孩子5．深度为6的二叉树，最多可以有个结点。

A．63 B．64 C．127 D．1286．在一棵非空二叉树的中序遍历序列里，根结点的右边结点。

A．只有左子树上的部分B．只有左子树上的所有C．只有右子树上的部分D．只有右子树上的所有7．在任何一棵二叉树的各种遍历序列中，叶结点的相对次序是。

A．不发生变化B．发生变化C．不能确定D．以上都不对8．权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是。

第六章 树和二叉树一、选择题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 ）。

第六章树和二叉树（下载后用阅读版式视图或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_l C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

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

7.深度为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结点的兄弟结点是C．空(4)F结点的双亲结点是(5)树的深度为(6)B结点的深度为(7)A结点所在的层是11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。

A．247 B．248 C．249 D．25013.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点( )。

数据结构练习第六章树一、选择题1.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-13.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A. 2m-1B. 2mC. 2m+1D. 4m4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A. BADCB. BCDAC. CDABD. CBDA5.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

A. 9B. 10C. 11D. 126．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

A. 2k-1 B .2k C. 2k-1 D. 2k-17．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

A. N0=N1+1 B. N=Nl+N2C. N=N2+1 D. N=2N1+l8．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N=（）。

A. Nl +N2+……+Nm B. l+N2+2N3+3N4+……+(m-1)NmC. N2+2N3+3N4+……+(m-1)Nm D. 2Nl+3N2+……+(m+1)Nm9．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。

A. 20B. 30C. 40D. 4510．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子11．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。

A. 3B. 4C. 5D. 612．深度为k的完全二叉树中最少有（）个结点。

【课后习题】第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.已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；三、单项选择（请将正确答案的代号填写在下表对应题号下面。

第6章树和二叉树一、选择题（每小题1分，共10分）1.以下数据结构中，（ A ）是非线性数据结构。

A.树B.线性表C.队列D.栈2.在一棵二叉树中第五层上的结点数最多为（ B ）。

A.8B.15C.16D.323. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。

A. CBEFDAB. FEDCBAC. CBEDFAD. 不定4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。

A.9B.11C.15D.不确定5.给定二叉树如图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（D ）。

A. LRNB. NRLC. RLND. RNL6.在下列存储形式中，哪一个不是树的存储形式？（ D ）A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.顺序存储表示法7.有n个叶子的哈夫曼树的结点总数为（D ）。

A．不确定B．2n C．2n+1 D．2n-18.设i为n个结点的完全二叉树结点编号，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ B ）A.2iB.2i+1C.2i-1D.i+19. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）。

A.23B.37C.44D.4610.一棵具有n个结点的完全二叉树的树高度（深度）是（ A ）。

A. +1B. log2n+1C.D. log2n-111.由权值分别为7，9，4，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。

A.36B.60C.48D.5312.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。

A. 24B. 71C. 48D. 5313.具有35个结点的完全二叉树的深度为( B )。

第六章树习题1单项选择题1、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则叶子结点个数是（B）。

A、9B、11C、15D、无法确定2、设给定权值总数有n个，其哈夫曼树的结点总数为( D )。

A、不确定B、2nC、2n+1D、2n–13、有关二叉树下列说法正确的是（B）。

A、二叉树的度为2B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为24、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点。

A、2hB、2h-1C、2h+1D、h+15、对于有n个结点的二叉树, 其高度为（）。

log D、不确定A、n log2nB、log2nC、⎣⎦n26、利用二叉链表存储树，则根结点的右指针是（）。

A、指向最左孩子B、指向最右孩子C、空D、非空7、树的后根遍历序列等同于该树对应的二叉树的( )。

A、先序遍历B、中序遍历C、后序遍历D、层序遍历8、在下列存储形式中，哪一个不是树的存储形式？（）A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法9、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

A、CBEFDAB、FEDCBAC、CBEDFAD、不定10、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A、空的或只有一个结点B、任一结点无左子树C、高度等于其结点数D、任一结点无右子树11、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )。

A、不确定B、0C、1D、212、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )。

A、X的双亲B、X的右子树中最左的结点C、X的左子树中最右结点D、X的左子树中最右叶结点13、引入二叉线索树的目的是（）.A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入和删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一14、下述编码中哪一个不是前缀码（）。

一．选择题1.设高度为h的二叉树只有为0和2的结点，则此类二叉树的结点数至少有（）个，至多有几个（）A.2hB.2h-1C.2h+1D.2h-1E.2h-1F.2h+12.高度为h的完全二叉树有（）个结点，至多有（）个结点。

A.2hB. 2h-1C. 2h+1D. 2h-13.具有n个结点的满二叉树有（）个叶结点。

A.n/2B.(n-1)/2C.(n+1)/2D.n/2+14.一棵具有n个叶节点的哈夫曼树，共有（）个结点。

A.2nB. 2n-1C.2n+1D.2n-15.一棵具有25个结点的完全二叉树最多有（）个结点。

A.48B.49C.50D.516.已知二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列是（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定7.已知二叉树的中序遍历序列是debac,后序遍历序列是dabec,则前序遍历序列是（）。

A.acbedB.decabC.deabcD.cedba8.下面4棵二叉树中，（）不是完全二叉树。

AC D9.在线索化二叉树中，t所指结点没有左子树的充分必要条件是（）。

A.t->left=nullB. t->ltag=1C. t->left=null且t->ltag=1D.以上都不对10.下列线索二叉树中（用虚线表示线索），符合后续线索树的定义的是（）。

11.算术表达式a+b*(c+d/c)转换为后缀表达式是（）。

A．ab+cde/* B．abcde/+*+C．abcde/*++ D. abcde*/++12.具有10个叶结点的二叉树中有（）个度为2的结点。

A．8 B.9 C.10 D.1113.一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11~1025D.10~102414.前序遍历与中序遍历结果相同的二叉树为（）；前序遍历和后序遍历结果相同的二叉树为（）的二叉树。

A.空二叉树B.只有根结点C.根结点无左孩子D.根结点无右孩子15.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。