习题六 树和二叉树
一、单项选择题
1． 以下说法错误的是 （ ）
A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种“分支层次“结构 E. 任何只含一个结点的集合是一棵树 2．下列说法中正确的是 （
A. B. C. D. 3.
A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义 4 .树最适合用来表示 （
A.
C.元素之间具有分支层次关系的数据
）
有序数据元素
D
B .无序数据元素 .元素之间无联系的数据
）
任何一棵二叉树中至少有一个结点的度为 2 任何一棵二叉树中每个结点的度都为 2 任何一棵二叉树中的度肯定等于 2 任何一棵二叉树中的度可以小于 2
讨论树、森林和二叉树的关系，目的是为了（ ）
5.若一棵二叉树具有 10个度为 2的结点， 5个度为 1 的结点，则度为 0 的结点个数是（ ）
A. 9
B . 11 C . 15 D .不确定
M1, M2和M3与森林F对应的二叉树根结点
6 ?设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为 的右子树上的结点个数是（ )。
A. M1 B .
7. 一棵完全二叉树上有
A. 250 B . 500
8.
M1+M2 C
. M3
. M2+M3
）
1001 个结点， 其中叶子结点的个数是（ C . 254
D . 505 E
.以上答案都不对
)
设给定权值总数有 n 个，其哈夫曼树的结点总数为 A.不确定 B
. 2n C . 2n+1
)
2 I-1
. 2n-1
9. 二叉树的第 I 层上最多含有结点数为（
A. 2I 10.
所有结点的度或为
I I-1
B . 2 I-1 -1
则这棵二叉树最少有 （ ） 0，或为 2， 一棵二叉树高度为 h,
D . h+1
）。 C .空 D .非空
C
D . 2I -1
结点
A. 2h B . 2h-1 C . 2h+1
11. 利用二叉链表存储树，则根结点的右指针是
12.已知一棵二叉树的前序遍历结果为 ABCDE F中序遍历结果为 CBAEDF则后序遍历的结果为（
A. CBEFDA
B . FEDCBA
C . CBEDFA D .不定
已知某二叉树的后序遍历序列是 ）
dabec, 中序遍历序
13.
列是 debac , 它的前序遍历是（
A. acbed B . decab C . deabc D . cedba 14.
列，中序序列和后序序列中，所有叶子结点的先后顺序（
A.都不相同
B
?完全相同
在二叉树结点的先序序）
C.先序和中序相同，而与后序不同 15.
D ?中序和后序相同，而与先序不同
在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A.左子结点
C.左子结点和右子结点
B
D
.右子结点
点，右子结点和兄弟结点 )
16．在下列情况中，可称为二叉树的是(
A. 每个结点至多有两棵子树的树 B. 哈夫曼树
C. 每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E. 以上答案都不对
17. 一棵左右子树均不空的二叉树在先序线索化后
A. 0 B. 1 C. 2 D.
18. 引入二叉线索树的目的是(
)
B
A.加快查找结点的前驱或后继的速度 C.为了能方便的找到双亲 A. 2n B . n－ l A. 2 B . 3 C . 4 D
D
C . n＋ l
其中空的链域的个数是：
不确定
( )
.为了能在二叉树中方便的进行插入与删除 .使二叉树的遍历结果唯一
)
19. n 个结点的线索二叉树上含有的线索数为(
D
.5
20. 由 3 个结点可以构造出多少种不同的二叉树？(
.n
)
21. 下面几个符号串编码集合中，不是前缀编码的是 ( )。
A. {0,10,110,1111} B C. {00,010,0110,1000} D
{11,10,001,101,0001} . {b,c,aa,ac,aba,abb,abc}
A[1..n] 中，则二叉树中
)
A中的位置是(
22. 一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 第i个结点(i从1开始用上述方法编号)的右孩子在数组
A. A[2i](2i<=n) C. A[i-2]
23、以下说法错误的是
B.
中的第一个结点， 点。
D (
) B
. A[2i+1](2i+1<=n) .条件不充分，无法确定
A. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
若一个二叉树的树叶是某子树的中序遍历序列则它必是该子树的后序遍历序列中的第一 个结
C. 已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。 D. 在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。 二、判断题(在各题后填写“/或“ X”) I. 完全二叉树一定存在度为 1 的结点。 ( ) 2 ?对于有N个结点的二叉树，其高度为
log 2 n。()
( )
( )
( )
中序遍历一棵二叉排序树的结点就可得到排好序的( )
完全二叉树中，若一个结点没有左孩子，则它必是树叶。( )
)
( )
3. 二叉树的遍历只是为了在应用中找到一种线性次序。 5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。 6.
结点序列。 7.
8. 二叉树只能用二叉链表表示。 (
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。 II. 12. 13. 15.
14. 二叉树中序线索化后，不存在空指针域。 ( )
霍夫曼树的结点个数不能是偶数。 ( )
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。
10. 用链表 (llink-rlink) 存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n-1 个空指针。 ( )
树形结构中元素之间存在一个对多个的关系。 ( ) 将一棵树转成二叉树，根结点没有左子树。 ( )
度为二的树就是二叉树。 ( )
数据结构第六章树和二叉树习题及答案
