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

admin2019-08-15 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://www.kaotiyun.com/show/1KCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：金文是指()

洋务运动时期，首批赴欧海军留学生派出的时间是()。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

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

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。

小明在家想下载一个大小为32MB的游戏软件，如果下载速度为512kbps，不考虑网络中断或速度发生变化，那么理论上他下载这个游戏软件需要()。

江湖诗派

试述毛泽东思想的历史地位和指导作用。

关于肥大，下列描述正确的有

在会计核算中，将一项包括建造多项资产的施工合同中的每项资产分立为单项合同处理，需要具备的条件有()。

指令“JMP　FAR　PTR　ABCD”(ABCD是符号地址)是(　　　)。

Readthetextbelow.Writeanessayinabout120words,inwhichyoushouldsummarizethekeypointsofthetextandmakecommen

Ifthisbillisnotpaidwithintendays,yourgassupplywillbecut_____.

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

计算机408

学硕统考专业

甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：金文是指()

洋务运动时期，首批赴欧海军留学生派出的时间是()。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

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

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。

小明在家想下载一个大小为32MB的游戏软件，如果下载速度为512kbps，不考虑网络中断或速度发生变化，那么理论上他下载这个游戏软件需要()。

江湖诗派

试述毛泽东思想的历史地位和指导作用。

关于肥大，下列描述正确的有

在会计核算中，将一项包括建造多项资产的施工合同中的每项资产分立为单项合同处理，需要具备的条件有()。

指令“JMP FAR PTR ABCD”(ABCD是符号地址)是( )。

Readthetextbelow.Writeanessayinabout120words,inwhichyoushouldsummarizethekeypointsofthetextandmakecommen

Ifthisbillisnotpaidwithintendays,yourgassupplywillbecut_____.

指令“JMP　FAR　PTR　ABCD”(ABCD是符号地址)是(　　　)。