句容市网上家长学校-办公经费申请报告

（1）若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出 受限双端队列
得到的输出序列是（ ）。
A
）
1234 B
）
4132 C
）
4231 D
）
4213
（
2
）将一个
A[1..100,1..1 00]
的三对角矩阵，按行优先存入一维数组
B[298]
中，
A
中 元素
a
66,65
在
B
数组
B
）
195 C
）
197
中的位置
k
为（ ）（假设
B[0]
的位置是
1
）。
A
）
198
D
）
198
（
3
）若度为
m
的哈 夫曼树中，其叶结点个数为
n
，则非叶结点的个数为（ ）。

A
）
n-1 B
）

n

1



m

C
）

n1



m1

D
）

n

1



m1

（
4
）若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻接矩阵必定为
（ ）。

A
）对称矩阵
B
）稀疏矩阵
C
）三角矩阵
D
）一般矩阵

（
5
）设森林
F
对应的二叉树为有
m
个结点， 此二叉树根的左子树的结点个数为
k
，则另一棵子树的结
点个数为（ ）。

A
）
m-k+1 B
）
k+1 C
）
m-k-1 D
）
m-k
（
6
）假定有< br>K
个关键字互为同义词，若用线性探测法把这
K
个关键字存入散列表中，至少要 进行（ ）
次探测。

A
）
K-1
次
B
）
K
次
C
）
K
＋
l
次
D
）
K(K+1)2
次


（
7
）一棵 深度为
k
的平衡二叉树，其每个非终端结点的平衡因子均为
0
，则该树共有（ ）个结点。
A
）
2
k-1
-1 B
）
2
k-1
C
）
2
k-1
+1 D
）
2
k
-1
（
8
）如表
r
有
100000
个元素，前
99999
个元素递增有序，则采用（

）方法比较次数较少。

A
）直接插入排序
B
）快速排序
C
）归并排序
D
）选择排序

（
9
）如果只考虑有序树的情形，那么具有
7
个结点的不同形态的树共有（ ）棵。

A）132 B）154 C）429 D）前面均不正确
（
10
）对
n(n>=2)
个权值均不相同的字符构成哈夫曼树，关于该树的叙 述中，错误的是（

）。

A
）该树一定是一棵完全二叉树

B
）树中一定没有度为
1
的结点

C
）树中两个权值最小的结点一定是兄弟结点

D
）树中任一非叶结点的权值一定不小于下一任一结点的权值

二、（本题8分）
斐波那契数列
Fn
定义如下：

F0
=0
，
F
1
=1
，
F
n
= F
n-1
+F
n-2

请就此斐波那契数列，回答下列问题：

（
1
）在递归计算
F
n
的时候，需要对较小的
F
n-1
，
F
n-2< br>，„，
F
1
，
F
0
精确计算多少次？
（
2
）若用有关大
O
表示法，试给出递归计算
Fn
时递 归函数的时间复杂度是多少？

三、（本题8分）
证明：如果一棵二叉树的后序序列 是
u
1
,
u
2
,
„
,
u
n
，中序序列是
u
p
,
u
p
,
„
,
u
p
，则由序列
1,2,
„
,n
可通
1 2n
过一个栈得到序列
p
1
,
p
2
,
„< br>,
p
n
。

四、（本题8分）
如下图所示为
5
个乡镇之间的交通图，乡镇之间道路的长度如图中边上所注。现在要在这
5
个乡镇 中选
择一个乡镇建立一个消防站，问这个消防站应建在哪个乡镇，才能使离消防站最远的乡镇到消防站的 路程最

短。试回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果。

1
3
5
6
4
9
4
12
2
6
3

五、（本题8分）
证明一个深度为
n
的
A VL
树中的最少结点数为：
Nn=F
n+2
-1 (n
≥
0)
其中，
Fi
为
Fibonacci
数 列的第
i
项。

六、（本题8分）
简单回答有关
AVL
树的问题：（北方名校经典试题）

（
1
）在有
n
个结点的
AVL
树中，为结点增加 一个存放结点高度的数据成员，那么每一个结点需要增加
多少个字位（
bit
）？
（
2
）若每一个结点中的高度计数器有
8bit
，那么这样的
AVL
树可以有多少层？最少有多少个关键字？

七、（本题8分）
设有
12
个数据
{25
，
40
，
33< br>，
47
，
12
，
66
，
72
，87
，
94
，
22
，
5
，
58}，它们存储在散列表中，利用线性探测再
散列解决冲突，要求插入新数据的平均查找次数不超过3
次。

（
1
）该散列表的大小
m
应设计多大？

（
2
）试为该散列表设计相应的散列函数。

（
3
）顺次将各个数据散列到表中。

（
4
）计算查找成功的平均查找次数。

八、（本题8分）
已知某电文中共出现了
10
种不同的字母，每个字母出现的频率分别为
A
：
8
，
B
：
5
，
C
：
3
，
D
：
2
，
E
：
7
，
F
：
23
，
G
：
9
，
H
：
11
，
I
：
2
，
J
：
35
，现在对这段电文 用三进制进行编码（即码字由
0
，
l
，
2
组成），问
电文编码总长度至少有多少位？请画出相应的图。

