判断下列说法是否正确：在长度都为n的有序单链表和顺序表上分别

[单选题]

判断下列说法是否正确：在长度都为n的有序单链表和顺序表上分别做顺序查找，若查找每个元素的概率相等，
则顺序查找表中任一元素的查找成功的平均查找长度相同。（）

```
正确
```
```
错误
```

别把我的紫青宝剑

答案：A

这个题比较关键的一点是理解最后一句话中的“顺序查找”。顺序查找的意思应当是按照这组数据从小到大（或从大到小）的顺序进行查找。

①有序单链表本质是单链表，单链表的访问只能是从第一个结点开始，用一个结点的next指针访问下一个结点，每访问一个结点就对比该结点中的数据是否是我们需要找的数据，如果是则说明找到然后停止查找，如果不是则依次访问下一个结点进行对比查找；因为该单链表有序，那么我们顺序查找这组数据时访问的次数依次是1,2，……，n-1,n（或者反之n，……，1），平均查找长度就是（n+1）/2。

②顺序表就相当于是一个数组，这组数据无序地存放在一个数组中，访问无序的数组的流程与访问单链表的类似，都是需要访问然后对比是否是所要找的数据，是则停止访问，否则访问下一个继续对比。因此平均查找长度也是（n+1）/2。

发表于 2020-03-18 09:58:47 回复(0)

Finalize

答案是A

顺序查找情况下线性表都是一个方向查找的(只有顺序查找存储结构可以既是顺序表和链表），所以平均查找长度一定是一样的

发表于 2020-04-01 16:07:32 回复(0)

牛客110086

答案：A

解析：（1）由于链表不能随机访问，要访问某个结点，必须从它的直接前趋指针域出发才能找到。因此，链式存储的线性表，即使是有序表，也只能使用顺序查找。顺序查找时，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。

假设在每个位置查找概率相等，即P1=P2… =Pn=1/n，若是从表头向表尾方向查找，则每个位置上查找比较次数为C1=1,C2=2,…，Cn=n。于是，查找成功的平均查找长度为：1×1/n+2×1/n+...+n×1/n=(n+1)/2

（2）有序单链表和顺序表都是单链表，查找方式相同，因此平均查找长度也相同。

发表于 2020-03-10 20:01:11 回复(0)

提交观点

问题信息

查找

上传者：zsw3

难度：

3条回答 1收藏 3765浏览

判断下列说法是否正确：在长度都为n的有序单链表和顺序表上分别

问题信息

热门推荐

相关试题