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

admin2023-02-06 41

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

选项

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

学硕统考专业

在成就测验的类型中，()是在教学过程中实施的，虽然也要让学生做题，对他们的作业评分，但其目的不是为学生划分等级，而是为了获取学生学习进步情况的有关信息，以便据此改进教学并促进学生学习。

对公文的主要信息和办理情况进行详细记载的处理活动属于收文办理中的()。

根据十九大精神，全面从严治党需要把()摆在首位。

长跑、登山等是需要长久坚持性的运动，以具备()气质特征的人选为佳。

课堂上经常出现这样的情况：在老师讲课的过程中，有的学生会在下面偷偷聊天；在做练习时，有的学生总是窃窃私语或很自由地大声讨论问题；一讨论起问题，学生就会争论不休。对此，下列相关表述最恰当的是()。

下面的叙述中正确的是()。Ⅰ．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比

磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220tpm，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200rpm。假定π=3，试

当出现下列哪种情况时，非正式群体会影响工作效率()

商品价值的货币表现是()

有助于黄瘤诊断的辅助检查不包括

患儿8个月，3天高热，咳嗽频繁。查体：T40℃，精神萎靡，呼吸困难，肺部闻及细湿口罗音，心率速，胸片示两肺有多发性小脓肿，血象WBC30.0×109/L，N0.90，最可能的诊断为

热力管网试运行的时间应从正常试运行状态的时间开始计算连续运行()h。

有的学校的学生修完规定年限的教育后，学校不发毕业证，这侵犯了学生的()。

某课堂以传授系统知识和理论为主要目的，应选择的教学方法是()。

中国共产党领导的多党合作制度是中国特色社会主义民主政治制度的基本内容之一。()

教学为个人全面发展提供科学的()。

关系中的属性或属性组合，其值能够唯一地标识一个元组，该属性或属性组合可选作为【】。