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

admin2019-01-30  21

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

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

答案C

解析 此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较,直到成功或失败,其ASL=(n+1)/2,即查找成功时的平均比较次数约为表长的一半。
    二分法查找过程可用一个称为判定树的二叉树描述,由于判定树的叶子结点所在层次之差最多为1,故n个结点的判定树的深度与n个结点的完全二叉树的深度相等,均为[log2n]+1。这样,折半查找成功时,关键字比较次数最多不超过[log2n]+1。所以,(1)应选择D,(2)应选C。
转载请注明原文地址:https://kaotiyun.com/show/KdRi777K
0

最新回复(0)