11级数据结构期末复习(2)

检索成功的平均检索长度：ASL=(1+2*2+3*4+4*8+5*5)/20=74/20=3.7 检索不成功的平均检索长度：ASL=(5*11+6*10)/（11+10）=115/21≈5.48

P229 9、11。

9、根据已知结点序列，画出建立二叉检索树T1的过程，并画出删掉相应结点的过程。 11、(1)画出最终的二叉检索树，并求平均检索长度

P230

18、（1）用线性探查法消解地址冲突，构造哈希表（求解过程：先用哈希函数求解每个关键字的哈希地址，有地址冲突的，用冲突法消解，最后再画出哈希表）

（3）求以上两种哈希表的平均检索长度 线性探查法ASL：（1*6+2+3*3+4+9）/12=2.5 拉链法ASL：(1*6+2*4+3+4) / 12 = 1.75

19、构造哈希表，并求在等概率情况下检查成功和不成功的平均检索长度。

（１）ｋ＝３３ ｈ（３３）＝（３×３３）％１１＝０ （２）ｋ＝４１ ｈ（４１）＝（３×４１）％１１＝２ （３）ｋ＝２０ ｈ（２０）＝（３×２０）％１１＝５ （４）ｋ＝２４ ｈ（２４）＝（３×２４）％１１＝６ （５）ｋ＝３０ ｈ（３０）＝（３×３０）％１１＝２

此时发生冲突，ｄ１＝ｈ（３０）＝２, d2＝（２＋（７×３０）％１０＋１）％１１＝３ （６）ｋ＝１３ ｈ（１３）＝（３×１３）％１１＝６

此时发生冲突，ｄ１＝ｈ（１３）＝６, d2＝（６＋（７×１３）％１０＋１）％１１＝８ （７）ｋ＝０１ ｈ（３３）＝（３×１）％１１＝３

此时发生冲突，ｄ１＝ｈ（１）＝３, d2＝（３＋（１×７）％１０＋１）％１１＝０ 此时发生冲突，ｄ２＝ｈ（１）＝０, d3＝（０＋（７×１）％１０＋１）％１１＝８ 此时发生冲突，ｄ３＝ｈ（１）＝８, d4＝（８＋（１×７）％１０＋１）％１１＝５ 此时发生冲突，ｄ４＝ｈ（１）＝５, d5＝（５＋（１×７）％１０＋１）％１１＝２ 此时发生冲突，ｄ５＝ｈ（１）＝２, d6＝＝（２＋（１×７）％１０＋１）％１１＝１０ （８）ｋ＝６７ ｈ（６７）＝（３×６７）％１１＝３

此时发生冲突，ｄ１＝ｈ（６７）＝３, d2＝（３＋（７×６７）％１０＋１）％１１＝２ 此时发生冲突，ｄ２＝ｈ（６７）＝２, d3＝＝（２＋（７×６７）％１０＋１）％１１＝１

从而得到相应的散列表如下。

从而可求出检索成功时的平均检索长度为

ＡＳＬ＝（１＋１＋１＋１＋２＋２＋６＋３）／８＝１７／８

由已知条件知，散列表表长为１１，表中记录数为８，且采用开放定址法解决冲突，从 而可得装填因子α＝８／１１，所以检索失败（即不成功）时的平均检索长度为 ＡＳＬ＝１／（１－α）＝１／（１－８／１１）＝１１／３

排序

复习内容：要求掌握各种算法的基本思想，给出实例能写出每一趟的排序结构 插入排序：直接插入排序（算法、时间复杂度、稳定性）、希尔排序（算法、排序过程、时间复杂度、稳定性）

交换排序：冒泡排序（算法、时间复杂度、稳定性）、快速排序（算法、排序过程、时间复杂度、空间复杂度、稳定性）

选择排序：直接选择排序（算法、时间复杂度、稳定性）、（大头、小头）堆排序（算法、构造和筛选过程、时间复杂度、稳定性）

二路归并排序（排序过程、时间复杂度、空间复杂度、稳定性）

P263课后习题 第3、15题 15： (1)(2)(4)为堆;

(3)不为堆，调整后为 （100 98 66 85 80 40 60 77 82 10 20）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库11级数据结构期末复习(2)在线全文阅读。