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

admin2013-05-11 16

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

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

软考中级

以下给出的地址中，属于子网197.182.15.19/28的主机地址是(48)。

如果帧中继网沿着帧传送方向出现了拥塞，则把帧地址字段中的FECN位设置为1，这样接收方就可通过(29)协议要求发送方降低数据速率。

现在具有加密/解密功能的路由器使人们通过互联网连接这些局域网成为可能，这就是我们通常所说的虚拟专用网(Virtual　Private　Network，VPN)，下列各项属于VPN所采用的加密手段的是(7)。

PC机不能接入因特网，这时采用抓包工具捕获的以太网接口发出的信息如下：可以看出该PC机的IP地址为(68)，默认网关的IP地址为(69)。PC不能接入Internet的原因可能是(70)。(70)

采用10Base一5的局域网表示(1)。采用特性阻抗为(2)Ω的粗同轴电缆。这种网络的收发器不在网卡上，而是直接与电缆相连，收发器电缆最长为(3)，最大节点数限于(4)个工作站。(4)

干兆以太网标准802．3z定义了一种帧突发方式(FrameBursting)，这种方式是指__________。(2010年上半年试题)

以下关于CISC(ComplexInstructionSetComputer，复杂指令集计算机)和RISC(ReducedInstructionSetComputer，精简指令集计算机)的叙述中，错误的是__________。(2009年下半年

在计算机系统中，构成虚拟存储器(8)。

按照国标《信息交换用汉字编码字符集——基本集》(即GB2312)规定，一个汉字由(1)个字节组成。为了达到中西文兼容的目的，区分汉字与ASCII码，汉字编码的最高位为(2)。

标准麻花钻由一尖、五刃、四面、()角组成。

在产品的成长期中，可采取的营销策略有()

A、炒黄法B、炒焦法C、炒炭法D、麸炒法E、米炒法蒲黄的炮制宜采用（）

A．成分B．用法用量C．不良反应D．注意事项根据《中药、天然药物处方药说明书内容书写要求》了解药品需慎用的情况，可查询()。

NPV与基准收益率的关系表现为()。

会计机构和会计人员在单位内部会计监督中的职权包括()。

下图甲、乙、丙、丁表示了我国四个地区的优势产业形成的要素构成图。这四个地区的优势产业依次是（）。

设齐次线性方程组Am×nx=0的解全是方程b1x1+b2x2+…+bnxn=0的解，其中x=(x1，x2，…，xn)T．证明：向量b=(b1，b2，…，bn)可由A的行向量组线性表出．

(2013年下半年上午试题22)算术表达式a+(b-c)*d的后缀式是_______。(-、+、水表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)

Workingatypewriterbytouch,likeridingabicycleorstrollingonapath,isbestdonebynotgivingitaglancingthought.O

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

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

软考中级

以下给出的地址中，属于子网197.182.15.19/28的主机地址是(48)。

如果帧中继网沿着帧传送方向出现了拥塞，则把帧地址字段中的FECN位设置为1，这样接收方就可通过(29)协议要求发送方降低数据速率。

现在具有加密/解密功能的路由器使人们通过互联网连接这些局域网成为可能，这就是我们通常所说的虚拟专用网(Virtual Private Network，VPN)，下列各项属于VPN所采用的加密手段的是(7)。

PC机不能接入因特网，这时采用抓包工具捕获的以太网接口发出的信息如下：可以看出该PC机的IP地址为(68)，默认网关的IP地址为(69)。PC不能接入Internet的原因可能是(70)。(70)

采用10Base一5的局域网表示(1)。采用特性阻抗为(2)Ω的粗同轴电缆。这种网络的收发器不在网卡上，而是直接与电缆相连，收发器电缆最长为(3)，最大节点数限于(4)个工作站。(4)

干兆以太网标准802．3z定义了一种帧突发方式(FrameBursting)，这种方式是指__________。(2010年上半年试题)

以下关于CISC(ComplexInstructionSetComputer，复杂指令集计算机)和RISC(ReducedInstructionSetComputer，精简指令集计算机)的叙述中，错误的是__________。(2009年下半年

在计算机系统中，构成虚拟存储器(8)。

按照国标《信息交换用汉字编码字符集——基本集》(即GB2312)规定，一个汉字由(1)个字节组成。为了达到中西文兼容的目的，区分汉字与ASCII码，汉字编码的最高位为(2)。

标准麻花钻由一尖、五刃、四面、()角组成。

在产品的成长期中，可采取的营销策略有()

A、炒黄法B、炒焦法C、炒炭法D、麸炒法E、米炒法蒲黄的炮制宜采用（）

A．成分B．用法用量C．不良反应D．注意事项根据《中药、天然药物处方药说明书内容书写要求》了解药品需慎用的情况，可查询()。

NPV与基准收益率的关系表现为()。

会计机构和会计人员在单位内部会计监督中的职权包括()。

下图甲、乙、丙、丁表示了我国四个地区的优势产业形成的要素构成图。这四个地区的优势产业依次是（）。

设齐次线性方程组Am×nx=0的解全是方程b1x1+b2x2+…+bnxn=0的解，其中x=(x1，x2，…，xn)T．证明：向量b=(b1，b2，…，bn)可由A的行向量组线性表出．

(2013年下半年上午试题22)算术表达式a+(b-c)*d的后缀式是_______。(-、+、水表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)

Workingatypewriterbytouch,likeridingabicycleorstrollingonapath,isbestdonebynotgivingitaglancingthought.O

现在具有加密/解密功能的路由器使人们通过互联网连接这些局域网成为可能，这就是我们通常所说的虚拟专用网(Virtual　Private　Network，VPN)，下列各项属于VPN所采用的加密手段的是(7)。