2. 考研
  3. 在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是( )。 Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的的直接前驱(2＜=i＜=n) Ⅱ．在最后一个结点后插入一个新的结点 Ⅲ．删除第一个结点 Ⅳ．在第i个结点后插入一个结点

在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是( )。 Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的的直接前驱(2＜=i＜=n) Ⅱ．在最后一个结点后插入一个新的结点 Ⅲ．删除第一个结点 Ⅳ．在第i个结点后插入一个结点

admin2018-09-11  41
问题 在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是(    )。
Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的的直接前驱(2＜=i＜=n)
Ⅱ．在最后一个结点后插入一个新的结点
Ⅲ．删除第一个结点
Ⅳ．在第i个结点后插入一个结点(1＜=i＜=n)
选项 A、仅Ⅰ
B、仅Ⅱ、Ⅲ
C、仅Ⅰ、Ⅱ
D、仅Ⅰ、Ⅱ、Ⅲ
答案C
解析 Ⅰ：由于线性表是用数组表示，即顺序存储，可以直接通过结点编号访问，所以Ⅰ的时间复杂度一定是O(1)。
    Ⅱ：由于是在最后一个结点处插入一个结点，所以不需要移动元素，故时间复杂度为O(1)。
    Ⅲ：删除第一个结点之后，需要将后续所有结点往前移动，所以时间复杂度为O(n)。
    Ⅳ：由于i是不固定的，所以后续结点i+1，i+2，…，n-1，都需要向后移动，所以时间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/AvRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)