数据结构习题及答案 下载本文

count1(r—>rchild,x,k);

} }

13./*从二叉树中查找出所有结点的最大值并返回*/ datatype maximum(bitreptr r) {static datatype max=0; if (r!=NULL)

{static datatype k1,k2; k1=maximum(r—>lchild); k2=maximum(r—>rchild); if (k1>max) max=k1; else if (k2>max) max=k2;

else if(r—>data>max)max=r—>data; }

return max;

}

14.依题意可以设这8个字母分别为A,B,C,D,E,F,G,H,则依据哈夫曼树的构造方法可得其对应的哈夫曼树为: A B C D E F G H 7 19 2 6 32 3

21 10

根据左0右1的原则可得各字母对应的哈夫曼编码为: A.1010 B.00 C.10000 D.1001 E.11 F.10001

G.01 H.1011

15.深度优先搜索序列:0,2,3,5,6,1,4

广度优先搜索序列:0,2,3,5,6,1,4 16.深度优先搜索序列:0,3,6,4,1,5,2 广度优先搜索序列:0,3,2,6,5,4,1 17. 始点 终点

最短路径 最短路径长度 V1

V2

(V1,V2) 4

V1 V3

(V1,V2,V3) 6 V2 V1

V3

(V2,V3,V1) (V2,V3) 5 2

V3 V1 V2

(V3,V1)

(V3,V1,V2)

3 7

18.最小生成树如图1.29所示。

19.生成的二叉排序树如图1.30所示。 2 1 2 6

图1.29

图1.30 平均查找长度:ASL=(1+2×2+3×4+4×4)/11=3 20.折半查找判定树如图1.31所示。

平均查找长度:ASL=(1+2×2+3×4+4×3)/10=2.9 图1.31 21.解答:二叉排序树如图1.32所示。

平均查找长度: ASL=(1+2×2+3×3+4×2+5×2)/10=3.2 图1.32

22.得到的链式哈希列表如图1.33所示。

平均查找长度:ASL=(1×8+2×3+3×1)/12=17/12 0 1 2 3 80 36 25 4 70 48 5 49 6 94 7 18 29 8 63 9 75 10 32 23.(1) 初始状态 [46] 74 53 14 26 38 86 65 27

34

第一趟 [46 74] 53 14 26 38 86 65 27 34

第二趟 [46 53 74] 14 26 38 86 65 27 34

第三趟 [14 46 53 74] 26 38 86 65 27 34

第四趟 [14 26 46 53 74] 38 86 65 27