[项目013] 查找的综合应用 显示答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。

最后更新：2023年12月23日

---

【课后作业】

作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。

1. 有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。
1). 试画出对其进行折半查找的判定树。
2). 若查找关键字为275或684的元素，将依次与表中哪些元素比较？
3). 计算折半查找时，查找成功的平均查找长度和查找不成功的平均查找长度。

答案及解析：
1). 判定树如下图所示：🏷️Img_Pro1301

2). 若查找关键字275，则依次查找的元素为509，154，275，共比较3次；若查找684，则依次查找的元素为509，677，897，765，共比较4次。

3). 在查找成功时，会找到图中的圆形结点，其平均查找长度为：
$ASL_{成功} = (1×1 + 2×2 + 3×4 + 4×7)/14 = 45/14$

在查找失败时，会找到图中的方形结点，其平均查找长度为：
$ASL_{失败} = (3×1 + 4×14)/15 = 59/15$

2.【2010统考真题】将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为 H(Key)=(key×3) mod 7，处理冲突采用线性探测在散列法，要求装填因子为0.7。
1). 请画出所构造的散列表。
2). 分别计算等概率下，查找成功和查找不成功的平均查找长度

答案及解析：
1). 构造散列表
根据题意可计算得到散列表长度 = $n/\alpha = 7/0.7 = 10$

关键字	7	8	30	11	18	9	14
哈希值	0	3	6	5	5	6	0

由此可得散列表：

散列地址	0	1	2	3	4	5	6	7	8	9
关键字	7	14	-	8	-	11	30	18	9	-
比较次数	1	2	-	1	-	1	1	3	3	-

2). 计算平均查找长度
$ASL_{成功} = (1×4+2+3×2)/7 = 12/7$

由于哈希函数的模长p=7，因此只需要考查散列地址为0~6的失败情况，遇到关键字为空时，比较停止。

$ASL_{失败} = (3+2+1+2+1+5+4)/7 = 18/7$

注意：此题未明确指出只计算关键词，因此需要对空结点进行比较。

3. 一棵二叉排序树按先序遍历得到的序列为 (50, 38, 30, 45, 40, 48, 70, 60, 75, 80)，试画出该二叉排序树，并求出等概率下查询成功和查找失败的平均查找长度。

答案及解析：
对于二叉排序树来说，其中序序列为有序序列。因此，根据先序遍历序列可得中序遍历序列为: (30, 38, 40, 45, 48, 50, 60, 70, 75, 80)。
根据先序遍历和中序遍历序列，可画出该二叉排序树： 🏷️Img_Pro1304

查询成功的平均查找长度：$ASL_{成功} = (1+2×2+3×4+4×3)/10 = 29/10 = 2.9$

查询失败的平均查找长度：$ASL_{失败} = (3×5+4×6)/11 = 39/11$

4. 依次把结点 (34, 23, 15, 98, 115, 28, 107) 插入初始状态为空的平衡二叉树，使得在每次插入后保持该树仍然是平衡二叉树。依次画出每次插入后所形成的平衡二叉排序树。

答案及解析：
🏷️Img_Pro1306

5. 给定一组关键字 {20, 30, 50, 52, 60, 68, 70}，给出创建一棵3阶B树的过程。

答案及解析：
🏷️Img_Pro1308

【选做题】[奖励分：0~1]

如下图所示的3阶B树，依次执行如下操作，画出各步操作的结果。🏷️Img_Pro1309

1). 插入90；2). 插入25；3). 插入45；4). 删除60；5). 删除80

答案及解析：
🏷️Img_Pro1309Ans

【扩展练习】

1. 使用散列函数H(key)=key%11，把一个整数值转换成散列表下标，先要把数据 {1, 13, 12, 34, 38, 33, 27, 22} 依次插入散列表。
1). 分别使用线性探测法和链地址法构造散列表。
2). 针对以上两种散列构造法，分别确定查找成功所需的平均查找长度和查找失败时所需的平均查找长度。

答案及解析：

关键字	1	13	12	34	38	33	27	22
哈希值	1	2	1	1	5	0	5	0

1. 线性探测法

散列地址	0	1	2	3	4	5	6	7
关键字	33	1	13	12	34	38	27	22
比较次数	1	1	1	3	4	1	2	8

$ASL_{成功} = (1+1+1+3+4+1+2+8)/8 = 21/8$
$ASL_{失败} = (9+8+7+6+5+4+3+2+1+1+1)/11 = 47/11$

