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

admin2017-01-04 36

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

选项

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

学硕统考专业

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

最早以立法形式巩固大化改新成果的法令是()。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

中共十二届六中全会确定的我国社会主义现代化建设的总体布局是()。

武昌起义是由哪个团体发动的?()

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

在一个双链表中，在p结点之前插入q结点的操作是()。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

什么是认识过程的第二次飞跃?这次飞跃的重要性和实现条件是什么?

临床上收集的尿标本分三种：()、()和()。

关于月经临床表现，下述错误的是

大城市乘客平均换乘系数不应大于()。

阅读材料，根据要求完成设计任务。某物理教科书关于“光的折射”一章某节展示的一张图片如图8所示。任务：简述光的折射规律。

注重过程和总结性评价与形成性评价相结合的评价方法体现了()

下列可以发布通缉令的是()。

[A]Theimportantroleofimageisparticularlyevidentinthebusinessworld.[B]Inthelongrunimagekeepthesamewavel

itisgenerallythoughtthatasteachersworkwithstudents,psychologycourseworkis______toteacher-training.

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

计算机408

学硕统考专业

简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。

最早以立法形式巩固大化改新成果的法令是()。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

中共十二届六中全会确定的我国社会主义现代化建设的总体布局是()。

武昌起义是由哪个团体发动的?()

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

在一个双链表中，在*p结点之前插入*q结点的操作是()。

一台主机申请了一个到www．ab@C@edu．cn的连接，为了获取服务器的IP地址，首先要进行DNS查询，下图为本次查询的过程，请回答如下问题：(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2

什么是认识过程的第二次飞跃?这次飞跃的重要性和实现条件是什么?

临床上收集的尿标本分三种：()、()和()。

关于月经临床表现，下述错误的是

大城市乘客平均换乘系数不应大于()。

阅读材料，根据要求完成设计任务。某物理教科书关于“光的折射”一章某节展示的一张图片如图8所示。任务：简述光的折射规律。

注重过程和总结性评价与形成性评价相结合的评价方法体现了()

下列可以发布通缉令的是()。

[A]Theimportantroleofimageisparticularlyevidentinthebusinessworld.[B]Inthelongrunimagekeepthesamewavel

itisgenerallythoughtthatasteachersworkwithstudents,psychologycourseworkis______toteacher-training.

在一个双链表中，在p结点之前插入q结点的操作是()。