早教吧作业答案频道 -->其他-->
在具有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个结点的单链表中,实...的网友还看了以下：
库伦定律的比例系数国际单位制是以电流作为基本单位的,那么电量应该是通过电流的定义式单位时间通过导体 2020-05-14 …
数学里的单位其实也是与实际计算有联系的,比如速度单位：千米/小时,它的写法就是来源于用总千米数除以 2020-05-22 …
pascal题目-栈-进制转换题目描述十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其 2020-06-28 …
初级会计实务计算公式甲公司采用移动加权平均法计算发出产成品的实际成本.2012年5月初产成品的账面 2020-07-17 …
某土方工程，工程量清单为1000m³，合同约定的综合单价为16元/m³，且实际工程量减少超过10% 2020-07-18 …
求助砂层沉降量预估方法砂土沉降的简单估算根据规范砂土密实e0.85~0.95.承载力小于140KP 2020-07-27 …
求判断一个数是否为素数的最简单算法一个数N,从实现最为简单的算法就是遍历N能否整除从2到sqrt(N 2020-11-24 …
编程实现一个计算器，按照四则运算优先级n编程实现一个简单计算器。请按照四则运算加、减、乘、除、幂（^ 2020-11-28 …
08清单招标项目,按清单计算规则,电缆长度是100米.按定额计算规则,长度为120米.请问：项目按0 2020-11-28 …
2010年11月14日，半年评选一次的全球超级计算机500强名单正式公布，我国“天河一号”超级计算机 2020-12-08 …