2. 链地址法
   🏷️Img_Pro1302

$ASL_{成功} = (1×4+2×3+3×1)/8 = 13/8$
$ASL_{失败} = (3+4+2+1+1+3+1+1+1+1+1)/11 = 19/11$

2. 已知一组关键字为 {26, 36, 41, 38, 44, 15, 68, 12, 6, 51, 25}，用链地址法解决冲突，加速装填因子 $\alpha=0.75$，散列函数的形式为H(Key)=Key%p，回答以下问题：
1). 构成出散列函数。
2). 分别计算出等概率情况下，查找成功和查找失败时的平均查找长度。（查找失败时，只需计算与关键字的比较次数，无需计算空结点的比较）

答案及解析：
1). 根据装填因子计算公式 $\alpha = n/m$，可得散列表表长 $m=n/\alpha = 11/0.75 = 15$（向上取整）。此时，模数p = 13，即散列函数为 H(key) = key%13。

2). 计算查找成功和查找失败时的平均查找长度

关键字	26	36	41	38	44	15	68	12	6	51	25
哈希值	0	10	2	12	5	2	3	12	6	12	12

根据哈希值可得链地址表：🏷️Img_Pro1303

$ASL_{成功} = (1×7+2×2+3×1+4×1)/11 = 18/11$
$ASL_{失败} = (1+0+2+1+0+1+1+0+0+0+1+0+4)/13 = 11/13$

注意：在本题中，计算失败时的评价查找长度只需计算与关键字的比较次数，无需计算空结点的比较。若需计算空结点的比较次数时，失败时的平均查找长度 $ASL_{失败} = (2+1+3+2+1+2+2+1+1+1+2+1+5)/13 = 24/13$

3. 设散列表为HT[0...12]，即表的大小为 m=13。现采用双散列法解决冲突，散列函数和再散列函数分别为：$H_0(Key)=Key\%13, H_i=(H_{i-1} + REV(Key+1)\%11 + 1)\%13, i=1,2,3,...,m-1$。其中，函数REV(x)表示颠倒十进制x的各位，如REV(37)=73, REV(7)=7等。若插入的关键码序列为(2, 8, 31, 20, 19, 18, 53, 27)，请回答：
1). 画出插入这8个关键码后的散列表。
2). 计算查找成功的平均查找长度ASL。

答案及解析：
1). 构造散列表

关键字	2	8	31	20	19	18	53	27
哈希值	2	8	5	7	6	5(9)	1	1(0)

在上表中，括号中的值为冲突后，使用再散列函数修正后的值，计算方法如下：
H1(18)=(H(18)+REV(19)%11+1)%13 = (5+3+1)%13 = 9，没有冲突。
H1(27)=(H(27)+REV(82)%11+1)%13 = (1+5+1)%13 = 7，发生冲突。
H2(27)=(H1(27)+REV(82)%11+1)%13 = (7+5+1)%13 = 0，没有冲突。

由此可得散列表如下：

散列地址	0	1	2	3	4	5	6	7	8	9	10	11	12
关键字	27	53	2	-	-	31	19	20	8	18	-	-	-
比较次数	3	1	1	-	-	1	1	1	1	2	-	-	-

2). 计算查询成功的的平均查找长度：
$ASL_{成功} = (1×6+2+3)/8 = 11/8$

4. 按照序列 (40, 72, 38, 35, 67, 51, 90, 8, 55, 21) 建立了一棵二叉排序树，画出该树，并求出在等概率情况下，查找成功的平均查找长度。

答案及解析：
根据题意可获得二叉排序树如下：🏷️Img_Pro1305

$ASL_{成功} = (1+2×2+3×3+4×2+5×2)/10 = 32/10 = 3.2$

5. 给定一个关键字集合 {25, 18, 34, 9, 14, 27, 42, 51, 38}，假定查找各关键字的概率相同，请画出其最佳二叉排序树。

答案及解析：

提示：

1. 当关键字概率相同时，最佳二叉排序树即为高度最小的二叉排序树。
2. 高度最小的二叉排序树即为折半查找二叉排序树，它是一棵平衡二叉树；平衡二叉树并非总是最佳二叉排序树。
3. 计算最小二叉排序树的基本思想是，先对关键字进行排序，然后按照折半查找判别树的方法构建二叉排序树。

1). 对给定关键字进行排序得：
{9, 14, 18, 25, 27, 34, 38, 42, 51}。

2). 构建二叉排序树
🏷️Img_Pro1307