习题八 查找
一、单项选择题
1．顺序查找法适合于存储结构为（ ）的线性表。
A． 散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( )
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 5．当采用分块查找时，数据的组织方式为 ( )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ ）。
A．正确 B. 错误
7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。
A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性
9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
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) 10．下图所示的4棵二叉树,( )是平衡二叉树。
（A） （B） （C） （D） 11．散列表的平均查找长度（ ）。
A． 与处理冲突方法有关而与表的长度无关 B． 与处理冲突方法无关而与表的长度有关 C． 与处理冲突方法有关且与表的长度有关 D． 与处理冲突方法无关且与表的长度无关
12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个
记录。
A．1 B. 2 C. 3 D. 4
13. 关于杂凑查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是
相同的
（3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
14. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
15. 将10个元素散列到个单元的哈希表中，则（ ）产生冲突。
A. 一定会 B. 一定不会 C. 仍可能会
二、填空题
1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____. 3．一个无序序列可以通过构造一棵_ _ _ _树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
4. 哈希表是通过将查找码按选定的__ __和 __ __，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_ __和 __ __。一个好的哈希函数其转换地址应尽可能__ __，而且函数运算应尽可能__ __。
5. 平衡二叉树又称__________，其定义是_____ _____。
6. 在哈希函数H（key）=key%p中，p值最好取__________。
7．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。
8. __________法构造的哈希函数肯定不会发生冲突。
9. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
10．在散列存储中，装填因子α的值越大，则__ __；α的值越小，则__ __。
11. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。 #define N /*学生人数*/
int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int head=1,mid,rear=N; do {mid=(head+rear)/2;
if(x<=a[mid]) __(1) __ else __(2)_ _; }while(__(3)_ _); if (a[head] 三、应用题 1．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？ 2. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表 222 长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 3. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。 4. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。 （1） 按次序构造一棵二叉排序树BS。 （2） 依此二叉排序树，如何得到一个从大到小的有序序列？ （3） 画出在此二叉排序树中删除“66”后的树结构。 5. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？ 6. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。 7. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题： (1).画出描述折半查找过程的判定树； (2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较? (4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。 四、算法设计题 1. 设记录R1,R2,…,Rn按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度。 2．试编写算法求出指定结点在给定的二叉排序树中所在的层数。 3. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。