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

admin2016-03-29 75

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

选项

答案因为基数排序所需的时间不仅与文件的大小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

学硕统考专业

分析南斯拉夫走上自治道路的原因。

【《国策基准》】东北师范大学2000年世界史综合卷真题；华东师范大学2013年历史学基础综合真题

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

东汉时期成书的崔寔()主要是地主经营田庄的家历，但是，书中所记农业技术经验也很丰富，为后人所取法。

下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()

中古时代实行索贡巡行赋税征收方式的国家是()。

下面哪项条约没有涉及德国的赔款问题?()

年鉴学派开创了总体史研究方法，其代表人物马克·布洛赫研究中世纪的代表作是()

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。Philosopheri：d0{wait(chopstick[i]；wait(ch

标准普尔公司定义为()级的债务被认为有足够的能力支付利息和偿还本金。尽管在通常情况下其能得到足够的保护，但变化的环境更可能削弱该级债务的还本付息能力。

ディズニーランドは、日曜祭日________、平日も来園者で一杯である。

可燃物、助燃物和点火源是导致燃烧的三要素，缺一不可，是必要条件。()

女性，20岁，风湿性心脏病二尖瓣狭窄病史5年，2年前有咯血病史。近来双下肢间歇性水肿，活动后气促。二尖瓣狭窄患者早期出现大咯血的原因是

唾液中的有机物主要是

液性指数说明土的软硬程度，用于确定()。

工程建设标准根据内容不同，可分为(　　)。

在()中，任何专业投资者的边际市场价值为零。

某种商品1～6周期的实际销售量分别为：580千克、580千克、600千克、610千克、630千克、630千克。采用算术平均数法计算，则第7周期销售量的预测值为()千克。

下列描述属于学习策略的特点的有()

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

计算机408

学硕统考专业

分析南斯拉夫走上自治道路的原因。

【《国策基准》】东北师范大学2000年世界史综合卷真题；华东师范大学2013年历史学基础综合真题

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

东汉时期成书的崔寔()主要是地主经营田庄的家历，但是，书中所记农业技术经验也很丰富，为后人所取法。

下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()

中古时代实行索贡巡行赋税征收方式的国家是()。

下面哪项条约没有涉及德国的赔款问题?()

年鉴学派开创了总体史研究方法，其代表人物马克·布洛赫研究中世纪的代表作是()

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。Philosopheri：d0{wait(chopstick[i]；wait(ch

标准普尔公司定义为()级的债务被认为有足够的能力支付利息和偿还本金。尽管在通常情况下其能得到足够的保护，但变化的环境更可能削弱该级债务的还本付息能力。

ディズニーランドは、日曜祭日________、平日も来園者で一杯である。

可燃物、助燃物和点火源是导致燃烧的三要素，缺一不可，是必要条件。()

女性，20岁，风湿性心脏病二尖瓣狭窄病史5年，2年前有咯血病史。近来双下肢间歇性水肿，活动后气促。二尖瓣狭窄患者早期出现大咯血的原因是

唾液中的有机物主要是

液性指数说明土的软硬程度，用于确定()。

工程建设标准根据内容不同，可分为( )。

在()中，任何专业投资者的边际市场价值为零。

某种商品1～6周期的实际销售量分别为：580千克、580千克、600千克、610千克、630千克、630千克。采用算术平均数法计算，则第7周期销售量的预测值为()千克。

下列描述属于学习策略的特点的有()

工程建设标准根据内容不同，可分为(　　)。