九、（本题9分）
已知一棵 度为
m
的树中有
N
1
个度为
1
的结点，
N
2
个度为
2
的结点，„，
N
m
个度为
m< br>的结点。试问该
树中有多少个叶子结点？（北方名校经典试题）

十、（本题15分）
试用递归法编写输出从
n
个数中挑选
k
个进行排列所得序列的算法。

模拟试题（七）参考答案
一、单项选择题（每小题 2 分，共20分）

（
1
）参考答案：
C
）

（
2
） 【分析】如下所示，三对角矩阵第
1
行和最后
1
行非零元素个数为
2
个，其余各行的非零元素个数是
3
个，所知
a
66,65
前 面共有
2+3*64
＝
194
个非零元素，
a
66,65< br>本身是第
195
个非零元。


a
11

a

21


A







a23
a
33

a
34

a
n2,n 1

a
n2,n2
a
n1,n
a
n2, n1
a
n1,n1
a
n,n1








a
n1,n

a
nn


a
12
a
22
a
3 2
参考答案：
B
）

（
3
）【分析】在哈夫曼树的 非叶结点中最多只有
1
个结点的度不为
m
，设非叶结点的个数为
k< br>，则其中
有
k-1
个结点的度为
m
，设另
1
个结点的度为
u
，则
2
≤
u
≤
m
，设结点 总数为
n
总
，则有如下关系：

n
总
-1=m(k-1)+u
①

n
总
=k+n
②

将②代入①可得：
k+n-1= m(k-1)+u
，解得：
k
( n1)(mu)
，由于
2
≤
u
≤
m
，所以可 得
0
≤
m-u
m1
＜
m-1
，所以可得：
n1n1

n1

+1
，可知
k
≤k
＜。


m1m1
m1

参考答 案：
C
）

（
4
）【分析】设顶点按拓扑排序序列为：v
0
,v
1
,…,v
n-1
，则对于邻接矩阵
A
，只有当
i时，才可能有弧
<
v
i
,v< br>j
>
，也就是当
i>j
时，一定没有弧
< v
i,v
j
>
，所以这时
A[i][j]=0
，可知邻接矩阵为三角 矩阵。

参考答案：
C
）

（
5
）【分析】设另一棵子树的结点个数为
n
，所以有
m=n+k+1
，可知
n= m-k-l
。

参考答案：
C
）

（
6
）【分析】因为
K
个关键字互为同义词，只有在存入第一个关键字的情况下不发生冲突，所以至少
需进行
1+2+
„
+K=K(K+1)2
次探测。

参考答案：
D
）

（
7
）【分析】由于每个非终端 结点的平衡因子均为
0
，所以每个非终端结点必有左右两个孩子，且左子
树的高度和右 子树的高度相同，这样
AVL
树是满二叉树。高度为
k
的满二叉树的结点数为
2
k
-l
。

参考答案：
D
）

（
8
）【分析】本题中只有直接插入排序利用前面有序的子序列这个性质，如用直接插 入排序对本题只需将最
后一个元素插入到前面
99999
个元素的有序子序列中即可， 显然比较次数较少。

参考答案：
A
）

（
9）【分析】具有
n
个结点有不同形态的树的数目和具有
n-l
个结点互不 相似的二叉树的数目相同（将
树转化为二叉树时，根结点右子树为空，所以除根结点而外只有左子树，其 不相似的二叉树的等价于不相似
的左子树）。具有
n
个结点互不相似的二又树的数目为
参考答案：
A
）

（
10
）参考答案：
A
）


1
1
n
6
C
2
C
12
132
。

n
，本题中应为
n1
61

二、（本题8分）
【解答】

（
1
）设在计算
F
n
时，由
F
n-1
+F
n-2
可知
Fn-1
要精确计算
1
次；

由
F
n-1
=F
n-2
+F
n-3
可知
F
n
=2F
n-2
+F
n-3
，
F
n-2
要精确计算
2
次；

由
F
n-2
=F
n-3
+F
n- 4
可知
F
n
=3F
n-3
+2F
n-4
，
F
n-3
要精确计算
3
次，
F
n
=3F< br>n-3
+2F
n-4
公式中
F
n-3
的系数为
F
n-3
要精确
F
n
=a
j
*F
n-j
+a
j-1
*F
n-j-1
。

计算次数，而F
n-4
的系数为
F
n-2
要精确计算次数，以此类推，设F
n-j
的精确计算次为
a
j
，则有：
由
F< br>n-j
=F
n-j-1
+F
n-j-2
可知
F
n
=(a
j
+ a
j-1
)*F
n-j-1
+a
j
*F
n-j-2

，
F
n-j-1
的精 确计算次数为
a
j+1
，所以有：

a
j+1
=a
j
+a
j-1

F
n-2
，
F
1
，
F
0
的精确计算次为：
1
，
2
，
3
，
5
，由于
F
n-1< br>要精确计算
a
1
为
1
次，即
a
1
= 1
，即可知
F
n-1
，„，„„，
a
j
=a
j-1
+a
j-2
„„

与斐波那契数列数列：

0
，
1
，
2
，
3
，
5
，„„，
F
n
=F
n-1
+F
n-2
„„

