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

admin2013-05-11 25

问题在具有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)。

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

软考中级

采用脉码调制(PCM)方法对声音信号进行编码，若采样频率为8000Hz，量化级为256级，那么数据传输率要达到(10)。

在图8-5所示的Internet接入拓扑结构中，定义一条规则号为104，禁止内部所有主机访问外部IP地址段为202.117.12.0/24的Web服务器。完成此访问控制规则配置任务的语句是(50)。

Themetricassignedtoeachnetworkdependsonthetypeofprotocol．Somesimpleprotocol，likeRIP，treatseachnetworkasequals．

TCP协议使用(1)次握手机制建立连接，当请求方发出SYN连接请求后，等待对方回答(2)，这样可以防止建立错误的连接。(2012年上半年试题)(1)

计算机中常采用原码、反码、补码和移码表示数据，其中，±0编码相同的是__________。(2009年上半年试题)

IEEE802．11定义的AdHoe网络是由无线移动结点组成的对等网，这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(63)

绒癌常见的转移部位是（　　）。

某城市拟建主干道总长15km，根据《环境影响评价技术导则一大气环境》，适用于该项目大气环境影响预测的推荐模式是()。

下列属于企业股权筹资方式的有()。

以下是某求助者做SCL一90的测验结果：总分：168阴性项目数：29在本测验中，阴性项目数是指()的项目。

两个相同的负电荷和一个正电荷附近的电场线分布如图3所示。c是两负电荷连线的中点，d点在正电荷的正上方，c、d到正电荷的距离相等，则下列说法错误的是()。

“三天打鱼，两天晒网”是缺乏意志（）的表现。

体育是以()为目标的教育活动。

持有过量现金可能导致的不利后果是()

Londonquicklybecameaflourishingport.

WhatdidtheIndonesia’smilitaryaskaidgroupstodo?

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

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

软考中级

采用脉码调制(PCM)方法对声音信号进行编码，若采样频率为8000Hz，量化级为256级，那么数据传输率要达到(10)。

在图8-5所示的Internet接入拓扑结构中，定义一条规则号为104，禁止内部所有主机访问外部IP地址段为202.117.12.0/24的Web服务器。完成此访问控制规则配置任务的语句是(50)。

Themetricassignedtoeachnetworkdependsonthetypeofprotocol．Somesimpleprotocol，likeRIP，treatseachnetworkasequals．

TCP协议使用(1)次握手机制建立连接，当请求方发出SYN连接请求后，等待对方回答(2)，这样可以防止建立错误的连接。(2012年上半年试题)(1)

计算机中常采用原码、反码、补码和移码表示数据，其中，±0编码相同的是__________。(2009年上半年试题)

IEEE802．11定义的AdHoe网络是由无线移动结点组成的对等网，这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(63)

绒癌常见的转移部位是（ ）。

某城市拟建主干道总长15km，根据《环境影响评价技术导则一大气环境》，适用于该项目大气环境影响预测的推荐模式是()。

下列属于企业股权筹资方式的有()。

以下是某求助者做SCL一90的测验结果：总分：168阴性项目数：29在本测验中，阴性项目数是指()的项目。

两个相同的负电荷和一个正电荷附近的电场线分布如图3所示。c是两负电荷连线的中点，d点在正电荷的正上方，c、d到正电荷的距离相等，则下列说法错误的是()。

“三天打鱼，两天晒网”是缺乏意志（）的表现。

体育是以()为目标的教育活动。

持有过量现金可能导致的不利后果是()

Londonquicklybecameaflourishingport.

WhatdidtheIndonesia’smilitaryaskaidgroupstodo?

绒癌常见的转移部位是（　　）。