发布时间 : 星期二 文章数据结构复习题及答案更新完毕开始阅读
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定 D．哈希表的平均查找长度有时也和记录总数有关 （13）下面关于哈希查找的说法，不正确的是（ ）。 A．采用链地址法处理冲突时，查找一个元素的时间是相同的
B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是
相同的
C．用链地址法处理冲突，不会引起二次聚集现象 D．用链地址法处理冲突，适合表长不确定的情况
（14）设哈希表长为14，哈希函数是H(key)=key，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。
A．8 B．3 C．5 D．9
（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。
A．不一定都是同义词 B．一定都是同义词 C．一定都不是同义词 D．都相同
2．应用题
（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树；
② 若查找元素54，需依次与哪些元素比较？ ③ 若查找元素90，需依次与哪些元素比较？
④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
①先画出判定树如下（注：mid=?(1+12)/2?=6）：
30
5 63
3 7 42 87
4 24 54 72 95
②查找元素54，需依次与30, 63, 42, 54 元素比较； ③查找元素90，需依次与30, 63,87, 95元素比较；
④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。
12
7 17
2 11 16 21
4 9 13
验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21
（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 解：
（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？
④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
①画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 ②查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
③查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
④对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/11