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

admin2009-01-19 45

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

选项

答案O(n)

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

Windows98通过提供虚拟机的机制来实现多任务处理功能。下列叙述中，错误的是(　　　)。

Windows环境下各种功能的具体操作主要靠(　　　)来实现的。

下面是关于“微处理器”的叙述，其中错误的是(　　　)。

假设8086/8088微处理器的(SS)=1050H，(SP)=0008H，(AX)=1234H。执行PUSH　AX指令后，下面(　　　)选项是正确的执行结果。

注册表是Windows98存储各种软硬件配置信息的“仓库”。在下列有关Windows98注册表的叙述中，错误的是

当并行接口芯片8255A被设定为方式2时，其工作的I/O口

汉字的区位码、国标码和机内码(又称内码)是三个不同的概念。假设某个汉字的区号是32，位号是63，则它的国标码是：

在80×86微处理器的标志寄存器中，有可能受算术运算指令影响的标志位是：

PC机中的中断源通常分为五种类型，它们是：I/O中断、时钟中断、故障中断、程序中断和(　　　)。

在FOXPRO的字段类型中，可以自定义宽度的类型有()。

下面哪种情况导致的口臭属于病理性口源性口臭

食管癌术后易发生吻合口瘘的原因不包括

下列选项中，属于证券交易内幕信息的是：()

下列关于外币财务报表折算的表述中，不正确的是()。

地图：路线

世界上第一个智力测验是由()编制的。

社会主义改造完成后，中国共产党的全新课题是()。

办公室更改电话号码，可用（）公布周知。

中国民族资产阶级的建国方案不能实行的原因。

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

三级数据库技术

NCRE全国计算机三级

Windows98通过提供虚拟机的机制来实现多任务处理功能。下列叙述中，错误的是( )。

Windows环境下各种功能的具体操作主要靠( )来实现的。

下面是关于“微处理器”的叙述，其中错误的是( )。

假设8086/8088微处理器的(SS)=1050H，(SP)=0008H，(AX)=1234H。执行PUSH AX指令后，下面( )选项是正确的执行结果。

注册表是Windows98存储各种软硬件配置信息的“仓库”。在下列有关Windows98注册表的叙述中，错误的是

当并行接口芯片8255A被设定为方式2时，其工作的I/O口

汉字的区位码、国标码和机内码(又称内码)是三个不同的概念。假设某个汉字的区号是32，位号是63，则它的国标码是：

在80×86微处理器的标志寄存器中，有可能受算术运算指令影响的标志位是：

PC机中的中断源通常分为五种类型，它们是：I/O中断、时钟中断、故障中断、程序中断和( )。

在FOXPRO的字段类型中，可以自定义宽度的类型有()。

下面哪种情况导致的口臭属于病理性口源性口臭

食管癌术后易发生吻合口瘘的原因不包括

下列选项中，属于证券交易内幕信息的是：()

下列关于外币财务报表折算的表述中，不正确的是()。

地图：路线

世界上第一个智力测验是由()编制的。

社会主义改造完成后，中国共产党的全新课题是()。

办公室更改电话号码，可用（）公布周知。

中国民族资产阶级的建国方案不能实行的原因。

Windows98通过提供虚拟机的机制来实现多任务处理功能。下列叙述中，错误的是(　　　)。

Windows环境下各种功能的具体操作主要靠(　　　)来实现的。

下面是关于“微处理器”的叙述，其中错误的是(　　　)。

假设8086/8088微处理器的(SS)=1050H，(SP)=0008H，(AX)=1234H。执行PUSH　AX指令后，下面(　　　)选项是正确的执行结果。

PC机中的中断源通常分为五种类型，它们是：I/O中断、时钟中断、故障中断、程序中断和(　　　)。