单选题

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

【正确答案】 C

【答案解析】

假定在线性表的任何位置上插入元素的概率 p i 是相等的，则在长度为 n 的线性表中插入一个元素时所需要移动元素的平均次数为