《数据结构》作业参考答案

一、选择题 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