第 1 题
下列对顺序存储的有序表（长度为 n）实现给定操作的算法中平均时间复杂度为 O(1) 的是（ ）。
A. 查找包含指定值元素的算法 B. 插入包含指定值元素的算法 C. 删除第 i 个元素的算法 D. 获取第 i 个值的算法
[tag_link]
正确答案：D
线性表的顺序存储结构采用一组地址连续的存储单元依次存储线性表的数据元素。特点是逻辑上相邻的数据元素在物理位置上相邻。线性表顺序存储结构是一种随机存取的存储结构，设线性表的每个元素占 L 个存储单元，第一个元素a1的存储地址是 LOC(a1)，则任意元素ai的 LOC(ai)=LOC(a1)+(i-1)*L。因此获取第 i 个值的算法为常量阶 O(1)。