下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是( )。

admin2022-10-24 60

问题下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是( )。

选项 A、在顺序存储的线性表中寻找最大项
B、在顺序存储的线性表中进行顺序查找
C、在顺序存储的有序表中进行对分查找
D、在链式存储的有序表中进行查找

答案A

解析寻找最大项，无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第1次查看的一个数据恰好是要找的数据，只需要比较1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是n和log₂n，平均情况则是“1～最坏情况”的平均，因而是不同的。故本题答案为A选项。

转载请注明原文地址:https://www.kaotiyun.com/show/GWkp777K

本试题收录于：二级C语言题库NCRE全国计算机二级分类

二级C语言

NCRE全国计算机二级

相关试题推荐

随机试题

最新回复(0)

下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是( )。

二级C语言

NCRE全国计算机二级

以下选项中正确的定义语句是

软件测试的目的是

由以下while构成的循环，循环体执行的次数是intk＝0；while(k＝1)k＋＋；

下列叙述中正确的是

使用VC++2010打开考生文件夹下prog1中的解决方案。此解决方案的项目中包含一个源程序文件progl．c。在此程序中，编写函数fun，其功能是：根据以下公式求π的值(要求精度0．0005，即某项小于0．0005时停止迭代)。程序运行后，若

设有下面的定义：Stnuctst{inta；floatb：}d；int*p；要使P指向结构变量d中的a成员，正确的赋值语句是()。

某二叉树中度为2的结点有10个，则该二叉树中有()个叶子结点。

下面不属于软件需求分析阶段主要工作的是

在C++程序中，如果要求通过函数来实现一种简单的功能，并且要求尽可能加快序执行速度，则应该选用()。

已知单元格A1，A2，A3，A4中数据分别为4，13，6和90A5中公式为“=SUM(A1：A3)+INT(A4/2)，则A5的值为()

根据法律规定，下列不属于承揽合同的是()

患者，男，35岁，常自汗出，恶风，面色苍白，舌质淡，苔薄白，脉浮虚者。治宜选用

[2003年第53题]贮水池的有效容积，不包括以下哪一条?

承包被保险人依法对第三者依法应承担的赔偿责任的保险是()。

在海外，开放式基金的销售主要分为()

SomecallittheSmartShooter,anewrifleforAmericaninfantrytroopsthatistwoweaponsinone,isaccurateupto1,000yar

Internet上的主机系统经常被“黑客”光顾，所谓“黑客”含义是()。