对有n个数据元素的顺序表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为_____________

A.(N+l)/2

B.N/2

C.N

D.[(1+N)*N]／2

概率为2／3，第四个元素的概率为1／8，则查找任一个元素的平均查找长度为_______。

A．23／8

B．20／8

C．17／8

D．14／8

A.顺序查找

B.分块查找

C.折半查找

D.二叉排序树查找

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

(1)搜索失败;

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

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

请将待查关键字k插入表尾。

A.i＞0

B.i≤n

C.1≤i≤n

D.1≤i≤n+1

次为________。

A．a[8]，a[5]，a[6]，a[7]

B．a[1]，a[8]，a[7]，a[6]

C．a[6]，a[4]，a[8]，a[5]

D．a[6]，a[2]，a[4]，a[5]

关键字值18的查找过程。

设在有序顺序表中搜索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的情况)。

时，分别需要比较_______次和_______次才能查找成功；若采用顺序查找时，分别需要比较______次和______次才能查找成功。