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

admin2016-03-29 47

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

选项

答案因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为厂，显然，十进制数基数为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/11Ri777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述当代科学技术革命兴起的背景、特点及影响。

在1959年中共中央召开的庐山会议上遭到错误批判的是()。

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式，最早提出这种方式的是()

新中国成立初期的土地政策与解放战争时期的土地政策的主要区别是()。

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

患者，男性，40岁。气促、下肢水肿2个月。体检发现心脏扩大，听诊闻及奔马律及心尖3／4级收缩期吹风样杂音，双肺少许湿啰音。肝大，下肢水肿。B超：左心房、左心室扩大明显。患者可能的诊断是

电力晶体管的缺点是()。

男性，35岁，烧伤总面积70％，Ⅲ。烧伤60％，在院外度过休克期，创面有感染，伤后4天入院，近2天来腹泻、黑粪，以往无溃疡病史。在明确诊断后，首先采取的治疗是

铁路建设单位对高速铁路和地质构造复杂的铁路建设工程实行工程地质勘察监理，或者在铁路线路及其邻近区域进行铁路建设工程施工不执行铁路营业线施工安全管理规定，影响铁路运营安全的，处理规定为()。

用友报表系统中，增加表页是在“数据”状态下进行的。()

以下关于投资性房地产确认中应注意的问题，说法不正确的是()。

某甲故意在某乙家的狗旁边鸣笛，致使拴在门边的狗受惊后挣脱锁链，冲出去咬伤了行人某丙，则()。

已知n阶矩阵则r(A2一A)=_____________.