早教吧作业答案频道 -->其他-->
在具有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个结点的单链表中,实...的网友还看了以下：
在指令的寻址方式中,存储器直接寻址,操作数在( )中,指令中的操作数是操作数的地址。A.通用寄存 2020-05-24 …
【问题1】(6分) 按照表4－1所列出的数据寻址方式,说明表4－3中各汇编指令指定的操作数或操作数地 2020-05-25 …
若指令中的地址码为A,变址寄存器为X,基址寄存器为B,则变址间址寻址方式的操作地址N=(5)。A.X 2020-05-26 …
设某指令系统的指令字是16位,每个地址码为6位.若二地址指令15条,一地址指令48条,则剩下的零地 2020-06-03 …
操作系统里面地址转换的问题在分页存储管理系统中,某作业的页表如下,已知页面大小为2048字节,试将 2020-06-24 …
汇编语言1．设DS=2000H,SS=3000H,BP=0200H,SI=4000H,BUF=10 2020-07-10 …
计算机组成原理高手帮帮我假设指令字长为16位，操作数的地址码为6位，采用扩展操作码技术，操作码位数 2020-07-21 …
3.指出下列操作数的寻址方式（分别指出源操作数的寻址方式和目的操作数的寻址方式）（1）MOVCOUN 2020-11-08 …
Linux操作系统问题\("▔□▔)/某计算机使用32bit逻辑地址,使用两级页表,逻辑地址被分为1 2020-11-23 …
计算机操作系统，求解，谢谢！！1.采用简单分页系统的内存管理，页面的大小是8K字节。现有一个逻辑地址 2020-12-28 …