Question

．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）

Answer 1

 O（n）

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

扩展资料：

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。

当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。

Answer 2

C
时间复杂度没有用i表示的，AD不对，这个题可以用最坏情况下的时间复杂度表示时间复杂度，最坏情况下就是访问an，指针需要移动n次，因此时间复杂度为O(n)

Answer 3

好吧，刚好搜到，，，当算法的时间复杂度T(n)与n无关时，T(n)=O(1).
T(n)与n成线性时T(n)=O(n).
位置为i意味着执行i次，则i<n=O(n).