问题
单项选择题
若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为 (1) 。
A．O(0)
B．O(1)
C．O(n)
D．O(n2
答案
参考答案：C
解析：在线性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定在线性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：[*]。因此，在长度为n的线性表中插入一个元素的时间复杂度为[*]。