首页
登录
从业资格
在具有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为( )
在具有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为( )
最全题库
2022-08-02
70
问题
在具有n个结点的有序单链表中插入一个新结点并保持有序的运算的时间复杂度为( )。A.O(1)B.O(logn)C.O(n)D.O(n2)
选项
A.O(1)
B.O(logn)
C.O(n)
D.O(n2)
答案
C
解析
本题考查数据结构基础知识。
在具有n个结点的有序单链表中插入一个新结点时,插入操作本身仅需要修改两个指针,时间主要消耗在顺序地比对需插入的元素与表中元素的大小,从而确定其插入位置。若要插入的元素小于表中的最小元素,则插入该元素时与表中的一个元素进行比较,若要插入的元素大于表中的最大元素,则需要与表中的n个元素全部比较一遍。
因此,单链表中参与比较的元素个数平均为(1+2+…+n+n)/(n+1),即该操作的时间复杂度为O(n)。
转载请注明原文地址:https://tihaiku.com/congyezige/2427452.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
4D进度管理软件中应包含()。A.成本信息 B.时间信息 C.几何信息 D
影响工程质量的因素主要有()。A.时间 B.机械 C.材料 D.方法 E
BIM信息的保持特征表示该信息必须保留的()。A.用途 B.时间 C.方式
根据评价时间不同,后评价又可以分为()。A.项目跟踪评价 B.项目实施效果评价
施工进度模拟即通过将BIM与()相连接,把空间信息与时间信息整合在一个可视的4D
5DBIM施工管理软件是在3D模型的基础上,附加施工的()。A.时间和成本信息
根据评价时间不同,后评价又可以分为()。A.跟踪评价 B.实施效果评价 C.
下列不符合臭氧消毒的说法是A.消毒时间应≥30分钟 B.臭氧发生器将空气中的氧
女性,34岁,全身化脓性感染,需抽血做血培养及抗生素敏感试验,最佳时间应是A.体
肢体长时间只有固定,而没有指导功能训练,可导致的并发症是A.钙血性肌挛缩 B.
随机试题
Ifyouarebuyingacar,youmaypayforitoutofsavings.A、假使你正在买一辆汽车,你也许会透支购买
Whyarehackersneededinscience?[br][originaltext]Scienceurgentlyneeds
SurvivalofEnglishLanguageI.Introduction—English
[originaltext]M:Ihearyou’reworkingasamarketsurveyorthissummer.It’sg
机器字长为8位,定点整数x的补码用十六进制表示为B6H,则其反码用十六进制表示为
下列有关审计管理的表述中,错误的是:A、审计管理要服从审计目标 B、审计管
各种运输方式内外部的各个方面的构成和联系,就是( )。 A.运输系统
仪表工程连续( )开通投入运行正常后即具备交接验收条件。A.12小时 B.2
某投资方案建设期为1年,第1年年初投资8000万元,第2年年初开始盈利,运营期为
患儿,男,1天,生后1分钟Apgar评分5分。查体:易激惹,心率150次/分,肌
最新回复
(
0
)