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

admin2019-08-01 34

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

《明定国是》诏的内容不包括()。

赋税是我国古代国家宏观管理经济的重要手段。　　据此回答问题：哪位皇帝的即位首次应用了秘密立储制?()

晚清时期清帝年号的正确排序是

经六朝时期的发展，南方形成了三个农业发达地区即()。

1918年美国总统威尔逊提出“十四点原则”，内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。

制瓷业是光彩夺目的一个手工业部门，北宋的制瓷业的重心在黄河流域和中原地区。回答问题：北宋的四大名窑是()

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

简述“风湿”的含义。

长期服用胺碘酮可以引起

设备设计过程质量监理的依据主要有以下()内容。

下列属于船舶吨税中延期优惠的是()。

下列有关集团财务报表审计的说法中错误的是()。

下列软件不是数据库软件的是_______。

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

计算机408

学硕统考专业

《明定国是》诏的内容不包括()。

赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题：哪位皇帝的即位首次应用了秘密立储制?()

晚清时期清帝年号的正确排序是

经六朝时期的发展，南方形成了三个农业发达地区即()。

1918年美国总统威尔逊提出“十四点原则”，内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。

制瓷业是光彩夺目的一个手工业部门，北宋的制瓷业的重心在黄河流域和中原地区。回答问题：北宋的四大名窑是()

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

简述“风湿”的含义。

长期服用胺碘酮可以引起

设备设计过程质量监理的依据主要有以下()内容。

下列属于船舶吨税中延期优惠的是()。

下列有关集团财务报表审计的说法中错误的是()。

下列软件不是数据库软件的是_______。

赋税是我国古代国家宏观管理经济的重要手段。　　据此回答问题：哪位皇帝的即位首次应用了秘密立储制?()