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

admin2018-08-12 83

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

选项

答案因为基数排序所需的时间不仅与文件的大小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://www.kaotiyun.com/show/6uRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

蒋介石在国民党的()全国代表大会上的对外关系演说表示国民党对日关系开始发生变化。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

解放军渡江战役中横渡长江的东西两个攻击点是()。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

在实际观察描述岩石颜色的过程中，有时只用一种颜色无法恰当地描述岩石，这时应采用()描述。

设f(x)＝e2x．求数项级数的和．

某妇女26岁，发现右侧卵巢肿物2年，1小时前突感右下腹剧痛伴恶心、呕吐，妇科检查：子宫(一)，右附件有拳头大囊性肿物，边界清，活动差，左附件(一)，其诊断是

A．心尖部舒张期震颤B．胸骨左缘第2肋间收缩期震颤C．胸骨左缘第3、4肋间收缩期震颤D．胸骨右缘第2肋间收缩期震颤E．胸骨左缘第2肋间连续性震颤主动脉瓣狭窄，可出现的是()

设备工作实施中，如果某项工作的进度超前，则(　　)。

下列不属于商业银行操作风险管理系统支持的工具的是()。

下列关于β值和标准差的表述中，正确的有()。

•Youwillhearfiveshortrecordings.•Foreachrecording,decidewhoisspeaking.•Writeoneletter(A--H)nexttothenumbero

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

计算机408

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

蒋介石在国民党的()全国代表大会上的对外关系演说表示国民党对日关系开始发生变化。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

解放军渡江战役中横渡长江的东西两个攻击点是()。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

在实际观察描述岩石颜色的过程中，有时只用一种颜色无法恰当地描述岩石，这时应采用()描述。

设f(x)＝e2x．求数项级数的和．

某妇女26岁，发现右侧卵巢肿物2年，1小时前突感右下腹剧痛伴恶心、呕吐，妇科检查：子宫(一)，右附件有拳头大囊性肿物，边界清，活动差，左附件(一)，其诊断是

A．心尖部舒张期震颤B．胸骨左缘第2肋间收缩期震颤C．胸骨左缘第3、4肋间收缩期震颤D．胸骨右缘第2肋间收缩期震颤E．胸骨左缘第2肋间连续性震颤主动脉瓣狭窄，可出现的是()

设备工作实施中，如果某项工作的进度超前，则( )。

下列不属于商业银行操作风险管理系统支持的工具的是()。

下列关于β值和标准差的表述中，正确的有()。

•Youwillhearfiveshortrecordings.•Foreachrecording,decidewhoisspeaking.•Writeoneletter(A--H)nexttothenumbero

设备工作实施中，如果某项工作的进度超前，则(　　)。