首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的
admin
2019-05-11
31
问题
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过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
程序员上午基础知识考试
软考初级
相关试题推荐
有4个B类网络地址:130.57.16.254、130.57.17.01、130.57.32.254和130.57.33.01。如果子网掩码为255.255.240.0,则下列说法中正确的是______。A.130.57.16.254和130.57.
在Word2003的编辑状态中,若设置一个文字格式为下标形式,应使用“格式”菜单中的菜单项为(1)____;统计文档的字数,需要使用的菜单是(2)____;插入声音文件,应选择“插入”菜单中的菜单项是(3)_____。(3)____
在Linux中,外部设备文件放在(1)_____中,设备文件sdc标识的设备类型为(2)_____。(2)_____A.IDE硬盘B.SCSI硬盘C.CD-ROM驱动器D.软盘驱动器
下列服务组件中,______可以使用户在Linux与Windows操作系统之间实现文件系统和打印机共享功能。A.FTPB.SambaC.DHCPD.Squid
中断是CPU与外部设备数据交换的重要方式。CPU响应中断必须具备三个条件,分别为:外部提出中断请求、中断未屏蔽和(1)____。CPU响应中断后,必须由(2)_____提供地址信息,引导程序进入中断服务子程序;中断服务程序的入口地址存放在(
计算机病毒是(1)_____。特洛伊木马一般分为服务器端和客户端,如果攻击主机为A,目标主机为B,则(2)____。(1)_____A.编制有错误的计算机程序B.设计不完善的计算机程序C.已被破坏的计算机程序D.以危害系统为目的的
下列选项中,(26)不属于”专利法”所称的执行本单位的任务所完成的职务发明。
我国国家标准分为强制性国家标准和推荐性国家标准,强制性国家标准的代号为(25)。
在定点二进制运算中,减法运算一般通过________来实现。
随机试题
以下控制测试程序中,属于测试“采购预付款循环”内部控制“发生”认定的是()。
机械性肠梗阻病例,当腹部平片中显示下列何项变化时应考虑绞窄性肠梗阻的可能
A.妊娠晚期无痛性阴道出血B.妊娠晚期腹痛伴阴道少量出血C.妊娠晚期,休克,阴道出血伴有血尿D.妊娠晚期,腹痛,宫底升高伴阴道出血E.妊娠晚期,胎位不清,阴道少量出血
男性,18岁,因转移性右下腹痛12小时入院,诊断为“急性阑尾炎”,当晚行阑尾切除术,病理为坏疽性阑尾炎。自术后次晨起,患者表现为腹痛,烦躁不安,未解小便。查体:面色较苍白,皮肤湿冷,心率110次/分,较弱,血压10.67/8kPa(80/60mmHg),腹
A.灭鼠B.灭蜱C.灭蚊D.灭蚤E.灭虱流行性乙型脑炎的预防措施是
严寒地区路面混凝土抗冻等级不宜小于()。
著名的SNMP协议使用的公开端口为________。
•Lookatthestatementsbelowandtheinformationaboutcardsontheoppositepage.•Whichcard(A,B,CorD)doeseachstate
Sinceitisnow(i)____tobuildthecomplexcentralprocessingunitofacomputeronasinglesiliconchipusingphotolithograp
A、Hewillhavethefinalexamonthatday.B、Hehasotherpaperstoprepare.C、Hehasbeeniiifor4days.D、Heisn’tabletobo
最新回复
(
0
)