首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的
admin
2019-05-11
27
问题
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的10个查询串,且要求使用的内存不能超过1GB。以下各方法中,可行且效率最高的方法是____________。
选项
A、将一千万个查询串存入数组并进行快速排序,再统计其中每个查询串重复的次数
B、将一千万个查询串存入数组并进行堆排序,再统计其中每个查询串重复的次数
C、利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用小根堆选出重复次数最多的10个查询串
D、利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用大根堆选出重复次数最多的10个查询串
答案
C
解析
本题考查数据结构应用知识。
快速排序和堆排序都属于内部排序方法,要求待排序的元素序列都放在内存。按最坏情况考虑,一千万个查询串需要的存储空间为225千万字节,也就是2.25×10
10
字节,远超过1GB(约等于10
9
)的存储容量限制,所以选项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
程序员上午基础知识考试
软考初级
相关试题推荐
某计算机的IP地址为192.168.1.68,网关为192.168.1.254。该计算机现在无法访问IP地址为202.120.45.12的主机,若要检测该计算机在其网段内是否工作正常,应使用______命令。A.ping192.168.1.254B
采用HTML创建一个E-mail地址的链接,下面正确的句法是______。A.<ahref=“mailto:xxxxx@abc.com.cn”>和我联系</a>B.<ahref=“news:xxxxx@abc.com.cn”>和我联系</a>
交换表的内容主要有______。A.目的MAC地址B.所对应的交换机端口号C.所在的虚拟子网D.以上全部
ADSL技术主要解决的问题是______。A.宽带传输B.宽带接C.宽带交换D.多媒体综合网络
虚存页面调度算法有多种,______调度算法不是页面调度算法。A.后进先出(LIPO)B.先进先出(FIFO)C.最近最少使用(LRU)D.随机选择(RAND)
我国著作权法中,______系指同一概念。A.出版权与版权B.著作权与版权C.作者权与专有权D.发行权与版权
中断是CPU与外部设备数据交换的重要方式。CPU响应中断必须具备三个条件,分别为:外部提出中断请求、中断未屏蔽和(1)____。CPU响应中断后,必须由(2)_____提供地址信息,引导程序进入中断服务子程序;中断服务程序的入口地址存放在(
下列选项中,(26)不属于”专利法”所称的执行本单位的任务所完成的职务发明。
汉字的区位码、国标码和机内码(又称内码)是3个不同的概念,假设某个汉字的区号是30(十进制数)、位号是63(十进制数),则在PC中它的内码(十六进制数)是(13)。
著作权权利人不包括______。
随机试题
试述清末教育新政的改革。
医疗机构在药品购销中暗中收受回扣或者其他利益,依法对其给予罚款处罚的机关是
能和三氯化铁发生呈色反应的药物为
承担商业银行风险管理的最终责任的机构是()。
下列选项中,不属于个人资产配置的产品组合的是()。
政府有意识地运用财政政策手段来调节社会总供求,利用国家财力干预经济运行,称为()。
把直线L的方程化为对称方程.
学生的记录由学号和成绩组成,N名学生的数据已在主函数中放入结构体数组S中,请编写函数fun,它的功能是:把分数最低的学生数据放在b所指的数组中,注意:分数最低的学生可能不止一个,函数返回分数最低的学生的人数。注意:部分源程序在文件PROG1.C文件中。请勿
设栈的顺序存储空间为S(1:m),初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后,top=0,则栈中的元素个数为()
Howaretornadoesdistinguishedfromwhirlwinds?Accordingtothepassage,whichofthefollowingbehaviorsisfrequentlychara
最新回复
(
0
)