12365847 图7-5无向图G
3．使用普里姆算法构造出如图 7-6 所示的图 G 的一棵最小生成树。1652155432364566 图7-6无向图G
解：使用普里姆算法构造棵最小生成树的过程如图 7-11所示。
21
11136(a)115346(b)34111346(c)1153354642242242(d)(e)
图 7-11 普里姆算法构造最小生成树的过程
4．使用克鲁斯卡尔算法构造出如图 7-7 所示的图 G 的一棵最小生成树。
16776425202351541812810253
图7-7 无向图G
解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图 7-12所示。
22
1256374125346(a)(b)6(c)16742583764112525836(d)464(e)16181245825376(f)4
图 7-12 克鲁斯卡尔算法构造最小生成树的过程
第8章 查找
单项选择题
1.顺序查找法适合于存储结构为 的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 C. 索引存储
2.对线性表进行折半查找时，要求线性表的存储方式是 。 A. 顺序存储 B. 链接存储
C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储
3.对有 18 个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为 。 A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3
4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。
23
A. 分块 B. 顺序 C. 二分 D. 散列
5.有一个有序表为{2，5，7，11，22，45，49，62，71，77，90，93，120}，当折半查找值为 90 的结点时，经过 次比较后查找成功。 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. 7 B. 3 C. 5 D. 4
7.在采用链接法处理冲突的开散列表上，假定装填因子a 的值为 4，则查找任一元素的平均查找长度为 。
A. 3 B.3.5 C.4 D.2.5 1-4 BCDA 5-7CAA 填空题
1.在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是 。 2.二分查找的存储结构仅限于 。
3.在散列存储中，装填因子α的值越大，则 ；α的值越小，则 。 ① 存取元素时发生冲突的可能性就越大 ② 存取元素时发生冲突的可能性就越小 4.对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的___________上继续查找。
5.高度为8的平衡二叉树至少有_______个结点。 6. 在散列函数 H(key)=key % p 中，p 应取 。
1. 散列表查找
2. 有序的顺序存储结构 3. ① ② 4. 左子树 5. 54 6. 素数
例题解析
【例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
24
d2j?1=( d1-j*j) % m； j=1，2，... 其计算函数如下：
H(19)=19 % 13=6 H(01)=01 % 13=1 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
其他地址为空。
25