问答题 已知一个有序顺序表A[BN-1]的表长为8N,并且表中没有关键字相同的数据元素。假设按如下所述的方法查找一个关键字值等于给定值X的数据元素:先在A[7],A[15],A[23],…,A[8K-1],…,A[8N-1]中进行顺序查找,若查找成功,则算法报告成功位置并返回;若不成功,当A[8K-1]<X<A[8×(K+1)-1]时,若X>A[8N-1]的关键字,则查找失败。
问答题 画出描述上述查找过程的判定树。
【正确答案】
【答案解析】相应的判定树如下图所示。其中,每一个关键字下的数字为其查找成功时的关键字比较次数。
问答题 计算相等查找概率下查找成功的平均查找长度。
【正确答案】
【答案解析】查找成功的平均查找长度为: