软件工程

在单链表中，若给定某个结点的指针，要删除该结点的后继结点的时间复杂度为（）。

题目

在单链表中，若给定某个结点的指针，要删除该结点的后继结点的时间复杂度为（）。

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

在具有n个结点的单链表中,实现()的操作，其算法的时间复杂度是O。

A.求链表的第i个结点

B.在地址为P的结点之后插入一个结点

C.删除表头结点

D.删除地址为P的结点的后继结点


正确答案：A

第2题：

单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是()。

A.若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)
B.在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理
C.加入头结点后，在链表中进行查找运算的时间复杂度为O(1)
D.加入头结点后，代表链表的头指针不因为链表为空而改变

答案：C
解析：
在链表中加入头结点后，查找表中某一元素仍然要从头指针出发，顺序找到目标元素或失败时找到表尾为止，时间复杂度与表长成正比。故D项错误。

第3题：

●在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p→*next→*next=head，则 (55) 。

(55) A．p指向头结点

B．p指向尾结点

C．*p的直接后继是头结点

D．*p的直接后继是尾结点


正确答案：D
【解析】因为循环链表的尾结点的指针域中存放的是头指针，而尾结点由其直接前驱结点的指针域所指向，因此，当指针p指向尾结点的直接前驱结点时，满足关系式p->next->next=head。

第4题：

对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为（），在给定值为x的结点后插入一个新结点的时间复杂度为（）


正确答案:O（1）；O（n）

第5题：

在长度为n(Il＞1)的()上，删除第一个元素.其时间复杂度为O(n)。

A.只有首结点指针的不带头结点的循环单链表
B.只有尾结点指针的不带头结点的循环单链表
C.只有尾结点指针的带头结点的循环单链表
D.只有头结点的循环单链表

答案：A
解析：
只有首结点指针的不带头结点的循环单链表删除第一个元素，需要遍历整个链表，因此A项的时间复杂度为O(n)，BCD三项的时间复杂度都为O(1)。

第6题：

在长度为n的()上删除第一个元素,其算法的时间复杂度为O(n)。

A.只有表头指针的不带表头结点的循环单链表

B.只有表尾指针的不带表头结点的循环单链表

C.只有表尾指针的带表头结点的循环单链表

D.只有表头指针的带表头结点的循环单链表


参考答案：A

第7题：

在具有n个结点的单链表中，实现()的操作，其算法的时间复杂度都是O(n)。

A.遍历链表和求链表的第i个结点
B.在地址为P的结点之后插入一个结点
C.删除开始结点
D.删除地址为P的结点的后继结点

答案：A
解析：
A项，由于单链表是非随机存取的存储结构，遍历链表和求链表的第i个结点都必须从头指针出发寻找，其时间复杂度为0(n)；B项，由于已知待插入结点的前驱结点，可以直接实现插入，其时间复杂度为0(1)；CD两项，可以直接实现删除操作，其时间复杂度为O(1)。

第8题：

单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是( )。

A．若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)

B．在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理

C．加入头结点后，代表链表的头指针不因为链表为空而改变

D．加入头结点后，在链表中进行查找运算的时问复杂度为O(1)


正确答案：D
解析：链表查找最常规的做法是从链表的头结点开始，顺序查找结点。由于需要顺序查找，时问复杂度自然就是O(n)了。

第9题：

在n个结点的单链表中要删除已知结点*p，需找到它的（），其时间复杂度为（）。


正确答案:前驱结点的地址 O（n）

第10题：

在单链表L中，指针P所指的结点有后继结点的条件是（）。


正确答案:p->next!=NULL

更多相关问题
相关内容