数据结构习题及答案

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．解答：二叉排序树如图１．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