第七章 查找

课程名称：算法与数据结构 总分：61分 答题时长：120分钟 出卷人：刘辉

一、单项选择题：(共13题，26分)
1、 下列对查找表经常进行的操作不正确的是（）
查询某个“特定的”数据元素是否在表中
检索某个“特定的”数据元素的各种属性
在查找表中插入或删除一个数据元素
对查找表进行排序或筛选
2、 下面关于“静态查找”和“动态查找”正确的是（ ）
动态查找不对查找表进行任何插入、删除元素的操作
静态查找在查找过程中需要对表元素进行插入或删除操作
静态查找不对查找表进行任何插入、删除元素的操作
顺序查找属于动态查找
3、 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
(n-1)/2
n/2
(n+1)/2
n
4、 以下不属于线性表的查找方法的是（ ）
顺序查找
树表的查找
折半查找
分块查找
5、 在顺序查找算法中使用监视哨可以免去查找过程中每一步都要检测整个表是否查找完毕，下面循环语句正确的是（ ）
for(i= ST.length; i>=1; - -i);
for(i= ST.length; ST.elem[i].key！=key; --i);
for(i= ST.length-1; i>=0; - -i);
for(i= ST.length; ST.elem[i].key==key; --i);
6、 适用于折半查找的表的存储方式及元素排列要求为（ ）。
链接方式存储，元素无序
链接方式存储，元素有序
顺序方式存储，元素无序
顺序方式存储，元素有序
7、 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
20，70，30，50
30，88，70，50
20，50
30，88，50
8、 对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。
3
4
5
6
9、 折半搜索与二叉排序树的时间性能（ ）。
相同
完全不同
有时不相同
数量级都是O(log2n)
10、 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。
顺序查找
折半查找
分块查找
哈希查找
11、 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。
（100，80， 90， 60， 120，110，130）
（100，120，110，130，80， 60， 90）
（100，60， 80， 90， 120，110，130）
(100，80， 60， 90， 120，130，110)
12、 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。
LL
LR
RL
RR
13、 在平衡二叉树中为调整平衡因子，需做LR平衡，则平衡旋转顺序为（ ）
先逆时针后顺时针
逆时针
顺时针
先顺时针后逆时针
二、简答题：(共3题，15分)
1、 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

① 画出描述折半查找过程的判定树；

② 若查找元素54，需依次与哪些元素比较？

③ 若查找元素90，需依次与哪些元素比较？

④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

2、 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。
3、 已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

三、问答题：(共4题，20分)
1、 写出折半查找的一般算法。
2、 试写出折半查找的递归算法。
3、 写出用二叉排序树查找的递归算法。
4、 试写一个判别给定二叉树是否为二叉排序树的算法。