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

admin2023-02-06 64

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

选项

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

学硕统考专业

进行课程管理时，应该强化课程意识，提高学校课程建设与管理的功能，构建重基础、多样化、有层次、综合性的课程结构。()

课程计划是课程安排的整体规划，是根据教育目的以及不同层次和类型的学校的培养目标，由教育主管部门制定的有关学校教育教学的指导性文件。课程计划的主要内容不包括()。

“教育的过程，在它自身以外没有目的，它就是它自己的目的。”这是()关于教育目的的观点。

关于教师和学生关系的两个对立观点是()。

某教师因教育方式不当，对学生进行人格侮辱，学生因不堪忍受而自杀。该教师的行为有过失的因素，要承担相应的法律责任。()

下列有关生活常识的叙述，不正确的是：

当单价为100元，边际贡献率为400%，安全边际量为1000件时，企业可实现利润

A．桑叶、菊花、蝉蜕B．白芷、苍耳子、辛夷C．羌活、防风、藁本D．蝉蜕、牛蒡子、薄荷E．柴胡、葛根、升麻既能疏散风热，又能透疹的药组是

下图表示的是()。

根据合同计价方式的不同，采用(　　)时，必须明确工程承包合同标的物的详细内容、工程量及其各种技术经济指标。

超声波：是人耳听不到的声波。按照这个定义，下列说法正确的是()。

和水力发电原理大同小异的是：

FOB原产地定价

IntheJulyrain,therun-downstreetinaBeijingsouthernsuburbevenlooksalittledreary.

Pentium微处理器在保护模式下，中断描述符表内最多有【　　】个中断描述符。

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

计算机408

学硕统考专业

进行课程管理时，应该强化课程意识，提高学校课程建设与管理的功能，构建重基础、多样化、有层次、综合性的课程结构。()

课程计划是课程安排的整体规划，是根据教育目的以及不同层次和类型的学校的培养目标，由教育主管部门制定的有关学校教育教学的指导性文件。课程计划的主要内容不包括()。

“教育的过程，在它自身以外没有目的，它就是它自己的目的。”这是()关于教育目的的观点。

关于教师和学生关系的两个对立观点是()。

某教师因教育方式不当，对学生进行人格侮辱，学生因不堪忍受而自杀。该教师的行为有过失的因素，要承担相应的法律责任。()

下列有关生活常识的叙述，不正确的是：

当单价为100元，边际贡献率为400%，安全边际量为1000件时，企业可实现利润

A．桑叶、菊花、蝉蜕B．白芷、苍耳子、辛夷C．羌活、防风、藁本D．蝉蜕、牛蒡子、薄荷E．柴胡、葛根、升麻既能疏散风热，又能透疹的药组是

下图表示的是()。

根据合同计价方式的不同，采用( )时，必须明确工程承包合同标的物的详细内容、工程量及其各种技术经济指标。

超声波：是人耳听不到的声波。按照这个定义，下列说法正确的是()。

和水力发电原理大同小异的是：

FOB原产地定价

IntheJulyrain,therun-downstreetinaBeijingsouthernsuburbevenlooksalittledreary.

Pentium微处理器在保护模式下，中断描述符表内最多有【 】个中断描述符。

根据合同计价方式的不同，采用(　　)时，必须明确工程承包合同标的物的详细内容、工程量及其各种技术经济指标。

Pentium微处理器在保护模式下，中断描述符表内最多有【　　】个中断描述符。