若有一个无序顺序表r1和递增有序顺序表r2，它们均含有n个元素，且可能存在相同关键字的元素。设计两个算法分别输出r1和r2中第一个关键字为k的元素位置，并分析成功查找的平均查找长度。

题目描述：给定两个无序顺序表r1和r2，它们均含有n个元素，并可能存在相同关键字的元素。设计两个算法分别输入r1和r2中第一个关键字为k的元素位置，并分析成本查找的平均查找长度。

答案：

该题考查的是查找算法。

算法一：顺序查找

该算法是从表的第一个元素开始顺序地对每一个元素进行比较，直到找到关键字等于k的元素为止。

该算法的成本是：

当查找到目标元素在待查找表的前面时，需要进行n次比较，查找成本为(n+1)/2。

当查找到目标元素在待查找表的后面时，需要进行n次比较，查找成本为n。

当目标元素不存在时，需要进行n次比较，查找成本为(n+1)/2。

因此平均查找长度为：

(n+(n+1)/2)/n= (3n+1)/4

算法二：折半查找

该算法是利用顺序表有序的特点，先将表分成两个部分，然后取中间位置的元素与关键字进行比较，如果相等，直接返回；如果中间位置的元素大于关键字，则在左半部分中继续查找；否则在右半部分中继续查找。

该算法的成本是：

当查找到目标元素时，需要进行k次比较，查找成本为log2n。

当目标元素不存在时，需要进行k次比较，查找成本为log2（n+1）

因此平均查找长度为：

[(log2n+1)/n ]+[(log2(n+1)+1)/n]

=([log2n+log2(n+1)+2]/n)

知识拓展：

平均查找长度是评价查找算法的一个重要指标，它反映了查找算法的效率。在某种意义上，它反映了查找数据所需的平均操作次数。它越小，则说明查找算法越优秀。