Ch7集合与搜索
一、选择题
（共12题）
1、从供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句，将其编号填入相应的括号内。（每小题1分，共5分）——（page 168） （1） 对线性表进行折半搜索时，要求线性表必须（ A ）。
（2） 采用顺序搜索算法查找长度为n的线性表时，元素的平均搜索长度为（ B ）。 （3） 采用折半搜索算法查找长度为n的线性表时，元素的平均搜索长度为（ C ）。 （4） 采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度应（ D ）对应
判定树的最大层次数。
（5） 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ E ）。 （6） 顺序搜索算法适合于存储结构为（ F ）的线性表。 【供选择的答案】 A：① 以数组方式存储 ③ 以链接方式存储 B：① n/2
② 以数组方式存储且结点按关键码有序排列 ④ 以链接方式存储且结点按关键码有序排列
③ （n+1）/2
④ （n-1）/2 ④ O（n） ④ 大于等于
② n
C：① O（n2） D：① 小于 E：① 相同
② O（nlog2n） ③ O（log2n） ② 大于 ② 不相同
③ 等于
③ 有时不相同
F：① 散列存储 ③ 压缩存储
② 顺序存储或链接存储 ④ 索引存储
二、简答题
2（1）、设有序顺序表中的元素依次为017， 094， 154， 170， 275，503， 509， 512， 553， 612， 677， 765， 897， 908。试画出对其进行折半搜索时的判定树， 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。——（page 157）
2（2）、设有序顺序表中的元素依次为017， 094， 154， 170， 275，503， 509， 512， 553， 612， 677， 765， 897， 908。试画出对其进行顺序搜索时的判定树， 并计算搜索
1
成功的平均搜索长度和搜索不成功的平均搜索长度。——（page 170）
3、在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ? S2 ? S3。若对于任意的a ? S1， b ? S2， c ? S3， 是否总有a ? b ? c？为什么？——（page 159）
4、请给出下列操作序列运算的结果：Union（1， 2）， Union（3， 4）， Union（3， 5）， Union（1， 7）， Union（3， 6）， Union（8， 9）， Union（1， 8）， Union（3， 10）， Union（3， 11）， Union（3， 12）， Union（3， 13）， Union（14， 15）， Union（16， 17）， Union（14， 16）， Union（1， 3）， Union（1， 14），要求 （1） 根据树的高度执行Union；
（2） 根据树中结点个数执行Union。——（page 160）
5、设有一个输入数据的序列是 { 46， 25， 78， 62， 12， 37， 70， 29 }， 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。——（page 161）
6、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树， 其最大高度是多少？ 最小高度是多少？
7、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少?
8、设有一个关键码的输入序列{55，31，11，37，46，73，63，02，07}，
（1）从空树开始构造平衡二叉搜索树， 画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。
（2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。——（page 173）
9、在二叉搜索树上删除一个有两个子女的结点时，可以采用以下方案：用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结
2
点。可随机选择其中一个方案。试编写函数实现这个删除方法。——（page 162）
10、设有一个关键码序列 {DEC， FEB， NOV， OCT， JUL， SEP， AUG， APR， MAR， MAY， JUN， JAN}
（1） 按字母顺序依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。
（2） 从所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整？ 若接着删除关键码FEB，又应如何删除与调整？——（page 166）
11、设有序顺序表中的元素依次为017， 094， 154， 170， 275，503， 509， 512， 553， 612， 677， 765， 897， 908。试画出对其进行顺序搜索时的判定树， 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
12、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索， 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同？——（page 157） （1） 搜索失败；
（2） 搜索成功，且表中只有一个关键码等于给定值k的对象；
（3） 搜索成功，且表中有若干个关键码等于给定值k的对象， 要求一次搜索找出所有对象。
3