在单链表中,查找第i个的元素时,其时间复杂度为()。A、O(n)B、O(1)C、O(n2)D、O(n-1)

题目
在单链表中,查找第i个的元素时,其时间复杂度为()。

A、O(n)

B、O(1)

C、O(n2)

D、O(n-1)

相似考题

1.在下列对单链表进行的操作中,算法时间复杂度为O(n)的是()。A、访问第i个元素的前驱(1B、在第i个元素之后插入一个新元素(1≤i≤n)C、删除第i个元素(1≤i≤n)D、对表中元素进行排序

2.阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。 函数DelListElem(LinkList L，int i，ElemType *e) 的功能是删除含头结点单链表的第 i个元素结点，若成功则返回 SUCCESS ，并由参数e 带回被删除元素的值，否则返回ERROR 。 例如，某含头结点单链表 L 如图 4-1 (a) 所示，删除第 3 个元素结点后的单链表如 图 4-1 (b) 所示。图4-1define SUCCESS 0 define ERROR -1 typedef int Status; typedef int ElemType; 链表的结点类型定义如下: typedef struct Node{ ElemType data; struct Node *next; }Node ,*LinkList; 【C 代码】 LinkList GetListElemPtr(LinkList L ，int i) { /* L是含头结点的单链表的头指针，在该单链表中查找第i个元素结点: 若找到，则返回该元素结点的指针，否则返回NULL */ LinkList p; int k; /*用于元素结点计数*/ if (i<1 ∣∣ !L ∣∣ !L->next) return NULL; k = 1; P = L->next; / *令p指向第1个元素所在结点*/ while (p && （1） ) { /*查找第i个元素所在结点*/ （2） ; ++k; } return p; } Status DelListElem(LinkList L ，int i ，ElemType *e) { /*在含头结点的单链表L中，删除第i个元素，并由e带回其值*/ LinkList p，q; /*令p指向第i个元素的前驱结点*/ if (i==1) （3） ； else p = GetListElemPtr(L ，i-1); if (!p ∣∣ !p->next) return ERROR; /*不存在第i个元素*/ q = (4) ； /*令q指向待删除的结点*/ p->next = q->next; /*从链表中删除结点*/ (5) ； /*通过参数e带回被删除结点的数据*/ free(q); return SUCCESS; }

3.若某线性表中最常用的操作是获取第i个元素和查找第i个元素的前驱，则采用（）存储方法最节省时间。A．顺序表B．单链表C．双向链表D．循环链表

4.在具有n个结点的单链表上查找值为y的元素时,其时间复杂度为()。A、O(n)B、O(1)C、O(n2)D、O(n-1)

参考答案和解析
参考答案：A
更多“在单链表中,查找第i个的元素时,其时间复杂度为()。 ”相关问题

  • 第1题：

    删除单链表的第i个结点不需要移动元素，故其时间复杂度为O（1)。


    错误

  • 第2题：

    长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_______________。


    B

  • 第3题：

    假设某个含有n个元素的线性表有如下运算： Ⅰ.查找序号为i（1≤i≤n）的元素 Ⅱ.查找第一个值为x的元素 Ⅲ.插入第一个元素 Ⅳ.插入最后一个元素 Ⅴ.插入第i（1≤i≤n）个元素 Ⅵ.删除第一个元素 Ⅶ.删除最后一个元素 Ⅷ.删除第i（1≤i≤n）个元素 现设计该线性表的如下存储结构： ① 顺序表 ② 带头节点的单链表 ③ 带头节点的循环单链表 ④ 不带头节点仅有尾节点的循环单链表 ⑤ 带头节点的双链表 ⑥ 带头节点的循环双链表. 指出各种存储结构中对应运算算法的时间复杂度。


    O(n)

  • 第4题：

    1、 实现线性表（a1,a2,...an）的单链表存储结构，并在其上实现查找第i个元素，在第i个位置插入一个元素，删除第i个元素的程序。


    C

  • 第5题：

    17、在单链表中做以下操作，时间复杂度为O（n)的有哪些？注意正确答案可能不止一个！！

    A．求表长度

    B．取第i个元素的值

    C．在表头插入元素

    D．在表头删除元素


    正确

相关内容