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

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

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

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

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

  • 第1题：

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

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

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

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

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


    正确答案：A
    解析：线性表按顺序方式存储，性表的第10个结点后面插入一个新结点，需要将第11～1000个 结点都向后移动一个位置；线性表按链接方式存储，性表的第10个结点后面插入一个新结 点，只需从第一个结点开始找到第10个结点在其后插入即可。删除道理相同。

  • 第2题：

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

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

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

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

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


    正确答案：A

  • 第3题：

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


    正确答案：C
    A和B是查找关键码值为900的结点，该关键码可能不在线性表中，此时查找失败，比较了1000次；若线性表按顺序方式存储，查找线性表中第 900 个结点，则可直接通过计算得到第900个结点的地址：a[900]的地址=a[1]+899×每个元素所占存储空间；若线性表按链接方式存储，查找线性表中第 900 个结点，则指针需从第一元素一个一个往下移动，直到第900个结点。

  • 第4题：

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


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

  • 第5题：

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

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

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

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

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


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

  • 第6题：

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

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

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

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

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


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

  • 第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题：

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

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

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

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

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


    正确答案：C

  • 第14题：

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

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

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

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

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


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

  • 第15题：

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

    A、以顺序方式存储

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

    C、以链接方式存储

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


    正确答案:B

  • 第16题：

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


    正确答案：A
    线性表按顺序方式存储，对于插入和删除操作会比较麻烦，A项中要在线性表的第100个节点后面插入一个新节点，需要移动后面900元素的位置，因此执行的时间相对来说是最长的。

  • 第17题：

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

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

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

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

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


    正确答案：A
    解析：本题考查点是线性表的基本操作。选项A：线性表按顺序方式存储，性表的第10个结点后面插入一个新结点，需要将第11个元素到第1000个元素依次向后移动一个位置，然后在第11个元素位置处插入新结点，因此要移动990个元素，插入一个元素。选项B：线性表按链接方式存储，性表的第10个结点后面插入一个新结点，只需要修改新结点的指针域和第10个结点的指针域就可以实现，无须移动元素。选项C：线性表按顺序方式存储，删除线性表的第990个结点，需要将第991个元素到第1000个元素依次向前移动一个位置，因此要移动10个元素。选项D：线性表按链接方式存储，删除指针P所指向的结点，只需要修改指针P所指向的指针域就可以实现，无须移动元素。因此，选项A所需的执行时间最长。

  • 第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）
    解析： 暂无解析

相关内容