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

admin2017-01-04 39

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

新王朝时期出现了什么类型的墓?()

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。

宁夏回族自治区的设立时间是()。

对斯大林时期形成的高度集中的社会主义经济政治体制的叙述，不确切的是()。

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

设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链表空为止，最后再删除表头结点。

已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

教学过程是教育心理学家们进行最早也是最多的一项研究内容。()

Rainforestsmaystoremuchlesscarbonthanwethought.Itcouldbetimetodramaticallyreviseourestimatesfollowingthedisc

美国学者凯茨在1955年提出领导者必须具备三大领导技能，即()

下列药物中性状为无臭、无味的是

下列关于操作员权限，说法正确的是()。

下列有关审计证据的说法中，正确的是()。

有线段MN和PQ不相交，线段MN上有6个点A1，A2，…，A6，线段PQ上有7个点B1，B2，…，B7．若将每一个A和每一个Bi连成不作延长的线段AiBj(i=1，2，…，6；j=1，2，…，7)，则由这些线段AiBj相交而得到的交点共有()．

TeachingandLearningMedicineAwardTwoscientistswhohavewonpraiseforresearchintothegrowthofcancercellscouldb