首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的
admin
2019-05-11
34
问题
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过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
程序员上午基础知识考试
软考初级
相关试题推荐
十进制数-82,若用二进制补码表示结果为(1)_____;十进制数25,若采用BCD码表示,结果为(2)_____。(1)_____A.01010010B.11010010C.10101101D.10101110
在取指令时首先将(1)_____的内容送往地址寄存器,然后将地址号通过(2)______送至存储器,选中并读取存储器中对应的单元内容。(1)_____A.程序计数器B.通用寄存器C.累加器D.标志寄存器
某计算机采用48×48数字化点阵字模表示一个汉字,字模中的每一个点在存储器中用一个二进制位存储。那么,现有1024个汉字需要在计算机中存储,则要求的存储空间应为______K字节。A.196B.244C.288D.312
以下对象中,______必须要有lock和unlock方法以确保多个用户无法同时改变某一属性。A.ApplicationB.SessionC.RequesetD.Response
SNMP实现其管理功能的方式是______。A.仅使用轮询的方式B.仅使用事件驱动的方式C.使用轮询与事件驱动结合的方式D.以上都不对
Catalyst3500(CiscoIOS系统)中启用STP的命令格式是______。A.spanning-treevlan<vlan>B.nospanning-treevlan<vlan>C.setspantreeenable<vla
下面关于静态路由表说法中错误的是______。A.是由人工方式建立的B.在网络系统运行时,系统将自动运行动态路由选择协议C.网络结构发生变化时,路由表无法自动地更新D.需要网络管理人员将每一个目的地址的路径输入到路由表中
我国著作权法中,______系指同一概念。A.出版权与版权B.著作权与版权C.作者权与专有权D.发行权与版权
一个A类网络已有60个子网,若还要添加两个新的子网,并且要求每个子网有尽可能多的主机ID,应指定子网掩码为(48)。
操作系统的主要任务是________________。
随机试题
应用肽疫苗或T细胞疫苗的理论依据是
正常情况下,窦房结对潜在起搏点的控制,是通过下列哪些方式实现的
肾移植后尿液细胞学检查可预示排斥反应的指征是
人体排泄的嘌呤核苷酸分解代谢的特征性终产物是
郑先生,69岁。右侧腹股沟斜疝嵌顿2小时,经手法复位成功。留院观察重点是
下列哪些案件法院审理时可以调解?(2010年卷二74题)
出口口岸()商品名称规格型号()
2015年4月,甲公司因欠乙公司货款100万元不能按时偿还,向乙公司请求延期至2016年4月1日还款,并愿意以本公司所有的3台生产设备进行抵押和1辆轿车进行质押,为其履行还款义务提供担保。乙公司同意了甲公司的请求,并与甲公司订立了书面抵押合同和质押合同。甲
已知A有一个特征值-2,则B=A2+2E必有一个特征值是_______.
Theyearhasflownanditisthat(1)............!TheAnnualDinnerandDancewillbeheldon(2)............from(3).......
最新回复
(
0
)