ch6习题及标准答案

习题６解答

判断题：

1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制,因此二叉树是树的特殊情形。( ╳ )

2.二叉树就是结点度为2的树。( ╳ )((哈工大２000年研究生试题)

3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。（╳）(陕西省１9９8年自考试题)

4.当k≥1时,高度为k的二叉树至多有21 k个结点。( ╳)

５.完全二叉树的某结点若无左孩子，则它必是叶结点。(√）(中科院软件所1９97年研究生试题）

6.用一维数组存放二叉树时,总是以前序遍历顺序存储结点。( ╳ )

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

8．存在这样的二叉树，对它采用任何次序的遍历,结果相同。(√)

(哈工大２00０年研究生试题)

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

１０.将一棵树转换成二叉树后，根结点没有左子树,（╳ )

(北邮１999年研究生试题。）

１１．由树转换成二叉树，其根结点的右子树总是空的。(√)

12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。( ╳）

13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。（╳ )

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

15.霍夫曼树一定是满二叉树。（╳ )

１6．树的度是树内各结点的度之和。( ╳ )

17．由二叉树的结点构成的集合可以是空集合。(√)

1８.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( ╳ )

选择题：

19.树最适合用来表示( C ）。

A．有序数据元素 B. 无序数据元素

C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

２0.如果结点A有３个兄弟，而且B是A的双亲，则B的度是（ D )。

A. 4 B．５ C． 1 Ｄ. 3

2１.下列有关二叉树的说法正确的是( Ｂ )。

(南京理工大学２000年研究生试题。)

A.二叉树的度为2 Ｂ. 一棵二叉树度可以小于2

C．二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为2

2２.以下说法错误的是（ B )。

Ａ．二叉树可以是空集 B．二叉树的任一结点都可以有两棵子树

C．二叉树与树具有相同的树形结构Ｄ. 二叉树中任一结点的两棵子树有次序

之分

23.假定在一棵二叉树中,双分支结点数为15，单分支结点数为３0个,则叶子结点数为（ B ）个。

A．１5 B．１6 C. 1７ D．47

24. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组Ｒ［1．．n]中,结点R[i]若有左子女,则左子女是结点( B )。

A.R[2i+1] Ｂ. R[2i］ C. R[i／2] D. R[２ｉ-１]

（参见严蔚敏《（c语言版)数据结构》P．１24 ~ １25,二叉树的性质，性质5) 25.设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是（Ｂ )。

Ａ．a在ｂ的右方Ｂ． a在b的左方Ｃ. a是b的祖先 D. a 是b的子孙

26.以下说法正确的是（ C ）。

A．若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。

B．若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。

C．在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。(提示：后继结点应为遍历右子树时访问的第一个结点,该后继结点或为叶子结点，则其无子女；或为仅有右子树，则其也是最多只能有一个子女;若有两个子女，则它本身已不是后继。)

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

27.以下说法错误的是( B )。

A．存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。

B. 二叉树是树的特殊情形。

Ｃ．由树转换成二叉树,其根结点的右子树总是空的。

D．在二叉树只有一棵子树的情况与也要明确指出该子树是左子树还是右子树。２8.将下图的二叉树按中序线索化，结点X的右指针和Y的左指针分别指向( Ｃ）。

,Ａ D. C,A

Ａ．A，D

29.在Ｎ个结点的线索二叉树中,线索的数目为( C ）。

A．N-１ B. N C. N+１Ｄ. 2N

（参见严蔚敏《(ｃ语言版）数据结构》Ｐ．12６ & P.１32)

３0.设有1３个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有( Ｄ )个结点。(全国2００１年自考题)