第6章树和二叉树一、选择题1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ）A、向量B、树C、图D、二叉树2.树最适合用来表示（ B ）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ）A、1a(2b(3d,3e),2c)B、a(b(D,e),c)C、a(b(d,e),c)D、a(b,d(e),c)4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。

A、先序B、中序C、后序D、从根开始按层次遍历5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。

A、3B、4C、5D、66.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。

log+1 C、log2n D、nA、n/2B、⎣⎦n2E、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1 J、n1K、n2L、n1+17.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ）A、n=m+hB、h+m=2nC、m=h-1D、n=2h-18.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多为（D ）。

A、2hB、2h-1C、2h-1D、2h-19.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1）A、8B、16C、15D、3210.深度为5 的二叉树至多有（ C ）个结点。

A、16B、32C、31D、1011.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点A、247B、248C、249D、25012.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点A、254B、255C、256D、25713.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。

A、15B、16C、17D、4714.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ B ）。

A、R[2i+1]B、R[2i]C、R[i/2]D、R[2i-1]15.在一棵非空二叉树的中序遍历序列中，根结点的右边（ A ）。

A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的所有结点D、只有左子树上的部分结点16.任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ A ）。

A、不发生改变B、发生改变C、不能确定D、以上都不对17.设n、m为一棵树上的两个结点，在中序遍历时，n在m 前的条件是（ C ）。

A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙18.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ D ），后序遍历中结点B的直接后继是（ E ）。

A、BB、DC、AD、IE、FF、C19.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（D ）。

A、acbedB、decabC、deabcD、cedba20.若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ C ）遍历方法最合适。

A、前序B、中序C、后序D、层次21.线索二叉树是一种（ C ）结构。

A、逻辑B、逻辑和存储C、物理D、线性22.如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的（ A ）。

A、前序B、中序C、后序D、层次序23.设T是哈夫曼树，具有5个叶结点，树T 的高度最高可以是（ E ）。

A、1B、2C、3D、4E、5F、624.由带权为8，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ D ）。

A、23B、37C、46D、4325.树的后根遍历序列等同于该树对应的二叉树的（ B ）。

A、先序遍历B、中序遍历C、后序遍历D、层次遍历26.以下说法错误的是（ A ）。

A、树形结构的特点是一个结点可以有多个直接前趋B、线性结构中的一个结点至多只有一个直接后继C、二叉树与树是两种不同的数据结构D、树(及一切树形结构)是一种“分支层次”结构27.以下说法错误的是（ C ）。

A、二叉树可以是空集B、二叉树的任一结点都有两棵子树C、二叉树与树具有相同的树形结构D、二叉树中任一结点的两棵子树有次序之分28.以下说法错误的是（ D ）。

A、完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B、在三叉链表上，二叉树的求双亲运算很容易实现C、在二叉链表上，求根，求左、右孩子等很容易实现D、在二叉链表上，求双亲运算的时间性能很好29.以下说法错误的是（D ）。

A、一般在哈夫曼树中，权值越大的叶子离根结点越近B、哈夫曼树中没有度数为1 的分支结点C、若初始森林中共有n 棵二叉树，最终求得的哈夫曼树共有2n-1 个结点D、若初始森林中共有n 棵二叉树，进行2n-1 次合并后才能剩下一棵最终的哈夫曼树30.将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21 的双亲结点编号为（ A ）。

A 、10 B、11 C、41 D、2031.任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（ C ）。

A、肯定发生变化B、有时发生变化C、肯定不发生变化D、无法确定32.下列说法正确的是（ A ）。

A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同33.下列说法中正确的是（ D ）。

A、任何一棵二叉树中至少有一个结点的度为2B、任何一棵二叉树中每个结点的度都为2C、任何一棵二叉树中的每个结点的度肯定等于2D、任何一棵二叉树中的每个结点的度都可以小于234.一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。

现采用（B ）遍历方式就可以得到这棵二叉树所有结点的递减序列。

A、前序B、中序C、后序D、层次35.对含有（ B ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A 、0 B、1 C 、2 D、不存在这样的二叉树36.在图6.2 中的二叉树中，（ C ）不是完全二叉树。

37.哈夫曼树的带权路径长度是（ B ）。

A、所有结点权值之和B、所有叶结点带权路径长度之和C、带权结点的值D、除根以外所有结点权值之和38.在线索二叉树上，线索是（ B ）。

A、两个标志域B、指向结点前驱和后继的指针C、数据域D、指向左、右子树的指针39.已给出如图6.3 所示哈夫曼树，那么电文CDAA 的编码是( B )。

A、110100B、11011100C、010110111D、1111110040.已给出的图6.3 所示二叉树，A,B,C,D 分别带权值为7，5，2，4 则该树的带权路径长度为（ C ）。

A、46B、36C、35D、都不是41.在线索化二叉树中，t 所指结点没有左子树的充要条件是（ B ）。

A、t->lchild==NULLB、t->ltag==1C、t->ltag==1&&t->lchild==NULLD、以上都不对42.下列叙述中正确的是（ D ）。

A、二叉树是度为2 的有序树B、二叉树中结点只有一个孩子时无左右之分C、二叉树中必有度为2 的结点D、二叉树中结点最多有两棵子树，并且有左右之分43.下图6.4 所示的几种结构中属于树型结构的是（ B ）。

、二、判断题1.二叉树是树的特殊形式。

X2.树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

V3.一棵有n 个结点的d 度树，若用多重链表表示，树中每个结点都是有d 个链域，则在树的n*d 个链域中，有n*(d-1)+1 个是空链域，只有n-1 个是非空的。

V4.前序遍历树和前序遍历与该树对应的二叉树，其结果相同。

V5.后序遍历树和中序遍历与该树对应的二叉树，其结果不同。

X6.前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。

X7.中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。

V8.若有一个结点是某二叉树子树的中序遍历序列中最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。

X9.二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。

V10.在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。

X11.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。

V12.在二叉树中插入结点，该二叉树便不在是二叉树。

X13.用一维数组存储二叉树时，总是以前序遍历存储结点。

X14.已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。

V15.不使用递归，也可以实现二叉树的前序，中序，后序遍历。

V16.在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。

V17.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。

X三、填空题1.在树型结构中，树根结点没有（双亲）结点，其余每个结点有且只有（ 1 ）个前驱结点；叶子结点没有（子）结点，其余每个结点的后继结点可以（是结点或叶子）。

2.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为（ 3 ），树的深度为（ 4 ），终端结点的个数为（ 6 ），单分支结点的个数为（ 1 ），双分支结点的个数为（ 1 ），三分支结点的个数为（ 2 ），C的双亲结点为（ A ），其孩子结点为（ F,G ）。

3.设树T 中除叶结点外，任意结点的度数都是3，则T的第I层结点的个数为（ 3^i-1 ）。

4.在具有n(n>=1)个结点的k叉树中，有（ (n-1)*k+1 ）个空指针。

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

6.一棵深度为k的满二叉树的结点总数为（ 2^k -1），一棵深度为k的完全二叉树的结点总数的最小值为（ 2^k-1），从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是（ ），最大值为（ ）。