线性表（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.对于线性表的顺序存储,假定每个数据元素占用m个存储单元,每个数据元素第一个单元的存储位置为该数据元素的存储位置,第1个数据元素的存储位置为b,则第i个数据元素的存储位置为?A.b+i*mB.b+(i-1)*mC.b+(i+1)*mD.b+m

2.在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？A．线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点B．线性表按链接方式存储，在线性表的第100个结点后面插入一个新结点C．线性表按顺序方式存储，删除线性表的第900个结点D．线性表按链接方式存储，删除指针P所指向的结点

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

4.在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最短？A．线性表按顺序方式存储，查找关键码值为666的结点B．线性表按链接方式存储，查找关键码值为666的结点C．线性表按顺序方式存储，查找线性表中第900个结点D．线性表按链接方式存储，查找线性表中第900个结点

更多“线性表（a1，a2，…，an）以链接方式存储时，访问第 i 位置元素的时间复杂度为（）。”相关问题

  • 第1题：

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

    A.O（0）

    B.O（1）

    C.O（n）

    D.O（n2）


    正确答案：C

  • 第2题：

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

    A．以顺序方式存储

    B．以链接方式存储

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

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


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

  • 第3题：

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

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

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

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

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


    正确答案：A

  • 第4题：

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

    A、以顺序方式存储

    B、以顺序方式存储,且数据元素有序

    C、以链接方式存储

    D、以链接方式存储,且数据元素有序


    正确答案:B

  • 第5题：

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

    A．以顺序方式存储

    B．以链式方式存储

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

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


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

  • 第6题：

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

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

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

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

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


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

  • 第7题：

    含有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个元素，消耗更多时间。

  • 第8题：

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


    正确答案:无

  • 第9题：

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

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

    B

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

    C

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

    D

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


    正确答案： D,B
    解析：

  • 第10题：

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

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

  • 第11题：

    单选题
    对线性表进行二分查找时，要求线性表必须（）。
    A

    以顺序存储方式

    B

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

    C

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

    D

    以链接存储方式


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

  • 第12题：

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

    O（i）

    B

    O（1）

    C

    O（n）

    D

    O（i-1）


    正确答案： A
    解析：

  • 第13题：

    线性表（a1，a2，?，an）以链式方式存储，访问第i位置元素的时间复杂度为()。

    A.O（0）

    B.O（1）

    C.O（n）

    D.O（n2）


    正确答案：C

  • 第14题：

    （ 12 ）在包含 1000 个元素的线性表中实现如下各运算，哪一个所需的执行时间最短？

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

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

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

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


    正确答案：C

  • 第15题：

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

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

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

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

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


    正确答案：A
    由于线性表采用的是顺序存储方式，用存储单元的邻接性体现线性表元素间的一维顺序关系，因此对线性表进行插入和删除运算时，可能需要移动大量的结点，以保持这种物理和逻辑的一致性。对于选项A)，后面的900个结点都要往后移动，对于选项C)，后面的100个结点都要往前移动。而对于线性表按链接方式存储，当进行插入与删除操作时，只改变相应的指针即可，所以比较4个选项的操作可易知，选项A)所需要的执行时间最长。 

  • 第16题：

    对长度为n的单链接存储的线性表，在表尾插入元素的时间复杂度为【 】。


    正确答案：O(n)
    O(n)

  • 第17题：

    若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为(1)。

    A．O(0)

    B．O (1)

    C．O(n)

    D．O(n2)


    正确答案：C
    解析：性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：。因此，在长度为n的线性表中插入一个元素的时间复杂度为。

  • 第18题：

    含有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个元素，消耗更多时间。

  • 第19题：

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


    正确答案:O（1）

  • 第20题：

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


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

  • 第21题：

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

    O（i）

    B

    O（1）

    C

    O（n）

    D

    O（i-1）


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

  • 第22题：

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

    O（log2n）

    B

    O（1）

    C

    O（n）

    D

    O（n2）


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

  • 第23题：

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

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

  • 第24题：

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

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

相关内容