单选题若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为______。(1≤i≤n+1)。

【正确答案】 C

【答案解析】 假定在线性表的任何位置上插入元素的概率Pi是相等的，则在长度为n的线性表中插入一个元素时所需要移动元素的平均次数为由此可见，在长度为n的线性表中插入元素的时间复杂度为D(n)。同理，可以计算出在长度为n的线性表中删除一个元素的时间复杂度也为O(n)。