数据结构
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。A、O（log2n）B、O（1）C、O（n）D、O（n2）
题目
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。
- A、O（log2n）
- B、O（1）
- C、O（n）
- D、O（n2）
相似问题和答案
第1题：
A、n-i
B、n-i+l
C、n-i-l
D、i
第2题：
A、O(nlog2n)
B、O(1)
C、O(n)
D、O(n2)
第3题：
● 对具有n个元素的顺序表（采用顺序存储的线性表）进行 （40） 操作，其耗时与n的大小无关。
（40）A．在第i（1≤i≤n）个元素之后插入一个新元素
B．删除第i（1≤i≤n）个元素
C．对顺序表中的元素进行排序
D．访问第i（1≤i≤n）个元素的前驱和后继
试题（40）分析
本题考查数据结构基础知识。
线性表的逻辑关系特点是元素依序排列。当采用顺序存储方式时（一维数组存储），可以随机访问其中的任何一个元素。在表中插入元素和删除元素都要移动其他元素，所需移动的元素个数大约为n/2，而排序所需时间更是与表中元素个数n相关。
参考答案（40）D
第4题：
以下关于线性表存储结构的叙述，正确的是（57）。
A.线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C.线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级，因为顺序存储结构访问元素时，能直接定位元素，这样，操作的时间复杂度为O（1）。
第5题：
向一个长度为n的顺序表中第i个元素(0≤i≤n)位置插入一个新元素时，需要从后向前依次后移(32)个元素。
A．n-i
B．n-i+1
C．n-i-1
D．i
解析：从n-1开始的元素都需要从后向前依次后移，直到包括i位置。需要移动n-1-i+1个元素。
第6题：
第7题：
第8题：
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()。
A.O（0）
B.O（1）
C.O（n）
D.O（n2）
第9题：
若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为(1)。
A．O(0)
B．O (1)
C．O(n)
D．O(n2)
解析：性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：。因此，在长度为n的线性表中插入一个元素的时间复杂度为。
第10题：
若长度为n的线性表采用顺序存储结构，那么删除它的第i个元素，需要它依次向前移动 ______个元素。
A．n-i
B． n+i
C． n-i-1
D． n-i+1
解析： 线性表顺序存储结构删除第i个元素，需将i以后的元素都向前移动一个位置，所以是n-i个元素。