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

admin2017-01-04 48

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

选项

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

学硕统考专业

农业革命的中心以及农业革命的影响。

试述明治维新过程中土地改革的主要内容和意义。

结合诸条约内容简述中国社会沦为半殖民地半封建社会的过程。

简述工农武装割据存在与发展的原因和条件。

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

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

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

随着科学文化交流的扩大和现代传播技术的进步，著作权有了很大的发展和变化，具体表现在()

简述艺术创作主体与客体的关系。

18岁的小王与25岁的张某伪造虚假证明办理了结婚登记，则其婚姻【】

男，4岁。2周前曾患感冒，今晨发现全身散发瘀点，下肢有瘀斑。病后不发热。检查：肝、脾(-)，血小板40×109/L，其他未见异常。导致患儿皮肤出现瘀点(斑)的最主要的原因是

猪囊尾蚴病是一种重要的人畜共患病，其病原体猪囊尾蚴不寄生于人的

痛风性关节炎最常见的好发部位为膝关节。()

甲欠乙8000元,乙多次催促,甲拖延不还。后乙告诉甲必须在半个月内还钱,否则将起诉他。甲立即将家中仅有的值钱物品———九成新电冰箱和彩电各一台以300元价格卖给知情的丙,被乙发现。下列说法中,正确的有()。

计算机在短短几十年间的发展就经历了四代，即()。

Settinganearlierbedtimeforyourchildrencouldhelpkeeptheirweight【B1】______,anewstudyfinds.Fastfood,toomuchscre