关于数据结构中的顺序表和无序表的查找

来源：百度知道 编辑：UC知道 时间：2024/05/21 10:21:06
若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找,试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同?
⑴查找不成功,即表中没有关键字等于定植k的记录;
⑵查找成功,且表中只有一个关键字等于定植k的记录;
⑶查找成功,且表中有若干个关键字等于定植k的记录,一次查找要求找出所有记录,此时的平均查找长度应考虑到所有记录时所用的比较次数;

由于是进行顺序查找，因此，情况（1）都要照完整个顺序表，需要时间为n次；情况（2）的平均查找长度为n/2，最好情况为1，最差为n；而无序顺序表要查完；情况（3）根情况（2）差不多，但是查找次数要稍微多一些