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

admin2013-05-11 24

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

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

答案B

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

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

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

某公司将现有网络进行升级改造，随着公司联网设备的增多，整个网络性能下降的越来越快。

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

某企业内部网段与Internet网互联的网络拓扑结构如图8-3所示，其防火墙结构属于(34)。

BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01．BGPisbasedonaroutingmethodcalledpathvectorrouting

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

在相隔2000km的两地间通过电缆以4800b／s的速率传送3000比特长的数据包，从开始发送到接收完数据需要的时间是(1)。如果用50kb／s的卫星信道传送，则需要的时间是(2)。(2009年下半年试题)(2)

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

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续天数，则完成该项目的最少时间为(9)天。活动EH和IJ的松弛时间分别为(10)天。

提高换热器的传热系数，能够有效地提高传热速率。

A．下肢放射性疼痛B．小腿外侧感觉障碍，拇趾背伸力弱C．两者均有D．两者均无L3～L4椎间盘突出症的临床表现可有

患者粟某，发热倦怠，胸闷腹胀。艘酸咽痛，颐肿口渴，身目发黄，尿赤淋浊，苔黄脉数。治宜选用()

关于五脏所藏的叙述，错误的是()

绿色建筑的含义是()。

买断式回购采用()的方式。

商业银行员工在工作中，由于知识/技能匮乏所造成的操作风险主要有()。

认为知识并不是对现实的准确表征，它只是一种解释、一种假设的理论属于()

通过指定字段的数据类型和宽度来限制该字段的取值范围，这属于完整性中的()。

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

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

软考中级

某公司将现有网络进行升级改造，随着公司联网设备的增多，整个网络性能下降的越来越快。

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

某企业内部网段与Internet网互联的网络拓扑结构如图8-3所示，其防火墙结构属于(34)。

BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01．BGPisbasedonaroutingmethodcalledpathvectorrouting

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

在相隔2000km的两地间通过电缆以4800b／s的速率传送3000比特长的数据包，从开始发送到接收完数据需要的时间是(1)。如果用50kb／s的卫星信道传送，则需要的时间是(2)。(2009年下半年试题)(2)

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

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续天数，则完成该项目的最少时间为(9)________________天。活动EH和IJ的松弛时间分别为(10)________________天。

提高换热器的传热系数，能够有效地提高传热速率。

A．下肢放射性疼痛B．小腿外侧感觉障碍，拇趾背伸力弱C．两者均有D．两者均无L3～L4椎间盘突出症的临床表现可有

患者粟某，发热倦怠，胸闷腹胀。艘酸咽痛，颐肿口渴，身目发黄，尿赤淋浊，苔黄脉数。治宜选用()

关于五脏所藏的叙述，错误的是()

绿色建筑的含义是()。

买断式回购采用()的方式。

商业银行员工在工作中，由于知识/技能匮乏所造成的操作风险主要有()。

认为知识并不是对现实的准确表征，它只是一种解释、一种假设的理论属于()

通过指定字段的数据类型和宽度来限制该字段的取值范围，这属于完整性中的()。

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续天数，则完成该项目的最少时间为(9)天。活动EH和IJ的松弛时间分别为(10)天。