第六章 树和二叉树
一．选择题
1. 以下说法错误的是          。
A.树形结构的特点是一个结点可以有多个直接前趋
B.线性结构中的一个结点至多只有一个直接后继
C.树形结构可以表达(组织)更复杂的数据
D.树(及一切树形结构)是一种"分支层次"结构
2.  如图6-2所示的 4 棵二叉树中，          不是完全二叉树。

图6-2  4 棵二叉树
3.  在线索化二叉树中，t 所指结点没有左子树的充要条件是          。
A. t->left == NULL                  B. t->ltag==1
C. t->ltag==1 且 t->left==NULL      D .以上都不对
4. 以下说法错误的是          。
A.二叉树可以是空集
B.二叉树的任一结点最多有两棵子树
C.二叉树不是一种树
D.二叉树中任一结点的两棵子树有次序之分
5.  以下说法错误的是          。
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B.在三叉链表上，二叉树的求双亲运算很容易实现
C.在二叉链表上，求根，求左、右孩子等很容易实现
D.在二叉链表上，求双亲运算的时间性能很好
6. 如图6-3所示的 4 棵二叉树，        是平衡二叉树。

图6-3  4 棵二叉树
7. 如图6-4所示二叉树的中序遍历序列是          。
A. abcdgef      B. dfebagc    C. dbaefcg        D. defbagc
图6-4  1 棵二叉树
8.  已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是          。
A. acbed      B. decab    C. deabc    D. cedba
9.  如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序就是 T2 中结点的          。
A.  前序    B.中序      C.  后序    D.  层次序
10.  某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是          。
A. bdgcefha        B. gdbecfha    C. bdgaechf      D. gdbehfca
11.  将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为          。
A.42    B.40        C.21        D.20
12.  一棵二叉树如图6-5所示，其后序遍历的序列为          。
A. abdgcefh      B. dgbaechf      C. gdbehfca        D. abcdefgh
图6-5  1 棵二叉树
13.  深度为 5 的二叉树至多有          个结点。
A. 16      B. 32     C.31      D.10
14.  对一个满二叉树，m 个叶子，n 个结点，深度为h，则          。
A. n=h+m      B. h+m=2n      C. m=h-1        D. n=2h-1
15.  如图6-6所示的二叉树是由有序树（森林）转换而来的，那么该有序树（森林） 有          个叶结点。
A. 4      B. 5      C. 6      D. 7
图6-6  1 棵二叉树
16. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少          个
A.k+1      B.2k    C.2k-1    D.2k+1
17. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用          遍历方式就可以得到这棵二叉树所有结点的递增序列。
A.先根    B.中根    C.后根    D.层次
18. 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有          个结点。 先序中序后序遍历二叉树
A.n1-1    B.n1    C.n1+n2+n3    D.n2+n3+n4
19. 森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T
转换成一棵二叉树后，且根结点的左孩子上有          个结点。
A.n1-1    B.n1    C.n1+n2+n3  D.n2+n3+n4
20. 对含有          个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0    B.1    C.2      D.不存在这样的二叉树
二．填空题
1.  有一棵树如图6-7 所示，回答下面的问题：
图6-7  1 棵二叉树
（1）这棵树的根结点是    ①   ；
（2）这棵树的叶子结点是    ②   ；
（3）结点 k3 的度是    ③   ；
（4）这棵树的度为    ④   ；
（5）这棵树的深度是    ⑤   ；
（6）结点 k3 的孩子是    ⑥    ；
（7）结点 k3 的双亲结点是    ⑦   。
2. 深度为 k 的完全二叉树至少有    ①    个结点，至多有    ②    个结点，若按自上而下，从左到右次序给结点编号（从 1 开始），则编号最小的叶子结点的编号是  ③    。
3.  一棵二叉树的第 i（i≥1）层最多有    ①    个结点；一棵有 n（n>0）个结点的满二叉树共有    ②    个叶子和    ③    个非终端结点。
4.  结点最少的树为    ①    ，结点最少的二叉树为    ②   。
5.  根据二叉树的定义，具有三个结点的二叉树有    ①    种不同的形态，它们分别是②   。
6.  具有n个结点的完全二叉树的深度为          。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。