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

admin2009-01-19 52

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

选项

答案O(n)

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

若有数据定义DATA　DW　1234H，执行指令MOV　BL，BYTE　PTR　DATA后，BL=【　　】。

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

为了使AX和BX寄存器中的两个16位二进制数具有相同的符号位，下面的程序段中应填写什么指令?(　　　)　　　　PUSH　　　　AX　　　　TEST　　　　AX,8000H　　　　JZ　　　　　　SAME　　　　XOR　　　　　BX,8000H　　　　SAM

Pentium微处理器在保护模式下，线性地址与段基址和偏移地址(偏移量)的关系是______。A)线性地址=段基址+偏移地址B)线性地址=段基址4+偏移地址C)线性地址=段基址16+偏移地址D)线性地址=段基址*64+偏移地址

随着计算机硬件的发展、用户需求的增加以及软件本身的不断改进，Windows操作系统也不断推出新版本。在下列有关Windows操作系统的叙述中，错误的是

在下图所示的高端嵌入式系统的软件组成图中，A应为【65】_程序，B应为【66】_程序。

嵌入式系统的开发过程按顺序可以分成【77】分析与规格说明、系统设计、【78】设计、系统集成与测试等4个阶段，测试的目的是验证模块／系统的功能和性能，以及发现错误。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

在关系数据库系统中，为了简化用户的查询操作，而又不增加数据的存储空间，常用的方法是创建

患者，男性，35岁。诊断为肝炎后肝硬化失代偿期，1周来出现轻微腹痛，腹腔积液增多。查体：T38．5℃。腹腔积液常规：呈草黄色，比重为1．018，蛋白32g／L，白细胞550×106／L，中性粒细胞0．85，最可能的并发症是

定期宣告判决的民事诉讼案件，应当在宣告后发送判决书。()

关于输卵管妊娠，下列说法哪项是错误的

弗洛伊德的精神分析理论的核心是()。

(log325)．(log527)=()．

有三位见习医生，他们在同一家医院中担任住院医生。(1)一星期中只有一天三位见习医生同时值班。(2)没有一位见习医生连续三天值班。(3)任两位见习医生在一星期中同一天休假的情况不超过一次。(4)第一位见习医生在星期日、

贬值改善国际收支的条件有：()

DuringMcDonald’searlyyearsFrenchfriesweremadefromscratcheveryday.RussetBurbankpotatoeswere【1】,cutintoshoestrin

Completethetablebelow.WriteNOMORETHANTHREEWORDSAND/ORANUMBERforeachanswer.

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

三级数据库技术

NCRE全国计算机三级

若有数据定义DATA DW 1234H，执行指令MOV BL，BYTE PTR DATA后，BL=【 】。

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

为了使AX和BX寄存器中的两个16位二进制数具有相同的符号位，下面的程序段中应填写什么指令?( ) PUSH AX TEST AX,8000H JZ SAME XOR BX,8000H SAM

Pentium微处理器在保护模式下，线性地址与段基址和偏移地址(偏移量)的关系是______。A)线性地址=段基址+偏移地址B)线性地址=段基址*4+偏移地址C)线性地址=段基址*16+偏移地址D)线性地址=段基址*64+偏移地址

随着计算机硬件的发展、用户需求的增加以及软件本身的不断改进，Windows操作系统也不断推出新版本。在下列有关Windows操作系统的叙述中，错误的是

在下图所示的高端嵌入式系统的软件组成图中，A应为【65】_______程序，B应为【66】_______程序。

嵌入式系统的开发过程按顺序可以分成【77】分析与规格说明、系统设计、【78】设计、系统集成与测试等4个阶段，测试的目的是验证模块／系统的功能和性能，以及发现错误。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

在关系数据库系统中，为了简化用户的查询操作，而又不增加数据的存储空间，常用的方法是创建

患者，男性，35岁。诊断为肝炎后肝硬化失代偿期，1周来出现轻微腹痛，腹腔积液增多。查体：T38．5℃。腹腔积液常规：呈草黄色，比重为1．018，蛋白32g／L，白细胞550×106／L，中性粒细胞0．85，最可能的并发症是

定期宣告判决的民事诉讼案件，应当在宣告后发送判决书。()

关于输卵管妊娠，下列说法哪项是错误的

弗洛伊德的精神分析理论的核心是()。

(log325)．(log527)=()．

贬值改善国际收支的条件有：()

DuringMcDonald’searlyyearsFrenchfriesweremadefromscratcheveryday.RussetBurbankpotatoeswere【1】,cutintoshoestrin

Completethetablebelow.WriteNOMORETHANTHREEWORDSAND/ORANUMBERforeachanswer.

若有数据定义DATA　DW　1234H，执行指令MOV　BL，BYTE　PTR　DATA后，BL=【　　】。

为了使AX和BX寄存器中的两个16位二进制数具有相同的符号位，下面的程序段中应填写什么指令?(　　　)　　　　PUSH　　　　AX　　　　TEST　　　　AX,8000H　　　　JZ　　　　　　SAME　　　　XOR　　　　　BX,8000H　　　　SAM

Pentium微处理器在保护模式下，线性地址与段基址和偏移地址(偏移量)的关系是______。A)线性地址=段基址+偏移地址B)线性地址=段基址4+偏移地址C)线性地址=段基址16+偏移地址D)线性地址=段基址*64+偏移地址

在下图所示的高端嵌入式系统的软件组成图中，A应为【65】_程序，B应为【66】_程序。