2. 计算机
  3. 搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高，其实互异的查询串不超过三百万个；显然，一个查询串的重复度越高，说明查询它的用户越多，也就是越热门)。现要统计最热门的

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高，其实互异的查询串不超过三百万个；显然，一个查询串的重复度越高，说明查询它的用户越多，也就是越热门)。现要统计最热门的

admin2019-05-11  50
问题 搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高，其实互异的查询串不超过三百万个；显然，一个查询串的重复度越高，说明查询它的用户越多，也就是越热门)。现要统计最热门的10个查询串，且要求使用的内存不能超过1GB。以下各方法中，可行且效率最高的方法是____________。
选项 A、将一千万个查询串存入数组并进行快速排序，再统计其中每个查询串重复的次数
B、将一千万个查询串存入数组并进行堆排序，再统计其中每个查询串重复的次数
C、利用哈希表保存所有的查询串并记下每个查询串的重复次数，再利用小根堆选出重复次数最多的10个查询串
D、利用哈希表保存所有的查询串并记下每个查询串的重复次数，再利用大根堆选出重复次数最多的10个查询串
答案C
解析 本题考查数据结构应用知识。
快速排序和堆排序都属于内部排序方法，要求待排序的元素序列都放在内存。按最坏情况考虑，一千万个查询串需要的存储空间为225千万字节，也就是2．25×1010字节，远超过1GB(约等于109)的存储容量限制，所以选项A和B是不可行的。另外，即便不考虑存储容量限制，在只要求找出最大的10个元素时快速排序也是不适用的。
选项C和D的区别是利用大顶堆还是小顶堆。设想需要在1000个元素中找出10个最大元素，用小顶堆的思路是：先用前10个元素建个小顶堆(堆顶是最小元素)，此后从第11个元素开始，顺序地将每个元素与堆顶元素比较，若小于或等于堆顶元素就舍弃之，若大于堆顶元素，则用该元素替换堆顶元素，并再次调整为小顶堆。重复该过程直到最后一个元素处理完，那么，在小顶堆中留下的10个元素实际上就是这1000个元素中的前10大元素。
本问题中需要在三百万个元素中按照重复次数找最大的10个元素，由于10个元素构成的小顶堆建立和调整时所花费的时间是个很小的常数c0，因此，采用这种方式在n为三百万个元素时找出10个最大者的运算时间是线性阶的(大约为n+e0，c0是小整数)。反之，如果采用大顶堆，一种情况是建立10个元素构成的大项堆，则在顺序地处理后面元素时，无法简单地确定需要替换该大顶堆中的哪个元素；另一种情况是建立由三百万个元素构成的大顶堆，在该数据量情况下，哈希表和大项堆都在内存存储，可能会突破1GB的存储容量限制，而且建立初始大顶堆的运算时间(有可能是达到4n)以及后面9次调整大顶堆的时间(9logn)的时间都远多于前面的小顶堆方案。
转载请注明原文地址:https://kaotiyun.com/show/GvVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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