数据结构第二单元测验答案.doc

数据结构第二单元测验答案
一、选择题
1.由3 个结点可以构造出多少种不同的有向树( )
A.2 B.3 C.4 D.5
2.由3 个结点可以构造出多少种不同的二叉树( )
A.2 B.3 C.4 D.5
3.二叉树的第I层上最多含有结点数为( )
A.2I B.2I-1-1 C.2I-1 D.2I -1
4.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
A.2h B.2h-1 C.2h+1 D.h+1
除第一层外,每层最少2个结点
5.一棵树高为K的完全二叉树至少有( )个结点
A.2k –1 B.2k-1 –1 C.2k-1 D.2k
6.深度为6的二叉树最多有( )个结点
A．64 B.63 C.32 D.31
7.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )
A.5 B.6 C.7 D.8
8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )
A.9 B.11 C.15 D.不确定
9.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )
A.250 B.500 C.254 D.505 E．以上答案都不对
10.对于有n 个结点的二叉树, 其高度为( )
A.nlog2n B.log2n C.ëlog2nû|+1 D.不确定
11.将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下.从左到右顺序结点编号，那么编号为41的双亲结点编号为（ ）
A.42 B.40 C.21 D.20
12.一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A
B
C
D

E
F

G

H

I
J
则结点E在二叉树的第（ ）层。
A. 1 B. 2 C. 3 D.4
13.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树
A.空或只有一个结点 B.高度等于其结点数
C.任一结点无左孩子 D.任一结点无右孩子
14.任何一棵二叉树的叶结点在其先根.中根.后根遍历序列中的相对位置( )
A.肯定发生变化 B.有时发生变化
C.肯定不发生变化 D.无法确定
15.二叉树线索化后，仍不能有效求解的问题是（ ）
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前驱
D.后序线索二叉树中求后续后继
一共有两种情况:一个是先序线索中求先序前驱和后序线索求后序后继
16.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的( )
A.前序 B.中序 C.后序 D.层次序
17.设森林T中有4棵树，第一.二.三.四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有( )个结点。
A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4
18.设给定权值总数有n 个,其哈夫曼树的结点总数为( )
A.不确定 B.2n C.2n+1 D.2n-1
19.下面几个符号串编码集合中，不是前缀编码的是( )
A.{0,10,110,1111} B.{11,10,001,101,0001}
C.{00,010,0110,1000} D.{b,c,aa,ac,aba,abb,abc}
20.一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn
21.n个结点的完全有向图含有边的数目是（ ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
22.下面关于图的存储的叙述中正确的是（ ）。
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
23.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）
A.先根遍历B.中根遍历C.后根遍历D.按层次遍历
24.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（ ）。
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
25.关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路 D．最短回路
26.下面关于求关键路径的说法不正确的是（ ）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
二、填空题
1.具有n个结点的满二叉树，其叶结点的个数是__(n+1)/2____。
2.完全二叉树中，结点个数为n，则编号最大的分支结点的编号为__ën/2û ____。
3.一棵共有n个结点的树，其中所有分支结点的度均为k，则该树中的叶子结点个数为 n-(n-1)/k 。
4.含4个度为2的结点和5个叶子结点的二叉树，可有_0至多个___个度为1的结点。
5.8层完全二叉树至少有_ 128(第七层满，加第八层１个)　_____个结点，拥有100个结点的完全二叉树的最大层数为__7__。
6.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为__ élog2kù+1 ____。
7.对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为 2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 ë i/2 û 。
8.具有N个结点的二叉树，采用二叉链表存储，共有_ N+1 _____个空链域。
9.在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==NULL && p->rchlid==NULL _____。
10.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的__前序 ____序列中的最后一个结点。
11.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_n___条弧。
12.如果含n个顶点的图形形成一个环，则它有___ n____棵生成树。
13.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需__队列__存放被访问的结点以实现遍历。
14.求图的最小生成树有两种算法，__克鲁斯卡尔____算法适合于求稀疏图的最小生成树。
三、判断题
1.树与二叉树是两种不同的树型结构。√
2.度为二的树就是二叉树。×
3.在二叉树的第i层上至少有2i-1个结点(i>=1)。×
4.完全二叉树一定存在度为1的结点。×
5.若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树( X )
6.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。√
7.若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反( √ )
8.二叉树的前序遍历并不能唯一确定这棵树，但是如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。×
9.已知一棵树的先序序列和后序序列，一定能构造出该树( √ )
10.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。√
11.有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。×
12.一个有向图的邻接表和逆邻接表中结点的个数可能不等。×
13.在无向图的深度优先遍历算法中，DFS（从某个顶点出发深度优先遍历图的算法）被调用了几次就说明该图有几个联通分量。（√ ）
14.需要借助于一个队列来实现DFS算法(深度优先遍历)。×
15.广度遍历生成树描述了从起点到各顶点的最短路径。×
16.既使有向无环图的拓扑序列唯一，也不能唯一确定该图。×
17.在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。×
四、解答题
1.已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树。
当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：

2.对于给定的5个实数W={8，5，13，2，6}，试构造哈夫曼树；并求出每个叶子结点的哈夫曼编码。

每个叶子的哈夫曼编码为：
权值为8的哈夫曼编码：10
权值为5的哈夫曼编码：011
权值为13的哈夫曼编码:11
权值为2的哈夫曼编码：010
权值为6的哈夫曼编码：00
注意：哈夫曼树及编码不唯一
3.对带权无向图（如图1所示）采用prim算法从顶点①开始构造最小生成树。(写出加入生成树顶点集合S和选择边Edge的顺序)

S：
顶点号

Edge：
（顶点，顶点，权值）
①
（ 1， 2，9 ）
①②
（ 2， 4，5 ）
①②④③
（ 2， 3，7 ）
①②④③
（ 3， 5，6 ）
①②④③⑤

（ 3， 6，7 ）
①②④③⑤⑥

四、算法设计题
1.编写算法实现二叉树的层次遍历顺序（同一层次从左至右）算法。
void LayerOrder(Bitree T) {//层序遍历二叉树
  InitQueue(Q); //建立工作队列 …….(1分)
  if（T）
  EnQueue(Q,T); …….(1分)
  while(!QueueEmpty(Q))  {
     DeQueue(Q,p); …….(4分)
     visit(p);
     if(p->lchild) EnQueue(Q,p->lchild); …….(2分)
     if(p->rchild) EnQueue(Q,p->rchild); …….(2分)
   }
}//LayerOrder
2. 试写出一递归函数，复制一棵二叉树。
BiTree Copy(BiTree t)//复制二叉树t
{BiTree bt;
if (t==null) bt=null;
else{bt=(BiTree)malloc(sizeof(BiNode)); bt->data=t->data;
bt->lchild=Copy(t->lchild);
bt->rchild=Copy(t->rchild);
}
return(bt); }//结束Copy

第 5 页 共 5 页