首页
登录
从业资格
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度
考试题库
2022-08-02
50
问题
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的10个查询串,且要求使用的内存不能超过1GB。以下各方法中,可行且效率最高的方法是(41)A.将一千万个查询串存入数组并进行快速排序,再统计其中每个查询串重复的次数B.将一千万个查询串存入数组并进行堆排序,再统计其中每个查询串重复的次数C.利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用小根堆选出重复次数最多的10个查询串D.利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用大根堆选出重复次数最多的10个查询串
选项
A.将一千万个查询串存入数组并进行快速排序,再统计其中每个查询串重复的次数
B.将一千万个查询串存入数组并进行堆排序,再统计其中每个查询串重复的次数
C.利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用小根堆选出重复次数最多的10个查询串
D.利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用大根堆选出重复次数最多的10个查询串
答案
C
解析
本题考查数据结构应用知识。
快速排序和堆排序都属于内部排序方法,要求待排序的元素序列都放在内存。按最坏情况考虑,一千万个查询串需要的存储空I间为225千万字节,也就是2.25×1010)字节,远超过1GB(约等于109)的存储容量限制,所以选项A和B是不可行的。另外,即便不考虑存储容量限制,在只要求找出最大的10个元素时快速排序也是不适用的。
选项C和D的区别是利用大顶堆还是小顶堆。设想需要在1000个元素中找出10个最大元素,用小顶堆的思路是:先用前10个元素建个小顶堆(堆顶是最小元素),此后从第11个元素开始,顺序地将每个元素与堆顶元素比较,若小于或等于堆顶元素就舍弃之,若大于堆顶元素,则用该元素替换堆顶元素,并再次调整为小顶堆。重复该过程,直到最后一个元素处理完,那么,在小顶堆中留下的10个元素实际上就是这1000个元素中的前10大元素。
本问题中需要在兰百万个元素中按照重复次数找最大的10个元素,由于10个元素构成的小顶堆建立和调整时所花费的时间是个很小的常数c0,因此,釆用这种方式在n为三百万个元素时找出10个最大者的运算时间是线性阶的(大约为n+c0,c0是小整数)。反之,如果采用大顶堆,一种情况是建立10个元素构成的大顶堆,则在顺序地处理后面元素时,无法简单地确定需要替换该大顶堆中的哪个元素;另一种情况是建立由三百万个元素构成的大顶堆,在该数据量情况下,哈希表和大顶堆都在内存存储,可能会突破1GB的存储容量限制,而且建立初始大顶堆的运算时间(有可能是达到4n)以及后面9次调整大顶堆的时间(9logn)的时间都远多于前面的小顶堆方案。
转载请注明原文地址:https://tihaiku.com/congyezige/2425612.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
小儿5岁时食管的长度为A.10cm B.12cm C.14cm D.16c
记录和总结每日的时间消耗情况,分析时间浪费的原因,采取适当的措施属于A.ABC时
在Linux操作系统中,网络管理员可以通过修改()文件对Web服务器端口
通常使用()作为用户名进行匿名FTP访问。A.guest B.email地
网络用户能进行QQ聊天,但在浏览器地址栏中输入www.educity.cn却不
图像文件格式可以分为静态和动态图像文件格式,以下文件格式中()属于动态图像文件格
宏病毒可以感染()文件。A.EXE B.COM C.Word D.DLL
入侵检测系统无法()。A.监测并分析用户和系统的活动 B.评估系统关键资源数据
包过滤防火墙不能()。A.防止感染了病毒的软件或文件的传输 B.防止企业内
在WindowsXP中,可以使用()来浏览日志文件,其中包含有()。A.用户
随机试题
Everythingaboutmyfuturewasambiguouslyassumed.Iwouldgetintodebtbygoi
[originaltext]W:Lookatthatbigfieldofcorn.Andthere’safarmwithsomeb
王某承租赵某私房两间。租期届满前,王某向赵某提出愿以6万元购买该房,赵某表示同意
更年期妇女内分泌变化主要表现为A.FSH升高,LH水平增高,雌、孕激素水平下降
关于幕墙工程技术的说法,错误的是( )。A.全玻幕墙的板面不得与其他刚性材料直
左图为给定的立体图,从任意角度剖开,右边哪一项不可能是它的截面图? A.如上图
行政复议机关应当自受理申请之日起()日内作出行政复议决定。A、15 B、30
在公路、铁道桥上敷设电缆要采取的措施有()。A.不得敷设在通行的路面上 B.
某单项工程,按如下进度计划网络图组织施工。 原计划工期是170d,在第75
诊断肺炎球菌肺炎,以下哪一项化验检查最有价值?( )A.痰培养可见肺炎球菌
最新回复
(
0
)