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

admin2019-08-15 74

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

选项

答案因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为r，显然，十进制数基数为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/1KCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

明清时期专制主义空前加强，据此回答问题：清代在散文方面，声势最大、影响最广的是桐城派，不属于该派的是()

《中国国民党改组宣言》发表的时间是()。

关于一战后构筑的凡尔赛体系，说法不正确的是()。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

【纳赛尔】(GamalAbdelNasser，1918—1970)北京师范大学2000年世界现当代史真题；南京大学2013年国际关系史真题

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

若某浮点机基数为4，尾数采用补码表示，则该浮点机的规格化尾数形式为()。

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

“把党建设成为始终走在时代前列、人民衷心拥护、勇于自我革命、经得起各种风浪考验、朝气蓬勃的马克思主义执政党”是新时代党的建设的()

患者，男性，65岁。阵发性胸痛10天，每次发作持续10分钟左右，运动可诱发。近1周胸痛发作频率增加，休息时亦有发作。有陈旧心肌梗死病史。该患者暂时不宜做的检查是

水利工程建设项目种类按其功能和作用可分为()。

甲公司共拥有两套相同的房屋，原价均为1000000元。一套用于生产经营，另一套则租给了乙公司，每年收取租金收入60000元。当地规定在计算房产税时允许减除的比例为30%，则甲公司每年应该交纳的房产税为()。

随着物质文明的不断发展，中国人民的精神文明也得到了极大的提升，但仍然有很多崇尚封建迷信的人，为求“平安富贵”，常会请和尚看相，请大师看风水，甚至迁祖坟等。从本质上看，这种做法属于()。

下列属于国家赔偿范围的是()。

第八次中国——一东盟经贸部长会议于2009年8月15日在泰国首都曼谷召开，双方共同签署了中国——东盟自贸区《投资协议》，标志着中国与东盟历时7年之久的自贸区主要谈判任务已经完成，该协议的重要意义在于

Marriagemayimproveyoursleep,andbettersleepmayimproveyourmarriage,twonewstudiessuggestWomenwhoaremarriedo

Readthearticlebelowaboutprofessionalheadhunters.Choosethebestsentencefromtheoppositepagetofilleachoftheg