（2）ASL=（1*1+2*2+3*4+4*2）/ 9 =2.78 （或=25/9）
7． 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：长度为10的判定树：
5 ------------------------------- 1次能找到
2 8 ------------------------ 2次能找到
1 3 6 9 ------------------ 3次能找到
4 7 10 ------------- 4次能找到
ASL=1/10（1*1+2*2+3*4+4*3）=2.9
8．二叉排序树如图所示，分别画出：
（1） 画出删除关键字15以后的二叉树，并要求其平均查找长度尽可能小； （2） 在原二叉排序树（即没有删除15）上，插入关键字20。
40
8 90 95 15 62
23 12
32 解：
（1） （2）
40
8 90
95 23 62 32 12
40 8 15 6212 20 23 32 90 95 9． 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为13，散列函数为：H（K）=K % 13。
试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。
解：（1） 线性探测再散列解决冲突时所构造的散列表：
0 1 14 2 1 3 68 4 27 5 55 6 19 7 20 8 84 9 79 10 23 11 11 12 10 ① ② ① ④ ③ ① ① ③ ⑨ ① ① ③ （2）平均查找长度ASL=（1*6+2*1+3*3+4*1+9*1）/12=30/3=3
10． 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。 设散列函数为：H（K）=K % 11。
试画出平方探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。 解：
（1） 平方探测再散列解决冲突时所构造的散列表。
0 11 1 22 2 3 3 47 4 92 5 16 6 7 7 8 29 9 8 10 ① ② ② ① ① ① ① ② ②
（2） 平均查找长度ASL=（1*5+2*4）/9 = 13/9 = 5/3 （或1.44）
11． 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为13，散列函数为：H（K）=K % 13。
试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。 解：（1） 链地址法解决冲突时所构造的哈希表。
0 ∧ 1 1 14 27 79 ∧ 2 ∧ 3 68 55 ∧ 4 ∧ 5 ∧ 6 7 19 84 ∧ 20 ∧ 8 ∧ 9 ∧ 10 11 23 10 ∧ 11 ∧ 12 ∧ （2）平均查找长度ASL=（1*6+2*4+3*1+4*1）/12 = 21/12 =7/4 (或1.75)
12． 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。 设散列函数为：H（K）=K 。
试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。 解：
（1） 链地址法解决冲突时所构造的哈希表。 0 11 47 22 ∧
1 ∧ 2 ∧ 3 4 5 3 ∧
92 ∧ 16 ∧ 7 6 ∧ 7 8 29 ∧
8 ∧ 9 ∧ 10 ∧ （2） 平均查找长度ASL=（1*6+2*3）/9 = 12/9 = 4/3 （或1.33）
五．算法设计题
1．设单链表的结点是按关键字从小到大排列的，试写出对此链表进行查找的算法。如果查找成功，则返回指向关键字为x的结点的指针，否则返回NULL。
2．试设计一个在用开放地址法解决从突的散列表上删除一个指定结点的算法。
3．设给定的散列表存储空间为H[1-m]，每个单元可存放一个记录，H[i]的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突的方法为线性控测法，编写一个函数将某记录R填入到散列表H中。
1．解：实现本题功能的算法如下，如果查找成功，则返回指向关键字为x的结点的指针，否则返回NULL。
node *sqsearch(node*head，int x) {
node *p=head; while (p!=NULL) { if (x>p->key) p=p->link; else
if (x==p->key)
return p; else
{ p=NULL;
return p;
}
}
}
2．解：算法思想是：首先计算要删除的关键字为k的记录所在的位置，将其置为空(即删除)，然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录，如果有则将记录移到原来k所在的位置，直至表中没有与k冲突的记录为止。实现本题功能的算法如下： void delete(sqlist r，int n，int k)
{ int h,h0,h1; h=k%n;
while (r[h].key!=k) h=(h+1)％n; r[h]=NULL; h0=h;
hl=(h+1)％n; while (hl!=h) {
while (r[h1].key％n!=h) hl=(hl+1)％n; r[h0]=r[h1]; r[h1]=NULL; h0=h1;
h1=(hl+1)％n;
}
}
3．解：本题的算法思想：先计算地址H(R.key)，如果没有冲突，则直接填入;否则利用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实现本题功能的函数如下： void insert(record H,int m,record R) { int i;
i=H(R.key); if (H[i]==NULL)
H[i]=R; else {
while (H[i]!=NULL) i=(i+1)%(m+1); H[i]=R;
}
}
模拟考试
查找应用题
1． 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4， 试画出二叉排序树的草图，并回答下列问题。
（1） 在二叉排序树查找9，依次和哪些关键字进行比较。 （2） 求平均查找长度ASL 解：
4 2 9 11 13
8 2
1621 7 17 12 （1）查找过程：12，7，11，9。
（2）ASL＝1/10（1×1＋2×2＋3×4＋4×3）＝29/10≈2.9 2．折半查找的的判定树如下图所示，
（1） 若查找元素56，需依次与哪些元素比较？ （2） 若查找元素16，需依次与哪些元素比较？
（3） 假定每个元素的查找概率相等，求查找成功时的平均查找长度（保留2位小数）。 解：
（1）查找元素56，需依次与32, 65, 47, 56 等元素比较 （2）查找元素16，需依次与32, 5，18, 16等元素比较
3． 设哈希表的地址范围为0～17，哈希函数为：H（K）＝K 。其中K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）。
其哈希表如下：
0 1 2
3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
30 31 46 47
4 4 2
4 16 56 78 96 3 18 4780 5 32 65 （3）ASL＝1/12（1×1＋2×2＋3×4＋4×5）＝37/12≈3.08
32 17 63 49 试回答下列问题：
24 40 10