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

来源：学生作业帮编辑：神马作文网作业帮分类：综合作业时间：2024/11/12 22:27:19

一道数据结构题目求解释。为什么？
下面的叙述不正确的是（ B.C ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

线性表有两种存储方式：顺序存储（也就是用数组），链式存储（也就是用链表）。
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选项是正确的。

一道数据结构题目求解释。为什么？求一道数据结构题目!C语言的! 一道数据结构题目求解答（给追加）一道高中地理题目,求解释. 一道高中地理题目,求解释~~` 求一句话数据结构的解释数据结构的题目求解答数据结构题目，求大神解决。！~！一道数据结构题目,求解,高手速来! 一道数据结构题目：哈弗曼算法求解一道数据结构题目（高手进）数据结构题目,