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

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

admin2019-08-15  51
问题 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为(  (1)  )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为(  (2)  )。在此假定N为线性表中结点数，且每次查找都是成功的。
选项 A、N+1
B、2log2N
C、log2N
D、N／2
E、Nlog2N
答案(1)D (2)C。
解析  此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。
    二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log2n]+1。这样，折半查找成功时，关键字比较次数最多不超过[log2n]+1。所以，(1)应选择D，(2)应选C。
转载请注明原文地址:https://kaotiyun.com/show/80Ci777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)