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

admin2009-01-19 40

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

选项

答案O(n)

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

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

在浮点加法运算中，尾数求和之前，一般需进行______操作。

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

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

操作系统的【　　】管理部分负责对作业或进程进行调度。

假设主频为66MHz的Pentium微处理器以非流水线方式访问存取时间为60ns的DRAM存储器，则在T1周期与T2周期之间至少应插入(　　　)等待状态。

鼠标器、打印机和扫描仪等设备都有一个重要的性能指标，即分辨率，它用每英寸的像素数目来描述，通常用三个英文字母【　　】来表示。

PC从键盘输入信息时采用的是以下哪种I/O方式______。A)无条件程序控制B)查询程序控制C)中断控制D)DMA控制

CCD芯片的像素数目是数码相机的重要性能指标，它与可拍摄的图像分辨率有密切的关系。假定一台200万像素数码相机，它所拍摄的像片能达到的最大分辨率是多少?______

Peopleinsomepartsoftheworldoftentaketheirwaterfor______.Theyuseasmuchwaterastheywish.

帝国主义奴役和控制中国的主要社会基础是

男性，58岁，因原发性肝癌行左半肝切除术后，预测肿瘤复发应定期复查

A．亲和力及内在活性都强B．与亲和力和内在活性无关C．具有一定亲和力但内在活性弱D．有亲和力、无内在活性，与受体不可逆性结合E．有亲和力、无内在活性，与激动药竞争相同受体竞争性拮抗药()。

“工农武装割据”是毛泽东提出的关于中国革命新道路理论的一个科学概念。它的主要形式是()。

“您在什么类型的企业工作过?”属于结构化面试中的()问题。

下列哪一项不属于现代教学设计的基本要求?()

合同当事人对合同的标的和金额进行自由协商，体现的是民法的哪一项原则()

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

三级数据库技术

NCRE全国计算机三级

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

在浮点加法运算中，尾数求和之前，一般需进行______操作。

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

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

操作系统的【 】管理部分负责对作业或进程进行调度。

假设主频为66MHz的Pentium微处理器以非流水线方式访问存取时间为60ns的DRAM存储器，则在T1周期与T2周期之间至少应插入( )等待状态。

鼠标器、打印机和扫描仪等设备都有一个重要的性能指标，即分辨率，它用每英寸的像素数目来描述，通常用三个英文字母【 】来表示。

PC从键盘输入信息时采用的是以下哪种I/O方式______。A)无条件程序控制B)查询程序控制C)中断控制D)DMA控制

CCD芯片的像素数目是数码相机的重要性能指标，它与可拍摄的图像分辨率有密切的关系。假定一台200万像素数码相机，它所拍摄的像片能达到的最大分辨率是多少?______

Peopleinsomepartsoftheworldoftentaketheirwaterfor______.Theyuseasmuchwaterastheywish.

帝国主义奴役和控制中国的主要社会基础是

男性，58岁，因原发性肝癌行左半肝切除术后，预测肿瘤复发应定期复查

A．亲和力及内在活性都强B．与亲和力和内在活性无关C．具有一定亲和力但内在活性弱D．有亲和力、无内在活性，与受体不可逆性结合E．有亲和力、无内在活性，与激动药竞争相同受体竞争性拮抗药()。

“工农武装割据”是毛泽东提出的关于中国革命新道路理论的一个科学概念。它的主要形式是()。

“您在什么类型的企业工作过?”属于结构化面试中的()问题。

下列哪一项不属于现代教学设计的基本要求?()

合同当事人对合同的标的和金额进行自由协商，体现的是民法的哪一项原则()

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

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

操作系统的【　　】管理部分负责对作业或进程进行调度。

假设主频为66MHz的Pentium微处理器以非流水线方式访问存取时间为60ns的DRAM存储器，则在T1周期与T2周期之间至少应插入(　　　)等待状态。

鼠标器、打印机和扫描仪等设备都有一个重要的性能指标，即分辨率，它用每英寸的像素数目来描述，通常用三个英文字母【　　】来表示。