2. 从业资格
  3. 对n个元素的有序表A[1．．n]进行顺序查找，其成功查找的平均查找长度（即在查找

对n个元素的有序表A[1．．n]进行顺序查找，其成功查找的平均查找长度（即在查找

最全题库2022-08-02  57
问题 对n个元素的有序表A[1．．n]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为（　　）。A.nB.（n+1）／2C.log2nD.n2
选项 A.n
B.（n+1）／2
C.log2n
D.n2
答案 B
解析 本题主要考查顺序查找。对于n个数据元素的表，若给定值key与表中第i个元素的关键字相等，则需进行n-i+1次关键字比较，即Ci=n-i+1。例如，当第n个元素的关键字为key时，需要比较1次（n-n+1=1），又如，当第1个元素为所求时，需要比较n次（n-1+1=n）。因此，查找成功时，顺序查找的平均查找长度为：；其中Pi为每个元素的查找概率，假设所有元素的查找概率均相等，即，则在等概率情况下有：
转载请注明原文地址:https://tihaiku.com/congyezige/2410080.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)