数据结构
一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。
题目
一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。
参考答案和解析
正确答案:O（1）；O（n）
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案
第1题：
在具有n个结点的单链表中,实现()的操作，其算法的时间复杂度是O。
A.求链表的第i个结点
B.在地址为P的结点之后插入一个结点
C.删除表头结点
D.删除地址为P的结点的后继结点
正确答案：A
第2题：
在具有n个结点的单链表中，实现()的操作，其算法的时间复杂度都是O(n)。
A.遍历链表和求链表的第i个结点
B.在地址为P的结点之后插入一个结点
C.删除开始结点
D.删除地址为P的结点的后继结点
B.在地址为P的结点之后插入一个结点
C.删除开始结点
D.删除地址为P的结点的后继结点
答案：A
解析：
A项，由于单链表是非随机存取的存储结构，遍历链表和求链表的第i个结点都必须从头指针出发寻找，其时间复杂度为0(n)；B项，由于已知待插入结点的前驱结点，可以直接实现插入，其时间复杂度为0(1)；CD两项，可以直接实现删除操作，其时间复杂度为O(1)。
第3题：
在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点,应执行s－>next=_______;和p－>next=________的操作。
参考答案：p->next;s
第4题：
在一个双向链表中指针p所指向的结点之前插入一个新结点时，其时间复杂性的量级为（）
正确答案:O(1)
第5题：
对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为（），在给定值为x的结点后插入一个新结点的时间复杂度为（）
正确答案:O（1）；O（n）
第6题：
在一个长度为n(n>1)的带头结点的单链表head上,另设有尾指针r(指向尾结点),执行()操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的尾结点
C.在单链表的第一个元素前插入一个新结点
D.在单链表的最后一个元素后插入一个新结点
参考答案：B
第7题：
在双向循环链表中，在p所指的结点之后插入指针f所指的新结点，其操作步骤是()。
答案：D
解析：
在双向循环链表中。在p所指的结点之后插入指针f所指的新结点的操作步骤为：改变f的前驱指针域，使其指向p；然后改变f的后继指针域，使其指向p的后继；接下来修改p的后继结点得前驱指针域，指向f，最后将f的地址付给p的后继指针。具体操作为：f—＞pnor=p；f—＞next=p—＞next；p—＞next—＞prior=f；P—＞next=f。
第8题：
要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点,若链表中结点的指针域为next,可执行 p－>next=s; s－>next= p－>next;的操作。()
此题为判断题(对，错)。
标准答案：错
第9题：
对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为（）；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为（）
正确答案:O（1）；O（n）
第10题：
在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂性的量级为（）
- A、O（n）
- B、O（1）
- C、O（n2）
- D、O（n／2）
正确答案:A