比较可知
a
j
=F
j+1
。

（
2
）由于
F
n
的计算最终要转化为
F
0
与
F
1
之和，其加法的计算次数为
F
0
与
F
1
的精确计算次数之和再减
1
之差，由于
F
0
=F
n-n< br>与
F
1
=F
n-(n-1)
，所以计算
F
n
时，加法计算次数为：

a
n
+a
n-1
-1=F
n+1
+F
n
-1
由于
Fn=
115
n
115
n
15
n
()()
，可知时间复杂度为< br>O(
()
)
。

22
2
55
三、（本题8分）
【解答】当
n=1
时，结论显然成立。

设
n<=k
时结论成立，当
n=k+1
时，设一棵二叉树的后序序列是
u
1
,
u
2
,
„
,
u
n
，中序序列是
u
p
,
u
p
,
„
,
u
p
，
12n
{
u
p
,
u
p
,
„
,
u
p
}
可知
u
n
是二叉树的根结点，设p
j
n
，可知
{
u
p
,
u
p
,
„
,
u
p
}
是左子树的结点集合，
1 2n
j1j1j2
是右子树的结点集合，进一步可知：

（
1
）左子树的后序序列是
u
1
,
u
2
,
„< br>,
u
j1
，中序序列是
u
p
,
u
p
,
„
,
u
p
，由归纳假设知序列
1,2,
„
,j-1
12
j1
可以通过一个栈得序列
p
1
,
p
2
,
„
,
p
j1
。
< br>（
2
）右子树的后序序列是
u
j
,
u
j1
,
„
,
u
n1
，中序序列是
u
p,
u
p
,
„
,
u
p
，设
u
1
„，

u
j
，

u
j1
，
u
2
n
j1j2

j
u
n1
；
u

p

u
p
，
u

p

u
p
，„，
u

p
u
p
，则
p
1

p
j1j1
，
p
2

p
j2
j1
，„，
u
n
1j12j2njn

，
p
2

，„，
p
n

j
p
n
j 1
，由归纳假设知序列
1,2,
„
,n-j
可以通过一个栈得序列
p
1

j
，显然按同样的
p
n

方式，
j,j+1,
„
,n-1
可以通过一个栈得序列
j 1p
1

,
j1p
2

,
„,
j1p
n

j
，也就是
p
j1，
p
j2
，„，
p
n
。
由（
1）（
2
）及
p
j
n
可知由
1,2,
„
,n
可通过一个栈得到序列
p
1
,
p
2
,
„
,
p
n
。由数学归纳法可知本题结

论成立。

四、（本题8分）
【解答】由弗洛伊德（
Floyd
）算法进行求解，具体步骤如下：


012

120



96





3
9
6
0
4
< br>

4
0
6


4
0
6< br>D
(1)
3


0129


1 20


6
，

(0)


D

960


6

4


0



31512


4
0
6
3

15


；

12< br>

6

0


D
(1)

0129

1206



960
< br>4




31512
3

< br>0129133



120
15

，61015


；

(2)
12

D

960412



6

131 0406


0

3151260

D
(3)
93


0129133


0129

120


120
61015
61015



。

，
(4)


960412

D

960410



1310406
910406




0

0


315106

3151 06

max_disdance(v
1
)=12
，
max _disdance(v
2
)=15
，设乡镇
v
i
到其他各 乡镇的最远距离为
max_disdance(v
i
)
，则有：
ma x_disdance(v
3
)=10
，
max_disdance(v4) =10
，
max_disdance(v
5
)=15
，所以可知消防 站应建在
v
3
或
v
4
乡镇，才
能使离消防站最远的 乡镇到消防站的路程最短。

五、（本题8分）
【解答】对
n
用归 纳法证明。当
n
＝
1
时，有
N1=F3-l=2-l=1
到 。当
n=2
时，有
N2=F4-1=3-1=2
。设
n 时也成立，即有
N
n
=F
n+2
-1
成立。
当
n=k+1
，对于一个
k+l
层深度的平衡二叉树而言，其左右子树都 是平衡的。结点数为最少的极端情况，
故左右子树中的结点数是不相等的，设其中一个是
k层深度的二叉平衡树，另一个是
k-l
层深度的二叉平衡树。
所以有：

N
k+1
=1+N
k
+N
k-1
==1+(Fk+2
-1)+(F
k+1
-1)= F
k+2
+F
k+1
-1= F
k+3
-1
当
n=k+1
时成立，由此可知深度为
n
都等式都成立。

六、（本题8分）
【解答】
n
个结点的平衡二叉树的最大高度为
h log(5(n1))2
，设表示高度需
xbit
，则有关系
15< br>2
式：
2
x
≥
h
＞
2
x-1
，所以有：


x

log
2
h



log
2
(log
15
(5(n1)) 2)



2
15
h2
()
2（
2
）设深度为
h
的平衡二叉树的最少关键字数为
n
h
，则有公式：
n1
，本题中
8bit
的计数
h
5

15
258
()
2
器共可以表示
2
8
= 256
层，即高度为
256
，从而可知最少有
n1
个关键字。< br>
5
七、（本题8分）
【解答】

