顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为( )在此假定N为线性表中结点数,且每次查拔都是成功的。

admin2019-05-20  54

问题 顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为(    )在此假定N为线性表中结点数,且每次查拔都是成功的。

选项 A、N+1
B、2log2N
C、log2N
D、N/2

答案D

解析 二分法查找过程可用一个称为判定树的二叉树描述,由于判定树的叶子结点所在层次之差最多为1,故n个结点的判定树的深度与n个结点的完全二叉树的深度相等,均为[log2n]+1。这样,折半查找成功时,关键字比较次数最多不超过[log2n]+1。所以,应选择D。
转载请注明原文地址:https://kaotiyun.com/show/xGCi777K
0

最新回复(0)