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

admin2023-02-06 61

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

选项

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

教师劳动所创造的价值，并不是以物化的形式表现出来的，而是作为一种潜在价值因素存在于学生身上。这说明教师劳动具有滞后性的特点。()

现代教学提倡以系统的观点为指导来选用教学方法，优化教学。选择教学方法主要的依据有()。

在智力技能形成的过程中，依据智力活动的实践，以展开的、外显的方式付诸实施的是()。

“侧耳聆听”“举目凝视”“屏息凝视”等现象反映出注意的()。

在制订课程计划时，应充分考虑到社会、学校、学生等条件的复杂性，给课程设计的执行者一定的自主空间，保证他们能够主动、灵活地落实课程计划。这体现了课程计划设计的()原则。

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1≤i≤n+1)。

A．中和游离外毒素B．抑制病原体对黏膜的黏附C．结合FcγR，促进吞噬病原体D．激活补体旁路途径，溶解革兰阴性菌E．干扰病毒的复制内毒素具有的作用

A．化学监测法B．物理监测法C．生物监测法D．仪器监测法E．无菌检验B—D试验属于

治理通货紧缩的主要措施有()。

在进行不具有商业实质的非货币性资产交换的核算时，如果涉及补价，支付补价的企业，应当以换出资产公允价值加上补价和应支付的相关税费，作为换入资产的入账价值。()

课堂教学结构包括教学时间的合理利用、课程表的编制和()。

在中围古代诗人眼中，大雁经常被视为书信的代名词，鸿雁传书是他们最为向往的意象之一。下列诗句中的大雁形象代表这一意象的是：

WhichofthefollowingistheresponsibilityofanHRmanager?

WhatdoesMr.Stevensonthinkofhisprofession?

Whatisthetopicoftheconversation?