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

admin2019-08-01 42

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。

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

1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。

简述大化改新的内容和影响。

玛雅人的物品交换颇为发达，通常用来作为交换媒介的是()。

()是清代管理边疆少数民族地区事务的机关，也掌管一部分外交事务。

血管紧张素转换酶(ACE)抑制药卡托普利的化学结构是

料位最高时，料位计指示也最高，这时探头接收到的射线最强。()

在德育教育中，对学生要坚持（），（），（），（）的方针。

股骨颈骨折病人术后第2周可进行

垂体病变引起丘脑上部病变引起

乳岩情志郁结证的用方是乳岩气血虚弱证的用方是

建设工程法律、行政法规、部门规章的效力从高到低依次为(　　)。

浙江三雕包括()。

强制储蓄效应

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

计算机408

学硕统考专业

列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。

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

1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。

简述大化改新的内容和影响。

玛雅人的物品交换颇为发达，通常用来作为交换媒介的是()。

()是清代管理边疆少数民族地区事务的机关，也掌管一部分外交事务。

血管紧张素转换酶(ACE)抑制药卡托普利的化学结构是

料位最高时，料位计指示也最高，这时探头接收到的射线最强。()

在德育教育中，对学生要坚持（），（），（），（）的方针。

股骨颈骨折病人术后第2周可进行

垂体病变引起丘脑上部病变引起

乳岩情志郁结证的用方是乳岩气血虚弱证的用方是

建设工程法律、行政法规、部门规章的效力从高到低依次为( )。

浙江三雕包括()。

强制储蓄效应

建设工程法律、行政法规、部门规章的效力从高到低依次为(　　)。