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

admin2009-01-19 35

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

选项

答案O(n)

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

直接存储器存取DMA操作前，需对DMA控制器进行初始化，初始化包括被传送数据的首地址、传送数据的字数和______三项内容。

以下叙述正确的是

执行下列哪一条指令后，就能用条件转移指令判断AL~BL寄存器中的最高位是否相同?

为使下面的指令序列执行后，能够改变标志存储器中最低位的状态，应该在下划线处填写什么指令?PUSHFPOPAXXORAX，0001HPUSHAX______

编制一个程序，其实现的功能为：将内存中从SOURCE开始的区域里存放的20个字节的压缩BCD码转换为ASCⅡ码，每个压缩的BCD码转换为两个ASCⅡ码，并在最高位加上奇校验位，结果存放到RESULT开始的内存区域。例如：内存中有：73H，4

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

S3C2410与一位数码管的连接如下图所示，假设8段数码管为共阳接法。U1作为锁存器(同相)，并用于驱动。为使下图中的数码管显示字符“0”的汇编语言程序片段如下，填空使程序语句完整(假设端口已经初始化为输出)。

在μC／OS–II系统中，可以采用的任务间通信机制有【67】、【68】、消息队列（messagequeue）、互斥信号量（mutex）和事件标志组（eventflag）等。

SQL语言支持数据库的外模式、模式和内模式结构。外模式对应于视图和部分基本表，模式对应于【】，内模式对应于存储文件。

ThepopulationofmanyAlaskancitieshas________doubledinthepastthreeyears.

正颌外科的头影测量正中矢状面标志点中，S点是指

A．肿瘤中有软骨样组织B．肿瘤中有牙乳头样组织C．肿瘤中有筛孔样结构D．肿瘤中有牙体组织E．肿瘤由黏液样细胞、表皮样细胞和中间细胞组成

下列比率中哪个越高，代表企业承担债务的能力越强()。

导游讲解“虚实结合法”的“实”是指与景观有关的()。

下列有关人体器官结构的说法错误的是()。

阅读教学改革的着力点应放在坚持()阅读，鼓励()阅读，推进()阅读。①赏析性②自主性③批判性④探究性

【2013．福建】某生精力旺盛、反应迅速、直率爽快、开朗热情，但往往缺乏耐心和自制力，而且焦躁易怒。该生的气质类型是()。

Advancingagemeanslosingyourhair,yourwaistlineandyourmemory,right?DanaDenisisjust40yearsold,but【C1】______she’s

A、Heislateforhisworkonthefirstday.B、Ittakesalongtimeforhimtogotowork.C、Heisveryexcitedfordrivingtowo