题8

题8

题目

[!question]+
在 个元素的线性表的数组表示中,时间复杂度为 的操作是().
I. 访问第 个结点和求第 个结点的直接前驱
II. 在最后一个结点后插入一个新的结点
III. 删除第1个结点
IV. 在第 个结点后插入一个结点
A. I
B. II. III
C. I. II
D. I. II. II

分析

[!NOTE]+
访问查找，都是可以通过序号直接O1的，但是插入和删除，因为需要调整整个结构，挪动元素，显然不是O1的

解

[!done]+
C
对于 ,解析略; 对于 ,在最后位置插入新结点不需要移动元素,时间复杂度为 ; 对于 III,被删结点后的结点需要依次前移,时间复杂度为 ; 对于 IV,需要后移 个结点, 时间复杂度为 。