选择题

1.把一棵树转换为二叉树后，这棵二叉树的形态是（   ）。              

A．唯一的                          Ｂ．有多种

C．有多种，但根结点都没有左孩子    Ｄ．有多种，但根结点都没有右孩子

答案：A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

2.由3个结点可以构造出多少种不同的二叉树？（    ）

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

答案：D  公式

3.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（  ）。

A．250         B． 500          C．254        D．501   

答案：D 解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

4.一个具有1025个结点的二叉树的高h为（  ）。

A．11          B．10             C．11至1025之间       D．10至1024之间

答案：C 解释：若每层仅有一个结点，则树高h为1025；且其最小树高为 ，即h在11至1025之间。（扩展具有n个（n>0）结点的完全二叉树的高度h为⌈log2(n+1)⌉或⌊log2n⌋+1）

5.深度为h的满m叉树的第k层有（  ）个结点。(1=<k=<h)

A．mk-1          B．mk-1            C．mh-1        D．mh-1

答案：A 解释：深度为h的满m叉树共有mh-1个结点，第k层有mk-1个结点。

6.利用二叉链表存储树，则根结点的右指针是（  ）。

A．指向最左孩子        B．指向最右孩子         C．空        D．非空

答案：C 解释：利用二叉链表存储树时（即孩子兄弟表示法），右指针指向兄弟结点（nextsibling），因为根节点没有兄弟结点（书本129页图有），故根节点的右指针指向空。

7.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（  ）遍历实现编号。

A．先序         B. 中序           C. 后序       D. 从根开始按层次遍历

答案：C 解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。

8.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（  ）遍历方法最合适。

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

答案：C 解释：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。

9.在下列存储形式中，（  ）不是树的存储形式？

A．双亲表示法   B．孩子链表表示法   C．孩子兄弟表示法   D．顺序存储表示法

答案：D 解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。

10.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（  ）。

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

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

答案：C 对应30题可去看看就懂了（高度和结点数相同即可）解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，属于半对，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。

11.设哈夫曼树中有199个结点，则该哈夫曼树中有（    ）个叶子结点。

A．99 B．100

C．101 D．102

答案：B 解释：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n= n0+n2=2*n0-1，得到n0=100。

12.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（  ）。

A．X的双亲                      B．X的右子树中最左的结点 

C．X的左子树中最右结点          D．X的左子树中最右叶结点

答案：C（同34题）

13.引入二叉线索树的目的是（  ）。

A．加快查找结点的前驱或后继的速度    B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲              D．使二叉树的遍历结果唯一

答案：A

14.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（   ）个。

A．n−1 B．n C．n + 1 D．n + 2

答案：C

15.n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。

A．该树一定是一棵完全二叉树

B．树中一定没有度为1的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

答案：A 解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。哈夫曼树不一定是完全二叉树，也不一定是平衡二叉树。

16.一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是______。

A. nh

B. n+h

C. n-1

D. h-1

答案 n-1 举例子就可以得到

17.若一棵3次树中有2个度为3的结点，1个度为2的结点，2个度为1的结点，该树一共有______ 个结点。

A. 5

B. 8

C. 10

D. 11

答案 D11 分支数+1

18.一棵度为5、结点个数为n的树采用孩子链存储结构时，其中空指针的个数是______。

A. 5n

B. 4n+1

C. 4n

D. 4n-1

答案 B 4n+1  5n-(n-1)=4n+1

19.若一棵有n个结点的二叉树，其中所有分支结点的度均为k，该树中的叶子结点个数是______。

A. n(k-1)/k

B. n-k

C. (n+1)/k

D. (nk-n+1)/k

答案 D. (nk-n+1)/k (举例子 比如7个结点且度为2，那就是只有3个度为2的结点，4个叶子节点，可以得到选项 C D，在举例子3个度为1的结点，那就是一个叶子节点，2个度为1的结点，排除C )

20.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为______。

A. 9

B. 11

C. 15

D. 不确定

答案 B11，叶子结点数=度为2的结点数+1

21.一棵二叉树中有7个叶子结点和5个单分支结点，其总共有______ 个结点。

