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

admin2013-05-11 39

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

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

软考中级

使用代理服务器(Proxy　Server)访问InteRNet的主要功能不包括(37)。

主存储器和CPU之间增加高速缓冲存储器(Cache)的目的是(1)。

计算机系统中的信息资源只能被授予权限的用户修改，这是网络安全的(25)。

图3-5是虚拟主机示意图，图中“N”部分不可能是(63)。

ISO9000系列标准和软件成熟度模型(CMM)都着眼于质量和过程管理。ISO9000系列标准强调质量管理必须坚持进行(9)。

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

IEEE802．11定义了无线局域网的两种工作模式，其中的(1)模式是一种点对点连接的网络，不需要无线接入点和有线网络的支持。IEEE802．11g的物理层采用了扩频技术，工作在(2)频段。(2008年上半年试题)(1)

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将__________。(2008年下半年试题)

情志不调可引起哪些病证

按提供信息的详细程度及其统驭关系，可以将会计科目分为()。

世界最大的珊瑚礁群所在的国家是()。

根据给定资料，概述以上资料所反映的主要问题。概述文字简明扼要，不超过200字。请你就给定的资料所反映的问题写一篇1200～1500字的文章，自拟标题。要求解决给定资料所反映的问题，要体现针对性和可操作性。

(厦门大学2011年初试真题)调节纳税人税收负担纵向平衡问题的税率形式多为()。

有16件产品，12个一等品，4个二等品，从中任取3个，至少有一个是一等品的概率为________．

网络故障管理的主要任务是______和排除网络故障。

A、责备B、惭愧C、后悔D、批评B“过意不去”习惯用语，表示惭愧、不好意思。

Mr.Smithhasboughtalotofbooksforhisdaughter,________he?

Formuchofitshistory,psychologyhasseemedobsessedwithhumanfailingsandpathology.Theveryideaofpsychotherapy,first

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

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

软考中级

使用代理服务器(Proxy Server)访问InteRNet的主要功能不包括(37)。

主存储器和CPU之间增加高速缓冲存储器(Cache)的目的是(1)。

计算机系统中的信息资源只能被授予权限的用户修改，这是网络安全的(25)。

图3-5是虚拟主机示意图，图中“N”部分不可能是(63)。

ISO9000系列标准和软件成熟度模型(CMM)都着眼于质量和过程管理。ISO9000系列标准强调质量管理必须坚持进行(9)。

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

IEEE802．11定义了无线局域网的两种工作模式，其中的(1)模式是一种点对点连接的网络，不需要无线接入点和有线网络的支持。IEEE802．11g的物理层采用了扩频技术，工作在(2)频段。(2008年上半年试题)(1)

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将__________。(2008年下半年试题)

情志不调可引起哪些病证

按提供信息的详细程度及其统驭关系，可以将会计科目分为()。

世界最大的珊瑚礁群所在的国家是()。

根据给定资料，概述以上资料所反映的主要问题。概述文字简明扼要，不超过200字。请你就给定的资料所反映的问题写一篇1200～1500字的文章，自拟标题。要求解决给定资料所反映的问题，要体现针对性和可操作性。

(厦门大学2011年初试真题)调节纳税人税收负担纵向平衡问题的税率形式多为()。

有16件产品，12个一等品，4个二等品，从中任取3个，至少有一个是一等品的概率为________．

网络故障管理的主要任务是______和排除网络故障。

A、责备B、惭愧C、后悔D、批评B“过意不去”习惯用语，表示惭愧、不好意思。

Mr.Smithhasboughtalotofbooksforhisdaughter,________he?

Formuchofitshistory,psychologyhasseemedobsessedwithhumanfailingsandpathology.Theveryideaofpsychotherapy,first

使用代理服务器(Proxy　Server)访问InteRNet的主要功能不包括(37)。