早教吧作业答案频道 -->其他-->
在具有n个结点的单链表中,实现下列哪些操作,其算法的时间复杂度都是O（n)?a)遍历链表和求链表的第i个结点b)在地址为p的结点之后插入一个结点c)删除开始结点d)删除地址为p的结点的后继结
题目详情
在具有n 个结点的单链表中,实现下列哪些操作,其算法的时间复杂度都是O（n)?
a)遍历链表和求链表的第i个结点
b)在地址为p的结点之后插入一个结点
c)删除开始结点
d)删除地址为p的结点的后继结点
a)遍历链表和求链表的第i个结点
b)在地址为p的结点之后插入一个结点
c)删除开始结点
d)删除地址为p的结点的后继结点
▼优质解答
答案和解析
a）平均复杂度为（n+1)/2;
b) 平均复杂度为 （n+1)/2;
c) 平均复杂度为 1;
d) 平均复杂度为 （n+1)/2;
所以a)、b)、d)的时间复杂度均为O(n);
c）为O（1）；
b) 平均复杂度为 （n+1)/2;
c) 平均复杂度为 1;
d) 平均复杂度为 （n+1)/2;
所以a)、b)、d)的时间复杂度均为O(n);
c）为O（1）；
看了 在具有n个结点的单链表中,实...的网友还看了以下：
在单链表中,若要删除指针p所指的结点的后继结点(next是结点的指针域),需要执行( )。A.P↑. 2020-05-23 …
在单链表中在指针p所指结点后插入结点q的操作是A.q:=p↑.link; p↑.link:=q↑.l 2020-05-23 …
在单链表中在指针p所指结点后插入结点q的操作是A.q:=p↑.link;p↑.link:=q↑.li 2020-05-24 …
在一个单链表中,若p所指结点不是最后结点,在p所指结点之后插入s所指结点,则应执行(32)操作。A. 2020-05-26 …
在具有n个结点的单链表中,实现下列哪些操作,其算法的时间复杂度都是O（n)?a)遍历链表和求链表的 2020-06-12 …
c++为什么不是A，有甚区别12．链表结点的结构类型为structlinkRec{intdata; 2020-06-22 …
为什么会在P-N结的两边产生内建电场 2020-06-25 …
假设长度大于1的单循环链表中,既无头结点,也无头指针,p为指向该链表中某一结点的指针,编写一个算法 2020-07-05 …
数据结构链表问题已知L是无表头的单链表，其P结点既不是首元结点，也不是尾元结点，在p结点后插入s结点 2020-11-20 …
数据结构双向链表4、已知P结点是某双向链表的中间结点,按要求写出对应的语句：(1)在P结点后插入S结 2020-12-08 …