Question

一道数据结构题目求解释。为什么？

下面的叙述不正确的是（ B.C ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

Answer 1

线性表有两种存储方式：顺序存储（也就是用数组），链式存储（也就是用链表）。
1）当线性表用顺序存储的时候，可以随机访问表里面的任意位置 i 的元素，找到任意位置 i 的元素的复杂度是一样的，和位置无关。

这是因为，顺序存储时，每个元素的存储位置的可以计算出来的，因此也就能根据元素在表中的位置，立即找到。

设第一个元素在内存中的地址为addr，每个元素的大小为 element_size 字节。那么第 i 个元素在内存中的位置为：addr+i*element_size(i>=0)。
可以看出，查找任意位置的元素的时间都是一样的。

2）当线性表用链式存储的时候，访问表里面的任意位置 i 的元素，需要从表里面第一个元素开始，逐次向后查找。

这是因为，链式存储时，第0个元素的存储地址是已知的。表中第i(i>=1)个元素的存储位置，保存在第(i-1)个元素中。
因此要知道第 i 个元素的地址，要先知道第(i-1)个元素的地址；
要知道第(i-1) 个元素的地址，要先知道第(i-2)个元素的地址；
......
要知道第 2 个元素的地址，要先知道第1个元素的地址；
要知道第 1 个元素的地址，要先知道第0个元素的地址；
第0个元素的地址是已知的。
可以看出，在链表中找第 i 个元素，和第 0~(i-1)个元素都有关系。第i个元素一共要找了 i 次。
因此，元素的位置越靠前，也就是 i 越小，能越快的找到。

综上所述，题目中的BC选项是不正确的，相反的，AD选项是正确的。