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

admin2019-08-01 43

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

选项

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

学硕统考专业

试述明代一条鞭法的主要内容和历史意义。

曾被日本维新派人士视为“枕中鸿宝”，对日本明治维新产生重要影响的著作是()。

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

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

试论魏孝文帝改革的内容及其意义。

两税法产生的背景、内容是什么?并对其进行评价。

试述新生活运动的主要内容并作评价。

(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

对于出口商品，经检验部门检验合格后，凭_______进行通关()

何时拔出负压引流管

煎中药时，一般第一煎加水量应淹过药面

在规定时间内没有参加资质年检的工程监理企业，其资质证书自行失效，且(　　)年内不得重新申请资质。

根据我国民事诉讼法的规定，该纠纷应由()的法院管辖。在确定由一个法院管辖后，G公司可以以()的身份参加诉讼。

【资料】李老师在检查学生知识掌握的情况时，通常其试卷不单选用选择题和判断题，还常常借助于填空题、简答题和论述题等。李老师的这种做法是否正确?

矛盾不可避免，问题总是存在，但我们既不能因为畏惧困难就，也不能只凭的一腔血勇。填入画横线部分最恰当的一项是()。

公民的作品，其发表权、著作财产权的保护期为作者终生及其死亡后五十年，作者的署名权、修改权、保护作品完整权的保护期不受限制。()

Internet使用的协议是

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

计算机408

学硕统考专业

试述明代一条鞭法的主要内容和历史意义。

曾被日本维新派人士视为“枕中鸿宝”，对日本明治维新产生重要影响的著作是()。

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

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

试论魏孝文帝改革的内容及其意义。

两税法产生的背景、内容是什么?并对其进行评价。

试述新生活运动的主要内容并作评价。

(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

对于出口商品，经检验部门检验合格后，凭_______进行通关()

何时拔出负压引流管

煎中药时，一般第一煎加水量应淹过药面

在规定时间内没有参加资质年检的工程监理企业，其资质证书自行失效，且( )年内不得重新申请资质。

根据我国民事诉讼法的规定，该纠纷应由()的法院管辖。在确定由一个法院管辖后，G公司可以以()的身份参加诉讼。

【资料】李老师在检查学生知识掌握的情况时，通常其试卷不单选用选择题和判断题，还常常借助于填空题、简答题和论述题等。李老师的这种做法是否正确?

矛盾不可避免，问题总是存在，但我们既不能因为畏惧困难就________，也不能只凭________的一腔血勇。填入画横线部分最恰当的一项是()。

公民的作品，其发表权、著作财产权的保护期为作者终生及其死亡后五十年，作者的署名权、修改权、保护作品完整权的保护期不受限制。()

Internet使用的协议是

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

在规定时间内没有参加资质年检的工程监理企业，其资质证书自行失效，且(　　)年内不得重新申请资质。

矛盾不可避免，问题总是存在，但我们既不能因为畏惧困难就，也不能只凭的一腔血勇。填入画横线部分最恰当的一项是()。