单向循环链表如下图所示，以下关于单向循环链表的叙述中，正确的是_________。

admin2021-03-24 71

问题单向循环链表如下图所示，以下关于单向循环链表的叙述中，正确的是_________。

选项 A、仅设头指针时，遍历单向循环链表的时间复杂度是O(1)
B、仅设尾指针时，遍历单向循环链表的时间复杂度是O(1)
C、仅设头指针时，在表尾插入一个新元素的时间复杂度是O(n)
D、仅设尾指针时，在表头插入一个新元素的时间复杂度是O(n)

答案C

解析在单链表存储结构中，任何情况下实现遍历(即遍访表中的所有元素)时间复杂度都是O(n)。
在单链表任何位置插入或删除结点，首先需要找到插入位置，该查找运算的时间复杂度可能是O(n)或D(1)，然后用O(1)复杂度的运算实现插入。
在单向循环链表的表尾插入一个新元素时，需要修改表尾结点的指针域，若仅设头指针时，则需要遍历表中所有结点才能找到表尾结点，因此时间复杂度为O(n)。
在单向循环链表的表头插入一个新元素时，需要修改表头结点(含头结点时)或表尾结点(不含头结点时)的指针域，仅设尾指针时，可以通过简单运算(即时间复杂度O(1))获得第一个结点的指针信息，再进行插入结点操作。

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

本试题收录于：程序员上午基础知识考试题库软考初级分类

程序员上午基础知识考试

软考初级

相关试题推荐

随机试题

最新回复(0)

单向循环链表如下图所示，以下关于单向循环链表的叙述中，正确的是_________。

程序员上午基础知识考试

软考初级

私网IP地址区别于公网IP地址的特点是___________。

甲和乙要进行保密通信，甲采用(52)加密数据文件，乙使用自己的私钥进行解密。

网络连接如下页上图所示，图中的设备D1是(23)。

在进行域名解析过程中，若主域名服务器出现故障，则在(51)上进行查找；若主域名服务器工作正常但未能查找到记录，由(52)负责后续解析。(52)

以下联网设备中，工作于网络层的设备是(21)。

在局域网的网管工作站上做配置管理的设备配置的收集工作时，发现一台路由器尽管被发现了，但是却取不到它的路由表，原因可能是______。

ThenumberofhomeusersandsmallbusinessesthatwanttousetheInternetiseverincreasing．Theshortageofaddressesisbecom

阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的对应栏内。【说明】本流程图用于计算菲波那契数列{a1=1，a2=1，…，an=an-1+an-2，|n=3，4，…}的前n项(n≥2)之和S。例如，菲波那契数列

In______programming,theuserdeterminesthesequenceofinstructionstobeexecuted,nottheprogrammer.

______isadevicewhichenablesdigitalmicrocomputerstocommunicateacrossanalogtelephonelines.

Manyolderparentsfindthemselvesbalancingtheirlimitedfinancialresources,decliningenergyandfailinghealthagainstthe

最有利于脑外肿瘤定位的CT表现为

A．灼痛B．重痛C．掣痛D．冷痛E．空痛

“无论至于何处，遇男或女，贵人及奴婢，我之唯一目的，为病家谋幸福。”出自()

当事人转让专利权的，专利权的转让自交付专利证书之日起生效。()(2013年)

企业收取包装物押金及其他各种暂收款项时，应贷记()科目。

A注册会计师接受委托，对甲公司提供鉴证服务。A注册会计师遇到下列事项，请代为作出正确的专业判断。如果A注册会计师在承接鉴证业务之后发现标准或鉴证对象不适当造成丁作范围受到限制，下列处理方式不恰当的是（）。

2016年全社会固定资产投资606466亿元，比上年增长7.9%，其中，固定资产投资（不含农户）596501亿元，增长8.1%。分区域看，东部地区投资249665亿元，比上年增长9.1%；中部地区投资156762亿元，增长12.0%；西部地区投资15405