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

admin2013-05-11 38

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

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

软考中级

为两个对等的开放系统之间提供按“请求/应答”方式交换管理信息的协议是(65)。

假定一条线路每1/16s采样一次，每个可能的信号变化都运载3bit的信息，则传输速率是(1)。

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

阅读以下说明，回答【问题1】～【问题6】，将解答填入对应的解答栏内。【说明】某公司通过在WindowsServer2003中安装IIS6.0来配置Web服务器，域名为www.csai.cn。

使用ADSL拨号上网，需要在用户端安装(19)协议。

WLANsareincreasinglypopularbecausetheyenablecost—effectiveconnectionsamongpeopleandapplicationsthatwerenotpossib

Allthreetypesofcryptographyschemeshaveuniquefunctionmappingtospecificapplications．Forexample，thesymmetrickey(1)ap

浮点数的表示分为阶和尾数两部分。两个浮点数相加时，需要先对阶，即(1)________________(n为阶差的绝对值)。

Thefirstsnowboardsweremadeinthe1960s.However,itwasinthelate1970sthattheybecamemore【C1】______Throughoutthe198

有关肿瘤的概念哪项是错误的

根据牛船税法律制度的规定，下列车船中，免征车船税的有()。(2()11年)

实现：远大：梦想

Weknowtodaythatthetraditionsoftribalartaremorecomplexand"primitive"thanitsdiscoverersbelieve;wehaveevenseen

计算机中图形格式一般有二类，即(101)和(102)。具体的存储方式有许多种，通常用图形文件的后缀名来区分，如以(103)为后缀名的，则是以ASCII方式存储的图形；而(104)则不是图形文件的后缀名。多媒体中的视频信息是指(105)。

数据库设计中反映用户对数据要求的模式是(　　)。

Jackisadiligentstudent.

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

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

软考中级

为两个对等的开放系统之间提供按“请求/应答”方式交换管理信息的协议是(65)。

假定一条线路每1/16s采样一次，每个可能的信号变化都运载3bit的信息，则传输速率是(1)。

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

阅读以下说明，回答【问题1】～【问题6】，将解答填入对应的解答栏内。【说明】某公司通过在WindowsServer2003中安装IIS6.0来配置Web服务器，域名为www.csai.cn。

使用ADSL拨号上网，需要在用户端安装(19)协议。

WLANsareincreasinglypopularbecausetheyenablecost—effectiveconnectionsamongpeopleandapplicationsthatwerenotpossib

Allthreetypesofcryptographyschemeshaveuniquefunctionmappingtospecificapplications．Forexample，thesymmetrickey(1)ap

浮点数的表示分为阶和尾数两部分。两个浮点数相加时，需要先对阶，即(1)________________(n为阶差的绝对值)。

Thefirstsnowboardsweremadeinthe1960s.However,itwasinthelate1970sthattheybecamemore【C1】______Throughoutthe198

有关肿瘤的概念哪项是错误的

根据牛船税法律制度的规定，下列车船中，免征车船税的有()。(2()11年)

实现：远大：梦想

Weknowtodaythatthetraditionsoftribalartaremorecomplexand"primitive"thanitsdiscoverersbelieve;wehaveevenseen

计算机中图形格式一般有二类，即(101)和(102)。具体的存储方式有许多种，通常用图形文件的后缀名来区分，如以(103)为后缀名的，则是以ASCII方式存储的图形；而(104)则不是图形文件的后缀名。多媒体中的视频信息是指(105)。

数据库设计中反映用户对数据要求的模式是( )。

Jackisadiligentstudent.

数据库设计中反映用户对数据要求的模式是(　　)。