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

admin2009-01-19 46

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

选项

答案O(n)

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下面是关于PC机中USB和IEEE-1394的叙述，其中正确的是(　　　)。

RAID是一种提高磁盘存储速度、容量和可靠性的技术。下面有关RAID的叙述中，错误的是(　　　)。

甲、乙两台PC机通过其串行接口进行全双工通信时，若使用发送数据信号TxD和接收数据信号RxD交换信息，则下面关于两机串口信号线连接的叙述中，正确的是(　　　)。

微处理器各部件之间通过______交换信息。

在汇编语言程序设计中，若调用不在本模块中的过程，则对该过程必须用伪操作命令(　　　)进行说明。

评价一种图像压缩算法优劣的方法不包括

从静态的观点看，操作系统中的进程是由【　　】、数据和进程控制块组成的。

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

医院感染

取得医师资格的可以医师注册后受吊销医师执业证书行政处罚的

白芍具有的功效是()

确诊二尖瓣狭窄最可靠的辅助检查是

在下述各项中，不属于现金流出的量是()。

口语交际课的教学设计，首先要___，话题要贴近_，密切联系学生的_和___，使每个学生有话可说，有话要说。

(2017·山东)关于影响人的身心发展的因素的观点中，下列不属于内发论的代表人物有()

十几个同学围成一圈，按顺时针方向一圈一圈的循环报数。如果报1和报100的是同一个同学，那么共有（）个同学。

Let’sfinishourhomeworkinafewseconds;it’stimewe______.

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

三级数据库技术

NCRE全国计算机三级

下面是关于PC机中USB和IEEE-1394的叙述，其中正确的是( )。

RAID是一种提高磁盘存储速度、容量和可靠性的技术。下面有关RAID的叙述中，错误的是( )。

甲、乙两台PC机通过其串行接口进行全双工通信时，若使用发送数据信号TxD和接收数据信号RxD交换信息，则下面关于两机串口信号线连接的叙述中，正确的是( )。

微处理器各部件之间通过______交换信息。

在汇编语言程序设计中，若调用不在本模块中的过程，则对该过程必须用伪操作命令( )进行说明。

评价一种图像压缩算法优劣的方法不包括

从静态的观点看，操作系统中的进程是由【 】、数据和进程控制块组成的。

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

医院感染

取得医师资格的可以医师注册后受吊销医师执业证书行政处罚的

白芍具有的功效是()

确诊二尖瓣狭窄最可靠的辅助检查是

在下述各项中，不属于现金流出的量是()。

口语交际课的教学设计，首先要_______，话题要贴近_______，密切联系学生的_______和_______，使每个学生有话可说，有话要说。

(2017·山东)关于影响人的身心发展的因素的观点中，下列不属于内发论的代表人物有()

十几个同学围成一圈，按顺时针方向一圈一圈的循环报数。如果报1和报100的是同一个同学，那么共有（）个同学。

Let’sfinishourhomeworkinafewseconds;it’stimewe______.

下面是关于PC机中USB和IEEE-1394的叙述，其中正确的是(　　　)。

RAID是一种提高磁盘存储速度、容量和可靠性的技术。下面有关RAID的叙述中，错误的是(　　　)。

甲、乙两台PC机通过其串行接口进行全双工通信时，若使用发送数据信号TxD和接收数据信号RxD交换信息，则下面关于两机串口信号线连接的叙述中，正确的是(　　　)。

在汇编语言程序设计中，若调用不在本模块中的过程，则对该过程必须用伪操作命令(　　　)进行说明。

从静态的观点看，操作系统中的进程是由【　　】、数据和进程控制块组成的。

口语交际课的教学设计，首先要___，话题要贴近_，密切联系学生的_和___，使每个学生有话可说，有话要说。