第6章+树和二叉树(习题)

数据结构练习第六章树一、选择题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章 树和二叉树内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应的操作，并在综合应用设计中，给出了对应算法的C 语言实现。

教学目标1．理解各种树和森林与二叉树的相应操作。

2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。

3．熟练掌握二叉树和树的各种存储结构及其建立的算法。

4．掌握哈夫曼编码的方法。

5．通过综合应用设计，掌握各种算法的C 语言实现过程。

基本知识点：树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。

难点：编写实现二叉树和树的各种操作的递归算法。

本章知识体系结构：课时安排：6个课时树的定义 树树的性质 树的逻辑表示法 树形表示法 树的存储结构 双亲存储结构 文氏表示法凹入表示法 括号表示法 孩子存储结构 孩子双亲存储结构二叉树二叉树的定义 二叉树的性质二叉树的逻辑表示法（采用树的逻辑表示法）二叉树的存储结构二叉树的顺序存储结构先序遍历 中序遍历 后序遍历二叉树的遍历 二叉树的链式存储结构（二叉链） 由先序序列和中序序列构造二叉树 由中序序列和后序序列构造二叉树二叉树的构造 二叉树的线索化 哈夫曼树二叉树和树之间的差别 二叉树与树、森林之间的转换二叉树和树课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握树、二叉树的基本概念和术语，二叉树的性质教学重点二叉树的定义、二叉树的性质、链式存储结构教学难点二叉树的性质、链式存储二叉树的基本操作组织教学一、树的定义二、树的基本概念三、二叉树的定义、性质四、二叉树的顺序存储结构和链式存储结构五、小结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握二叉树遍历的三种方法及二叉树的基本操作教学重点二叉树的遍历算法教学难点中序与后序遍历的非递归算法组织教学一、复习二叉树的定义二、遍历二叉树的三种方法三、递归法遍历二叉树四、二叉树的基本操作五、总结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标理解树与森林的转换，掌握哈夫曼树教学重点哈夫曼树教学难点树与森林的转换组织教学一、导入二、树与森林三、哈夫曼树四、小结作业习题6课堂情况及课后分析前面几章讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，可用于描述客观世界中具有单一前驱和后继的数据关系。

【课后习题】第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(E,F(G)),D),回答下⾯的问题：这棵树的根结点是谁？这棵树的叶⼦结点是什么？结点C的度是多少？这棵树的度是多少？这棵树的深度是多少？结点C的孩⼦结点是哪些？结点C的双亲结点是谁？2、若⼀棵度为4的树中度为1,2,3,4的结点个数分别是4,3,2,2，则该树中叶⼦结点的个数是多少？总结点个数是多少？3、⼀棵⾼度为h的完全k次数，如果按照层次⾃上向下、⾃左向右的顺序从1开始对全部结点编号，试问：最多有多少个结点？最少有多少个结点？编号为q的结点的第i个孩⼦结点的编号是多少？4、若⼀棵⼆叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为结点的总个数为5、⼀棵完全⼆叉树有1001个结点，其中叶⼦结点的个数为6、⼀棵⾼度为h的完全⼆叉树⾄少有个结点。

7、⼀棵⾼度为5的完全⼆叉树⾄多有个结点。

8、设⾼度为h的⼆叉树上只有度为0和度为2的结点，则此类⼆叉树⾄少包含个结点。

