全屏显示专题章节

1.若二叉树用二叉链表作存储结构，则在n个结点的二叉树链表中只有n－1个非空指针域。

2.二叉树中每个结点的两棵子树的高度差等于1。

3.二叉树中每个结点的两棵子树是有序的。

4.二叉树中每个结点有两棵非空子树或有两棵空子树。

5.二叉树中所有结点个数是2k－1－1，其中k是树的深度。

6.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i－1个结点。

7.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n＋1个为空指针。

8.具有12个结点的完全二叉树有5个度为2的结点。

9.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

10.二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。

1.由3个结点所构成的二叉树有____________种形态。

2.一棵深度为6的满二叉树有____________个分支结点和____________个叶子。

3.一棵具有257个结点的完全二叉树，它的深度为____________。

4.设一棵完全二叉树有700个结点，则共有____________个叶子结点。

5.设一棵完全二叉树具有1 000个结点，则此完全二叉树有____________个叶子结点，有____________个度为2的结点，有____________个结点只有非空左子树，有____________个结点只有非空右子树。

6.一棵含有n个结点的k叉树，可能达到的最大深度为______，最小深度为________。

7.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序）、后序法（即按LRN次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是____________。

8.用5个权值｛3，2，4，5，1｝构造的哈夫曼树的带权路径长度是__________。

1.树最适合用来表示（）。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。

A.15　B.16　C.17　D.47

3.假定一棵三叉树的结点数为50，则它的最小高度为（）。

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

4.在一棵二叉树上第5层的结点数最多为（）。

A.8　B.16　C.15　D.32

5.用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R［1..n］中，若结点R［i］有子树，则左子树是结点（）。

A.R［2i＋1］　B.R［2i］　C.R［i／2］　D.R［2i－1］

6.在一棵具有k层的满三叉树中，结点总数为（）。

A.（3k－1）／2　B.3k－1　C.（3k－1）／3　D.3k

7.由4个叶子结点，权值分别为9、2、5、7的数据集造一棵哈夫曼树，该树的带权路径长度为（）。

8.具有n（n＞0）个结点的完全二叉树的深度为（）。

A.log2（n）　B.log2（n）　C.log2（n）＋1　D.log2（n）＋1

9.由n个数据元素构造的哈夫曼树，共有（）个结点。

A.n－1　B.2n－1　C.2n　 D.2n＋1

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

A.不发生改变　B.发生改变　C.不能确定　D.以上都不对

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

A.a在b的右方　B.a在b的左方　C.a是b的祖先　D.a是b的子孙

12.如下图所示，其中（）不是完全二叉树。

13.在线索二叉树中，t所指结点没有左子树的充要条件是（）。

A.t－lchild＝＝NULL

C.t－ltag＝＝1 ＆＆t－lchild＝＝NULL

14.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。

A.2h　B.2h－1　C.2h＋1　D.h＋1

15.以下说法中错误的是（）。

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

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

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

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

16.二叉树在线索化后，仍不能有效求解的问题是（）。

A.先序线索二叉树中求先序后继　B.中序线索二叉树中求中序后继

C.中序线索二叉树中求中序前驱　D.后序线索二叉树中求后序后继

17.一棵有124个叶结点的完全二叉树，最多有（）个结点。

A.247　B.248　C.249　D.250

18.如果完全二叉树结点的后序序列是abcdefgh，则结点的前序序列（）。

A.不能唯一确定　B.是hgfedcba

C.是abdchegf　D.是hdbacgef

19.根据使用频率为五个字符设计的哈夫曼编码不可能是（）。

A.111，110，10，01，00　B.000，001，010，011，1

C.100，11，10，1，0　D.001，000，01，11，10

20.用整数1，2，3，4，5作为五个树叶的权值，可构造一棵带树路径长度值为（）的哈夫曼树。

A.33　B.15　C.34　D.54

1.给定二叉树的两种遍历序列，前序遍历序列：DACEBHFGI；中序遍历序列：DCBEHAGIF。试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

2.若根据题图6－1中所示的二叉树建立线索二叉树，请在图中画出其中表示前驱的线索，并写出求结点后继的规律。

3.如题图6－2所示，一棵二叉树的结点数据采用顺序存储结构存储于数组中，请画出该二叉树的链式存储表示。

4.试写出题图6－3所示二叉树的“先序、中序、后序”遍历时得到的结点序列。

5.把题图6－4所示的树转换成二叉树。

6.画出与题图6－5二叉树相应的森林。

（1）本章“性质2、性质3、性质4”的证明。

（2）证明在有n个结点的二叉链表中必定有n＋1个空链域。

（3）试证明在Huffman树中共有2n－1个结点。

（4）任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m－1）个度数为2。

8.若以数据集｛4，5，6，7，10，12，18｝为结点的权值构造Huffman树，试画出该Huffman树，并计算带权路径长度WPL。

五、算法设计题

1.编写按层次顺序（同一层自左至右）遍历二叉树的算法。

2.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。

3.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。