数据结构Ch6习题答案.docVIP

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

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

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

n0=n2+1

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

A．3B．4C．5D．6

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

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

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

n0=n2+1

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

A．2k-1B．2kC．2k+1-1D．2k+1

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

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

A．debacB．acbedC．decbaD．不确定

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

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

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)二叉树。

空或只有一种结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子

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

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

18．判断线索二叉树中某结p有左孩子的条件是(C)。

A．p!=nullB．p-lchild!=nullC．p-ltag=0D．p-ltag=1

19．实现任意二叉树的后序非递归算法而不使用堆栈构造，最佳方案是二叉树采用(C)存储构造。

A．二叉链表B．广义存储构造C．三叉链表D．次序存储构造

20．在一棵二叉树结点的先序遍历序列，中序遍历序列和后序遍历序列中，所有的叶子结点的先后次序(B)。

A