A. 16

B. 18

C. 12

D. 31

答案 B18 解释 因为结点数=N0+N1+N2,N0+N2+1,所以结点数等于7+5+6=18

22.一棵二叉树中有35个结点，其中所有结点的度之和是______。

A. 35

B. 16

C. 33

D. 34

答案 D34 解释 因为结点数=N0+N1+N2,N0+N2+1，所以结点数35=N1+2N2+1，可以得出N1=0，N2=17，N0=18，综上所有结点的度之和是度为2的结点数17个，为34

23.一棵完全二叉树中有501个叶子结点，则至少有______ 个结点。

A. 501

B. 502

C. 1001

D. 1002

答案C1001 解释 有501个叶子结点，那么一定有500个度为2的结点，要是至少 那么度为1的结点为0，那就是501+500=1001

24.一棵完全二叉树中有501个叶子结点，则至多有______ 个结点。

A. 501

B. 502

C. 1001

D. 1002

答案D 1002 解释 有501个叶子结点，那么一定有500个度为2的结点，要是至多 那么度为1的结点为1，那就是501+500+1=1002

25.一棵高度为8的完全二叉树至少有______ 叶子结点。

A. 63

B. 64

C. 127

D. 128

答案 B 64 解释 高度为8 此题求叶子结点 ，第七层结点满加第8层的一个叶子结点，那就是相当于求第七层的结点数，即2的6次方64，

 

26.一棵高度为8的完全二叉树至多有______ 叶子结点。

A. 63

B. 64

C. 127

D. 128

答案 D128 （如上图）

27.一棵满二叉树共有64个叶子结点，则其结点个数为______。

A. 64

B. 65

C. 127

D. 128

答案 C127 （没有度为1的结点，度为2的结点63个）

设森林F中有三棵树，第一，第二和第三棵树的结点个数分别为M1，M2和M3，与森林F对应的二叉树根结点的左子树上的结点个数是（），右子树上的结点个数是（）。 

​ 答案：M1 - 1，M2 + M3

森林转换成二叉树
如图所示：

28.设森林F中有3棵树，第一、第二和第三棵树的结点个数分别为9、8和7，则与森林F对应的二叉树根结点的右子树上的结点个数是______。

A. 16

B. 15

C. 7

D. 17

答案 B15（8+7=15）

29.如果一棵二叉树B是由一棵树T转换而来的二叉树，那么T中结点的先根序列对应B的______ 序列。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

答案 A. 先序遍历

30.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是______。

A.空或只有一个结点

B.高度等于其结点数

C.任一结点无左孩子

D.任一结点无右孩子

答案 B 解析：
A.如果是空，或者是只有一个结点那么先序遍历和后序遍历得到的序列是一样的。
C.在任何一个结点没有左孩子的时候

先序遍历为：123
后序遍历为：321
D.与C同理（半对）
B.满足每一层只有一个结点，即树高等于结点的数目时题目条件成立

扩展 还有一种是前序遍历和中序遍历相反 答案是任一结点无右孩子(前序 根左右，中序 左根右  )会发现没有右子树 刚刚好相反

一个有两个以上结点的二义树的前序遍历序列与中序遍历序列正好相反，则该二义树

A.任一结点没有左千树    B.任一结点没有右子树

C.任一结点不能同时有左子树和右子树   D.不存在

答案 B

31.一棵二叉树的先序序列为ABCDEFG，它的中序序列可能是______。

A. CABDEFG

B. ABCDEFG

C. DACEFBG

D. ADCFEGB

答案 B. ABCDEFG

第一种情况，当原来的二叉树左子树全为空的时候，即如下图所示：

 第二种情况 

 附加题二叉树的先序序列和中序序列相同的条件是（ ）。

只有右子树

32.一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为______。

A. CBEFDA

B. FEDCBA

C. CBEDFA

D. 不确定 

答案 A 

33.由含n个结点的二叉树线索化后有______ 个线索（不计头结点）。

A. 2n

B. n+1

C. n-1

D. 2n-1

答案B. n+1

34.若x是中序线索二叉树中一个有左孩子的结点，且不是根结点，则x的前驱结点为______。

