首页 > 试题广场 >

关于单向链表,以下说法正确的有()

[不定项选择题]
关于单向链表,以下说法正确的有()
  • 单向链表中指向头结点的指针First,可用于单向链表的判空依据
  • 单向链表中指向头结点的指针First,可用于定位所有其他结点的位置
  • 已知操作节点地址的情况下,单向链表插入,删除的时间复杂度小于查找的时间复杂度
  • 单向链表允许在非表头进行插入或删除操作
C:这样描述是有问题的,首先如果节点未知,C肯定错误,因为无论插入还是删除都要先查,如果节点地址已知,那他们的时间复杂度都是O(1),地址已知,根本不用查
发表于 2019-06-10 09:08:02 回复(7)
选:ABCD
【分析】

C++中的链表结构体如下:
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
A选项:如果单链表的头指针指向的结点为NULL,则单链表为空。
B选项:利用链表的链式储存结构,可以通过头指针定位任意一个结点的位置。
C选项:单链表的插入O(1),删除的时间复杂度O(1),小于查找的时间复杂度O(n)。【在已知操作结点地址的前提下】
D选项:单链表非表头结点的插入删除只需要修改next指针的指向,并且增加或释放相应的结点即可。
编辑于 2022-04-05 16:07:24 回复(0)
ABCD。根据选项可以看出该题考查的是单链表的基本操作(判空、增、删、查)。

  • 单链表头结点是一个指针,指向Node数据类型,如果头结点指示的是NULL,则该链表为空。所以A正确
  • 根据头结点的next指向,可以依次遍历出单链表所有节点的位置(即查找操作,但时间复杂度比较大)所以B正确。
  • 单链表的增删只需更改指针的指向,而查找需要从链表头依次对比,所以插入、删除时间复杂度小于查找,C正确
  • 图所示,假如在上图的节点2,3之间(非表头)插入节点4。删除也是同理。所以D正确


编辑于 2019-05-21 18:09:43 回复(4)
题目描述有问题,如果插入删除给定了结点就是O(1)
不然也是O(n)
发表于 2019-12-12 10:19:49 回复(0)
鄙人认为C不严谨,从严谨的态度上看,若是在某个具体的点后面插入和删除便是O(1),若不是具体的点,则是O(n),则C应该是在不谈论是否在具体点后,删除的时间复杂度应小于等于( <=) 查找的时间复杂度。
发表于 2020-07-18 15:26:40 回复(1)
B正确:根据头结点的next指向,可以依次遍历出单链表所有节点的位置(即查找操作,但时间复杂度比较大)
C错误:已经知道地址:插入、删除时间复杂度为O(1)   ,但是根本就不用再查
发表于 2023-04-26 11:10:40 回复(0)
c选项难道不应该先查找再删除吗,不查找怎么删除?
发表于 2019-08-27 11:45:31 回复(1)
单向链表删除某节点,需要先遍历找到它的前驱节点。
发表于 2023-09-25 22:15:31 回复(0)
lllab满了 l卤牛。你为什么要抽一下我的那.. elite 。哦哦哦哦哦哦哦噢
发表于 2023-07-22 16:26:30 回复(0)
如果插入删除第一个元素,查找复杂度显然小于插入删除
发表于 2022-10-27 12:05:31 回复(0)
差点就把自己搞糊涂了,幸亏翻一下书
发表于 2021-08-25 14:02:25 回复(0)
链表的删除不是需要查找到,以后进行的操作的吗。
发表于 2019-10-19 00:04:56 回复(0)