对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

admin2010-05-13 39

问题对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

选项

答案O(n)

解析初始状态没有部分排序的文件中若有n个记录，可以把它看作n个子文件，每个子文件中只包含一个记录，因而是部分排序的。通常先将两个子文件归并，得到n/2个部分排序的较大的于文件，每个子文件中只包含2个记录。再将这些子文件归并，如此反复，直到归并到一个文件中，排序完成。上述每步归并都是将两个子文件全成一个文件，这种做法叫“二路归并排序”。二路归并排序时，需利用一个同待排序数组一样大小的辅助数组，所以其空间复杂度为O(n)。

转载请注明原文地址:https://kaotiyun.com/show/VySZ777K

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

三级数据库技术

NCRE全国计算机三级

下面关于无线通信技术的一些叙述中，错误的是()。

下面是关于嵌入式系统使用的存储器的叙述，其中错误的是()。

存储器容量单位有字节(B)、千字节(KB)、兆字节(MB)、吉字节_【55】和太字节_【56】等。

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】；组成部分B是【42】。

在μC／OS—II操作系统中，内核对任务的管理通过名为【69】的数据结构进行。当任务切换时，任务的工作现场被保存到任务的【70】中。

下面是嵌入式最小硬件系统组成框图，用于说明嵌入式系统的组成，图中两个框中的①和②应分别填写的是【57】和【58】。

在存储结构方面，ARM7采用【49】结构，而ARM9～ARM11均采用【50】结构。

在μC／OS—II系统中，可以采用的任务间通信机制有_【67】、_【68】、消息队列(messagequeue)、互斥信号量(mutex)和事件标志组(eventflag)等。

对n个记录的文件进行堆排序，最坏情况下的执行时间为

在生产关系的内容中，起决定作用的是【】

对X线的叙述，下列正确的是

产后腹痛的分型

A．共价键B．氢键C．离子-偶极和偶极-偶极相互作用D．范德华引力E．疏水性相互作用乙酰胆碱与受体的作用，形成的主要键合类型是()

如题1—127图所示，真空中距离为d的两个点电荷q1=q，q2=3q，则电场强度为零的点应在两电荷间的连线上，此点与q1相距()。(下列答案四选一)

金融租赁公司是经中国人民银行批准。以经营融资租赁业务为主的非银行金融机构。()

关于气质，正确的说法包括()。

将整个测验按照测验题目材料的性质分为若干分测验，同一分测验的题目按照其难度由易到难排列，这种测验的排列方式是()。

Howwelookandhowweappeartoothersprobablyworriesusmorewhenweareinourteensorearlytwentiesthanatanytimein

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【 】。

三级数据库技术

NCRE全国计算机三级

下面关于无线通信技术的一些叙述中，错误的是()。

下面是关于嵌入式系统使用的存储器的叙述，其中错误的是()。

存储器容量单位有字节(B)、千字节(KB)、兆字节(MB)、吉字节_________【55】和太字节_________【56】等。

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是__________【41】；组成部分B是__________【42】。

在μC／OS—II操作系统中，内核对任务的管理通过名为__________【69】的数据结构进行。当任务切换时，任务的工作现场被保存到任务的__________【70】中。

下面是嵌入式最小硬件系统组成框图，用于说明嵌入式系统的组成，图中两个框中的①和②应分别填写的是【57】和【58】。

在存储结构方面，ARM7采用【49】结构，而ARM9～ARM11均采用【50】结构。

在μC／OS—II系统中，可以采用的任务间通信机制有_________【67】、_________【68】、消息队列(messagequeue)、互斥信号量(mutex)和事件标志组(eventflag)等。

对n个记录的文件进行堆排序，最坏情况下的执行时间为

在生产关系的内容中，起决定作用的是【】

对X线的叙述，下列正确的是

产后腹痛的分型

A．共价键B．氢键C．离子-偶极和偶极-偶极相互作用D．范德华引力E．疏水性相互作用乙酰胆碱与受体的作用，形成的主要键合类型是()

如题1—127图所示，真空中距离为d的两个点电荷q1=q，q2=3q，则电场强度为零的点应在两电荷间的连线上，此点与q1相距()。(下列答案四选一)

金融租赁公司是经中国人民银行批准。以经营融资租赁业务为主的非银行金融机构。()

关于气质，正确的说法包括()。

将整个测验按照测验题目材料的性质分为若干分测验，同一分测验的题目按照其难度由易到难排列，这种测验的排列方式是()。

Howwelookandhowweappeartoothersprobablyworriesusmorewhenweareinourteensorearlytwentiesthanatanytimein

对n个记录的文件进行二路归并排序，所需要的辅助存储空间为【】。

存储器容量单位有字节(B)、千字节(KB)、兆字节(MB)、吉字节_【55】和太字节_【56】等。

下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】；组成部分B是【42】。

在μC／OS—II操作系统中，内核对任务的管理通过名为【69】的数据结构进行。当任务切换时，任务的工作现场被保存到任务的【70】中。

在μC／OS—II系统中，可以采用的任务间通信机制有_【67】、_【68】、消息队列(messagequeue)、互斥信号量(mutex)和事件标志组(eventflag)等。