习题五

一、选择题

1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足    C    。

A、所有的结点均无左孩子                  B、所有的结点均无右孩子

C、只有一个叶子结点                      D、是任意一棵二叉树

2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是  E      。

   A、250       B、500      C、254       D、505      E、以上答案都不对

3、以下说法正确的是    C    。

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

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

C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点

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

4、以下说法错误的是   C     。

   A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近

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

C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树，因为不知道树的根结点是哪一个

D、在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的

5、一棵有124个叶结点的完全二叉树，最多有   A     个结点。

   A、247          B、248          C、249       D、250       E、251

6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序    A    。

   A、不发生变化                B、发生变化             C、不能确定

7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是    B    。

  A、a在b的右方                     B、a在b的左方

C、a是b的祖先                     D、a是b的子孙

8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为    C    。

   A、k+1              B、2k                C、2k-1               D、2k+1

9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有   D     个结点。

   A、13               B、12                C、26                 D、25

10、下面几个符号串编码集合中，不是前缀编码的是   B     。

   A、{0，10，110，1111}               B、{11，10，001，101，0001}

C、{00，010，0110，1000}            D、{b,c,aa,ac,aba,abb,abc}

11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用    A    存储结构。

  A、三叉链表         B、广义表        C、二叉链表       D、顺序表

12、以下说法错误的是    B    。

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

B、二叉树是树的特殊情形

C、由树转换成二叉树，其根结点的右子树总是空的

D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面

    A    是正确的。

A、树的先根遍历序列与其对应的二叉树先序遍历序列相同

B、树的后根遍历序列与其对应的二叉树后序遍历序列相同

C、树的先根遍历序列与其对应的二叉树中序遍历序列相同

D、以上都不对

14、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。则该二叉树是    C    。

   A、二叉排序树                B、哈夫曼树           遍历树                 c  C、堆

15、下列有关二叉树的说法正确的是  B      。

   A、二叉树的度为2                   B、一棵二叉树度可以小于2

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

16、某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是   B     。

   A、EGFACDB                        B、EACBDGF

C、EAGCFBD                        D、上面的都不对

17、对二叉排序树进行    B    遍历，可以得到该二叉树所有结点构成的排序序列。

   A、前序         B、中序       C、后序         D、按层次

18、由二叉树的前序和后序遍历序列    B    唯一地确定这棵二叉树。

   A、能                          B、不能

19、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为     C   个。

   A、4            B、5          C、6            D、7

20、在一棵深度为h的完全二叉树中，所含结点的个数不小于   D     。

  A、2^h           B、2^h+1       C、2^h-1          D、2^h-1

21、在一棵具有n个结点的二叉树第i层上，最多具有    C    个结点。

  A、2ⁱ           B、2ⁱ⁺¹       C、2ⁱ-1          D、2ⁿ

22、在下列情况中，可称为二叉树的是   B    。

  A、每个结点至多有两棵子树的树            B、哈夫曼树

C、每个结点至多有两棵子树的有序树        D、每个结点只有一棵右子树

E、以上答案都不对

 

二、填空题

 1、8层完全二叉树至少有   128     个结点，拥有100个结点的完全二叉树的最大层数为   7     。

 2、树在计算机内的表示方式有  双亲表示法  、  孩子表示法  、 孩子兄弟表示法  。

 3、一棵有n个结点的满二叉树有  0   个度为1的结点，有   ┕n/2┛   个分支（非终端）结点和 ┕n/2┛+1   个叶子，该满二叉树的深度为  ┕log₂n┛+1   。

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

 5、一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为 （n×（k-1）+1）/k 。

 6、深度为k（设根的层数为1）的完全二叉树至少有 2k-1 个结点，至多有  2k-1  个结点。

 7、设只包含根结点的二叉树高度为0，则高度为k的二叉树最大结点数为  2k+1-1 ，最小结点数为 k+1 。

 8、一棵完全二叉树有999个结点，它的深度为 10 。

 9、对于一棵具有n个结点的树，该树中所有结点的度数之和为  n-1 。

 10、有n个结点并且其高度为n的二叉树有 2n-1 个。

 11、一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1=  n-2n0+1 。

 12、若一棵二叉树的叶子数为n0，则该二叉树中左、右子树皆非空的结点个数为 n0-1 。

 13、设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 2n0-1 个结点。

 14、若以{4、5、6、7、8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 69 。

 

三、判断题

 1、完全二叉树的某结点若无左孩子，则它必是叶结点。   （对  ）

 2、存在这样的二叉树，对它采用任何次序的遍历，结果相同。（  对  ）

 3、二叉树就是结点度为2的树。（  错  ）

 4、二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树。（  错  ）

 5、已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（错  ）

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

 7、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（对   ）

 8、将一棵树转换成二叉树后，根结点没有左子树。（错   ）

 9、用树的前序遍历和中序遍历可以导出树的后序遍历。（对   ）

 10、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（  对   ）

 11、不使用递归也能实现二叉树前序、中序和后序遍历。（  对   ）