单选题
顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为(
2
)，二分法查找只适用于查找顺序存储的有序表，平均比较次数为(
3
)。在此假定N为线性表中结点数，且每次查找都是成功的。
A.N+1
B.2log
2
N
C.log
2
N
D.N/2
E.Nlog
2
N
F.N
2
A
B
C
D
E
F
【正确答案】
D
【答案解析】
A
B
C
D
E
F
【正确答案】
C
【答案解析】
此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)/2，即查找成功时的平均比较次数约为表长的一半。
二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log
2
n]+1。这样，折半查找成功时，关键字比较次数最多不超过[log
2
n]+1。所以，(1)应选择D，(2)应选C。
提交答案
关闭