Question

顺序表查找的平均查找长度是多少？

Answer 1

若对大小为N的有序顺序表进行顺序查找，当查找不成功时，平均查找长度为 59)；当查找成功且表中仅有一个关键字等于欲查找的元素时，平均查找长度为 60 。

由于计算平均查找长度是以最坏可能性考虑,故从第一个节点开始比较到尾节点，需要比较n次，查找长度n；从第二个节点开始比较到尾节点,需要比较n-1次，查找长度n-1，最后一个节点比较1次,查找长度1，总长数＝n+(n-1)+...+2+1=n(n+1)/2。

查找不成功时平均查找长度＝(n(n+1)/2)* (1/(n+1))=n/2 ，具体算的过程类似查找成功时平均查找长度（ASL=(n+1)/2)。

扩展资料：

顺序表顺序将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构采用顺序存储结构的线性表。

顺序表的存储特点：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L
　1≤i≤n 其中，L是元素占用存储单元的长度。

参考资料来源：百度百科-顺序表