[项目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). 计算折半查找时，查找成功的平均查找长度和查找不成功的平均查找长度。
2.【2010统考真题】将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为 H(Key)=(key×3) mod 7，处理冲突采用线性探测在散列法，要求装填因子为0.7。
1). 请画出所构造的散列表。
2). 分别计算等概率下，查找成功和查找不成功的平均查找长度
3. 一棵二叉排序树按先序遍历得到的序列为 (50, 38, 30, 45, 40, 48, 70, 60, 75, 80)，试画出该二叉排序树，并求出等概率下查询成功和查找失败的平均查找长度。
4. 依次把结点 (34, 23, 15, 98, 115, 28, 107) 插入初始状态为空的平衡二叉树，使得在每次插入后保持该树仍然是平衡二叉树。依次画出每次插入后所形成的平衡二叉排序树。
【选做题】[奖励分：0~1]
如下图所示的3阶B树，依次执行如下操作，画出各步操作的结果。🏷️Img_Pro1309
1). 插入90；2). 插入25；3). 插入45；4). 删除60；5). 删除80
【扩展练习】
1. 使用散列函数H(key)=key%11，把一个整数值转换成散列表下标，先要把数据 {1, 13, 12, 34, 38, 33, 27, 22} 依次插入散列表。
1). 分别使用线性探测法和链地址法构造散列表。
2). 针对以上两种散列构造法，分别确定查找成功所需的平均查找长度和查找失败时所需的平均查找长度。
2. 已知一组关键字为 {26, 36, 41, 38, 44, 15, 68, 12, 6, 51, 25}，用链地址法解决冲突，加速装填因子 ，散列函数的形式为H(Key)=Key%p，回答以下问题：
1). 构成出散列函数。
2). 分别计算出等概率情况下，查找成功和查找失败时的平均查找长度。（查找失败时，只需计算与关键字的比较次数，无需计算空结点的比较）
3. 设散列表为HT[0...12]，即表的大小为 m=13。现采用双散列法解决冲突，散列函数和再散列函数分别为：。其中，函数REV(x)表示颠倒十进制x的各位，如REV(37)=73, REV(7)=7等。若插入的关键码序列为(2, 8, 31, 20, 19, 18, 53, 27)，请回答：
1). 画出插入这8个关键码后的散列表。
2). 计算查找成功的平均查找长度ASL。
4. 按照序列 (40, 72, 38, 35, 67, 51, 90, 8, 55, 21) 建立了一棵二叉排序树，画出该树，并求出在等概率情况下，查找成功的平均查找长度。
5. 给定一个关键字集合 {25, 18, 34, 9, 14, 27, 42, 51, 38}，假定查找各关键字的概率相同，请画出其最佳二叉排序树。