将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

admin2016-03-29 81

问题将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

选项

答案因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为厂，显然，十进制数基数为10，二进制数的基数为2。要建立r个空队列所需时间为O(r)；把n个记录分放到各个队列中，重新收集起来需要的时间为O(n)，因此一趟排序所需的时间复杂度为O(n+r)；若每个关键字有d位，则总共要进行d遍排序，所以基数排序的时间复杂度为O(d(n+r))。由于关键字的位数d与基数r和最大关键字取值有关。因此不同的r和关键字将需要不同的时间。所以，本题中总的时间复杂度为O(d(n+2))，d为关键字最大值对应的二进制数位数，即将十进制的关键字用二进制数表示时，复杂度增大了。另外只需要设置两个指针队列，即将十进制的关键字用二进制数表示时，空间复杂性减少了。

解析

转载请注明原文地址:https://kaotiyun.com/show/11Ri777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?

计算机408

学硕统考专业

下面对官渡之战的表述正确的是()。

凡尔赛体系是由一系列条约组成的，其中战胜国与匈牙利签订的条约为()。

对《魏玛宪法》的内容和影响叙述不正确的是()。

分析抗战胜利后的国际国内形势。

简述中共七大的背景、内容和意义。

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

罗斯福和胡佛经济政策的最大区别在于()。

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

一次分配所有资源的方法可以预防死锁的发生，它破坏的死锁四个必要条件中的()。

关于妊娠合并糖尿病的处理，不恰当的为

A、7-羟基黄酮醇B、5，7-二羟基黄酮C、5，7-二羟基异黄酮D、5，7-二羟基二氢黄酮E、5，7-二羟基二氢黄酮醇1HNMR中δ5.2左右有一个呈双二重峰芳香质子信号(J=11.0Hz，5.0Hz)的化合物是（

静脉滴注给药达到稳态血药浓度99％所需半衰期的个数为()。

某期货公司的资产为3亿元，负债为1．8亿元，该公司进入风险预警期。在风险预警期，证监会派出机构可以采取的措施有()。

支票限于见票即付，不得另行记载付款日期。另行记载付款日期的法律后果是()。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是()。

()第一次从国家的角度阐明了中等教育应该面向所有儿童的设想，明确提出了初等教育后分流的主张。

Whatisthenoticeabout?

Here’smyphonenumber.Let’skeepin______.