设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出

17，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行顺序搜索时的判定树，并计算搜索成功的平均搜索长度和搜索不成功的平均搜紫长度。

A.3

B.4

C.5

D.6

采用折半搜索法搜索长度为n的有序顺序表，搜索每个元素的平均比较次数（)对应二叉判定树的高度（设高度≥2)。

A、小于

B、大于

C、等于

D、大于等于

率时的平均搜索长度是否相同？

(1)搜索失败;

(2)搜索成功，且表中只有一个关键码等于给定值k的元素;

(3)搜索成功，且表中有若千个关键码等于给定值k的元素，要求一次搜索找出所有元素。

已知如下所示长度为12的关键字有序的表: （1)试按表中元索的顺序依次插入到一棵初始为空的二

已知如下所示长度为12的关键字有序的表:

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

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

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

每次从无序表中取出一个元素，把它插人到有序表中的适当位置，此种排序方法讯做（①)排序;每次从无

序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做(②)排序。

设A={1,2,3,4,5,6.7,8.9},在AxA上的关系R={（（a,b),（c,d))la+d=b+c},试证明R是等价关系,并求

设A={1,2,3,4,5,6.7,8.9},在AxA上的关系R={((a,b),(c,d))la+d=b+c},试

证明R是等价关系,并求分析:本题R的有序偶的第一个元素和第二个元素本身也是有序偶,即第一元素为(a,b),

第二元素为(c,d),而不是通常的第一元素为a第二元素为b.满足本关系R的两个有序偶元素

的关系解释为a+d=b+c,即第一个有序偶中的第一个元素a与第二个有序偶中的第二个元素

d相加等于第一个有序偶中的第二个元素b与第二个有序偶中的第一个元素c相加,按此原则,根据普通加法的性质来推出前后两个有序偶可满足自反对,称,传递性质,故而证明R是等价关系.

当求具体的等价类时,将待求的元素(此题为有序偶,如(1,3))去配满足阿类性质的所有元素(也是有序偶).例如,[(1,3)]中的(6,8),7.9)等满足1+8=3+6.1+9=3+7等

设在有序顺序表中搜索x的过程为：首先用x与表中的第4i（i=0，1，…)个元素做比较，如果相等，则搜索

成功;否则确定下一步搜索的区间为4(i-1)+1到4i-1.然后在此区间内与第4i-2个元素作比较，若相等则搜索成功，否则继续与第4i-3或4i-1个元索进行比较，直到搜索成功。

(1)给出实现算法。

(2)试面出当表长n=16时的判定树，并推导此搜索方法的平均搜索长度(考虑搜索元素等概率和n%4=0的情况)。