英文论坛-qqh
数据结构第二单元测验答案
一、选择题
1.
由
3
个结点可以构造出多少种不同的有向树
( )
A.2
B.3 C.4
D.5
2.
由
3
个结点可以构造出多少种不同的二叉树
( d)
A.2 B.3 C.4
D.5
3.
二叉树的第
I
层上最多含有结点数为
< br>(c )
I
I-1
I-1
I
A.2
B.2
-1
C.2
D.2
-1
4.
一棵二叉树高度为
h,
所有结点的度或为
0
，或为
2
，则这棵二叉树最少有
( b )
结点
A.2h
B.2h-1
C.2h+1
D.h+1
除第一层外
,
每层最
少
2
个结点
5.
一棵树高为
K
的完全二叉树至少有
( c )
个结点
< br>k
k-1
k-1
k
A.2
–
1
B.2
–
1
C
.
2
D.2
6.
深度为
6
< br>的二叉树最多有
( c
)
个结点
A
．
64
B
.
63
C.32 D.31
7.
设树
< br>T
的度为
4
，其中度为
1
，
2
，
3
和
4
的结点个数分别为<
/p>
4
，
2
，
1
，
1
则
T
中的叶子数
为
(
)
A.5 B.6 C.7
D
.
8
8
.
若一棵二叉树具有
10
个度为
2
的结点，
5
个度为
1
的结点，则度为
0
< br>的结点个数是
( c )
A.9
B
.
11
C.15 D.
不确定
9
.
一棵完全二叉树上有
1001
个结点
，其中叶子结点的个数是
( e )
A.250
B.500 C.254 D.505
E
．以上答案都不对
10.
对于有
n
个结点的二叉树
,
其高度为
( d )
2
n
2
n C.
?
< br>log
2
n
?
< br>|+1
D
.
不确定
11.
将含有
83
个结点的完全二叉树从根结点开始编号，根为
1
号，按从上
到下
.
从左到右顺
序结点编号，那么编
号为
41
的双亲结点编号为（
）
A.42 B.40 C.21
D
.
20
1
2.
一个二叉树按顺序方式存储在一个维数组中，如图
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
在二叉树的第（
c
）层。
A. 1 B. 2
C. 3
D.4
1
3.
某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（
b
）的二叉树
A.
空或只有一个结点
B
.
高度等于其结点数
C.
任一结点无左孩子
D.
任一结点无右孩子
14.
任何一棵二叉树的叶结点在其先根
.
中根
.
后根遍历序列中的相对位置
( c
)
A.
肯定发生变化
B.
有时发生变化
C
.
肯定不发生变化
D.
无法确定
15
< br>.
二叉树线索化后，仍不能有效求解的问题是（
d
）
A.
先序线索二叉树中求先序后继
B.
中序线索二叉树中求中序后继
C.
中序线索二叉树中求中序前驱
第
1
页
共
5
页
<
/p>
D
.
后序线索二叉树中求后续后继
一共有两种情况
:
一个是先序线索中求先序前驱和后序线索求后序后继
16.<
/p>
如果
T
2
是由有
序树
T
转化而来的二叉树，那么
T
中结点的前序就是
T
2
中结点的
( a )
A
.
前序
B.
中序
C.
后序
D.
层次序
17.
< br>设森林
T
中有
4
棵树，第一
.
二
.
三
.
四棵树的结点个数分别是
n1,n2,n3,n4,
那么当把森
林
< br>T
转换成一棵二叉树后，且根结点的右子树上有
( d
)
个结点。
A.n
1
-1
B.n
1
C.n
1
+n
2
+n
3
D
.
n2+n3
+n4
18.
设给定权值总数有
n
个
,
其哈夫曼树的结点总数为
< br>( d )
A.
不确定
B.2n C.2n+1
D
.
2n-1
19.
下面几个符号串编码集合中，不是前缀编码的是
(
b)
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
）。
A
．
n-1
B
．
n
C
．
n+1
D
．
nlogn
21.n
个结点的完全有向图含有边的数目是（
d
）
。
A
．
n*n
Ｂ．
n
（
n
＋１）
C
．
n
／
2
D
．
n*<
/p>
（
n
－
l
）
22.
下面关于
图的存储的叙述中正确的是（
b
）
。
A.<
/p>
用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B.
用邻接表法存储图，占用的存储空间大小
与图中边数和结点个数都有关。
C.
用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D.
用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结
点个数无关
23.
在图的邻接表存储
结构上执行深度优先搜索遍历类似于二叉树上的
（
a
）
A.
先根遍历
B.
中根遍历
C.
后根遍历
D.
按层次遍历
24.
已知有向图
G=(V,E)
，其中
V=
{V
1
,V
2
,V
3
,V
4
,V
5
,V
6
,V
7
}
，
2
<
br>,V
具有
E={
1
,V
>,
1
,V
3
>,
1
,V
4
>,
2
,V
5
>,
3
,V<
/p>
5
>,
3
,
V
6
>,
4
,V
6
>,
5
7
>,
6
,V
7
>},G
的拓扑序列
是（
a
）
。
A
．
V
1
,V
3
,V
4
,V
6
,V
2
,V
5
,V
7
B
．
V
1
,V
3
,V
2
,V
6
,V
4
,V
5
,V
7
C
．
V
1
,V
3
,V
4
,V
5
,V
2
,V
6
,V
7
D
．
V
1
,V
2
,V
5
,V
3
,V
4
,V
6
,V
7
25.
关键路径是事件结点网络中（
a
）
。
A
．从源点到汇点的最长路径
B
．从
源点到汇点的最短路径
C
．最长回路
D
．最短回路
26.
下面关于求关键路径的说法不正确的是（
c
）
。
A
．求关键路径是以拓扑排序为基础的
B
．一个事件的最早开始时间同以该事件为尾的弧的活动最早开
始时间相同
C
．一个事件的最迟开
始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间
的差
D
．关键活动一定位于关键路径上
二、填空题
1.
n
个结点的满二叉树，其叶结点的个数是
_
_(n+1)/2__
__
。
2.
完全二叉树中，结点个数为
n
，则编号最大的分支结点的编号为
_
_
?
n/2
?
_
___
。
3.
一棵共有
n
个结点的树，其中所有分支结点的度均为
k
，则该树中的叶子
结点个数为
n-(n-1)/k
。
4.
含<
/p>
4
个度为
2
的结
点和
5
个叶子结点的二叉树，可有
_0
至多个
__
_
个度为
1
的结点。
5.8
层完全二叉树至少有
_
128(
第七层满，加第八层１个
)
__
___
个结点，拥有
100
个结点
的完全二叉树的最大层数为
_
_7_
_
。
第
2
页
共
5
页