我要招人

去企业版

首页 > 试题广场 >

若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除

[单选题]

若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（　）存储方式最节省运算时间和存储空间。

```
单链表
```
```
仅有头指针的单循环链表
```
```
双向链表
```
```
仅有尾指针的单循环链表
```

查看正确选项

Mendax_Ame

D删除表位元素需要将尾指针指向其前一个元素，要循环遍历整个链表找到这个元素

发表于 2018-06-07 08:41:45 回复(0)

贺宏宏

单链表：尾插入O(n),尾删O(n)

仅有头的单循环链表：尾插入O(n),尾删O(n)

双向链表：尾插入O(n),尾删O(n)

仅有尾指针的单循环链表：尾插入O(1),尾删O(n)

相比较而言时间上还是D最好。空间上，D项只多用一个尾指针空间复杂度尾O(1)

发表于 2018-06-22 11:55:28 回复(2)

胡妞妞

D因为删除需要知道前一个元素的指针，这里只知道尾指针，所以删除最后一个元素需要遍历到最后一个元素。

发表于 2017-09-27 08:52:29 回复(0)

쯔위야

D如果队尾删自己，需要修改前一个节点接下来的指向，问题是单链表回溯不了前一个节点，我认为是这样。

发表于 2018-10-26 14:24:45 回复(0)

盯裆猫

其实我觉得是D

操作：

1.在最后一个元素之后插入一个元素

2.删除进入表中的最后一个元素

操作1理解为在表中的最后一个元素之后插入一个元素

操作2理解为删除进入表中的最后一个元素，可是进入表中的最后一个元素不一定要放在表的最后啊，可以放在头部，即使用头插法建表。

那么我么再看D仅有尾指针的单循环链表。如图：

操作1则表示在A之后插入一个元素：

设新增节点为s，则为

s.next=last.next;
last.next=s;

插好后为

时间复杂度为O（1）

操作2则表示删除数据为E的节点

last.next=last.next.next;

时间复杂度为O（1）

发表于 2018-07-24 15:00:19 回复(4)

仅存老实人

对单链表就不赘述了，对题目的理解：双向链表(一般有头结点和尾结点)对头和尾都是o(1)

发表于 2019-01-11 10:11:27 回复(0)

字节内推dd

错因：这里的这个双向链表没说带头指针和尾指针，所以普遍认为这只是一个普通的双向链表，因此插入和删除的时间复杂度都是O(n)，因为你要找到哪个是尾指针（我是这么理解的虽然我觉得这样很扯）

其他：

单链表：尾插入O(n),尾删O(n)

仅有头的单循环链表：尾插入O(n),尾删O(n)

双向链表：尾插入O(n),尾删O(n)

仅有尾指针的单循环链表：尾插入O(1),尾删O(n)

相比较而言时间上还是D最好。空间上，D项只多用一个尾指针空间复杂度尾O(1)

发表于 2022-03-01 13:13:35 回复(0)

李在赣神魔捏

删除一个元素最关键的就是找到他的前驱结点，只有尾指针的单循环链表，找到其前驱时间复杂度为O(n)，故选双向链表

发表于 2019-12-05 01:43:07 回复(0)

名字是谷雨

只说双向链表，感觉不够，应该要么带尾指针，要么循环。不然也没法很快找到最后一个元素的前驱

发表于 2019-10-16 21:08:37 回复(0)

热得八达鸟

其实我有个疑问：如果是在只有尾指针的情况下，把尾节点和它指向的下一个节点的值对换一下，删除下一个节点，这样不也达到了删除最后一个节点的目的了吗

发表于 2019-11-25 21:26:13 回复(0)

正在卷的三文鱼很讨厌吃香菜

删除最后一个节点需要知道前一个节点，只用带尾指针的单循环链表不行

发表于 2019-07-01 22:56:36 回复(0)

sf54837

评论区里这么多D的。。。仅有尾指针的话前一个结点位置也不知道呀

发表于 2020-09-05 21:52:34 回复(2)

请叫我猿叔叔

我只画个图等大神来解决？

发表于 2017-06-14 22:54:36 回复(5)

牛客441824850号

D：插入需要知道尾指针O(1);删除需要知道尾指针前面的地址O(n)

发表于 2023-11-02 19:51:23 回复(0)

大题小做

d选项删除的时候找一个替罪羊删掉就可以了

发表于 2023-09-03 20:58:47 回复(0)

冰㒱沝

在链表中删除一个节点实际上是有两种思路的。一种是知道他的前驱节点指针，改变他的指向，之后free这个节点另外一个是知道这个节点的指针，然后将他的后一个节点的值向前移动，将他的后一个节点删除。但是本题是最后一个节点诶。所以采用第一种方式删除最后一个节点的话，还是需要遍历整个链表，之后进行删除。但是知道了尾节点之后，在他的后面插入一个元素十分的方便。双向链表是错的因为没有指明其头指针和尾指针，那么还是需要遍历的

发表于 2023-05-31 11:18:30 回复(0)