30、以下说法错误的是（ ）
A、完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B、在三叉链表上，二叉树的求双亲运算很容易实现 C、在二叉链表上，求根，求左、右孩子等很容易实现 D、在二叉链表上，求双亲运算的时间性能很好 31、以下说法错误的是（ ）
A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点
C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点
D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
32、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（ ）
A 、10 B、 11 C、 41 D、 20
33、任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（ ） A、肯定发生变化 B、有时发生变化 C、肯定不发生变化 D、无法确定 34、下列说法正确的是（ ）
A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同 B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同 D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同 35、下列说法中正确的是（ ）
A、任何一棵二叉树中至少有一个结点的度为2 B、任何一棵二叉树中每个结点的度都为2
C、任何一棵二叉树中的每个结点的度肯定等于2 D、任何一棵二叉树中的每个结点的度都可以小于2
36、一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵二叉树所有结点的递减序列。
A、前序 B、中序 C、后序 D、层次
37、对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A 、0 B、 1 C 、2 D、 不存在这样的二叉树
38、在图6.2中的二叉树中，（ ）不是完全二叉树。
A、 B、 C、 D、
图6.2
39、树最适合用来表示（ ）
A、有序数据元素 B、无序数据元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 40、哈夫曼树的带权路径长度是（ ）
A、所有结点权值之和 B、所有叶结点带权路径长度之和
C、带权结点的值 D、除根以外所有结点权值之和 41、在线索二叉树上，线索是（ ）
A、两个标志域 B、指向结点前驱和后继的指针 C、数据域 D、指向左、右子树的指针 42、已给出如图6.3所示哈夫曼树，那么电文CDAA的编码是( )
A、110100 B、11011100 C、010110111 D、11111100
A B C D 图6.3
43、已给出的图6.3所示二叉树，A,B,C,D分别带权值为7，5，2，4则该树的带权路径长度为（ ）
A、46 B、36 C、35 D、都不是 44、在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）
A、t->lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对 45、下列叙述中正确的是（ ）
A、二叉树是度为2的有序树 B、 二叉树中结点只有一个孩子时无左右之分
C、二叉树中必有度为2的结点 D、 二叉树中结点最多有两棵子树，并且有左右之分 46、下图6.4所示的几种结构中属于树型结构的是（ ）
A、 B、 C、 D、
图6.4
二、 判断题
1、二叉树是树的特殊形式。
2、树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
3、一棵有n个结点的d度树，若用多重链表表示，树中每个结点都是有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。
4、前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 5、后序遍历树和中序遍历与该树对应的二叉树，其结果不同。 6、前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 7、中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。
8、若有一个结点是某二叉树子树的中序遍历序列中最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。
9、二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。 10、在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。 11、中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。
12、在二叉树中插入结点，该二叉树便不在是二叉树。 13、用一维数组存储二叉树时，总是以前序遍历存储结点。
14、已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。 15、不使用递归，也可以实现二叉树的前序，中序，后序遍历。
16、在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。 17、中序遍历线索二叉树，不必使用栈。
18、对于后序线索二叉树要找到它的任一结点的后继有时是困难的。 19、有n个结点的不同的二叉树有n！棵。
20、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。
三、 填空题
1、在树型结构中，树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结点没有（ ）结点，其余每个结点的后继结点可以（ ）。 2、假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为（ ），树的深度为（ ），终端结点的个数为（ ），单分支结点的个数为（ ），双分支结点的个数为（ ），三分支结点的个数为（ ），C的双亲结点为（ ），其孩子结点为（ ）。
3、设树T中除叶结点外，任意结点的度数都是3，则T的第I层结点的个数为（ ）。 4、在具有n(n>=1)个结点的k叉树中，有（ ）个空指针。 5、一棵含有n个结点的k叉树，可能达到的最大深度为（ ），最小深度为（ ）。 6、一棵深度为k的满二叉树的结点总数为（ ），一棵深度为k的完全二叉树的结点总数的最小值为（ ），从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是（ ），最大值为（ ）。
7、设根结点的层次数为0，定义树的高度为树中层次最大的结点的层次加1，则高度为k的二叉树具有的结点数目，最少为（ ），最多为（ ）。 8、n个结点的完全二叉树，若按从上到下、从左到右给结点顺序编号，则编号最大的非叶结点编号为（ ），编号最小的叶结点编号为（ ）。
9、在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=（ ）。 10、一棵二叉树的第I层最多有（ ）个结点，一棵有n个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。
11、一棵完全二叉树的第5层有5个结点，则共有（ ）个结点，其中度为1的结点有（ ）个，度为0的结点有（ ）个。
12、具有n个结点的完全二叉树，其叶子结点的个数为（ ）。
13、对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（ ）个，其中（ ）个用于链接孩子结点，（ ）个空闲。
14、对于一棵具有n个结点的二叉树，当它为一棵（ ）二叉树时具有最小高度，高度为（ ），当它为一棵单支树时具有（ ）高度，高度为（ ）。
15、树所对应的二叉树其根结点的（ ）子树一定为空。
16、从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是（ ）。 17、结点最少的树为（ ），结点最少的二叉树为（ ）。
18、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ ），后序遍历中结点B的直接后继为（ ）。
19、某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为（ ），该二叉树对应的森林包括（ ）棵树。
20、在一棵二叉树上按（ ）遍历得到的结点序列为有序序列。 21、由n个权值构成的哈夫曼树共有（ ）个结点。
22、由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（ ）。
23、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
补充填空题：
1. 树（及一切树形结构）是一种________结构。在树上，________结点没有直接前趋。对树上任一结点X
来说，X是它的任一子树的根结点惟一的________。
2. 一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________。 3. 二叉树第i(i≥1)层上至多有______个结点。 4. 深度为k(k≥1)的二叉树至多有______个结点。
5. 对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 6. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。 7. 具有n个结点的完全二叉树的深度为______。
8. 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。 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. 每个二叉链表还必须有一个指向______结点的指针，该指针具有标识二叉链表的作用。 12. 对二叉链表的访问只能从______指针开始。
13. 具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其
余的________个指针域为NULL。
14. 已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为 。 15. 二叉树有不同的链式存储结构，其中最常用的是________与________。
16. 可通过在非完全二叉树的“残缺”位置上增设 ________ 将其转化为完全二叉树。 17. 具有100个结点的完全二叉树的深度是 。 18. 深度为90的满二叉树上，第10层有 个结点。
19. 在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 20. 具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的
分支结点序号是________，编号最小的分支结点序号是________，编号最大的叶子结点序号是________，编号最小的叶子结点序号是________。
21. 若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为________。
22. 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为________个。 23. 设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有 个结点。
24. 现有按中序遍历二叉树的结果为ABC，问有________种不同形态的二叉树可以得到这一遍历结果。 25. 以数据集{4，5，6，7，10}为叶结点的权值所构造的哈夫曼树的带权路径长度为________。
26. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有________
个叶子结点。 27. 设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是________。 28. 如果结点a有三个兄弟，而且b是a的双亲，则b的度是______。
29. 一棵树的形状如图6.5所示，它的根结点是________，叶子结点是________，结点H的度是________，
这棵树的度是________，这棵树的深度是________，结点F的儿子结点是________，结点G的父结点是________。
A
B C D
E G H I F
J K L O P M N Q R
