第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、3 B、4 C、5 D、6
6. 在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高
度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。
A、n/2 B、?log2n?+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+1 7. 对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ）
A、n=m+h B、h+m=2n C、m=h-1 D、n=2-1
8. 设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多
为（D ）。
A、2h B、2h-1 C、2
h-1
D、2
h
h
-1
9. 在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1）
A、8 B、16 C、15 D、32 10. 深度为5 的二叉树至多有（ C ）个结点。
A、16 B、32 C、31 D、10 11. 一棵有124 个叶结点的完全二叉树，最多有（B ）个结点
A、247 B、248 C、249 D、250 12. 含有129 个叶子结点的完全二叉树，最少有（ D ）个结点
A、254 B、255 C、256 D、257
13. 假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。
A、15 B、16 C、17 D、47
14. 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组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、B B、D C、A D、I E、F F、C
19. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（D ）。
A、acbed B、decab C、deabc D、cedba
20. 若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ 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、1 B、2 C、3 D、4 E、5 F、6
24. 由带权为8，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ D ）。
A、23 B、37 C、46 D、43 25. 树的后根遍历序列等同于该树对应的二叉树的（ 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、 20
31. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（ C ）。
A、肯定发生变化 B、有时发生变化 C、肯定不发生变化 D、无法确定 32. 下列说法正确的是（ A ）。
A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同 B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同 D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同 33. 下列说法中正确的是（ D ）。
A、任何一棵二叉树中至少有一个结点的度为2 B、任何一棵二叉树中每个结点的度都为2
C、任何一棵二叉树中的每个结点的度肯定等于2 D、任何一棵二叉树中的每个结点的度都可以小于2
34. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大
于右子树上所有结点的值。现采用（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、110100 B、11011100 C、010110111 D、11111100