19．若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________、________三种，按这三种次序进行的遍历分别称为________、________、________。
20．树的主要遍历方法有________、________、________等三种。
21．判定树的每个________包含一个条件，对应于一次比较或判断，每个________对应一种分类结果。
22．设定T是一判定树，其终端结点为n1,……，nk。每个终端结点ni对应的百分为pi（通常将pi称为n1的权）。再假定ni的祖先数为li，这样，按T进行分类的平均比较次数为________。
23．根据文字说明，请在以下横线处填充适当的语句。
采用静态链表作存储结构，设置一个大小为2n-1的数组,令数组每个元素由四个域组成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下： typedef struct
{float wt /*权值*/ int parent,lchild rchild; /*指针域*/ }node;
typedef node hftree[2*n-1];
在这种存储结构上的哈夫曼算法可描述如下：
void Huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/ {int i,j,x,y; float m,n;
for(i=0;i<2*k-1;i++)
{ T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;
21
if(________)T[i].wt=W[i]; else T[i].wt=0 }
for(i=0;i { x=0;y=0;m=maxint;n=maxint; for(j=0;j if((T[j].wt T[k+i].lchild=________;T[k+i].rchild=________; } 24．若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。 25．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 26．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是________，编号最小的分支结点序号是________，编号最大的叶子结点序号是________，编号最小的叶子结点序号是________。 27．二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的________。 28．先根遍历树和先根遍历与该树对应的二叉树，其结果________。 29．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 22 30．由________转换成二叉树时，其根结点的右子树总是空的。 31．哈夫曼树是带权路径度________的树，通常权值较大的结点离根________。 32．有m个叶子结点的哈夫曼树，其结点总数为________。 33．一棵树的形状如图填空题33所示，它的根结点是________，叶子结点是________，结点H的度是________，这棵树的度是________，这棵树的深度是________，结点F的儿子结点是________，结点G的父结点是________。 34．树的结点数目至少为________，二叉树的结点数目至少为________。 35．________中结点的最大度数允许大于2，而________中结点的最大度数不允许大于2。 36．结点最少的树为________，结点最少的二叉树为________。 37．若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为________。 38．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为________个。 39．现有按中序遍历二叉树的结果为ABC，问有________种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是________。 40．以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈无曼树为________，其带权路径长度为________。 41．有m个叶子结点的哈夫曼树上的结点数是________。 42．已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有________个叶子结点。 23 43．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是________。 三、单向选择题 1． 以下说法错误的是 ( ) ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继 ③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种\分支层次\结构 ⑤任何只含一个结点的集合是一棵树 2，以下说法错误的是 ①二叉树可以是空集 ②二叉树的任一结点都有两棵子树 ③二叉树与树具有相同的树形结构 ④二叉树中任一结点的两棵子树有次序之分 3、以下说法错误的是 ①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 ②在三叉链表上，二叉树的求双亲运算很容易实现 ③在二叉链表上，求根，求左、右孩子等很容易实现 ④在二叉链表上，求双亲运算的时间性能很好 4、以下说法错误的是 ①一般在哈夫曼树中，权值越大的叶子离根结点越近 ②哈夫曼树中没有度数为1的分支结点 ③若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点 24 ( ) ( ) ( ) ④若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点 ( ) ①64 ②63 ③32 ④31 6．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为( ) ①42 ②40 ③21 ④20 7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( ) ①肯定发生变化 ②有时发生变化 ③肯定不发生变化 ④无法确定 8．设二叉树有n个结点，则其深度为 ( ) ①n-1 ②n ③5floor(log2n) ④无法确定 9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ ）个 ①k+1 ②2k ③2k-1 ④2k+1 10.( ) ①树的先根遍历序列与其对应的二叉树的先根遍历序列相同 ②树的先根遍历序列与其对应的二叉树的后根遍历序列相同 ③树的后根遍历序列与其对应的二叉树的先根遍历序列相同 ④树的后根遍历序列与其对应的二叉树的后根遍历序列相同 11．下列说法中正确的是 ( ) ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2 25 41的双结点编号为 下列说法正确的是