对于一个长度为n的顺序存储[1]的线性表[2],在表头插入元素的时间复杂度为()。A. O(log 2 n)B. O(n 2 )C. O(n)D. O(nlog 2 n)

考查要点：本题主要考查顺序存储结构下线性表插入操作的时间复杂度分析。

解题核心思路：
顺序存储结构（如数组）的插入操作需要移动后续所有元素以腾出空间。在表头插入时，所有元素都需要依次后移一位，移动次数与表长$n$成正比，因此时间复杂度为$O(n)$。

破题关键点：

• 顺序存储结构的特点：元素在内存中连续存放，插入操作需物理移动元素。
• 移动次数的计算：表头插入时，需移动$n$个元素，总时间与$n$线性相关。

在顺序存储的线性表中，插入元素的操作步骤如下：

1. 腾出插入位置：
   若在表头插入元素，需将原第1个元素移动到第2个位置，原第2个元素移动到第3个位置，依此类推，直到最后一个元素移动到第$n+1$个位置。
   移动次数：共需移动$n$个元素。

2. 插入新元素：
   将新元素放入腾出的第1个位置。
   时间复杂度：插入操作本身为$O(1)$，但移动元素的时间为$O(n)$，因此总时间复杂度为$O(n)$。

选项分析：

• A. $O(\log_2 n)$：通常对应二分查找等分治算法，与插入无关。
• B. $O(n^2)$：可能出现在多次插入操作且每次移动次数叠加的情况，但本题仅单次插入。
• C. $O(n)$：正确，移动$n$个元素的时间复杂度为线性。
• D. $O(n \log_2 n)$：常见于排序算法（如归并排序），与插入操作无关。