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

admin2023-02-06 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/zXPiFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

一个好的教师必须挚爱自己的职业，对教学有极大的热情，这样他才可能积极地投入到教学工作中去。这体现了()是成为好教师的关键。

卡文顿根据学生追求成功和避免失败的倾向，将学生分为四类，其中()的学生有很多保护自己胜任感的策略，使用各种自我防御术，从外部寻找个人无法控制的原因来解释失败。

教师的教育专业素养除要求教师具有先进教育理念、良好的教育能力外，还应具有()。

下列不属于《中小学教师职业道德规范》中“终身学习”的内容的是()。

我国地大物博，许多风景名胜和古迹分布在名山大川之中。下列关于我国风景名胜的叙述中，错误的是：

一个梯子靠墙摆放，顶端距离地面高度为5米。如果将其底部朝着墙移动1米。则顶端高度也将上升1米。此时梯子底部与墙面距离为：

F1赛车中，赛车手为了提升成绩，往往喜欢追求高速转弯。但高速转弯很容易侧滑出跑道引起事故。当赛车进入如图的弯道时，图中的4条路线中较合理的是()。

总线的一次信息传送过程大致分为()阶段。Ⅰ．请求总线Ⅱ．总线仲裁Ⅲ．寻址(目的地址)Ⅳ．信息传送Ⅴ．状态返回(错误报告)

在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的()

甲系某国有公司的经理，在其任职期间，利用职务便利，以明显高于市场的价格向其妻弟经营的工厂采购原料，使公司遭受重大损失。甲的行为构成()

桡神经损伤可致()

钩端螺旋体病的传播途径不包括

(2005)文化遗产保护最重要的原则是()。

现有一种债券，期限为3年，息票利率为10％，面值为1000美元，每年付息一次。请根据以上资料回答下列问题：如果该债券只在到期日一次性返还本金和利息，市场收益率为15％，那么该债券的市场价格应为()美元。

A证券的预期报酬率为12％，标准差为15％；B证券的预期报酬率为18％，标准差为20％。投资于两种证券组合的机会集是一条曲线，有效边界与机会集重合，以下结论中正确的有()。(2005年)

简述历史教学中复习的意义。

对于ASCII码在机器中的表示，下列说法正确的是