练习题6

1. 单项选择题

（1）树最适合用来表示（ ）。 A.有序数据元素 B.无序数据元素 C.元素之间具有层次关系的数据 D.元素之间无联系的数据 答：C

（2）树是结点的有限集合，它（ ① ）根结点，记为T。其余的结点分成为m（m≥0）个（ ② ）的集合T1、T2、…、Tm，每个集合又都是树，此时结点T称为Ti的双亲结点，Ti称为T的子树（1≤i≤m）。一个结点的子树个数为该结点的（ ③ ）。

①：A.有0个或1个 B.有0个或多个 C.有且只有1个 D.有1个或1个以上 ②：A.互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 ③：A.权 B.维数 C.次数（或度） D.序 答：①A ②A ③C （3）二叉树（ ① ）。在完全的二叉树中，若一个结点没有（ ② ），则它必定是叶子结点。每棵树都能唯一地转换成与它对应的二叉树，由一棵树转换成的二叉树中，一个结点N的左孩子是N在原树里对应结点的（ ③ ），而N的右孩子是它在原树里对应结点的（ ④ ）。

①： A.是特殊的树 B.不是树的特殊形式 C.是两棵树的总称 D.有是只有二个根结点的树形结构 ②： A.左子结点 B.右子结点 C.左子结点或者没有右子结点 D.兄弟 ③～④：A.左孩子结点 B.最右子结点 C.最邻近的右兄弟 D.最邻近的左兄弟 E.最左的兄弟 F.最右的兄弟 答：①B ②A ③A ④C

（4）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A.唯一的 B.有多种 C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子 答：A

（5）假定一棵度为3的树中结点数为50，则其最小高度为（ ）。 A. 3 B. 4 C. 5 D. 6 答：C

（6）若一棵度为7的树有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有（ ）个叶子结点。

A. 35 B. 28 C. 77 D. 78 答：D

（7）下列叙述中，正确的是（ ）。

数据结构简明教程

A.二叉树就是度为2的树 B.二叉树中不存在度大于2的结点 C.二叉树是有序树 D. 二叉树中每个结点的度均为2 答：B

（8）深度为5的二叉树至多有（ ）个结点。 A. 16 B. 32 C.31 D.10 答：C

（9）对一个满二叉树，有m个叶子结点，n个结点，深度为h，则（ ）。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 答：D

（10）完全二叉树中，编号为i的结点的层次是（ ）。 A. i B. ?log2i? C. ?log2(i+1)? D. C. ?log2i?+1 答：D

（11）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A. 250 B. 501 C. 254 D. 505 答：B

（12）一棵有124个叶结点的完全二叉树，最多有（ ）个结点。 A. 247 B. 248 C. 249 D. 250 答：B

（13）若唯一确定一棵二叉树，只需要知道该二叉树的（ ）。 A. 先序序列 B. 中序序列 C. 中序和后序序列 D. 先序和后序序列 答：C （14）一棵二叉树的先序遍历序列和其后序遍历序列正好相反，则该二叉树一定是（ ）。 A.空树或只有一个结点 B.哈夫曼树 C.完全二叉树 D.高度等于其结点数 答：D

（15）一棵二叉树的后序遍历序列为D、A、B、E、C，中序遍历序列为D、E、B、A、C，则先序遍历序列为（ ）。

A.A、C、B、E、D B.D、E、C、B、A C.D、E、A、B、C D.C、E、D、B、A 答：D

（16）在线索化二叉树中，p所指结点没有左子树的充要条件是（ ）。 A.p->lchild == NULL B.p->ltag==1 C.p->ltag==1且p->lchild==NULL D.以上都不对 答：B

（17）根据使用频率为5个字符设计的哈夫曼编码不可能是（ ）。 A. 111,110,10,01,00 B. 000,001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10 答：C

2. 填空题

（1）由3个结点所构成的二叉树有（ ）种形态。 答：5

（2）一棵深度为6的满二叉树有（ ① ）个分支结点和（ ② ）个叶子结点。 答：①31 ②32

（3）设一棵完全二叉树有700个结点，则共有（ ）个叶子结点。 答：350

（4）设一棵完全二叉树具有1000个结点，则此完全二叉树有（ ① ）个叶子结点，有（ ② ）个度为2的结点，有（ ③ ）个单分支结点。

答：①500 ②499 ③1

（5）一棵二叉树的第i（i≥1）层最多有（ ）个结点。 答：2i-1

（6）深度为h的完全二叉树至少有（ ① ）个结点，至多有（ ② ）个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（ ③ ）。

答：① 2h-1 ② 2h-1 ③ 2h-1。

（7）对含有n个结点的二叉树进行中序递归遍历，该算法平均空间复杂度为（ ）。 答：O(n)

（8）用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是（ ）。 答：33

3. 简答题

（1）一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的，即在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。另外，一棵度为2的树至少有3个结点，而一棵二叉树的结点个数可以为0。

（2）试求含有n0个叶子结点的完全二叉树的总结点数。

答：由二叉树的性质可知，n2=n0-1，在完全二叉树中，度为1的结点数n1至多为1，所以具有n0个叶子结点的完全二叉树结点数是n0+(n0-1)+1=2n0或2n0-1。

（3）某二叉树的结点数据采用顺序存储结构如下：

1 E 2 A 3 F 4 # 5 D 6 # 7 H 8 # 9 # 10 C 11 # 12 # 13 # 14 G 15 I 16 # 17 # 18 # 19 # 20 B ① 画出该二叉树；

② 写出结点值为D的双亲结点及左、右子树。 ③ 将此二叉树还原为森林。

答：① 该二叉树如图8.21所示。

数据结构简明教程

A D C B G E F H I E A C D F G H I

B

图8.21 一棵二叉树 图8.2 二叉树还原成的森林

② 结点值为D的结点的双亲结点为结点值为A的结点，其左子树为以C为根结点的子树，其右子树为空。

③ 由此二叉树还原成的森林如图8.2所示。

（4）证明完全二叉树的每棵子树也都是完全二叉树。

证明：让T是一棵完全二叉树，S是它的一棵子树。由子树定义可知，S是由T中某个结点及其所有子孙构成的。由于T是完全二叉树，T的所有叶子结点都在两个相邻的层次上，因此，S的所有叶子结点都在两个相邻的层次上。类似的，如果在S中存在不位于底层上结点层，那么，该层也不位于T的底层上，它必须在T中所有底层叶子结点的右边，因此它也必须在S中所有底层叶子结点的右边。从而得到S是完全二叉树。

（5）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。

先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A

答：由这些显示部分推出二叉树如图8.3所示。则先序序列为ABDFKICEHJG；中序序列为DBKFIAHEJCG；后序序列为DKIFBHJEGCA。

B D K F I A C G E H J 图8.3 一棵二叉树

（6）如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0=n2+1，即n2=n0-1，则总结点数n=n0+n2=2n0-1。

4. 算法设计题

（1）已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计一个算法求出离下标分别