11136(a)115346(b)34111346(c)1153354642242242(d)(e)
图 7-11 普里姆算法构造最小生成树的过程
4．使用克鲁斯卡尔算法构造出如图 7-7 所示的图 G 的一棵最小生成树。
16776425202351541812810253
图7-7 无向图G
解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图 7-12所示。
21
1256374125346(a)(b)6(c)16742583764112525836(d)464(e)16181245825376(f)4
图 7-12 克鲁斯卡尔算法构造最小生成树的过程
第8章 查找
单项选择题
1.顺序查找法适合于存储结构为 B 的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 C. 索引存储
2.对线性表进行折半查找时，要求线性表的存储方式是 C 。 A. 顺序存储 B. 链接存储
C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储
3.对有 18 个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为 D 。 A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3
4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 A 查找方法。
22
A. 分块 B. 顺序 C. 二分 D. 散列
5.有一个有序表为{2，5，7，11，22，45，49，62，71，77，90，93，120}，当折半查找值为 90 的结点时，经过 C 次比较后查找成功。 A. 1 B. 2 C. 4 D. 8
6.设哈希表长 m=14，哈希函数 H(key)=key % 11。表中已有 4 个结点：addr(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址为空，如用线性探测再散列处理冲突，关键字为 49 的结点的地址是 A 。
A. 7 B. 3 C. 5 D. 4
7.在采用链接法处理冲突的开散列表上，假定装填因子a 的值为 4，则查找任一元素的平均查找长度为 A 。
A. 3 B.3.5 C.4 D.2.5 填空题
1.在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是 散列表查找 。
2.二分查找的存储结构仅限于 有序的顺序存储结构 。
3.在散列存储中，装填因子α的值越大，则 ① ；α的值越小，则 ② 。 ① 存取元素时发生冲突的可能性就越大 ② 存取元素时发生冲突的可能性就越小 4.对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的______左子树_____上继续查找。
5.高度为8的平衡二叉树至少有___54____个结点。
6. 在散列函数 H(key)=key % p 中，p 应取 素数 。
例题解析
【例8-1】设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key % 13 ,采用开放地址法的二次探测再散列方法解决冲突，试在 0～18 的散列地址空间中对该关键字序列构造哈希表。
解：依题意，m=19，二次探测再散列的下一地址计算公式为：
d1=H(key)
d2j=( d1+j*j) % m
d2j?1=( d1-j*j) % m； j=1，2，... 其计算函数如下：
H(19)=19 % 13=6 H(01)=01 % 13=1
23
H(23)=23 % 13=10 H(14)=14 % 13=1 (冲突) H(14)=(1+1*1) % 19=2 H(55)=55 % 13=3 H(20)=20 % 13=7 H(84)=84 % 13=6 (冲突) H(84)=(6+1*1) % 19=7 (仍冲突) H(84)=(6-1*1) % 19=5 H(27)=27 % 13=1 (冲突)
H(27)=(1+1*1) % 19=2 (冲突) H(27)=(1-1) % 19=0 H(68)=68 % 13=3 (冲突) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=10 % 13=10 (冲突) H(10)=(10+1*1) % 19=11 (仍冲突) H(10)=(10-1*1) % 19=9 H(77)=77 % 13=12
因此：各关键字的记录对应的地址分配如下： addr(27)=0
addr(01)=1 addr(14)=2 addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=11 addr(77)=12
其他地址为空。 综合题
1.设散列表为 T［0..12］，散列函数为 H（key）= key，给定键值序列是｛39，36，28，38，44，15，42，12，06，25｝，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和查找失败时的平均查找长度。
24
解 用散列函数 H（key）= key% 13计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。
键值序列：｛39，36，28，38，44，15，42，12，06，25｝ 散列地址： 0，10，2，12，5，2，3，12，6，12 （1）线性探查法处理冲突
用线性探查法处理冲突构造的散列表见表8-1所示。
表8-1 用线性探查法处理冲突构造的散列表
下标 T［0..12］ 查找成功探查次数 查找失败探查次数
0 1 9
1 3 8
2 1 7
3 2 6
4 2 5
5 1 4
6 1 3
7 9 2
8 1
9 1
10 11 12 36 1 2
1
38 1 10
39 12 28 15 42 44 06 25
在等概率的情况下，查找成功的平均查找长度 ASL=（1×6+2×2+3×1+9×1）/10=2.2
设待查键值 k不在散列表中：若 H（k）= k% 13= d，则从 i=d开始顺次与 T［i］位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0，则必须将 k与 T［0］、T［1］、?、T［8］中的键值进行比较之后，发现 T［8］为空，比较次数为 9、类似地可对 k% 13=1，2，3，?，12进行分析可得查找失败的平均查找长度。
ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突
用拉链法处理冲突构造的散列表见图8-2所示。
图8-2 拉链法处理冲突构造的散列表
在等概率的情况下查找成功的平均查找长度：
25