数据结构Ch6习题答案.pdf

Ch6树

一、选择题：

1．下列关于哈夫曼树的叙述，错误的是(C)。

A．哈夫曼树根结点的权值等于所有叶结点权值之和。

B．具有n个叶结点的哈夫曼树共有2n-1个结点。

C．哈夫曼树是一棵二叉树，因此它的结点的度可以为0，1，2。

D．哈夫曼树是带权路径长度最短的二叉树。

2．由3个结点可以构成多少棵不同形态的二叉树(C)。A．

3B．4C．5D．6

3．如果一棵二叉树结点的前序序列是A，B，C，后序序列是C，B，A，则该二叉树结点的中序序列是(D)。A．

A，B，CB．A，C，BC．B，C，AD．不能确定

4．如图所示的4棵二叉树中，B()不是彻底二叉树。

A．B．C．D．

5．二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法(B)

A．正确B．错误

若结点有左子树，则令其lchild指针指示其左孩子；若结点没有左子树，则令其lchild指针指示其前驱；若

结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。

6．二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法(A)。

A．正确B．错误

7．对一棵70个结点的彻底二叉树，它有(A)个叶子结点。A

．35B．40C．30D．44

1

8．设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为(D)。A．

10B．11C．12D．不确定

n=n+1

02

9．假定根结点的层次为0，含有15个结点的二叉树最小高度为(A)。A．

3B．4C．5D．6

假定根结点的层次为1，含有15个结点的二叉树最小高度为4

10．若一棵二叉树中，度为2的结点数为9，该二叉树的叶子结点的数目为(A)。A．

10B．11C．12D．不确定

n=n+1

02

11．设根结点的层次为0，则高度为k的二叉树的最大结点数为(C)。A．

2-1B．2C．2-1D．2

kkk+1k+1

若设根结点的层次为1，则这棵树的高度为k+1，高度为k+1的二叉树的最大结点数为2-1

k+1

12．以知某二叉树的后序遍历序列为abdec，先序遍历序列为cedba，它的中序遍历序列为(D)。A

．debacB．acbedC．decbaD．不确定

13．设高度为h的二叉树上惟独度为0和度为2的结点,则此二叉树所包含的结点数至少为(B)。A．

2hB．2h-1C．2h+1D．h+1

2

14．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是(C)。

A．n在m右方B．n是m祖先C．n在m左方D．n是m子孙

15．将一棵有100个结点的彻底二叉树从上到下,从左到右挨次对结点进行编号,根结点的编号为49的结点的左孩子编号

为(A)。

A．98B．99C．50D．48

16．某二叉树的前序和后序序列正好相反,则该二叉树一定是(B)二叉树。

A．空或者惟独一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子

17．对于一棵满二叉树，m个树叶，n个结点，深度为h，则(C)。

A．h+m=2nB．m=h-1C．n=2-1D．n=h+m

h

18．判断线索二叉树中某结p有