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

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

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

计算机408

学硕统考专业

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