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

admin2009-01-19 53

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

选项

答案O(n)

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

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

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

以下哪一个不是CPU与外设进行数据交换所采用的方式

当Intel　8251A工作在同步方式时，引脚同步检测SYNDET可作为输入或输出信号使用。若工作在外同步方式，该引脚为【　　】；若工作在内同步方式，该引脚为输出。

下面哪一项不是文件系统的功能(　　　)。

串操作指令中，有REP　前缀的串操作指令结束的条件是(　　　)。

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

设F是属性组U上的一组函数依赖，下列哪一条属于Armstrong公理系统中的基本推理规则?

我国公务员考核等次包括()

A．带蹬吊带法B．手法复位，石膏固定C．骨盆截骨(Salter)术切开复位D．骨盆内移截骨(Chiari)术6个月小儿先天性髋脱位的治疗可用

A．化学药品注册分类1类B．化学药品注册分类2类C．化学药品注册分类3类D．化学药品注册分类4类E．化学药品注册分类5类天然物质中提取的新的有效化学单体属于

下列各项中，表述正确的有()。

依据《中华人民共和国民法典》，限制民事行为能力人造成他人损害的，由()承担侵权责任。

我国宗教团体的“三自”原则是()。

红领巾：少先队员

Inthepastfiftyyears,Americansocietyhaschangedagreatdeal.Fiftyyearsago,mostAmericanslivedinsmall【C1】______.Th

JamesMartin的信息工程学提出了一种企业数据处理系统建设的模式，其中包括很多模块Ⅰ．企业模型的建立Ⅱ．特定主题数据库的详细的数据模型设计Ⅲ．过程化语言的使用Ⅳ．信息资源的战略规则以上哪些是最低层的两个模块?

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

三级数据库技术

NCRE全国计算机三级

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

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

以下哪一个不是CPU与外设进行数据交换所采用的方式

当Intel 8251A工作在同步方式时，引脚同步检测SYNDET可作为输入或输出信号使用。若工作在外同步方式，该引脚为【 】；若工作在内同步方式，该引脚为输出。

下面哪一项不是文件系统的功能( )。

串操作指令中，有REP 前缀的串操作指令结束的条件是( )。

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

设F是属性组U上的一组函数依赖，下列哪一条属于Armstrong公理系统中的基本推理规则?

我国公务员考核等次包括()

A．带蹬吊带法B．手法复位，石膏固定C．骨盆截骨(Salter)术切开复位D．骨盆内移截骨(Chiari)术6个月小儿先天性髋脱位的治疗可用

A．化学药品注册分类1类B．化学药品注册分类2类C．化学药品注册分类3类D．化学药品注册分类4类E．化学药品注册分类5类天然物质中提取的新的有效化学单体属于

下列各项中，表述正确的有()。

依据《中华人民共和国民法典》，限制民事行为能力人造成他人损害的，由()承担侵权责任。

我国宗教团体的“三自”原则是()。

红领巾：少先队员

Inthepastfiftyyears,Americansocietyhaschangedagreatdeal.Fiftyyearsago,mostAmericanslivedinsmall【C1】______.Th

JamesMartin的信息工程学提出了一种企业数据处理系统建设的模式，其中包括很多模块Ⅰ．企业模型的建立Ⅱ．特定主题数据库的详细的数据模型设计Ⅲ．过程化语言的使用Ⅳ．信息资源的战略规则以上哪些是最低层的两个模块?

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

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

当Intel　8251A工作在同步方式时，引脚同步检测SYNDET可作为输入或输出信号使用。若工作在外同步方式，该引脚为【　　】；若工作在内同步方式，该引脚为输出。

下面哪一项不是文件系统的功能(　　　)。

串操作指令中，有REP　前缀的串操作指令结束的条件是(　　　)。