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

admin2023-02-06 52

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

选项

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

学硕统考专业

教师对学生的态度会影响学生人格的形成。如果学生在人格方面表现出没有组织纪律性，缺乏团体目标的特点，从教师影响学生的方面来说，教师态度是()的。

课外辅导是帮助和指导学生学习的活动。下列关于课外辅导的说法错误的是()。

课堂环境对师生交往有重要的影响，下列课桌摆放的形式中()不利于师生之间交流。

教学过程的规律有哪些?()

下列关于教育目的的价值取向确立应注意的问题，说法正确的有()。

下列关于地图的叙述正确的是：

已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。

从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、、／四种运算，例如：234-34+2$。

雌性腊肠犬，6岁，一个月来精神沉郁，时有发热。抗生素治疗后病情好转，停药后复发。现病情加重，阴部流红褐色分泌物。B超探查见双侧子宫角增粗，内有液性暗区。该病例手术时，必须要结扎()

具有清胃凉血功用的方剂是

民事诉讼中，审判人员的回避和书记员的回避，分别由谁(　　)决定。

下列关于锅炉电力线路的敷设，说法正确的是()。

柜台交易的转让价格一般由证券公司报出，并根据投资者的接受程度而进行调整。()

我国社会主义道德的基本原则是()

社会学习理论的基本观点有()。

某地有传唱本地歌曲的习俗，当地政府为了弘扬本地文化特色，拟组织有奖歌唱比赛，领导把这件事交代给你，请问你焦么组织？

______，如今都变成一个个英俊强健的小伙子。

TheCarnegieFoundationreportsaysthatmanycollegeshavetriedtobe"allthingstoallpeople".Indoingso,theyhaveincre

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

计算机408

学硕统考专业

教师对学生的态度会影响学生人格的形成。如果学生在人格方面表现出没有组织纪律性，缺乏团体目标的特点，从教师影响学生的方面来说，教师态度是()的。

课外辅导是帮助和指导学生学习的活动。下列关于课外辅导的说法错误的是()。

课堂环境对师生交往有重要的影响，下列课桌摆放的形式中()不利于师生之间交流。

教学过程的规律有哪些?()

下列关于教育目的的价值取向确立应注意的问题，说法正确的有()。

下列关于地图的叙述正确的是：

已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。

从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、*、／四种运算，例如：234-34+2*$。

雌性腊肠犬，6岁，一个月来精神沉郁，时有发热。抗生素治疗后病情好转，停药后复发。现病情加重，阴部流红褐色分泌物。B超探查见双侧子宫角增粗，内有液性暗区。该病例手术时，必须要结扎()

具有清胃凉血功用的方剂是

民事诉讼中，审判人员的回避和书记员的回避，分别由谁( )决定。

下列关于锅炉电力线路的敷设，说法正确的是()。

柜台交易的转让价格一般由证券公司报出，并根据投资者的接受程度而进行调整。()

我国社会主义道德的基本原则是()

社会学习理论的基本观点有()。

某地有传唱本地歌曲的习俗，当地政府为了弘扬本地文化特色，拟组织有奖歌唱比赛，领导把这件事交代给你，请问你焦么组织？

______，如今都变成一个个英俊强健的小伙子。

TheCarnegieFoundationreportsaysthatmanycollegeshavetriedtobe"allthingstoallpeople".Indoingso,theyhaveincre

从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、、／四种运算，例如：234-34+2$。

民事诉讼中，审判人员的回避和书记员的回避，分别由谁(　　)决定。