微信刷题,考证常用
  • 试题题型【选择题】
试题内容
下列算法中均以比较作为基本运算,则平均情况与最坏情况下的时间复杂度相同的是(    )。
  • A.在顺序存储的线性表中进行顺序查找
  • B.在顺序存储的有序表中进行对分查找
  • C.在顺序存储的线性表中寻找最大项
  • D.在链式存储的有序表中进行查找
  • 参考答案:C
  • 解题思路:寻找最大项,无论如何都要查看所有的数据,与数据原始排列顺序没有多大关系,无所谓最坏情况和最好情况,或者说平均情况与最坏情况下的时间复杂度是相同的;
    而查找无论是对分查找还是顺序查找,都与要找的数据和原始的数据排列情况有关,最好情况是第1次查看的一个数据恰好是要找的数据,只需要比较1次;
    如果没有找到再查看下一个数据,直到找到为止,最坏情况下是最后一次查看的数据才是要找的,顺序查找和对分查找在最坏情况下比较次数分别是n和log2n,平均情况则是1~最坏情况的平均,因而是不同的。故选C。