首页 > 试题广场 >

对于链式存储的线性表,查找结点和删除结点的时间复杂度为( )

[单选题]

对于链式存储的线性表,查找结点和删除结点的时间复杂度为( )。

  • O(n) O(n)
  • O(n) O(1)
  • O(1) O(n)
  • O(1) O(1)
这题就很迷惑,题目大概分成了两种,一种是删除认为只是删除的,那就是O(1),如果认为删除本身还带有查找元素的话那就是自然是O(n),这道理大家都懂,主要是不知道题目到底想问啥。麻了
发表于 2022-08-21 14:09:44 回复(2)
B,平均复杂度O(n)和O(1),删除节点时不考虑查找该结点的步骤
发表于 2019-03-11 14:13:09 回复(0)
答案:A
链式删除和查找都要从开头遍历,所以O(N)
发表于 2018-06-14 22:14:44 回复(0)
题目描述不清晰啊这
发表于 2023-01-02 13:00:32 回复(0)
顺序存储的查找时间复杂度为O(1),因为地址是连续的。只要知道首元素的地址,根据下表可以很快找到指定位置的元素。而插入和删除操作由于可能要在插入前or删除后对元素进行移动,所以时间复杂度为O(n)。
链式存储相反,查找时需要从头元素逐个寻找,时间复杂度为O(n)。当插入or删除时,由于制药变更元素中下一个元素的存储地址即可,时间复杂度为O(1)。
表面上没问题,但是实际使用中,要在链表中删除or插入元素时,总要遍历找到位置,这时时间复杂度为O(n)。所以!在链式存储结构中,删除or插入的时间复杂度为O(1)的是有前提条件的!必须事先知道一直元素当前的位置!!!
发表于 2022-07-10 10:43:39 回复(0)
链表删除指定节点的复杂度应该是O(1)才对,但是如果要按值删就需要先查找到该元素的前驱,时间复杂度为O(n),单纯的删除操作时间复杂度为O(1)。
发表于 2022-03-24 21:07:35 回复(0)
A,虽然是链式存储,但还是要先查找借点
发表于 2021-03-06 14:45:54 回复(0)
到底几啊??
发表于 2020-12-06 12:22:31 回复(0)

很明显是c啊!顺序存储线性表查找时间复杂度是1!删除增加很麻烦是n!其他人回答的有没有常识?

发表于 2019-12-15 23:53:45 回复(4)
b
发表于 2019-12-11 15:39:41 回复(0)

A

发表于 2019-11-06 20:06:21 回复(0)
A
发表于 2019-04-21 16:09:56 回复(1)