数据结构单元9

（2）在二叉树排序BT中删除“12”后的树结构：

1 1

13 10 5 或 513

3 8 3 8

7 10 7 9

9

5． 对于给定结点的关键字集合K={34，76，45，18，26，54，92，38}， （1）试构造一棵二叉排序树；

（2）求等概率情况下的平均查找长度ASL。 解：

（1）构造二叉排序树

34

18 76

92 26 45 38 54

（2）ASL=（1*1+2*2+3*3+4*2）/ 8 =2.75 （或=11/4）

6． 对于给定结点的关键字集合K={4，8，2，9，1，3，6，7，5}， （1）试构造一棵二叉排序树；

（2）求等概率情况下的平均查找长度ASL。 解：

（1）构造二叉排序树

4

2 8 1 3 5 67 9

（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

23 6212 32 95 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 23 10 ∧ 11 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;