itgle.com

线性表（a1,a2,…,an）以链式方式存储时，访问第i个元素的时间复杂度为（）A．O（i）B．O（1）C．O（n）D．O（i-1）

题目

线性表（a1,a2,…,an）以链式方式存储时，访问第i个元素的时间复杂度为（）

A．O（i）

B．O（1）

C．O（n）

D．O（i-1）

相似考题

1.对线性表进行折半查找时,要求线性表必须_______。A、以顺序方式存储B、以链式方式存储C、以顺序方式存储且表中元素按关键字有序排列D、以链式方式存储且表中元素按关键字有序排列

2.线性表（a1，a2，?，an）以链式方式存储，访问第i位置元素的时间复杂度为()。A.O（0）B.O（1）C.O（n）D.O（n2）

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

4.若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用()存储方式最节省时间。

参考答案和解析
O（n）
更多“线性表（a1,a2,…,an）以链式方式存储时，访问第i个元素的时间复杂度为（）”相关问题

  • 第1题：

    对线性表进行二分查找，要求线性表为______。

    A．以顺序方式存储

    B．以链式方式存储

    C．以顺序方式存储，且要求数据元素有序

    D．以链接方式存储，且要求数据元素有序


    正确答案：C
    解析：二分查找的前提是线性表以顺序存储，且数据元素有序。

  • 第2题：

    对线性表进行二分查找时，要求线性表必须( )。

    A．以顺序存储方式存储

    B．以顺序存储方式存储，且数据元素有序

    C．以链式存储方式存储

    D．以链式存储方式存储，且数据元素有序


    正确答案：B
    解析：对线性表进行二分查找时，要求线性表必须以顺序存储方式存储，且数据元素有序。

  • 第3题：

    在包含1000个元素的线性表中实现如下运算，_______所需的执行时间最长。

    A．线性表按顺序方式存储，性表的第100个结点后面插入一个新结点

    B．线性表按链式方式存储，性表的第100个结点后面插入一个新结点

    C．线性表按顺序方式存储，删除线性表的第900个结点

    D．线性表按链式方式存储，删除指针P所指向的结点


    正确答案：A
    解析：选项B、D中的运算无须移动结点，通过修改指针即可完成，选项A中的运算需要移动900个结点，选项C中的运算需要移动100个结点，故选项A中的运算最耗时。

  • 第4题：

    含有n个元素的线性表采用顺序存储方式时，对其运算速度最快的操作是(36)。

    A.访问第i个元素(l＜i≤n)

    B.删除第i个元素(1≤j≤n)

    C.在第i个元素(1≤i≤n)之后插入一个新元素

    D.查找与特定值相匹配的元素


    正确答案：A
    本题考查数据结构基础知识。线性表(a1,a2,a3.......an)采用顺序存储方式如下图所示，其逻辑上相邻的元素物理位置也是相邻的，因此，按照序号访问元素的速度是很快的。访问第i个元素(1≤i≤n)的元素，仅需计算出a1的存储位置再进行内存的随机访问操作即可，以LOC(a1)表示线性表中第一个元素的存储位置，L表示每个元素所占存储单元的个数，则计算LOC(a1)的方式如下：LOC(a1)=LOC(a1)+(i-I)×L再分析其他运算，不在表尾插入或删除时就需要移动其他元素，这是比较耗时的。查找与特定值相匹配的元素时，需要经过一个与表中多个元素进行比较的过程，相对于随机访问第i个元素，消耗更多时间。

  • 第5题：

    在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（）。


    正确答案:O（1）

  • 第6题：

    顺序存储结构的线性表中，访问第i个元素与其位置（）关。（填有或无）


    正确答案:无

  • 第7题：

    对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）


    正确答案:O(n)；O(1)

  • 第8题：

    对线性表进行二分检索时，要求线性表必须（）。

    • A、以顺序存储方式存储
    • B、以链式存储方式存储
    • C、以顺序存储方式存储且数据有序
    • D、以链式存储方式存储且数据有序

    正确答案:C

  • 第9题：

    单选题
    线性表（a1，a2，…，an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。
    A

    O（i）

    B

    O（1）

    C

    O（n）

    D

    O（i-1）


    正确答案： B
    解析： 暂无解析

  • 第10题：

    单选题
    若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。
    A

    O（log2n）

    B

    O（1）

    C

    O（n）

    D

    O（n2）


    正确答案： D
    解析： 暂无解析

  • 第11题：

    填空题
    对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）

    正确答案： O(n),O(1)
    解析： 暂无解析

  • 第12题：

    填空题
    设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为（）在链式存储结构上实现顺序查找的平均时间复杂度为（）

    正确答案： O（n）,O（n）
    解析： 暂无解析

  • 第13题：

    以下关于线性表存储结构的叙述，正确的是（57）。

    A.线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级

    B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级

    C.线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级

    D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级


    正确答案：A
    线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级，因为顺序存储结构访问元素时，能直接定位元素，这样，操作的时间复杂度为O（1）。

  • 第14题：

    在包含1000个元素的线性表中实现如下运算，_______所需的执行时间最短。

    A．线性表按顺序方式存储，查找关键码值为666的结点

    B．线性表按链式方式存储，查找关键码值为666的结点

    C．线性表按顺序方式存储，查找线性表中第900个结点

    D．线性表按链式方式存储，查找线性表中第900个结点


    正确答案：C
    解析：若线性表按顺序方式存储，线性表中第900个结点的存储地址可根据线性表的起始地址直接计算出。

  • 第15题：

    在包含1000个元素的线性表中实现如下各运算，________所需的执行时间最短。

    A．当线性表按链接方式存储时，删除指针P所指向的结点

    B．当线性表按顺序方式存储时，性表的第10个结点后面插入一个新的结点

    C．当线性表按顺序方式存储时，删除线性表第10个结点

    D．当线性表按链式方式存储时，性表的第10个结点后面插入一个新结点


    正确答案：A
    解析：A中不需要移动数据元素。B中需要移动990个数据元素。C中需要移动990个数据元素。D中需要查找10个结点。

  • 第16题：

    含有n个元素的线性表采用顺序存储方式时，对其运算速度最快的操作是( )。

    A.访问第i个元素(1≤i≤n)
    B.删除第i个元素(1≤i≤n)
    C.在第i个元素(1≤i≤n)之后插入一个新元素
    D.查找与特定值相匹配的元素

    答案：A
    解析：
    本题考查数据结构基础知识。
    线性表(a1，a2，…，an)采用顺序存储方式如下图所示，其逻辑上相邻的元素物理位置也是相邻的，因此，按照序号访问元素的速度是很快的。

    访问第i个元素(1≤i≤n)的元素，仅需计算出ai的存储位置再进行内存的随机访问操作即可，以LOC(a1)表示线性表中第一个元素的存储位置，L表示每个元素所占存储单元的个数，则计算LOC(ai)的方式如下：
    LOC(ai)=LOC(a1)+(i-1)×L
    再分析其他运算，不在表尾插入或删除时就需要移动其他元素，这是比较耗时的。查找与特定值相匹配的元素时，需要经过一个与表中多个元素进行比较的过程，相对于随机访问第i个元素，消耗更多时间。

  • 第17题：

    在具有n个元素的顺序存储结构的线性表中，若给定的是某个元素的关键字值，要访问该元素的其它信息的时间复杂度是（）。


    正确答案:O(n)

  • 第18题：

    对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）。


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

  • 第19题：

    设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为（）在链式存储结构上实现顺序查找的平均时间复杂度为（）


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

  • 第20题：

    多选题
    下面的叙述不正确的是（  ）。
    A

    线性表在链式存储时，查找第i个元素的时间同i值无关

    B

    线性表在链式存储时，查找第i个元素的时间同i值成正比

    C

    线性表在顺序存储时，查找第i元素的时间同i值无关

    D

    线性表在顺序存储时，查找第i个元素的时间同i值成正比


    正确答案： D,B
    解析：

  • 第21题：

    填空题
    顺序存储结构的线性表中，访问第i个元素与其位置（）关。（填有或无）

    正确答案： 无
    解析： 暂无解析

  • 第22题：

    填空题
    对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）。

    正确答案： O（1）,O（n）
    解析： 暂无解析

  • 第23题：

    单选题
    线性表（al，a2，…，an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。
    A

    O（i）

    B

    O（1）

    C

    O（n）

    D

    O（i-1）


    正确答案： A
    解析：

  • 第24题：

    填空题
    在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（）。

    正确答案： O（1）
    解析： 暂无解析

相关内容