第5章 树与二叉树习题参考答案.pdfVIP

君子忧道不忧贫。——孔丘

习题五参考答案

备注:红色字体标明的是与书本内容有改动的内容

一、选择题

1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（B）遍历操作相同。

A．先根B.中根C.后根D.层次

2．在哈夫曼树中，任何一个结点它的度都是（C）。

B．0或1B.1或2C.0或2D.0或1或2

3．对一棵深度为h的二叉树，其结点的个数最多为（D）。

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

4．一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（A）

A．所有结点无左孩子B.所有结点无右孩子

C.只有一个根结点D.任意一棵二叉树

5．一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（B）

B．所有结点无左孩子B.所有结点无右孩子

C.只有一个根结点D.任意一棵二叉树

6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结

点的个数是（C）

A．2B.3C.4D.5

7．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根

遍历序列为（B）。

A．FEDCBAB.CDBFEAC.CDBEFAD.DCBEFA

8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根

遍历序列为（B）。

A．ABCDEFB.ABDCEFC.ABCDFED.ABDECF

9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（B）

A．2B.3C.4D.5

10．在有n个结点的二叉树的二叉链表存储结构中有（C）个空的指针域。

A．n-1B.nC.n+1D.0

二、填空题

1.在一棵度为m的树中，若度为1的结点有n个，度为2的结点有n个，……，度为m

12

的结点有n个，则这棵树中的叶结点的个数为1+n+2n+3n+…+(m-1)n。

m234m

2.一棵具有n个结点的二叉树，其深度最多为n，最少为[log2n]+1。

3.一棵具有100个结点的完全二叉树，其叶结点的个数为50。

4.以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是217。

5.有m个叶结点的哈夫曼树中，结点的总数是2m-1