在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。

admin2013-05-11 23

问题在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。

选项 A、O(1)
B、O(n)
C、O(nlogn)
D、O(n²)

答案B

解析本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等，即

则在有序单链表上查找插入位置的平均比较次数为：

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。

软件设计师上午基础知识考试

软考中级

在SNMPv1管理框架中，如果代理需要向管理站报告一个异常事件，则代理发出trap报文。以下事件中不属于异常事件的是(37)。

RS-232C是(34)之间的接口标准，其规定的电平表示方式为(35)。当使用RS232C连接相关设备时，电缆的长度不应超过(36)m。当用RS232C直接连接两台计算机时，采用零调制解调器方式，其连接方式为(37)。当计算机需要通过相连的MO-DEM

在Linux操作系统中提供了大量的网络配置命令，其中不带参数的route命令用来查看本机的路由信息，(70)命令也可以完成该项功能。

王某是一名软件设计师，按公司规定编写软件文档，并上交文件存档，这些软件文档属于职务作品，且____________。

在Windows环境下，DHCP客户端可以使用(1)命令重新获得IP地址，这时客户机向DHCP服务器发送一个(2)数据包来请求租用IP地址。(2008年上半年试题)(1)

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]给出一个接收三个数a、b、c作为三角形边长并输出三角形的类型的程序。程序代码如下所示：结点源代码行Areada,b,cB

产品生命周期的开始点是_______。

实践是检验真理的唯一标准。这是因为【】

某牛场10％的牛发生羞明、流泪、痉挛，有浆液性或脓性分泌物，角膜混浊，血管增生，有的病牛出现角膜溃疡，体温40．5～41．5℃，精神沉郁，食欲不振。最可能发生的疾病是

清肝火的药物是主清心与小肠之火的药物是

下列各项，关于仲裁庭组成的表述正确的是()。

某公司生产甲产品和乙产品，甲产品和乙产品为联产品。6月份发生加工成本600万元。甲产品和乙产品在分离点上的数量分别为600个和400个。采用实物数量分配法分配联合成本，甲产品应分配的联合成本为（）万元。

Scientistsaresupposedtochangetheirminds.【F1】Havingadoptedtheirviewsonscientificquestionsbasedonanobjectiveeval