A、必然快 B、必然慢 C、相等 D、不能确定
20、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C )。
A、必定快 B、不一定 C、在大部分情况下要快 D、取决于表递增还是递减 21、具有12个关键字的有序表，折半查找的平均查找长度（ A ）。 A、3.1 B、4 C、2.5 D、5 22、折半查找的时间复杂性为（ D ）
A、O（n2） B、O（n） C、O（nlogn） D、O（logn） 23、当采用分快查找时，数据的组织方式为 ( B )。 A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C、 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分成若干块，每块（除最后一块外）中数据个数需相同 24、二叉查找树的查找效率与二叉树的( C ) 有关。
A、高度 B、结点的多少 C、树型 D、结点的位置 25．在等概率情况下,一棵平衡树的ASL为 ( B )
A、O(1) B、O( log2n ) C、 O((log2n)2) D、O(nlog2n)
26、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )。 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)
27、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C、 RL D、RR 28、下列关于m阶B-树的说法错误的是( D )。 A、根结点至多有m棵子树 B、所有叶子都在同一层次上
C、 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D、 根结点中的数据是有序的
29、下面关于m阶B树说法正确的是( B )。
①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。
36
A、 ①②③ B. ②③ C、 ②③④ D. ③ 30、下面关于B和B+树的叙述中，不正确的是( C ) 。
A、B树和B+树都是平衡的多叉树。 B、B树和B+树都可用于文件的索引结构。 C、B树和B+树都能有效地支持顺序检索。 D、B树和B+树都能有效地支持随机检索。
三、判断题
1、查找相同结点的效率折半查找总比顺序查找高。(× ) 2、索引顺序表的特点是块内可无序，块间要有序。（ √ ）
3、在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。( ?) 4、在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。(√ ) 5、若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。（√ ） 6、折半搜索适用于有序表，包括有序的顺序表和有序的链表。(╳ )
7、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（√ ）
8、在散列检索中，“比较”操作一般也是不可避免的。（√ ）
9、在m阶B-树中每个结点上至少有 个关键字，最多有m个关键字。(× )
10、负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（√ ） 11、散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（√ ）
12、哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 (× ) 13、若散列表的负载因子α<1，则可避免冲突的产生。(× )
14、用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。(× )
15、在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。(× )
16、顺序查找法适用于存储结构为顺序或链接存储的线性表。（√ ）
17、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。(× )
18、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找
成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（√ ）
19、任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间. (× )
20、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。(× )
37
四、简答题
1、对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
2、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1） 画出描述折半查找过程的判定树； （2） 若查找元素54，需依次与哪些元素比较？ （3） 若查找元素90，需依次与哪些元素比较？
（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解：
（1） 先画出判定树如下（注：mid=?(1+12)/2?=6）：
30
5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；
（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08
3、设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下：
38
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10 （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）＝17/11=1.5454545454≈1.55
4、设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA、，处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。
0 K ASL=20/9 0
1 2 3 4 5 6 7 8 9 10 1 TA 2 BA 3 M 4 D 5 CI 6 X 7 8 9 TN 10 I
ASL=15/9
5、输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴ 画出该二叉排序树；
⑵ 画出删除结点302后的二叉排序树。
解： 100 50 302 30 66 200 450 260 100 50 260 39 30 66 200 450
6、设有一组关键字：{19，01，23，14，55，20，84，27，68}，采用哈希函数： H（key）=key mod 7，采用开放地址法的线性探测再散列方法解决冲突。 要求：在0∽11的散列地址空间中对该关键字序列构造哈希表。
0 1 2 3 4 5 6 7 8 9 10 11 解： 0 1 2 3 4 5 6 7 8 9 10 11 14 01 23 84 7、已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DeC、
(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序
树，并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查
找成功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找
19 55 20 27 68 长度。
8、用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 解：
40