（
1
） 线性探测再散列的哈希表查找成功的平均查找长度为：
S
nl

也就是
12m
≤
4
／
5
，

所以
m
≥
15
，可取
m=15
。

（
2
）散列函数可取为
H(key)=key % 13
（
3
）散列表如表
7-4
所示。

散列表

0

1
40
2
66
3
94
4

5
5
6
58
7
33
8
47
9
72
10
87
11
22
12
25
13
12
14

11
(1)
≤
3
，解得α≤
4
／
5
，
21

（
4
）
12
个数据
{25，
40
，
33
，
47
，
12
，
66
，
72
，
87
，
94
，
22
，
5
，
58
｝的比较次数分别是：
1
，
1
，
1
，
1
，
2
，
2
，
3
，
2
，
1
，
3
，
1
，
1
。

可知查找成功的平均查找次数
=(1+1+1+1+2+2+3+2+1+3+ 1+1)12=1.25
八、（本题8分）
【解答】有
n
个叶子结点的带 权路径长度最短的二叉树称哈夫曼树，同理，存在有
n
个叶子结点的带权
路径长度最短 的三叉、四叉、
……
、
k
叉树，也称为哈夫曼树。如叶子结点数目不足以构成 正则的
k
叉树（树
中只有度为
k
或
0
的结点），即 不满足
(n-l)MOD(k-l)=0
，需要添加权为
0
的结点，添加权为
0
的结点的个数
为：
k-(n-1)MOD(k-1)-1
。添加的 位置应该是距离根结点的最远处。

所构造出的哈夫曼树如下图所示：

< br>其中，每个字母的编码长度等于叶子结点的路径长度，电文的总长度为

wl
= 191
。

ii
i1
n
m=n
k
+n< br>，注释：对于正则的
k
叉树，设叶结点数为
n
，度为
k
的结点数为
n
k
，结点总数为
m,
则有
m-1=knk
，
两式相减可得
n-1=(k-1)n
k
，即
(n- l)MOD(k-l)=0
；如
n
与
k
不满足此关系，
n< br>加上
k-(n-1)MOD(k-1)-1
后，
n’=
n+(k-(n-1)MOD(k-1)-1)
，这时：

(n’-l)MO D(k-l)=(n+(k-(n-1)MOD(k-1)-1)-l)MOD(k-l)
=((n-1)+(k-1)-(n-1)MOD(k-1))MOD(k-l)

=((n-1)-(n-1)MOD(k-1))MOD(k-l)
=0
。

现有
12
个初始归并段，其记录数分别为｛
30,44,8,6,3,20,60,18,9,62,68,85
｝，采用
3-
路平衡归并，画出最
佳归并树。

九、（本题9分）
【解答】设该树中结点 总数为
N
，叶子结点个数为
N
0
，则有：

N

N
i0
m
i


i












（
1
）

（
2
）

N1

iN
i1
m
由（
2
）
-
（
1
）再经过移项可得：
N 1
m
(i1)N


0i
i1
十、（本题15分）
【解答】

对 于排列的解空间可构造一个虚拟的解空间树，比如
n=5
，
k=3
时的解空间 树如下图所示，可采用对此
树进行先序遍历方式进行遍历，并用递归法进行递归输出从
n
个数中挑选
k
个进行排列所得序列。


具体算法实现如下：



文件路径名
:exam7alg.h
template
void Arrage(ElemType a[],int k,int n, int outlen=0)

操作结果
:
回溯法输出排列序列，
a[0..k-1]
为
k
个数的排列序列
outlen
为当 前所求排列


序列的长度，其中
outlen=k
时的排列序列为 所求；
n
为
list
数组长度

{
if (k < 0 || k >= n) return;
此时无排列

int i;
临时变量

if (outlen == k + 1)
{
得到一个排列

for (i = 0; i < k; i++)
{
输出一个排列

cout << a[i];
输出
a[i]
}
cout <<
用空格分隔不同排列

}
else
{
对解空 间进行前序遍历，
a[outlen..n]
有多个排列，递归的生成排列

for (i = outlen; i < n; i++)

}






}
{



}

处理
a[i]
Swap(a[outlen+1], a[i]);
交换
a[outlen+1]
与
a[i]
Arrage(a, k, n, outlen + 1);
对序列长度
outlen+1
递归

Swap(a[outlen+1], a[i]);
交换
a[outlen+1]
与
a[i]
*模拟试题（八）
注：本套试题选作

一、单项选择题（每小题 2 分，共20分）

（
1
）一个
n*n
的带状矩阵
A=[a
ij
]
如下：

a
11

a

21


A






a
12
a
22a
32
a
23
a
33

a
34

a
n2,n1

a
n2,n2
a
n 1,n
a
n2,n1
a
n1,n1
a
n,n1< br>








a< br>n1,n

a
nn


将带状区域中的元素
a
ij
（
|i-j|
≤
1
）按行序为主序存储在一维数组
B[3n-2]
中，元素
a
ij
在
B
中的存储位置 是
（ ）。

A
）
i+2j-2 B
）
2i+j-3 C
）
3i-j D
）
i+j+1
（
2
）一
n
×
n
的三角矩阵
A=[a
ij
]
如下：


a
11





a
12
a
22

a
1n


a
2n






a
nn

将三角矩阵中元素
a
ij
(i
≤
j)
按行序为主序的顺序存储在一维数组
B[n (n+1)2]
中，则
a
ij
在
B
中的位置是
（ ）。

A
）
(i-1)(2n+i)2+i-j B
）
(i-1)(2n-i+2)2+j-i
C
）
(i-1)(2n-i)2+j-i-1 D
）
(i-1)(2n-i+2)2+j-i-1
（
3
）设有一 棵度为
3
的树，其叶结点数为
n
0
，度为
1
的结点 数为
n
1
，度为
2
的结点数为
n
2
，度为
3
的
结点数为
n
3
，则
n
0
与< br>n
1
，
n
2
，
n
3
满足关系（ ）。

A
）
n
0
=n
2
+1 B
）
n
0
=n
1
+2n
3
+1 C
）
n
0
=n
2
+n
3
+1 D
）
n
0
=n
1
+n
2
+n
3
< br>（
4
）
G
是一个非连通无向图，共有
28
条边，则该 图至少有（ ）个顶点。

A
）
6 B
）
7 C
）
8 D
）
9
（
5
）设图
G
用邻结表存储，则拓扑排序的时间复杂度为（ ）。

A
）
O(n) B
）
O(n+e) C
）
O(n
2
) D
）
O(n×e)
（
6
）用
n
个键值构造一棵二叉排序树，最低高度为（ ）。

n
B
）
n
C
）
nlog
2
n D
）

log
2
n

1

2< br>（
7
）若需在
O(nlogn)
的时间内完成对数组的排序，且要求排 序是稳定的，则可选择的排序方法是
（ ）。

A
）快速排序
B
）堆排序
C
）归并排序
D
）直接插入排序

（
8
）在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。（北方名校经
典试题）

A
）直接插入排序
B
）起泡排序
C
）简单选择排序
D
）基数排序

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

A
）
247 B
）
248 C
）
249 D
）
250
（
10
）一个序列 中有10000个元素，若只想得到其中前10个最小元素，最好采用 ( )方
法。
A）快速排序 B）堆排序
C）插入排序 D）二路归并排序
二、（本题8分）
要借助栈由输入序列是输入
1,2,3,
„
,n
得到的输出序列为
p
1
,p
2
,p
3
,< br>„
,p
n
(
此输出序列是输入序列经过栈操作
后的某个排列< br>)
，则在输出序列中不可能出现当
i时有
p
j
k
i
的情况。

三、（本题8分）
已 知某一完全
k
叉树只有度为
k
的结点及叶结点，设叶结点数为
n0
，试求它的树高
h
。（南方名校经典
试题）

四、（本题8分）
试讨论怎样在一棵中序线索二叉树上查找给定结点
x
在后序序列中的后继。

五、（本题8分）
具有
n
个关键字的
B
一树的查找的最大路径长度是多少？

六、（本题8分）
对长度为
12
的有序表
(a
1
，
a
2
，„，
a
12
)
（其中
a
i
j
当
i时）进行折半查找，在设定查找不成功时，关键< br>字
x1
、
x>a
12
以及
a
i
i+1
(i=1,2,…,11)
等情况发生的概率相等，则查找不 成功的平均查找长度是多少？

八、（本题8分）
（
1
）设
T
是具有
n
个内结点的判断二叉树，
I
是它的内路径长度，
E
是它的外路径长度，试利用归纳法
证明
E
＝
I
＋2n
，
n
＞
0
。

（
2
）利 用（
1
）的结果，试说明，成功查找的平均比较次数
s
与不成功查找的平均比 较次数
u
之间的关
A
）
系，可用公式
s(1
1
n
)u1
，
n
＞
0
表示。

提 示：判断二叉树只有度为
0
或度为
2
的结点；判断二叉树成功查找的比较次数 为内路径长度与内结点
数之和，不成功查找的比较次数为外路径长度。

九、（本题9分）
一个深度为
h
的满
m
叉树有如下性质： 第
h
层上的结点都是叶结点，其余各层上每个结点有
m
棵非空子
树。 问：

（
1
）第
k
层有多少个结点？（
k
≤
h
）

（
2
）整棵树有多少个结点？

（
3
）若按层次从 上到下，每层从左到右的顺序从
1
开始对全部结点编号，编号为
i
的结点的双 亲结点的编号
是什么？编号为
i
的结点的第
j
个孩子结点（若存在） 的编号是什么？

十、（本题15分）
设散列表的关键字取值范围为
0 ~ m-1
，
n
为对散列表的最大插入次数，设计散列表，允许使用以
O(m+n )
空间，要求查找、插入和删除算法的时间复杂度都是
O(1)
。

模拟试题（八）参考答案
一、单项选择题（每小题 2 分，共20分）

（
1
）参考答案：
B
）

（
2
） 【分析】存储位置
=n+(n-1)+…+(n-i+2)+i-j=(i-1)(2n-i+2)2+ j-i
。

参考答案：
B
）

（
3
）【分析】用
n
表示结点总数，则有：
n= n
0
+n
1
+n
2
+n
3
；

由于除根结点而外，结点与分支一一对应，而分支数
= n
1
+2n
2
+3n
3
，即有：
n-1= n
1
+2n
2
+3n
3
。

由上面两式可 得：
n
0
=n
1
+2n
3
+1
参考答案：
B
）

（
4
）【分析】本题中由于是非 连图，至少有一个顶点与其他顶点不连，这个顶点是孤立点，其他顶点可
组成一个连通图，由于
8
个顶点的完全图共有
28
条边，所以具体
28
个顶点的连通图的顶 点个数至少为
8
，这
样非连通图至少有
9
个顶点。

参考答案：
D
）

（
5
）【分析】对于有
n
个顶点
e
条边的有向图，建立各顶点的入度时间复杂度为
O(e)
，建立入度为零的
栈的时间复杂度为
O(n)
，在拓扑排序过程中，最多每个顶点进一 次栈，入度减
1
的操作最多总共执行
e
次，
可知总的时间复杂度为< br>O(n+e)
参考答案：
B
）


（
6< br>）【分析】当用
n
个键值构造一棵二叉排序树是一棵完全二叉树时，高度最低，此时高度 为

log
2
n

1
。
参考答案：D
）

（
7
）【分析】快速排序和堆排序都是不稳定的，应排除 ；归并排序稳定，时间复杂度
O(nlogn)
，满足条
件；直接插入排序，时间复杂 度为
O(n
2
)
，排除。

参考答案：
C
）

（
8
）【分析】对直接插入排序 而言，算法时间复杂度为
O(n
2
)
，但若待排记录序列为“正序”时，其时
间复杂度可提高至
O(n)
。若待排记录序列按关键字“基本有序”，直接插入排序的 效率就可大大提高，此外
由于直接插入排序算法简单，在
n
值很小时效率也高。

参考答案：
A
）

（
9
）【分析】完全二 叉树中度为
1
的结点最多只有
1
个，由二叉树的度和结点的关系：

n=n
0
+n
1
+n
2
(1)

n=n
1
+2n
2
+1

(2)
< br>由
2(1)-(2)
得，
n=2n
0
+n
1
-1=247+n
1
≤
248
，所以本题应选择
B
）。

参考答案：
A
）

（
10
）参考答案：
B
）

二、（本题8分） < br>【解答】设
p
j
k
i
成立，则表示 在
p
i
出栈之前
p
j
和
p
k
都已 入栈，并且还留在栈中，但要满足
p
j
k
的出
栈次序是 不可能的，由于按照
i的次序，当
p
j
和
p
k
同时在栈中时，必然
p
k
被
p
j
盖住，由栈的 后进先出的
性质，当
i有
p
k
< p
j
i
，与假设矛盾。

三、（本题8分）
【解答】设度为
k
的结点数为
n
k
，结点总数为
n
，则有如下关系：

n= n
k
+n
0
①


又由于树中只有
n-1
条边，所以：

n-1=k
×
n
k
②


由①与②可得：
n
k
=(n
0
-1) (k-1)
，进而有
n=
kn
0
1

k1
(k-1)
≤
k
h
-1
对于
k< br>叉完全树有如下关系：
k
h-1
-1
＜
n×
(k-1 )
＜
k
h
，从而：
h-1
≤
log
k(n×(k-1))
＜
h
，进而：
h

log
k
(n(k1))

1

即有：
k
h-1
≤
n×
所以：
h=

log
k
(kn< br>0
1)

1

四、（本题8分）
【解答】由于 后序遍历二叉树需要知道的关键是访问当前结点的双亲结点，需要由中序线索树才能得到
当前结点的双亲 ，中序线索树有如下性质：

若
x
是
parent
的左孩子 ，则
parent
是
x
的最右子孙的右线索；

若
x
是
parent
的右孩子，则
parent
是
x
的最左子孙的左线索。

用以上性质能找到
x
的双亲结点
parent
。

若
x
是
parent
的右孩子，则
parent
结点就是< br>x
的后序序列的后继结点；如下图（
1
）中结点①的后继是结
点②。< br>
若
x
是
parent
的左孩子，则：

如 果
parent
的右指针域为线索的话，那么
parent
就是
x< br>的后序序列的后继结点，如下图（
2
）中结点②的
后继是结点③。

否则
parent
右子树中最左边第一个左右孩子均为线索的结点，就是
x
的后序序列的后继结点。如下图（
3
）
中结点②的后继是结点③。


五、（本题8分）
【解答】树的查找路径是从根结点开始到所要查找的结点的路径 ，最大不会超过
B-
树的深度。在
B
树中，

除根结点外所有非终端结点都含有


m

棵子树，所以有
n
个关键字的
B-
树的最大深度为根结点具有两棵子

2< br>
树，其余非终端点有


m

棵子树，设最大路 径长度是
x
，由于叶子结点表示查找不成功，叶子结点不含关键


2

字，可知
B-
树的深度为
x+1
，

第
1
层共有
1
个结点，含
1
个关键字；

第
2
层共有
2
个结点，含
2(


m

-1)
个关键字；



2
第
3
层共有
2

„„


m

m

m

2(-1)
个关键字；

个结点，含


2

2

2

x2

m

第
x
层共有
2

2



m

个结点，含
2

2


x2
(

m

-1)
个关键字；


2


m


m

(-1)
＝
2


2
< br>
2



x1
故，共含有的关键个数为：

m

m

m


m

1+2(-1)+2(-1)+
„
+2


2


2


2




2



x2
1


m

由此可得：
n2

2


x1< br>1
，解得：
x1log

m

(
< br>2


n1
)
，这就是具有
n
个关键宇 的
B
一树的查
2
找的最大路径长度。

六、（本题8分）
【解答】折半查找对应的判定树如下图所示。查找不成功的对应于外部结点。查找不成功所走的路径是< br>从根结点到每个外部结点（图中方块结点），和给定值进行比较的关键字个数等于该路径上内部结点个数。


在不成功情况下，一共比较的次数为
3*3+4*10=49
次。

平均查找长度为
4913
≈
3.77
七、（本题8分）
【解答】对于
a
来说，在
S2
中总可找到离
a
最近的祖先结 点
d
，这时
a，这时如
d
为
b
的右孩 子，则
有
a
在
b
的右子树上，所以
a>b
，也就是 说
a并不总是成立，同理
b也并不总是成立。

八、（本题8分）

【解答】
（
1
）证明：
n=1
时显然成立，设
n =k
时成立，即
E
k
=I
k
＋
2k
，当< br>n=k+1
时，设所增加的结点的路径长度
为
D
k
，则有：< br>
I
k+1
=I
k
+D
k

Ek+1
=E
k
-D
k
+2(D
k
+1)=E< br>k
+D
k
+2=I
k
+2k+D
k
+2=I
k+1
+2(k+1)=I
k+1
+2n
结论也成立。

（
2
）根据二叉树性质：度为
0
的结点数
=
度为< br>2
的结点数
+1
，所以外结点数
=n
＋
l
。

s=
查找成功总的比较次数

内结点数
=(I+n)n
①

u=
查找失败总的比较次数

外结点数
=E(n +1)=(I+2n)(n+1)
②

由①得：
I=ns-n
，由②得：
I=(n+1)u-2n
，所以可得：
ns-n=(n+1)u-2n，进一步得：
s(1
1
n
)u1
。

九、（本题9分）
【解答】
（
1
）设第
v
层有
u
个结点
(m，则由于第
v
层的每个结点有
m
个孩子，所以第
v+1
层的结点个数为
mu
。

第
1
层有
1
个结点，第
2
层有
m
个结点， 第
3
层有
m
2
结点，用数学归纳法易知
k
层共有< br>m
k-1
个结点。

m
h
1
（
2
）整棵树结点数
=1+m+m+
„
+m=
。

m 1
2h-1
（
3
）设编号为
i
的结点双亲的结点编号为x
，将编号为
i
的结点视为完全二叉树的最后一个结点，因此，
此完全< br>m
叉树中至少有
x-l
个度为
m
的结点，而
x
号结点的度
d
（
1
≤
d
≤
m
），其余的结点均为叶子结点，
而编号
i
就是此完全
m
又树的总结局 数，于是有：

(x-1)m+d+1=i
所以有
x
imd 1
，由于
1
≤
d
≤
m
，所以有：

m
im2imim2

11x
mmm
可知：
x

im2

。


< br>m

设编号为
i
的第
j
个子结点为完全
m< br>叉树的最后一个结点
n
，此完全
m
叉树中有
i-1
个 度为
m
的结点，
m+j+1
一个度为
j
的结点，其他结点 均为叶子结点，可得：
n=(i-l)×
十、（本题15分）
【解答】在理想情况下 ，可实现散列表查找、插入、删除操作的操作时间为
O(1)
，对于本题，由于已经知道了关键字的取值范和散列表的最大插入次数，可作理想化处理哈希方法：将查找与数据在一起的哈希表一分为二 ：采
用两个数组
ht
和
elem
，其中
ht
是从
0
到
m-1
的整数数组 （做索引用）；
elem
数组的数据类型为哈希表中各元素的
类型，其元素个数为n
（即最大的插入次数），两个数组都不需要初始化。使用计数器
lastE
表示 上次所用到的
elem
中的位置，初值为
-1
。
ht[k]
中的值可能无效（用
-1
表示）也可能是
elem
的索引（用来寻找关键字为
k
的元素），如
下图所示：

具体算法实现当如下：



文件路径名
:exam8alg.h

理想散列表类

template
class IdealHashTable
{
protected:

散列表的的数据成员
:
int *ht;
用作
elem
的索引

ElemType *elem;
在放插入的哈希表的元素

int lastE;
计数器，表示上次用到的
elem
位置

int n;
最大插入次数

int m;
关键字范围
0~m-1

public:

理想散列表方法声明及重载编译系统默认方法声明
:
IdealHashTable(int maxInsertCount, int size);
构造函数

~IdealHashTable();
析造函数

void Traverse(void (*Visit)(const ElemType &)) const;
遍历散列表

bool Search(const KeyType &key, ElemType &e) const;
查寻关键字为
key
的元素

bool Insert(const ElemType &e);
插入元素
e
bool Delete(const KeyType &key, ElemType &e);
删除关键字为
key
的元素，用
e
返回元素值

IdealHashTable(const IdealHashTable ©);
复制构造函数

IdealHashTable &operator=
(const IdealHashTable ©);
赋值语句重载

};


理想散列表类的实现部分

template
IdealHashTable::IdealHashTable(int maxInsertCount, int size)

操作结果
:
构造最大插入次数为
maxInsertCount,
关键字范围为
0~size-1
的空理想散列表

{
n = maxInsertCount;
最大插入次数

m = size;
关键字范围为
0~size-1
ht = new int[n];
为
elem
索引表分配存储空间

elem = new ElemType[m];
为元素分配存储空间

lastE = -1;
初始化
lastE
for (int pos = 0; pos < n; pos++)
{
初始化
ht
ht[pos] = -1;

}
}

template
IdealHashTable::~IdealHashTable()

操作结果
:
销毁散列表

{
delete []ht;
释放
ht
delete []elem;
释放
elem
}

template
void IdealHashTable::Traverse(void (*Visit)(const ElemType &)) const

操作结果
:
依次对散列表的每个元素调用函数
(*visit)
{
for (int pos = 0; pos < m; pos++)
{
对散列表的每个元素调用函数
(*visit)
if (ht[pos] != -1) (*Visit)(elem[ht[pos]]);
}
}

template
bool IdealHashTable::Search(const KeyType &key, ElemType &e) const

初始条件
:
关键字
key
的范围为
0~m-1
，
ht[key]
的范围为
0~lastE

操作结果
:
查寻关键字为
key
的元素的值
,
如 果查找成功
,
返回
true,
并用
e
返回元素的值
,

否则返回
false
{
if (key < 0 || key >= m)
{
范围错

return false;
查找失败

}
else if (ht[key] < 0 || ht[key] > lastE || elem[ht[key]] != key)
{
表中没有要查找的元素

return false;
查找失败

}
else
{
存在要查找的元素

e = elem[ht[key]];
用
e
返回元素值

return true;
查找成功

}
}

template
bool IdealHashTable::Insert(const ElemType &e)

操作结果
:
将元素插入到
elem
数组
lastE
位置，同时修改索引值

{
KeyType key = e; e
的关键字

ElemType eTmp;
临时变量

if (key < 0 || key >= m)

{
范围错

return false;
插入失败

}
else if (Search(key, eTmp))
{
查找成功

return false;
插入失败

}
else if (lastE == n - 1)
{
超过最大插入次数

return false;
插入失败

}
else
{
elem[++lastE] = e;
修改计数器，将元素插入到表中

ht[key] = lastE;
索引表
ht
中
ht[key]记录关键字为
key
的元素在
elem
中的位置

return true;
插入成功

}
}

template
bool IdealHashTable::Delete(const KeyType &key, ElemType &e)

操作结果
:
删除关键字为
key
的数据元素
,
删除成功返回
true,
并用
e
返回元素值，否则返回
fa lse,

通过将
lastE
位置元素移到删除位置，
lastE
指向倒数第二个元素，从逻辑上完成删除

{
if (!Search(key, e))
{
查找失败

return false;
删除失败

}
else
{
查找成功

e = elem[ht[key]];
用
e
返回被删除元素值

elem[ht[key]] = elem[lastE--];
将最后元素移到所删除处
,
将修改
Las tE
指向新的末记录

int k = elem[ht[key]];
原最后元素的关键字

ht[k] = ht[key];
修改索引值

ht[key] = -1;
修改
ht [key]
为
-1
，表示关键字为
key
的元素已初删除

return true;
删除成功

}
}

template
IdealHashTable::IdealHashTable(
const IdealHashTable ©)

操作结果：由散列表
copy
构造新散列表
--
复制构造函数

{
n = copy.n;
最大插入次数

m = copy.m;
关键字范围为
0~m-1
ht = new int[n];
为
elem
索引表分配存储空间

elem = new ElemType[m];
为元素分配存储空间

lastE =
计数器，表示上次用到的
elem
位置


int pos;
临时变量

for (pos = 0; pos < m; pos++)
{
复制元素索引

ht[pos] = [pos];
复制元素索引值

}
for (pos = 0; pos < m; pos++)
{
依次复制数据元素

elem[pos] = [pos];
复制元素值

}
}

template
IdealHashTable &IdealHashTable::
operator=(const IdealHashTable ©)

操作结果：将散列表
copy
赋值给当 前散列表
--
赋值语句重载

{
if (© != this)
{
delete []ht;
释放
ht
delete []elem;
释放
elem

n = copy.n;
最大插入次数

m = copy.m;
关键字范围为
0~m-1
ht = new int[n];
为
elem
索引表分配存储空间

elem = new ElemType[m];
为元素分配存储空间

lastE =
计数器，表示上次用到的
elem
位置


int pos;
临时变量

for (pos = 0; pos < m; pos++)
{
复制元素索引

ht[pos] = [pos];
复制元素索引值

}
for (pos = 0; pos < m; pos++)
{
依次复制数据元素

elem[pos] = [pos];
复制元素值

}
}
return *this;
}