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

admin2019-08-15 56

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

选项

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

学硕统考专业

马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》

书院制度，始于唐而盛于宋，根据所学知识。回答问题：南宋书院的复起，是由朱熹开始的。他重建白鹿洞书院，亲自到书院讲学，还亲手制定()

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

下列的网络协议中，()的运输层协议是使用TCP的。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

厌食油腻厚昧，多见于

山楂的炮制方法宜选用阿胶的炮制方法宜选用

在总账系统中对应收账款进行往来核算实际上是对应收账款进行明细核算。()

出入境检验检疫机构对发现检疫对象或不符合安全卫生条件的商品、物品、包装和运输工具，无权禁止进口，但可提出进行消毒、灭菌、杀虫或其他排除安全隐患的措施等无害化处理措施。()

下列关于银行代理服务类业务的说法中，正确的是()。

某教师利用课堂提问、课堂讨论等形式来决定自己是否需要改善教学，这种评价类型属于()评价。

第二次世界大战全面爆发的标志性事件是()。

设(1)f(x，y)在点(0，0)处是否连续?(2)f(x，y)在点(0，0)处是否可微?

以下叙述中错误的是

A)Toawriter,self-publishingisanincrediblypowerfulandalluringconcept.Onthesimplestlevel,it’sanintriguingsoluti