《数据结构》作业参考答案
一、选择题 1． a b 2． c 3． b 4． a,d 5． b 6． d 7． b 8．D 9．D 10．B 11．C 12．C 13． c 14．d 15．a 16．b 17．c
18．d 19．c 20．b 21．b 22．c 23．c 24．d 25．d 26．c
二、填空题 1．
i(i?1)?j 22．3 4
k-1kk-2
3． 2, 2-1, 2+1
4． v1, v3, v2, v4, v5 5． 4
6．数据项 7．结点的直接前驱结点， 结点的直接后继结点 8．ST.top= =-1
9．参加比较的两个字符串长度相同 10．2?1 11．120
三、算法应用题
h1．解答： 62
37 25
19 18 12 13 10 9 6 4 5
WPL=4*4+5*4+6*3+7*3+10*3+12*2+18*2 =9*4+23*3+30*2 =36+69+60 =165
2．解答：和已知序列对应的二叉树是： E
B F
A D
C G
3．
7 H I K J
4．解答：
各关键字的哈希函数值见下表：
1
10 1
3
7
6
1
3
11 10 12
key H(key) =key
19 01 23 14 55 20 84 27 68 11 10 77 6
采用开放地址法的线性探测再散列方法解决冲突，已知其装填因子??得哈希表如下：
地址 0
key 比较次数
2，对上表中的关键字序列构造所31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 23 11 10 77 1
1
3
2
01 14 55 27 68 19 20 84 1
2
1
4
3
1
1
3
在等概率情况下，其查找成功时的平均查找长度是：
ASLsucc?1?2?1?4?3?1?1?3?1?1?3?223 ?1212
5．和已知序列对应的森林如下图示：
A
B D G I
C E F J
6．解答：设这8个字母的权重为7，19，2，6，32，3，21，10
H K L
0 0 11 1 0 5 1 6 28 0 0 60 1 1 100 1 0 40 1 32 19 21 17 1 0 7 10 2 3 由上图的哈夫曼树知这8个字母的哈夫曼编码分别为0010，10，00000，0001，01，00001，11，0011
7．解答：
①如图所示的无向带权图的邻接矩阵如下图示：
1 2 3 4 5 6 1 0 6 1 5 ∞ ∞ 2 6 0 5 ∞ 3 ∞ 3 1 5 0 5 6 4 4 5 ∞ 5 0 ∞ 2 5 ∞ 3 6 ∞ 0 6 6 ∞ ∞ 4 2 6 0 按Prim算法求得的最小生成树如下图(f)所示（树中结点用粗黑实线表示）：假设初始时，树中只有一个顶点，不含有任何一条边，下图（a）～(f)为用Prim算法求其最小生成树的过程。
0 1 2 3
V1 V2 V3 V4 6 V2 5 3 6 V5 6 (a) 6 V2 5 3 6 V5 6 (d) V1 1 5 V3 4 V6 5 V4 2 6 V2 5 3 V3 6 V5 6 (e)
4 V6 V1 1 V3 5 4 V6 5 V4 2 6 V2 5 3 6 V5 6 (b) V1 1 5 V4 2 5 6 V2 5 3 6 V5 6 (f)
V1 1 5 V3 4 V6 5 V4 2 6 V2 5 3 6 V5 6 （c） V1 1 5 V3 4 V6 5 V4 2 V1 1 5 V3 4 V6 5 V4 2 ②如图所示的无向带权图的邻接表如下图示：
1 0 0 0 2 2 1 2 3 NULL 4 NULL 3 NULL 5 NULL