树和二叉树(习题及作业)

树和二叉树练习题及解答_richard一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

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

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

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

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

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

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

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

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

（正确。

用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。

由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。

）即有后继链接的指针仅n-1个。

（√ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有 5 种形态。

2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+n2= n0-1=31 个分支结点和 26-1 =32个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

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

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

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

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

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

4. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为n 2，则有n0= 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）次序的遍历实现编号。

数据结构树和二叉树习题一、树的基本概念1.请简要描述树的基本概念及其特点。

答：树是由n(n≥0)个节点组成的有限集合。

其中：-若n=0，则为空树。

-若n＞0，则树有且仅有一个称为根的节点，其他节点可以分为多个互不相交的有限集合，每个集合本身又是一棵树，称之为根的子树。

树的特点包括：-每个节点存放的数据可以是同种或不同种的数据类型。

-每个节点最多有一个父节点和多个子节点。

2.请列举树的应用场景。

答：树的应用场景包括但不限于以下几个方面：-文件系统：操作系统中的文件系统通常使用树来组织文件和目录。

-数据库：数据库中的索引通常使用树来存储和组织数据。

-编译原理：编译器使用语法树来解析源代码。

-社交网络：社交网络中的关注和粉丝关系可以表示为树。

二、二叉树3.请定义二叉树。

答：二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

4.请画出以下二叉树的结构图：A/\BC/\/\DEFG答：以下是该二叉树的结构图：A/\BC/\/\DEFG5.请写出以下二叉树的前序遍历、中序遍历和后序遍历结果：/\23/\45答：-前序遍历结果：1,2,4,5,3-中序遍历结果：4,2,5,1,3-后序遍历结果：4,5,2,3,1三、二叉树的操作6.请实现二叉树的插入操作。

答：以下是二叉树的插入操作的示例代码：```class Node:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef insert(root, value):if root is None:root = Node(value)else:if value < root.value:if root.left is None:root.left = Node(value)else:insert(root.left, value)else:if root.right is None:root.right = Node(value)else:insert(root.right, value)```7.请实现二叉树的查找操作。

习题五树与二叉树一、选择题1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。

A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。

A、250B、500C、254D、505E、以上答案都不对3、以下说法正确的是。

A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点4、以下说法错误的是。

A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的5、一棵有124个叶结点的完全二叉树，最多有个结点。

A、247B、248C、249D、250E、2516、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。

A、不发生变化B、发生变化C、不能确定7、设a、b为一棵二叉树上的两个结点。

在中序遍历时，a在b前面的条件是。

A、a在b的右方B、a在b的左方C、a是b的祖先D、a是b的子孙8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。

A、不确定B、2kC、2k-1D、2k+19、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。

A、13B、12C、26D、2510、下面几个符号串编码集合中，不是前缀编码的是。

习题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时，则（）。

第六章树和二叉树作业一、选择题（每题2分，共24分）。

1. 一棵二叉树的顺序存储情况如下：树中，度为2的结点数为（ C ）。

A．1 B．2 C．3 D．42. 一棵“完全二叉树”结点数为25，高度为（B ）。

A．4 B．5 C．6 D．不确定3．下列说法中，（B ）是正确的。

A. 二叉树就是度为2的树B. 二叉树中不存在度大于2的结点C. 二叉树是有序树D. 二叉树中每个结点的度均为24.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（B ）。

A. CABDEFGB. BCDAEFGC. DACEFBGD. ADBCFEG5．线索二叉树中的线索指的是（C ）。

A．左孩子 B.遍历 C.指针 D.标志6. 建立线索二叉树的目的是（A ）。

A. 方便查找某结点的前驱或后继B. 方便二叉树的插入与删除C. 方便查找某结点的双亲D. 使二叉树的遍历结果唯一7. 有 D ）示意。

A.B.C.D.8. 一颗有2046个结点的完全二叉树的第10层上共有（B ）个结点。

A. 511B. 512C. 1023D. 10249. 一棵完全二叉树一定是一棵（A ）。

A. 平衡二叉树B. 二叉排序树C. 堆D. 哈夫曼树10．某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ C ）的二叉树。

A ．空或只有一个结点B ．高度等于其结点数C ．任一结点无左孩子D ．任一结点无右孩子11．一棵二叉树的顺序存储情况如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E 0 F 0 0 G H 0 0 0 X结点D 的左孩子结点为（ D ）。

A ．EB ．C C ．FD ．没有12．一棵“完全二叉树”结点数为25，高度为（ B ）。

A ．4B ．5C ．6D ．不确定二、填空题（每空3分，共18分）。

1. 树的路径长度：是从树根到每个结点的路径长度之和。

对结点数相同的树来说，路径长度最短的是 完全 二叉树。

E F D GAB/+ +* - C* 第六章树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DED. -+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 ．5 B．6 C．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 ）。

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，该树采用孩子兄弟链存储结构时，则总的指针域数为（）。

树和二叉树习题及答案一、填空题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）次序的遍历实现编号。

n-，由于1 、【答案】B。

如果根结点的深度为1，则满二叉树结点总数为2111-=2048-1=2047<2381，故整个树高为11（满二叉树）+1=12。

由于本题设定的根结点21深度为0，故该题的树高为11。

2、【答案】BC。

不论先根、中序和后根，左子树的结点总是出现在右子树结点的前面。

①先根: 123456，后根:325641，则1是根；②先根：与1相连的是2，后根以2为界，得到1的左右两棵子树，左子树：32，右子树564。

③递归求解，先根: 23，后根32，得到：3既可以是2的左子树，也可以是右子树④先根：456，后根：564，得到：先根、后根遍历得到的二叉树不唯一⑤对生成的二叉树（两种情况）中根遍历，得到答案B和C。

关于先根、中根和后根遍历求解问题，需要大家重点掌握。

3、【答案】ABD。

①先根：124563 后根：4652731 得到：根结点为1。

②先根1后为2，后根以2为分界，4652是根结点的左子树（其中2是左结点），73是根结点的右子树。

③继续递归求解，先根：456 后根：465，则4为2的左子树，56为2的右子树。

④先根：56 后根：65，则5为2的右子树，6既可以是5的左子树，也可以是右子树。

⑤先根：37 后根：73，则1的右子树为3，7既可以是3的左子树，也可以是右子树，得到全树结构。

最后中根遍历，共4组解。

ABD是其中三种，还是一种：4265137。

4、【答案】C。

设二叉树中度为0的结点(叶子)有N0个，度为1的结点有N1个，度为2的结点有N2个，所有结点个数：N0＋N1＋N2，所有的边数：N0*0+N1*1+N2*2=N1+2N2。

由于每个结点上都有一条边，除根结点外，所以有N0+N1+N2=N1+2N2+1→N0=N2+1 …………①完全二叉树有2*N-1个结点（奇数个），而完全二叉树的上一层是一棵满二叉树，而满二叉树的结点个数是2^k-1（k是层数，是奇数个），所以此二叉树最下一层是偶数个结点，这样的二叉树没有度为1的结点，即N1=0，得到N0+N2=2*N-1 →N2=2*N-N0-1 …………②将②式代入①式，得到N0=N。