第9章 查找
1．选择题
（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
A．(n-1)/2 B． n/2 C．(n+1)/2 D．n （2）适用于折半查找的表的存储方式及元素排列要求为（ ）。
A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A．必定快 B．不一定
C．在大部分情况下要快 D．取决于表递增还是递减 （4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50
（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。
A．3 B．4 C．5 D．6 （6）折半搜索与二叉排序树的时间性能（ ）。
A．相同 B．完全不同 C．有时不相同 D．数量级都是O(log2n) （7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。 A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90） C．（100，60， 80， 90， 120，110，130） D．(100，80， 60， 90， 120，130，110)
（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。
A．LL B．LR C．RL D．RR （9）下列关于m阶B-树的说法错误的是（ ）。 A．根结点至多有m棵子树 B．所有叶子都在同一层次上
C．非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D．根结点中的数据是有序的
（10）下面关于B-和B+树的叙述中，不正确的是（ ）。
A．B-树和B+树都是平衡的多叉树 B．B-树和B+树都可用于文件的索引结构 C．B-树和B+树都能有效地支持顺序检索 D．B-树和B+树都能有效地支持随机检索 （11）m阶B-树是一棵（ ）。
A．m叉排序树 B．m叉平衡排序树 C．m-1叉平衡排序树 D．m+1叉平衡排序树 （12）下面关于哈希查找的说法，正确的是（ ）。
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
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）：
②查找元素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，请画出所得到的二叉排序树。
验算方法： 用中序遍历应得到排序结果： 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
（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
散列地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）
23
H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。
（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
① 线性探测法； ② 链地址法。 ① 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 4 1 12 1 49 1 38 2 13 1 24 2 32 1 21 2 比较次数 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8
ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11
②
ASLsucc =（1*5+2*3）/8=11/8
ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11
（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？
④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
解： （1）画表如下： 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 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/11
（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
散列地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）
H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。 （7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
① 线性探测法； ② 链地址法。
散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 4 1 12 1 49 1 38 2 13 1 24 2 32 1 21 2 比较次数 23
ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8
ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11