A、二叉树的度为2 B、一棵二叉树度可以小于2
C、二叉树中至少有一个结点的度为2 D、 二叉树中任一个结点的度都为2 4、某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是_____。 A、EGFACDB B、EACBDGF C、EAGCFBD D、上面的都不对
5、设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是_____。
A、m-n B、m-n-1 C、n+1 D、条件不充分，无法确定。 6、对二叉排序树进行_____遍历，可以得到该二叉树所有结点构成的排序序列。 A、前序 B、中序 C、后序 D、按层次 7、_____的遍历仍需要栈的支持
A、前序线索树 B、中序线索树 C、后序线索树 8、在一棵深度为h的完全二叉树中，所含结点的个数不小于_____。 2h 2h+1 2h-1 2h-1
9、在一棵具有n个结点的二叉树第I层上，最多具有_____个结点。 2I 2I+1 2I-1 2n
10、在下列情况中，可称为二叉树的是_____。
A、每个结点至多有两棵子树的树 B、哈夫曼树
C、每个结点至多有两棵子树的有序树 D、每个结点只有一棵右子树 11、树最适合用来表示_____
A、有序数据元素 B、无序数据元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 12、以下说法错误的是_____。
A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点
C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1个结点
D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终的哈夫曼树 13、以下说法错误的是_____。
A、二叉树可以是空集 B、二叉树的任一结点都可以有两棵子树
C、二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 14、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是_____的二叉树。 A、空或只有一个结点 B、任一结点无左子树 C、高度等于其结点数 D、任一结点无右子树 二、填空题
1、如果结点A有3兄弟，而且B是A的双亲，则B的度是_____。 2、高度为h的二叉树中叶子结点的数目至多为_____。
3、具有n个结点的二叉树，采用二叉链表存储，共有_____个空链域。 4、利用树的孩子兄弟表示法存储，可以将一棵树转换成_____。 5、二叉树的线索化实质是将二叉链表中的_____改为_____。
6、在一棵树中，_____结点没有前驱结点，其余每个结点有且只有一个_____，可以有任意多个_____结点。
7、二叉树有不同的链式存储结构，其中最常用的是_____与_____。 8、对于一棵完全二叉树，设一个结点的编号为I,若它的左孩子结点存在，则其编号为_____；若右孩子结点存在，则其编号为_____；而双亲结点的编号为_____。
30
9、对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为_____个，其中_____个用于指向孩子结点，_____个指针空闲着。
10、一棵左右子树均不空的二叉树在先序线索化后，其空指针域有_____个。
11、用一维数组存放一棵完全二叉树：ABCDEFGHIJKL,则后序遍历该二叉树的结点序列为_____。
12、深度为k的完全二叉树，其前k-1层共有_____个结点。
13、对任何二叉树，若度为2的结点数为n2，则叶子数n0=_____。
14、具有n个结点的完全二叉树若按层次从上到下，从左到右对其编号（根结点为1），则编号最大的分支结点序号是_____，编号最小的分支结点序号是_____，编号最大的叶子结点序号是_____，编号最小的叶子结点序号是_____。 15、结点最少的树为_____，结点最少的二叉树为_____。
16、若二叉树的一个叶子结点是某子树中根遍历序列中的第一个结点，则它必然是该子树后根遍历序列中的_____个结点。
17、二叉树通常有_____存储结构和_____存储结构。
18、哈夫曼树是带权路径长度_____的树，通常权值较大的结点离根_____。 参考答案：
一、 选择题
1、D 2、C 3、B 4、B 5、A 6、B 7、C 8、D 9、C 10、B 11、C 12、D 13、C 14、D
二、 填空题
1、4 2、2h-1 3、n+1 4、一棵二叉树 5、空指针域 存放该结点的前驱或后继信息 6、树根 双亲（或前驱） 孩子（或后继） 7、二叉链表 三叉链表 8、2i 2i+1 [i/2] 9、2n n-1 n+1 10、0 11、HIDJKEBLFGCA 12、2k-1-1 13、n2+1 14、[n/2] 1 n [n/2]+1 15、只有根结点的树 空二叉树 16、第一 17、顺序 链式 18、最短 较近
三、算法设计：
1、设某通讯电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是16、5、9、3、30、1。试画出编码用的哈夫曼树
2、给定一棵用链表表示的二叉树，其根结点为root，试写出二叉树结点数目的算法。 int count(TREENODEPTR root) {int top ,num;
TREENODEPTR stack[max]; Num=0; If(root!=NULL) {top=1; stack[top]=root; while(top>0) { top--; num++;
if(root->rchild!=NULL) { top++;
stack[top]=root->rchild; }
31
if(root->lchild!=NULL) { top++;
stack[top]=root->lchild; }}}
return (num);
}
3、给定一棵用链表表示的二叉树，其根结点为root，试写出求二叉树各结点的层数的算法。 #define max 100
void layer(TREENODEPTR root) {
TREENODE que[max]; int hp,tp,lc,level;
if(root!=NULL) {
hp=0; /*hp指向当前搜索结点*/ tp=1; /*tp为队列指针*/
lc=1; /*lc指向搜索过程中某一层中最后的一个结点*/ que[1]=root; /*root所指向结点进入队列*/ level=1;
do
{ hp=(hp%max)+1; /*当前队列的队头结点出队*/ root=que[hp];
if(root->lchild!=NULL) /*root所指结点的左孩子入队*/ {tp=(tp%max)+1; que[tp]=root->lchild;
}
if(root->rchild!=NULL) /*root所指结点的右孩子入队*/ {tp=(tp%max)+1; que[tp]=root->rchild; }
printf(“node %c:%d”,root->data,level); if (hp= =lc)
{ level++;
lc=hp; /*lc为下一层中最右边结点在队列中的位置*/ }
}while (hp!=tp);
}}
h
4、已知深度为h的二叉树以一维数组[2-1]作为其存储结构，请写一个算法，求该二叉树中叶结点的个树。
Int leafcount (int bt[2-1] ) { int I,len ,count;
len=2h-1; count=0;
for(I=1;I<=len;I++)
32
h
if(bt[I]!=0)
if(2*I>len) count++; else
if((bt[2*I]= =0)&&(bt[2*I+1]= =0)) count++; return (count); }
习
一、选择题：
题六
1、具有n个顶点的有向图最多有_____条边。
A、N B、n(n-1) C、n(n+1) D、n2
2、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是_____。 A、G中有弧
A、n-1 B、n C、n+1 D、nlog2n 4、下列说法中，正确的有_____。 A、最小生成树也是哈夫曼树
B、最小生成树唯一
C、普里姆（Prim）最小生成树算法时间复杂度为O(n2)
D、克鲁斯卡尔（Kruskal）最小生成树算法比普里姆算法更适合于边稠密的网 5、下图所示的拓扑排列的结果序列为_____。
A、 125634 B、516234 C、123456 D、521634
第5题图 第9题图
6、判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用_____。 A、求关键路径的方法 B、求最短路径的Dijkstra方法 C、深度优先遍历算法 D、广度优先遍历算法
7、在一个具有n个顶点的有向图中，若所有顶点的出度之和为S，则所有顶点的入度之和为_____。
A、S B、s-1 C、s+1 D、n
8、在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为_____。 A、K B、k+1 C、k+2 D、2k 9、下图的深度优先搜索序列为_____。 A、DFS（A）：ABEDCF B、DFS（A）：AEFCDB C、DFS（A）：ABCEDF D、DFS（A）：ACBDEF
33
10、一个有n个顶点的无向连通图，它所包含的连通分量个数为_____。
A、0 B、1 C、n D、n+1
11、对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点单链表中的结点数为_____。
A、 k1 B、k2 C、k1-k2 D、k1+k2
12、对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为_____。
A、k1 B、k2 C、k1-k2 D、k1+k2 13、对于一个无向图，下面_____的说话是正确的。
A、每个顶点的入度等于出度 B、每个顶点的度等于其入度与出度之和 C、每个顶点的入度为0 D、 每个顶点的出度为0
14、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用_____。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储 二、填空题：
1、有n个顶点的有向图，至少需要_____条弧才能保证是连通的。
2、求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间约为_____ms。 3、一个连通图的_____是一个极小连通子图。
4、在AOE网中，从源点到汇点路径上各活动的时间总和最长的路径称为_____。 5、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
6、有向图中的结点前驱后继关系的特征是_____。
7、顶点活动网（AOV网）是 有向图。 8、有向图的极大强连通子图称为 。
9、在一个具有n个顶点的无向完全图中，包含有 条边；在一个具有n个顶点的有向完全图中，包含有 条边。
10、对含有n个顶点e条边的无向连通图，利用普里姆算法生成最小生成树的时间复杂度为 ，利用克鲁斯卡尔算法生成最小生成树的时间复杂度为 。 11、若无向图G的顶点度数最小值大于等于 时,G至少有一条回路。 12、连通分量是无向图中的 连通子图。
13、从源点到汇点长度最长的路径称关键路径，该路径上的活动称 。 参考答案：
一、 选择题：
1、B 2、D 3、A 4、C 5、B 6、C 7、A 8、B 9、B 10、B 11、B 12、A 13、A 14、B 二、 填空题
1、n-1 2、160 3、生成树 4、最短路径 5、n-1 6、一个结点可能有若干个前驱，也可能有若干个后继。 7、用顶点表示活动，边表示活动间先后关系的 8、有向图的强连通分量 9、n(n-1)/2 n(n-1) 10、O(n2) O(elog2e) 11、2 12、极大 13、关键活动 三、 算法设计：
1、 写出从图的邻接表转换成邻接矩阵表示的算法。 Void adjlisttoarray(int a[ ][ ])
{
34