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

admin2019-08-15 88

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

选项

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

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

在一个HDLC帧的数据中，如果出现了000111111011这样的流，请问发送到信道上它将会变成()。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

著名的网络OSI七层模型是由()组织提出来的。

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

Whydoesthespeakersay,"Thishasneverhappenedbefore"?

A、Becauseofthedietthatischaracteristicofthesecultures.B、Becauseoftheirlivingconditions.C、Becauseofthepeopleof

谷胱甘肽过氧化物酶含有

CT扫描时某断层中部可见五角形的鞍上池，由大脑纵裂池、外侧窝池、交叉池和桥池组成。视交叉两侧为

下列()不是深圳证券交易所质押式企业债回购交易品种。

个人所得税法中规定不适用附加减除费用的是()。

TodayisSunday.I’vebeeninCanadafortwomonths.ThisisthefirsttimethatI’vebeenawaymyfamilyforsucha【M1】______

某应用系统需使用运行于两个地点的分布式数据库，该应用系统经常需要进行某一查询操作，此查询需要对两个分布在两地数据量很大的表进行连接操作。这两张数据变化很慢。为了提高查询速度，下列方法中最可行的是()。

Whencollegestudentsreturnhomefortheholidays,theycanbringmorethanpresentswiththem.Theycanalsocausestressand