2. 计算机
  3. 某顺序存储的表格，其中有90000个元素，已按关键字的值的上升顺序排列。现假定对各个元素进行查拢的概率是相同的，并且各个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为(56)，最大比较次数是(57)。 　　　现把90000个元素按排列顺序划

某顺序存储的表格，其中有90000个元素，已按关键字的值的上升顺序排列。现假定对各个元素进行查拢的概率是相同的，并且各个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为(56)，最大比较次数是(57)。 　　　现把90000个元素按排列顺序划

admin2009-02-15  43
问题 某顺序存储的表格，其中有90000个元素，已按关键字的值的上升顺序排列。现假定对各个元素进行查拢的概率是相同的，并且各个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为(56)，最大比较次数是(57)。
　　　现把90000个元素按排列顺序划分成若干组，使每组有g个元素(最后一组可能不足g个)。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的8是(58)，此时的平均比较次数是(59)，当s的值大于90000时，此方法的查找速度接近于(60)。
选项 A、快速分类法
B、斐波那契查找法
C、二分法
D、顺序查找法
答案D
解析 对于顺序查找法，显然平均比较次数为45000，最大比较次数为90000。
分块查找时，在块内进行顺序查找，当在给定n的前提下，组g取时，总的平均比较次数取最小值所以可以得出g的大小为300，平均比较次数也为300 (略去1不计)。
显然，当g大于90000时，全部元素构成一组，此法的查找速度接近于顺序杳找法。
转载请注明原文地址:https://kaotiyun.com/show/YQxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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