A. x的双亲结点

B. x的右子树中最左下结点

C. x的左子树中最右下结点

D. x的左子树中最右下结点

答案 C. x的左子树中最右下结点

35.一棵哈夫曼树中共有199个结点，它用于多少个字符的编码______。

A. 99

B. 100

C. 101

D. 199

答案 B. 100 解释 根据哈夫曼树的性质  哈夫曼树中没有度为1的结点。

199= n0 + n1 + n2  
n2 = n0 - 1
n1 = 0
199 = n0 + n0 -1  
可知 n0 =100（因为哈夫曼树编码就是对叶子结点编码）

36.根据使用频率为5个字符设计的哈夫曼编码不可能是______。

A. 000，001，010，011，1

B. 0000，0001，001，01，1

C. 000，001，01，10，11

D. 00，100，101，110，111

答案 D. 00，100，101，110，111 解释 哈夫曼树的节点要么是叶子结点，要么是度为2的节点，不可能出现度为1的节点。

​

37. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）

答案 不会改变，所有的叶节点都是从左到右的。可以画图举例子

38.设给定权值总数有n 个，其哈夫曼树的结点总数为( )。

答案 哈夫曼树没有度为1的结点.且权值所在结点都是叶子. 二叉树中度为2的结点数比叶结点少1 即由权值总数为n，知道叶子结点数为n，又度为2的结点为n-1个，故共有n+n-1=2n-1个

39.具有n个叶子的哈夫曼树中，总的结点数是__， 度为1的结点数是__。

2n-1  0 （因为哈夫曼树没有度为1的结点，结点数为度为2的结点数加上度为0的结点数，而度为0的结点数个数=度为2结点数的+1） 

40.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（)

----C 
---/ 
--E 
-/-\ 
D---B 
-----\ 
------A

后序遍历就是：左右根，中序遍历就是：左根右。1.后序遍历得C为根节点。2.中序得C无右子树，后序得C下一个根节点为E。3，中序DEBA得D为E的左子树，后序DAB得B为E的下一个根节点，只能为E的右子树了，中序BA得A为B的右之树。

其实根据后序和中序先确定了根结点为c，在根据后序来看左右根，所以e为根，在中序中e左边为d左子树，e右边ba就是e的右子树。。。。

判断题

1.二叉树是一种特殊的树。
错

2.将一棵树转成二叉树，根结点没有左子树。
错（没有右子树）

3.哈夫曼树的结点个数不能是偶数。
对（没有度为1的结点，结点数为2N0-1）n0为叶子结点，或者为2n2+1（n2为度为2的结点）

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

5.给定一棵树，可以找到唯一的一棵二叉树与之对应。
对

6.在二叉树的二叉链表结构中，指针p所指结点为叶子结点的条件是（ ）。
p->lchild== NULL && p->rchlid ==NULL

7.一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是       ；编号是i的结点所在的层次号是        （根所在的层次号规定为1层）。

编号最小的叶子结点序号是：2(k-2)次方+1 （可画图看出），结点i所在的层次号为 [log2i]+1

8.在哈夫曼编码中，当两个不同字符出现的频率相同时，其编码也相同

错误 （哈夫曼树中 两个频率相同的字符不会有相同的哈夫曼编码，除非它们是相同的字符。哈夫曼树中不可能出现相同的编码！）

9.完全二叉树中，若一个结点没有左孩子，则它必是树叶

对

 图1为完美二叉树（满叉树），图2为完全二叉树，两树相同序号的结点在树的位置上相同，而图三6号位置与图一位置不同，则它不是完全二叉树。
所以完全二叉树如果没有左结点，则一定没有右结点，即没有左孩子，它就一定是树叶。

10.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点正确吗？

错误  （在矩阵的三元组中，元素的排列是有规则的，规则为先行后列。所以在将数组的 行下标与列下标的值互换,并把m和n的值互换后，还需要重排三元组间的次序，这样才能实现矩阵的转置。）

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。  对 （想想哈夫曼树的构造，不就是先让两个小的结合，再依次结合，不就最后权值大离根近）