题目
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。A. O(n)，O(n)B. O(n)，O(1)C. O(1)，O(n)D. O(1)，O(1)
对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。
A. O(n)，O(n)
B. O(n)，O(1)
C. O(1)，O(n)
D. O(1)，O(1)
题目解答
答案
C. O(1)，O(n)
解析
顺序存储的线性表（如数组）的访问和增删操作的时间复杂度分析：
- 访问结点：通过数组索引直接计算存储地址，时间复杂度为O(1)。
- 增删结点：需要移动后续元素以腾出或填补空间，时间复杂度为O(n)（最坏情况下需移动所有元素）。
访问结点的时间复杂度
- 顺序存储结构中，每个元素的存储位置可通过公式计算：
起始地址 + (i-1)*元素大小。 - 无需遍历，直接定位，因此时间复杂度为O(1)。
增删结点的时间复杂度
- 插入：假设在第k个位置插入元素，需将第k到第n个元素依次后移一位，时间复杂度为O(n)。
- 删除：假设删除第k个元素，需将第k+1到第n个元素依次前移一位，时间复杂度为O(n)。