文档介绍：、选择题(10*2%=20%)
for (j=1; j<=n;j++)
for (k=n; k>=1; k/=2)
count++;
A、O(n2) B、O(nlogn) C、O(logn) D、O(n)
对某个无向图结点？
森林中共有几个叶子结点？
解答：
(1) 3 (2 分)
A C F (1 分)
6 2 3 (1 分)
6 (1 分)
2、（6分）用Prim算法（初始顶点集S = {7}）构造出下图的一棵最小生成树，请用图示法
画出其构造过程。
图解：（每图1分）
①
② ③
⑤ ⑥
（1）
（6分）已知序列{17, 31, 13, 11, 20, 35, 25, 8},请将上述序列初始建为一个极小化堆，并给出输出前两个最小关键字后重建的堆。（要求画出初始建堆和两次调整后堆的示意图）。
图解:
（每图2分）
4. （5 分）设有一组关键字｛10 100 32 45 58 126 3 29 200 400 0｝散列表大小 hashSize=13, 表项下标从0到12,散列函数h（x）采用先将关键码各位数字折叠相加，再用%hashSize将相加的结果映像到表中的办法，采用二次散列技术（h2i-1（x）=|h（x）+i2|%hashsize, h2i（x）=|h（x）-i2|%hashsize解决冲突，画出相应的闭散列表，并指出每一个产生冲突的关键码分别产生了多少次冲突。
解答：（）
下标
关键字
冲突次数
0
58
0
1
10
0
2
100
1
3
3
0
4
400
0
5
32
0
6
200
3
7
8
9
45
0
10
126
1
11
29
0
12
0
9
5. （6分）已知如图所示的有向图，请按照Dijkstra算法找出顶点A到所有其它顶点的最短路径。（要求给出具体迭代过程）
解答：(，)
迭代
S
U
Dist[B]
Dist[C]
Dist[D]
Dist[E]
Dist[F]
Dist[G]
初始
A
-
5
3
8
8
8
8
1
{A,C}
C
5
3
10
10
8
8
2
{A,C,B}
B
5
3
10
8
8
6
3
{A,C,B,G}
G
5
3
10
7
8
6
4
{A,C,B,G,E}
E
5
3
9
7
8
6
5
{A,C,B,G,E,F}
F
5
3
9
7
8
6
6
{A,C,B,G,E,F,D}
D
5
3
9
7
8
6
A-B： 5
A—C： 3
A—B — G — E — D： 9
A—B — G — E： 7
A—B — G — E—F： 8
A—B — G： 6
四、程序填空题(共6分)
1、(6分)下列算法实现在中序线索二叉树中求结点p的前驱，请在空白处填入正确的语句或表达式。
ThreadedNode *Predecessor( ThreadedNode *p )
{