9、⼀个具有1025个结点的⼆叉树的⾼度h为10、在⼀棵完全⼆叉树中，结点个数为n，则编号最⼤的分⽀结点的编号为11、⼀棵⼆叉树的先序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为12、⼀棵⼆叉树的先序遍历为ABCDEFG，它的中序遍历可能为A.CABDEFGB. ABCDEFGC.DACEFBGD.ADCFEGB思考：⼆叉树的先序和中序遍历相同的条件是？⼆叉树的后序和中序遍历相同的条件是？13、⼀棵⼆叉树的后序遍历为DABEC，中序遍历为DEBAC，则先序遍历为14、⼀棵⼆叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该⼆叉树根结点的右孩⼦为16、根据使⽤频率为5个字符设计的赫夫曼编码不可能的是A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,1017、根据使⽤频率为5个字符设计的赫夫曼编码不可能的是A. 000,001,010,011,1B.0000,0001,001,01,1C. 000,001,01,10,11D.00,100,101,110,11118、设有13个值，⽤它们组成⼀棵赫夫曼树，则该赫夫曼树共有个结点。

第三单元课后练习题（参考答案）知识点范围：第6章树与二叉树、第7章图一、选择题（每小题1分，共25分）1．树最适合用来表示 C 。

A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据2．深度为5的二叉树至多有 C 个结点。

A．16 B．32 C．31 C．103．对一个满二叉树，m个叶子，n个结点，深度为h，则 D 。

A．n = h+m B．h+m = 2n C．m = h-1 D．n = 2h-14．任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 A 。

A．不发生改变B．发生改变C．不能确定D．以上都不对5．设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为：AA．10 B．11 C．12 D．不确定6．在下述论述中，正确的是 D 。

①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③B．②③④C．②④D．①④7．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，森林F中第一棵树的结点的个数是 A 。

A．m-n B．m-n-1 C．n+1 D．不能确定8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是 B 。

A．9 B．11 C．15 D．不能确定9．具有10个叶子结点的二叉树中有 B 个度为2的结点。

A．8 B．9 C．10 D．1110．在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。

A．1/2 B． 1 C．2 D． 411.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

A． 2i+1 B． 2i C． i/2 D． 2i-112．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为： CA．3 B．2 C．4 D．513．已知一算术表达式的中缀形式为A＋B *C–D/E，后缀形式为ABC *+DE/–，其前缀形式为 D 。

1、树最适合用来表示（）。

A.元素之间无联系的数据B.元素之间具有层次关系的数据C.无序数据元素D.有序数据元素正确答案：B2、现有一“遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。

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

A.线性表B.树C.数组D.图正确答案：B3、一棵节点个数为n、高度为h的m（m≥3）次树中，其分支数是（）。

A.n+hB.h-1C.n-1D.nh正确答案：C4、若一棵3次树中有2个度为3的节点，1个度为2的节点，2个度为1的节点，该树一共有（）个节点。

A.11B.5C.8D.10正确答案：A解析： A、对于该3次树，其中有n3=2，n2=1，n1=2，总分支数=总度数=n-1，总度数=1×n1+2×n2+3×n3=10，则n=总度数+1=11。

5、设树T的度为4，其中度为1、2、3、4的节点个数分别为4、2、1、1，则T中的叶子节点个数是（）。

A.6B.8C.7D.5正确答案：B解析： B、这里n1=4，n2=2，n3=1，n4=1，度之和=n-1=n1+2n2+3n3+4n4=15，所以n=16，则n0=n-n1-n2-n3-n4=16-8=8。

6、有一棵三次树，其中n3=2，n2=1，n0=6，则该树的节点个数为（）。

A.9B.12C.大于等于9的任意整数D.10正确答案：C解析： C、n=n0+n1+n2+n3=6+n1+1+2=9+n1。

7、假设每个节点值为单个字符，而一棵树的后根遍历序列为ABCDEFGHIJ，则其根节点值是（）。

A.JB.BC.以上都不对D.A正确答案：A8、一棵度为5、节点个数为n的树采用孩子链存储结构时，其中空指针域的个数是（）。

A.4nB.4n-1C.4n+1D.5n正确答案：C解析： C、总指针数=5n，非空总指针数=分支数=n-1，空指针域的个数=5n-(n-1)=4n+1。

9、有一棵三次树，其中n3=2，n2=2，n1=1，该树采用孩子兄弟链存储结构时，则总的指针域数为（）。