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

admin2023-02-06 44

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

教师劳动所创造的价值，并不是以物化的形式表现出来的，而是作为一种潜在价值因素存在于学生身上。这说明教师劳动具有滞后性的特点。()

以下选项除了()都是教师仪容仪态需要遵守的要求。

无论是在社会主义社会，还是在资本主义社会，甚至是在其他的社会形态里，人们的某些行为规范是相同的，比如尊老爱幼，因此道德是没有阶级性之分的，是人类共有的行为规范。()

《党政机关公文处理工作条例》规定，公文处理工作应当坚持的原则包括()。

根据我国仲裁法，下列事项不能申请仲裁的有()。

以下现象不属于学习迁移的是()。

现代教学提倡以系统的观点为指导来选用教学方法，优化教学。选择教学方法主要的依据有()。

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1≤i≤n+1)。

已知开环稳定的系统，其开环频率特性的奈奎斯特图如图所示，则该闭环系统________。

能够引起体位性低血压的药物有：

患者，女，19岁，诊断为弥漫性单纯甲状腺肿，其合适的治疗方法是

早期诊断宫颈癌采用以下哪一项

牵牛子的功效有

关于司法和司法制度，下列哪一表述不成立？(2011—卷一—45，单)

财产转让所得中可扣除的费用有(　　)。

由于技术错误或人为造成房屋倒塌、伤害人命等，承包商都必须承担刑事责任，这属于()。

A、自然连接B、交C、投影D、并A关系R和关系S有公共域，关系T是通过公共域的等值进行连接的结果，符合自然连接，选A。

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

计算机408

学硕统考专业

教师劳动所创造的价值，并不是以物化的形式表现出来的，而是作为一种潜在价值因素存在于学生身上。这说明教师劳动具有滞后性的特点。()

以下选项除了()都是教师仪容仪态需要遵守的要求。

无论是在社会主义社会，还是在资本主义社会，甚至是在其他的社会形态里，人们的某些行为规范是相同的，比如尊老爱幼，因此道德是没有阶级性之分的，是人类共有的行为规范。()

《党政机关公文处理工作条例》规定，公文处理工作应当坚持的原则包括()。

根据我国仲裁法，下列事项不能申请仲裁的有()。

以下现象不属于学习迁移的是()。

现代教学提倡以系统的观点为指导来选用教学方法，优化教学。选择教学方法主要的依据有()。

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1≤i≤n+1)。

已知开环稳定的系统，其开环频率特性的奈奎斯特图如图所示，则该闭环系统________。

能够引起体位性低血压的药物有：

患者，女，19岁，诊断为弥漫性单纯甲状腺肿，其合适的治疗方法是

早期诊断宫颈癌采用以下哪一项

牵牛子的功效有

关于司法和司法制度，下列哪一表述不成立？(2011—卷一—45，单)

财产转让所得中可扣除的费用有( )。

由于技术错误或人为造成房屋倒塌、伤害人命等，承包商都必须承担刑事责任，这属于()。

A、自然连接B、交C、投影D、并A关系R和关系S有公共域，关系T是通过公共域的等值进行连接的结果，符合自然连接，选A。

财产转让所得中可扣除的费用有(　　)。