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

admin2019-08-15 45

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

选项

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

学硕统考专业

下列哪部戏剧不是曹禺的作品()。

清政府在鸦片战争中战败的主要原因是()。

中国共产党在大革命失败后，根据中国革命的新特点，明确了“工农武装割据”的思想，其核心内容不包括()。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：对于二里头文化的发现的意义，下列选项表述最准确的是()

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

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

下列关于RISC的叙述中，错误的是()。

电解质离子通过细胞膜的扩散量取决于

十二经筋是指：十二皮部是指：

A．补体经典激活途径的固有成分B．补体旁路激活途径的固有成分C．补体三条激活途径的共同成分D．补体旁路途径激活物E．补体经典途径激活物脂多糖

男性，39岁。尿道疼痛，阴部、腰骶部不适，排尿不畅，下腹部不适，精神抑郁，舌质淡红，苔薄白腻，脉弦数。实验室检查：衣原体检测结果阳性。以下治疗方法中不妥当的是

某企业“预收账款”账户期末贷方余额为150000元，本期共增加130000元，减少140000元，则该账户的期初余额为()元。

以下不属于导游从事领队服务的条件的是()。

认为教学的主要任务在于通过开设希腊文、拉丁文、逻辑、文法和数学等学科发展学生的智力，至于学科内容的实用意义则是无关紧要的。这是()。

与恒牙相比较乳牙髓腔形态特点是什么?

关于犯罪的未完成形态，下列表述正确的有()。